Two-row and two-column mixed-integer presolve using hashing-based pairing methods
- PDF / 607,260 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 150 Views
Two-row and two-column mixed-integer presolve using hashing-based pairing methods Patrick Gemander1 · Wei-Kun Chen2 · Dieter Weninger1 · Leona Gottwald3 · Ambros Gleixner3 · Alexander Martin1 Received: 1 October 2019 / Accepted: 10 July 2020 © The Author(s) 2020
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. Keywords Linear programming · Mixed-integer linear programming · Optimization solver · Presolve Mathematics Subject Classification 90C05 · 90C10 · 90C11 · 65Y05
1 Introduction Presolve for mixed-integer programming (MIP) is a set of routines that remove redundant information and strengthen the model formulation with the aim of accelerating a subsequent main solution process, which is usually a branch-and-cut approach. Further, presolve is an excellent complement to branch-and-cut, because it focuses on model reductions and reformulations that are commonly not in the working space of branch-and-cut, e.g., greatest common divisor reductions or redundancy detection.
Extended author information available on the last page of the article
123
P. Gemander et al.
Presolve can be very effective, and it frequently makes the difference between a problem being intractable and solvable (Achterberg and Wunderling 2013). Considering that presolve is undisputedly an important building block in solving MIP problems, there exist comparatively few articles in the MIP literature. Only in the last few years there has been a moderate increase in the number of publications on this subject. One of the earliest contributions was by Brearley et al. (1975). Later Johnson and Suhl (1980), Guignard and Spielberg (1981), Crowder et al. (1983), and Hoffman and Padberg (1991) investigated presolve techniques for zero-one inequalities. Savelsbergh (1994) published preprocessing and probing techniques for MIP problems. Many of the methods published in it are now standard in almost every MIP solver. Presolve also plays an important role in linear programming (Andersen and Andersen 1995) and especially for interior point algo
Data Loading...
