Publication Date:
2020-08-05
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.
Language:
English
Type:
bachelorthesis
,
doc-type:bachelorThesis
Format:
application/pdf
Permalink
