G. Mathematics of Computing
Refine
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3)
Keywords
- MINLP (1)
- MIPLIB2003 (1)
- Mixed Integer Programming (1)
- OBBT (1)
- ParaSCIP (1)
- Supercomputer (1)
- Ubiquity Generator Framework (1)
- adaptive search behavior (1)
- bound tightening (1)
- branch-and-bound (1)
Institute
Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT.
Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs.
We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.
Contemporary supercomputers can easily provide years of
CPU time per wall-clock hour. One challenge of today's software
development is how to harness this wast computing power in order to solve
really hard mixed integer programming instances. In 2010, two out of
six open MIPLIB2003 instances could be solved by ParaSCIP in more than
ten consecutive runs, restarting from checkpointing files.
The contribution of this paper is threefold:
For the first time, we present computational results of single runs for
those two instances. Secondly, we provide new improved upper and lower
bounds for all of the remaining four open MIPLIB2003 instances.
Finally, we explain which new developments led to these results and
discuss the current progress of ParaSCIP. Experiments were conducted on
HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.