Optimization Online


Binary Extended Formulations of Polyhedral Mixed-integer Sets

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Robert Hildebrand (rhil***at***vt.edu)

Abstract: We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer 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 branch-and-bound 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 (0-1 Programming )


Download: [PDF]

Entry Submitted: 01/02/2018
Entry Accepted: 01/02/2018
Entry Last Modified: 04/13/2018

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