Polyhedral Characterization of Discrete Dynamic Programming

R. Kipp Martin, Ronald L. Rardin and Brian A. Campbell
Additional contact information
R. Kipp Martin: University of Chicago, Chicago, Illinois
Ronald L. Rardin: Purdue University, West Lafayette, Indiana
Brian A. Campbell: Purdue University, West Lafayette, Indiana

Operations Research, 1990, vol. 38, issue 1, 127-138

Abstract: Many interesting combinatorial problems can be optimized efficiently using recursive computations often termed discrete dynamic programming . In this paper, we develop a paradigm for a general class of such optimizations that yields a polyhedral description for each model in the class. The elementary concept of dynamic programs as shortest path problems in acyclic graphs is generalized to one seeking a least cost solution in a directed hypergraph. Sufficient conditions are then provided for binary integrality of the associated hyperflow problem. Given a polynomially solvable dynamic program, the result is a linear program, in polynomially many variables and constraints, having the solution vectors of the dynamic program as its extreme-point optima. That is, the linear program provides a succinct characterization of the solutions to the underlying optimization problem expressed through an appropriate change of variables. We also discuss projecting this formulation to recover constraints on the original variables and illustrate how some important dynamic programming solvable models fit easily into our paradigm. A classic multiechelon lot sizing problem in production and a host of optimization problems on recursively defined classes of graphs are included.

Keywords: programming: dynamic programming and polyhedral theory; cutting planes (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.1.127 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:1:p:127-138

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().