Computational aspects of relaxation complexity

DOI10.1007/978-3-030-73879-2_26zbMath1497.90223OpenAlexW3161949514MaRDI QIDQ2061898

Gennadiy Averkov, Christopher Hojny, Matthias Schymura

Publication date: 21 December 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-73879-2_26

zbMATH Keywords

integer programming formulationrelaxation complexity

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (2)

Computational aspects of relaxation complexity: possibilities and limitations ⋮ Computational aspects of relaxation complexity

Uses Software

• relaxation_complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Moving out the edges of a lattice polygon
• On a circle-cover minimization problem
• Lower bounds on the sizes of integer programs without additional variables
• Minimum polygonal separation
• On the complexity of polyhedral separability
• On defining sets of vertices of the hypercube by linear inequalities
• Strong IP formulations need large coefficients
• Computational aspects of relaxation complexity
• A note on the extension complexity of the knapsack polytope
• Polynomial size IP formulations of knapsack may require exponentially large coefficients
• PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite
• Verallgemeinerung einer Mordellschen Beweismethode in der Geometrie der Zahlen, Zweite Mitteilung
• Threshold Numbers and Threshold Completions

This page was built for publication: Computational aspects of relaxation complexity