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

Gemander P, Chen WK, Weninger D, Gottwald L, Gleixner A, Martin A (2020)

Publication Type: Journal article

Publication year: 2020

Journal

EURO Journal on Computational Optimization Springer

DOI: 10.1007/s13675-020-00129-6

Abstract

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.

Authors with CRIS profile

Patrick Gemander Economics - Discrete Optimization - Mathematics (EDOM) Dieter Weninger Economics - Discrete Optimization - Mathematics (EDOM) Alexander Martin Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Beijing Institute of Technology (BIT) / 北京理工大学 CN China (CN) Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB) DE Germany (DE)

How to cite

APA:

Gemander, P., Chen, W.K., Weninger, D., Gottwald, L., Gleixner, A., & Martin, A. (2020). Two-row and two-column mixed-integer presolve using hashing-based pairing methods. EURO Journal on Computational Optimization. https://dx.doi.org/10.1007/s13675-020-00129-6

MLA:

Gemander, Patrick, et al. "Two-row and two-column mixed-integer presolve using hashing-based pairing methods." EURO Journal on Computational Optimization (2020).

BibTeX: Download