Optimization Online


A mixed-integer branching approach for very small formulations of disjunctive constraints

Joey Huchette (huchette***at***mit.edu)
Juan Pablo Vielma (jvielma***at***mit.edu)

Abstract: We study the existence and construction of very small formulations for disjunctive constraints in optimization problems: that is, formulations that use very few integer variables and extra constraints. To accomplish this, we present a novel mixed-integer branching formulation framework, which preserves many of the favorable algorithmic properties of a traditional mixed-integer programming formulation, including amenability to the branch-and-bound algorithm and the generation of cutting planes. We show that any disjunctive constraint can be formulated with only two integer variables in this framework. Additionally, we give an explicit geometric construction for ideal formulations for the broad class of combinatorial disjunctive constraints, which should be of independent interest. We use this result to construct ideal mixed-integer branching formulations for any combinatorial disjunctive constraint with two control variables and only a linear number of facets. Finally, we give a ideal mixed-integer branching formulation for the SOS2 constraint with only two integer variables and four general inequality constraints.

Keywords: Mixed-integer programming, formulations, disjunctive constraints, branching

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 09/28/2017
Entry Accepted: 09/28/2017
Entry Last Modified: 12/03/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