  


Binary Extended Formulations of Polyhedral Mixedinteger Sets
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: We analyze different ways of constructing binary extended formulations of polyhedral mixedinteger sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call ``unimodular" extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branchandbound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases. Keywords: Extended formulations, bounded integer variables, split cuts, affine transformations Category 1: Integer Programming Category 2: Integer Programming (Cutting Plane Approaches ) Category 3: Integer Programming (01 Programming ) Citation: Download: [PDF] Entry Submitted: 01/02/2018 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  