On the Complexity of Selecting Disjunctions in Integer Programming

DOI10.1137/080737587zbMath1211.90136OpenAlexW2158102350MaRDI QIDQ3083283

Ted K. Ralphs, Ashutosh Mahajan

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080737587

zbMATH Keywords

complexityinteger programmingdisjunctionssplit inequalitiesgeneral branching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (11)

Improved branching disjunctions for branch-and-bound: an analytic center approach ⋮ Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point ⋮ Achieving MILP feasibility quickly using general disjunctions ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube ⋮ Could we use a million cores to solve an integer program? ⋮ Compressing branch-and-bound trees ⋮ Thinner is not always better: cascade knapsack problems ⋮ Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices ⋮ On the rational polytopes with Chvátal rank 1 ⋮ A Unified Framework for Multistage Mixed Integer Linear Optimization

This page was built for publication: On the Complexity of Selecting Disjunctions in Integer Programming