New Rounding and Propagation Heuristics for Mixed Integer Programming

Please always quote using this URN: urn:nbn:de:0297-zib-13322
  • 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.
  • 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.

Download full text files

Export metadata

Metadaten
Author:Gregor Hendel
Document Type:Bachelor's Thesis
Tag:Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Granting Institution:Technische Universität Berlin
Date of final exam:2011/05/10
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:2011/07/13
Pagenumber:95