  


Compact Representation of NearOptimal Integer Programming Solutions
Thiago Serra(tserracmu.edu) Abstract: It is often useful in practice to explore nearoptimal 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 nearoptimal 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 nearoptimal. 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 nearoptimal solutions. Keywords: decision diagrams; integer programming; postoptimality Category 1: Integer Programming (01 Programming ) Citation: Submitted manuscript Download: [PDF] Entry Submitted: 09/30/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  