Optimization Online


A geometric way to build strong mixed-integer programming formulations

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

Abstract: We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.

Keywords: Mixed-integer programming

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


Download: [PDF]

Entry Submitted: 10/09/2019
Entry Accepted: 10/09/2019
Entry Last Modified: 10/09/2019

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