@misc{GamrathFischerGallyetal.2016, author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, year = {2016}, abstract = {The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.}, language = {en} } @misc{BertholdHendel2013, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-And-Propagate}, issn = {1438-0064}, doi = {10.1007/s10732-014-9271-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17596}, year = {2013}, abstract = {For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.}, language = {en} } @misc{Hendel2015, author = {Hendel, Gregor}, title = {Enhancing MIP branching decisions by using the sample variance of pseudo-costs}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54591}, year = {2015}, abstract = {The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.}, language = {en} } @masterthesis{Hendel2011, type = {Bachelor Thesis}, author = {Hendel, Gregor}, title = {New Rounding and Propagation Heuristics for Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13322}, school = {Zuse Institute Berlin (ZIB)}, pages = {95}, year = {2011}, abstract = {Die vorliegende Arbeit befasst sich mit Primalheuristiken f{\"u}r gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP). Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierf{\"u}r sind u. a. Optimierungsprobleme im {\"o}ffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation. Das L{\"o}sen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umst{\"a}nden von bereits fr{\"u}hzeitig zur Verf{\"u}gung stehenden L{\"o}sungen, daher sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute L{\"o}sung f{\"u}r eine große Zahl an MIPs liefern und somit die L{\"o}sezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen k{\"o}nnen. Primalheuristiken sind Suchverfahren zum Auffinden zul{\"a}ssiger L{\"o}sungen eines MIP. Verschiedene Typen von Primalheuristiken sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten w{\"a}hrend der Branch-and-Bound-Suche decken. W{\"a}hrend Start- und Rundeheuristiken zu Beginn des L{\"o}seprozesses eine große Rolle bei der Suche nach der ersten zul{\"a}ssigen L{\"o}sung haben, arbeiten Verbesserungs-heuristiken auf schon bekannten L{\"o}sungen, um neue, bessere L{\"o}sungen zu produzieren. Diese Arbeit besch{\"a}ftigt sich mit Primalheuristiken, welche Teil des MIP-L{\"o}sers SCIP sind. Im ersten Kapitel werden nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die Kapitel 2-4 der Arbeit auf. In diesen werden drei zus{\"a}tzliche Heuristiken vorgestellt, im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine 2-Opt-Heuristik f{\"u}r MIP und eine neue Startheuristik, Shift-And-Propagate. Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden Beispielen eingef{\"u}hrt und anhand von Pseudocode-Algorithmen begleitet werden. Zus{\"a}tzlich enth{\"a}lt jedes Kapitel Auswertungen der mit den neuen Heuristiken gemessenen Ergebnisse von SCIP. Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.}, language = {en} } @misc{AchterbergBertholdHendel2011, author = {Achterberg, Tobias and Berthold, Timo and Hendel, Gregor}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, doi = {10.1007/978-3-642-29210-1_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13255}, number = {11-29}, year = {2011}, abstract = {Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.}, language = {en} } @misc{Hendel2015, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57098}, year = {2015}, abstract = {Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.}, language = {en} } @misc{BertholdHendelKoch2016, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {The Three Phases of MIP Solving}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1392519}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61607}, year = {2016}, abstract = {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.}, language = {en} }