Strong IP formulations need large coefficients

DOI10.1016/J.DISOPT.2021.100624MaRDI QIDQ2019425zbMATH OpenOpenAlexFDO

Authors Christopher Hojny

Publication date 21 April 2021

Published in Discrete Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.disopt.2021.100624

zbMATH Keywords

bounded coefficientsinteger programmingIP formulationstrong cutting planes

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Polynomial size IP formulations of knapsack may require exponentially large coefficients
• Coefficient strengthening: a tool for reformulating mixed-integer programs
• Formulations and Reformulations in Integer Programming
• Strong formulations of robust mixed 0-1 programming
• Strong formulations for mixed integer programs: valid inequalities and extended formulations

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A characterization of knapsacks with the max-flow--min-cut property
• A relax-and-cut framework for Gomory mixed-integer cuts
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Anti-blocking polyhedra
• Approximating polyhedra with sparse inequalities
• Branched polyhedral systems
• Coefficient reduction for inequalities in 0–1 variables
• Computing the integer programming gap
• Cut search methods in integer programming
• Describing orbitopes by linear inequalities and projection based tools.
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Fenchel Cutting Planes for Integer Programs
• Finding descriptions of polytopes via extended formulations and liftings
• Geometric algorithms and combinatorial optimization.
• Greedoids
• How good are sparse cutting-planes?
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 2086915 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Integrality gaps of integer knapsack problems
• Lectures on Polytopes
• Maximum matching and a polyhedron with 0,1-vertices
• Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix
• On defining sets of vertices of the hypercube by linear inequalities
• On imposing connectivity constraints in integer programs
• On the combinatorial complexity of approximating polytopes
• On the facial structure of set packing polyhedra
• On the generation of deep disjunctive cutting planes
• Optimal cutting planes from the group relaxations
• Optimal scaling of balls and polyhedra
• Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem
• Packing and partitioning orbitopes
• Practical strategies for generating rank-1 split cuts in mixed-integer linear programming
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Presolve Reductions in Mixed Integer Programming
• Sensitivity theorems in integer linear programming
• Solution of large-scale symmetric travelling salesman problems
• Solving Large-Scale Zero-One Linear Programming Problems
• Sparsity of integer formulations for binary programs
• The cutting stock problem and integer rounding

Cited in

(5)

• Computational aspects of relaxation complexity
• Complexity of linear relaxations in integer programming
• Polynomial size IP formulations of knapsack may require exponentially large coefficients
• Computational aspects of relaxation complexity: possibilities and limitations
• Efficient MIP techniques for computing the relaxation complexity

This page was built for publication: Strong IP formulations need large coefficients

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