Journal article
Compact representation of near-optimal integer programming solutions
Mathematical programming, Vol.182(1-2), pp.199-232
07/01/2020
DOI: 10.1007/s10107-019-01390-3
Abstract
It is often useful in practice to explore near-optimal solutions of an integer programming problem. We show how all solutions within a given tolerance of the optimal value can be efficiently and compactly represented in a weighted decision diagram. The structure of the diagram facilitates rapid processing of a wide range of queries about the near-optimal solution space, as well as reoptimization after changes in the objective function. We also exploit the paradoxical fact that the diagram can be reduced in size if it is allowed to represent additional solutions. We show that a "sound reduction" operation, applied repeatedly, yields the smallest such diagram that is suitable for postoptimality analysis, and one that is typically far smaller than a tree that represents the same set of near-optimal solutions. We conclude that postoptimality analysis based on sound-reduced diagrams has the potential to extract significantly more useful information from an integer programming model than was previously feasible.
Details
- Title: Subtitle
- Compact representation of near-optimal integer programming solutions
- Creators
- Thiago Serra - Carnegie Mellon UniversityJ. N. Hooker - Carnegie Mellon University
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.182(1-2), pp.199-232
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-019-01390-3
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 34
- Language
- English
- Date published
- 07/01/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984696756602771
Metrics
1 Record Views