search query: @author Martin, R. K. / total: 8
reference: 1 / 8
« previous | next »
| Author: | Martin, R. K. Rardin, R. L. Campbell, B. A. |
| Title: | Polyhedral characterization of discrete dynamic programming. |
| Journal: | Operations Research
1990 : JAN-FEB, VOL. 38:1, p. 127-138 |
| Index terms: | DYNAMIC PROGRAMMING |
| Language: | eng |
| Abstract: | Many combinatorial problems can be modelled as linear programs, but efficient solution requires that the relaxation approximates the discrete model. A paradigm is developed that yields a polyhedral characterization. The concept of dynamic programming as shortest path problems is extended to a hypergraph. The emphasis is on polyhedral consequences of formulating dynamic programs as linear programs. For polynomially solvable problems, the characterization is not only complete, that is, sufficient to describe an optimum for any allowed objective function coefficients, but also succint, that is, posed over polynomially many variables and constraints. The methods lead to a problem reformulation using both auxiliary variables and vectors. |
« previous | next »
SCIMA