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

Weiterer Publikationstyp


Details zur Publikation

Autorinnen und Autoren: Chen W, Gemander P, Gleixner A, Gottwald L, Martin A, Weninger D
Jahr der Veröffentlichung: 2019
Sprache: Englisch


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 presolving 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 presolving techniques
that consider pairs of rows or columns. Additionally, we develop an enhancement to
one of these presolving 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.


FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Gemander, Patrick
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Weninger, Dieter Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Zitierweisen

APA:
Chen, W., Gemander, P., Gleixner, A., Gottwald, L., Martin, A., & Weninger, D. (2019). Two-row and two-column mixed-integer presolve using hash-based pairing methods.

MLA:
Chen, Weikun, et al. Two-row and two-column mixed-integer presolve using hash-based pairing methods. 2019.

BibTeX: 

Zuletzt aktualisiert 2019-09-09 um 09:24