Generalized dynamic programming methods in integer programming
(1973) Mathematical Programming — Vol. 4, p. 222-232 (1973)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 467.17 KB
Details
- Authors
- Abstract
- When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.
- Affiliations
Citations
Wolsey, L. (1973). Generalized dynamic programming methods in integer programming. Mathematical Programming, 4, 222-232. https://doi.org/10.1007/BF01584662 (Original work published 1973)