Library

Description: Die vorliegende Arbeit befasst sich mit Primalheuristiken für gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP). Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierfür sind u. a. Optimierungsprobleme im öffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation. Das Lö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änden von bereits frühzeitig zur Verfügung stehenden Lösungen, daher sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute Lösung für eine große Zahl an MIPs liefern und somit die Lösezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen können. Primalheuristiken sind Suchverfahren zum Auffinden zulässiger Lösungen eines MIP. Verschiedene Typen von Primalheuristiken sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten während der Branch-and-Bound-Suche decken. Während Start- und Rundeheuristiken zu Beginn des Löseprozesses eine große Rolle bei der Suche nach der ersten zulässigen Lösung haben, arbeiten Verbesserungs-heuristiken auf schon bekannten Lösungen, um neue, bessere Lösungen zu produzieren. Diese Arbeit beschäftigt sich mit Primalheuristiken, welche Teil des MIP-Lö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ätzliche Heuristiken vorgestellt, im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine 2-Opt-Heuristik fü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ührt und anhand von Pseudocode-Algorithmen begleitet werden. Zusätzlich enthält jedes Kapitel Auswertungen der mit den neuen Heuristiken gemessenen Ergebnisse von SCIP. Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.

Description: Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the optimization of a linear objective function under a certain number of linear side constraints including the need for some of the involved variables to take integral solution values. Applications of MIP based optimization can be found in the area of public transit, scheduling, automatic vehicle routing, network design, etc. From a complexity point of view, MIP solving is known to be NP-hard and most commonly tried to be solved via Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP in various ways. Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics: while start heuristics are particularly valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality. This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP. The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used. The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg and Berthold. In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose, namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement heuristic for MIP and the propagation heuristic Shift-and-Propagate. It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms. Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details. All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.

Description: 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.

Description: 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.

Description: 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.

Description: 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 specialized version of a two-sample Student’s 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.

Description: 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.