Two-row and two-column mixed-integer presolve using hashing-based pairing methods

  • In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Patrick Gemander, Wei-Kun Chen, Dieter Weninger, Leona Gottwald, Ambros Gleixner
Document Type:Article
Parent Title (English):EURO Journal on Computational Optimization
Volume:8
Issue:3-4
First Page:205
Last Page:240
Year of first publication:2020
DOI:https://doi.org/10.1007/s13675-020-00129-6