A geometric way to build strong mixed-integer programming formulations
Copyright policy )A geometric way to build strong mixed-integer programming formulations
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.
arXiv admin note: text overlap with arXiv:1709.10132
- Massachusetts Institute of Technology United States
- Rice University United States
formulations, mixed-integer programming, Mixed integer programming, Optimization and Control (math.OC), disjunctive constraints, Special polytopes (linear programming, centrally symmetric, etc.), Polyhedral combinatorics, branch-and-bound, branch-and-cut, FOS: Mathematics, Mathematics - Optimization and Control
formulations, mixed-integer programming, Mixed integer programming, Optimization and Control (math.OC), disjunctive constraints, Special polytopes (linear programming, centrally symmetric, etc.), Polyhedral combinatorics, branch-and-bound, branch-and-cut, FOS: Mathematics, Mathematics - Optimization and Control
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!