Polyhedral Characterization of Discrete Dynamic Programming

DOI10.1287/OPRE.38.1.127zbMath0711.90066OpenAlexW2036652785MaRDI QIDQ3496158

Ronald L. Rardin, Brian A. Campbell, R. Kipp Martin

Publication date: 1990

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.38.1.127

zbMATH Keywords

shortest pathpolyhedral descriptionacyclic graphsdirected hypergraphrecursive computationshyperflowmultiechelon lot sizing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Production models (90B30) Combinatorial optimization (90C27) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39) Boolean programming (90C09)

Related Items (35)

Knapsack polytopes: a survey ⋮ Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ Partial objective inequalities for the multi-item capacitated lot-sizing problem ⋮ Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ Strong formulations for mixed integer programming: A survey ⋮ On the extension complexity of scheduling polytopes ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Matrices with lexicographically-ordered rows ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ A strong formulation for the graph partition problem ⋮ Packing, partitioning, and covering symresacks ⋮ A polyhedral perspective on tropical convolutions ⋮ Unnamed Item ⋮ Facets of the Stochastic Network Flow Problem ⋮ Unnamed Item ⋮ Column generation for extended formulations ⋮ Target Cuts from Relaxed Decision Diagrams ⋮ Fixed-charge transportation problems on trees ⋮ Some efficiently solvable problems over integer partition polytopes ⋮ Expressing combinatorial optimization problems by linear programs ⋮ Constructing Extended Formulations from Reflection Relations ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Circuit and bond polytopes on series-parallel graphs ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ Extended formulations in combinatorial optimization ⋮ Extended formulations for vertex cover ⋮ Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers ⋮ Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Gainfree Leontief substitution flow problems ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming ⋮ Scheduling two chains of unit jobs on one machine: A polyhedral study ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams ⋮ The mixing set with divisible capacities: a simple approach ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph

This page was built for publication: Polyhedral Characterization of Discrete Dynamic Programming