Algorithmische Verbesserungen für die Lösung diskreter Optimierungsmodelle

Abstract

In den letzten Jahren wurde das Konzept zur Lösung von gemischt-ganzzahligen Modellen stark weiterentwickelt. Mit Hilfe der strengen LP-Relaxierung, mit dem Branch-and-Cut-Ver¬fahren, aber auch mit den leistungsstärkeren Computern werden schwere Modelle schneller oder überhaupt erst gelöst. Da viele Anwendungen in der Wirtschaft eingesetzt werden, muss bei kurzfristigen Änderungen schnell eine neue optimale Lösung im Bezug auf die Verände¬rungen gegeben sein. Die Lösungszeit vieler Probleme ist demnach immer noch zu lang, und es werden leider auch noch viele Probleme überhaupt nicht gelöst. Aus zeitlichen Gründen löst ein Großteil der An¬wender die Probleme nicht bis zur Optimalität und benutzt stattdessen für ihre Planung schnell gefundene Integer-Lösungen, die entfernt von dem Optimum liegen. Aus dieser Problematik ergibt sich das primäre Ziel der vorliegenden Arbeit. Es sollen möglichst früh im Branch-and-Bound gute Integer-Lösungen gefunden werden. Dabei wird ausgehend von dem bestehenden Optimierungssystem MOPS der Branch-and-Bound-Prozess umstrukturiert und durch neue Branching-Strategien, eine veränderte Bound Reduction mit verschiedenen Einsatzmöglichkeiten und Heuristiken vor und während des Branch-and-Bounds erweitert. Dabei wird u.a. bestehendes mathematisches Wissen aus der Literatur angewandt bzw. erweitert und implementiert. Durch die Einführung der erweiterten Modellklassen wird das Spektrum der Modellierung ausgedehnt. Anhand von 10 leichten und 10 schweren Modellen der MILPlib, MIPLIB3 und MIPLIB2003 werden die einzelnen Strategien und Heuristiken getestet und mit dem alten Branch-and-Bound verglichen. Unter den entwickelten Strategien gibt es keine klar dominierende Strategie, aber sie erfüllen zumeist das gesetzte Ziel, schneller und bessere Integer-Lösungen zu finden.

The concept of solving mixed-integer optimization problems was enhanced in the last decades. Difficult problems are solved faster or are even solved with the help of tight LP relaxation, high-performance computers and the branch-and-cut approach. A lot of applications are used in the industry and have to produce optimal integer solutions as soon as possible, if there is a short-time change in the data of the model. The solution time of many problems are too long and some problems cannot be solved in a reasonably amount of time. In the consequence of time-limitations some application stop before the optimal integer solution was found and uses the actual integer solution instead, which can be l far away of the optimum. This described problem produces the primal ambition of this dissertation. The intention is to find good integer solution quite early in the branch-and- bound. Therefore the branch-and-bound algorithm of the existing optimization system MOPS is restructured und the system is extended by new branching strategies, a modified bound reduction with several applications and heuristics before and during the branch-and-bound. Existing knowledge of the mathematic literature are applied or rather extended and finally implemented. The introduction of the extended model classes extends the spectrum of modelling. The several strategies and heuristics are tested with 10 easy and 10 difficult models of the libraries MIPlib, MIPLIB3 and MIPLIB2003 and are compared to the default strategy of the old branch-and-bound. None of the new developed strategies obvious dominate all other strategies, but the most of them achieved the goal to find earlier and better integer solution.