Optimization Online


Compact Representation of Near-Optimal Integer Programming Solutions

Thiago Serra(tserra***at***cmu.edu)
John Hooker(jh38***at***andrew.cmu.edu)

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, once the optimal value is known. The structure of a decision diagram facilitates rapid processing of a wide range of queries about the near-optimal solution space. To obtain a more compact diagram, we exploit the property that such diagrams may become paradoxically smaller when they contain more solutions. We use sound decision diagrams, which innocuously admit some solutions that are worse than near-optimal. We describe a simple "sound reduction" operation that, when applied repeatedly in any order, yields a smallest possible sound diagram for a given problem instance. We find that sound reduction yields a structure that is typically far smaller than a tree that represents the same set of near-optimal solutions.

Keywords: decision diagrams; integer programming; postoptimality

Category 1: Integer Programming (0-1 Programming )

Citation: Submitted manuscript

Download: [PDF]

Entry Submitted: 09/30/2017
Entry Accepted: 09/30/2017
Entry Last Modified: 09/30/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society