Many interesting combinatorial problems can be optimized efficiently using recursive computations often termed discrete dynamic programming. In this paper, the authors develop a paradigm for a general class of such optimizations that yield a polyhedral description for each model in the class. The elementary concept of dynamic programs as shortest path problem 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. The authors also discuss projecting this formulation to recover constraints on the original variables and illustrate how some important dynamic programming solvable models fit easily into the present paradigm. A classic multiechelon lot sizing problem in production and a host of optimization problems on recursively defined classes of graphs are included.
