Polyhedral Characterization of Discrete Dynamic Programming

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.