A geometric way to build strong mixed-integer programming formulations

DOI10.1016/J.ORL.2019.10.003MaRDI QIDQ2294389zbMATH OpenOpenAlexWikidataFDO

Authors Joey Huchette, J. P. Vielma

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.10409

zbMATH Keywords

disjunctive constraintsformulationsmixed-integer programming

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

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.

Recommendations

• A combinatorial approach for small and strong formulations of disjunctive constraints
• Tight formulations for some simple mixed integer programs and convex objective integer programs
• Small and strong formulations for unions of convex sets from the Cayley embedding
• Compact formulations as a union of polyhedra
• Ideal, non-extended formulations for disjunctive constraints admitting a network representation

Cites work

• 50 Years of Integer Programming 1958-2008
• Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
• Mixed integer linear programming formulation techniques
• Mixed-integer convex representability
• Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions
• Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
• Modelling with integer variables
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Strong SOCP relaxations for the optimal power flow problem
• Using Piecewise Linear Functions for Solving MINLPs

Cited in

(8)

• Ideal, non-extended formulations for disjunctive constraints admitting a network representation
• Small and strong formulations for unions of convex sets from the Cayley embedding
• Incremental and encoding formulations for mixed integer programming
• Stronger formulations of mixed integer linear programs: an example
• A combinatorial approach for small and strong formulations of disjunctive constraints
• Strong mixed-integer formulations for the floor layout problem
• Modeling combinatorial disjunctive constraints via junction trees
• Facet separation for disjunctive constraints with network flow representation

This page was built for publication: A geometric way to build strong mixed-integer programming formulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294389)