Efficient MIP techniques for computing the relaxation complexity

DOI10.1007/S12532-023-00241-9MaRDI QIDQ6095738zbMATH OpenOpenAlexFDO

Authors Gennadiy Averkov, Christopher Hojny, Matthias Henze

Publication date 8 September 2023

Published in Mathematical Programming Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

branch-and-cutbranch-and-pricemixed-integer programming modelsrelaxation complexity

Mathematics Subject Classification ID

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

Abstract: The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We employ efficient mixed-integer programming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances that could not be solved previously.

Recommendations

• Computational aspects of relaxation complexity
• Computational aspects of relaxation complexity: possibilities and limitations
• Complexity of linear relaxations in integer programming
• Extension complexity lower bounds for mixed-integer extended formulations

Cites work

• A note on resolving infeasibility in linear programs by constraint relaxation
• Accurately learning from few examples with a polyhedral classifier
• Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, Lblock, DES(L) and other bit-oriented block ciphers
• Complexity of linear relaxations in integer programming
• Computational aspects of relaxation complexity: possibilities and limitations
• Dimension of the Lisbon voting rules in the EU council: a challenge and new world record
• Extended formulations in combinatorial optimization
• scientific article; zbMATH DE number 1550909 (Why is no real title available?)
• Lifting linear extension complexity bounds to the mixed-integer setting
• Mathematics and Politics
• 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 the extension complexity of polytopes separating subsets of the Boolean cube
• Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem
• Polyhedral separability through successive LP
• Polynomial size IP formulations of knapsack may require exponentially large coefficients
• Polytopes associated with symmetry handling
• Strong IP formulations need large coefficients
• The densest hemisphere problem

Cited in

(7)

• A relaxation algorithm for solving mixed integer programming problems
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Complexity of linear relaxations in integer programming
• Computational aspects of relaxation complexity: possibilities and limitations
• McCormick-Based Relaxations of Algorithms
• The role of rationality in integer-programming relaxations
• Efficient algorithm for generating optimal inequality candidates for MILP modeling of Boolean functions

This page was built for publication: Efficient MIP techniques for computing the relaxation complexity

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