Solving mixed-integer programs arising in production planning

Optimierung gemischt-ganzzahliger Programme in der Produktionsplanung

  • In the light of increasing globalization and ongoing rapid developments in information technology, software systems for planning production and supply networks play an important role for companies to remain competitive in future markets. Most planning systems use optimization methods for determining an efficient and economical production or supply network plan. In particular, mixed-integer optimization plays an important role in this context. It can be observed that the size of the arising mixed-integer programs has constantly increased over recent decades. The challenge is to ensure a high scalability of running time and solution quality even for very large instances anticipated in futuIn the light of increasing globalization and ongoing rapid developments in information technology, software systems for planning production and supply networks play an important role for companies to remain competitive in future markets. Most planning systems use optimization methods for determining an efficient and economical production or supply network plan. In particular, mixed-integer optimization plays an important role in this context. It can be observed that the size of the arising mixed-integer programs has constantly increased over recent decades. The challenge is to ensure a high scalability of running time and solution quality even for very large instances anticipated in future. To address this challenge, we pursue three different approaches. In the first part of the work, we initially describe presolving methods known from literature and practice. Based on these methods, we develop eight new presolving techniques for mixed-integer programming and confirm their benefit by computational results on real-world instances. Decomposition methods are well suited for achieving a high scalability of running time and solution quality. Therefore, we examine a decomposition approach in the second part of this thesis. Our algorithm splits the original problem into mixed-integer subproblems and solves the subproblems alternately to determine an optimal solution. By presenting computational results, we show that our method performs significantly better than a standard decomposition approach. In the last part, we describe an aggregation scheme for solving discrete lot-sizing problems. Starting with a coarsened formulation of the original problem, the formulation gets refined until an optimal solution is determined. Test results demonstrate that our approach usually accomplishes a better running time than a state-of-the-art mixed-integer solver.show moreshow less
  • Vor dem Hintergrund fortschreitender Globalisierung and einer nach wie vor rasanten Entwicklung in der Informationstechnologie, spielen Softwaresysteme zur Planung von Produktion und Versorgungsnetzen eine immer wichtigere Rolle für eine zukünftige Wettbewerbsfähigkeit von Firmen. Die meisten Planungssyteme nutzen zur Bestimmung eines effizienten und ökonomischen Planes Methoden der Optimierung. Insbesondere spielt die gemischt-ganzzahlige Optimierung hierfür eine wichtige Rolle. Dabei ist festzustellen, dass die Größe der zu lösenden gemischt-ganzzahligen Programme seit Jahrzehnten stetig zunimmt. Die Herausforderung besteht darin, eine hohe Skalierbarkeit von Laufzeit und LösungsqualiVor dem Hintergrund fortschreitender Globalisierung and einer nach wie vor rasanten Entwicklung in der Informationstechnologie, spielen Softwaresysteme zur Planung von Produktion und Versorgungsnetzen eine immer wichtigere Rolle für eine zukünftige Wettbewerbsfähigkeit von Firmen. Die meisten Planungssyteme nutzen zur Bestimmung eines effizienten und ökonomischen Planes Methoden der Optimierung. Insbesondere spielt die gemischt-ganzzahlige Optimierung hierfür eine wichtige Rolle. Dabei ist festzustellen, dass die Größe der zu lösenden gemischt-ganzzahligen Programme seit Jahrzehnten stetig zunimmt. Die Herausforderung besteht darin, eine hohe Skalierbarkeit von Laufzeit und Lösungsqualität für sehr große Instanzen auch in der Zukunft zu gewährleisten. Um dieser Herausforderung zu begegnen, verfolgen wir in dieser Arbeit drei verschiedene Ansätze. Im ersten Teil der Arbeit werden zunächst bekannte Presolving-Methoden aus der Literatur und Praxis beschrieben. Darauf aufbauend entwickeln wir acht neue Presolving-Methoden für gemischt-ganzzahlige Programme und belegen deren großes Potenzial anhand von Rechenergebnissen auf realen Instanzen. Da Dekompositionsverfahren für große Instanzen prädestiniert sind, um eine hohe Skalierbarkeit von Laufzeit und Lösungsqualität zu ermöglichen, untersuchen wir im zweiten Teil der Arbeit einen Dekompositionsansatz. Unser Algorithmus zerlegt das ursprüngliche Problem in gemischt-ganzzahlige Teilprobleme und löst diese abwechselnd, um eine optimale Lösung zu bestimmen. Anhand von Rechenergebnissen zeigen wir, dass unser Ansatz ein deutlich besseres Laufzeitverhalten aufzeigt als ein herkömmliches Dekompositionsverfahren. Im letzten Teil der Arbeit beschreiben wir ein Aggregationsschema zum Lösen diskreter Losgrößenprobleme. Dabei wird das Problem zunächst auf einer gröberen Darstellung gelöst und diese solange verfeinert bis sich eine Optimallösung bestimmen lässt. Durch eine ausführliche Rechenstudie belegen wir, dass dieser Ansatz gewöhnlich eine bessere Laufzeit erzielt als ein hocheffizienter gemischt-ganzzahliger Löser.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Dieter Weninger
URN:urn:nbn:de:bvb:29-opus4-82264
Advisor:Alexander Martin, Robert E. Bixby, Laurence A. Wolsey
Document Type:Doctoral Thesis
Language:English
Year of Completion:2016
Embargo Date:2017/02/09
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Date of final exam:2016/10/26
Release Date:2017/02/20
Tag:Aggregation; Decomposition; Lot-sizing; Presolving
SWD-Keyword:Gemischt-ganzzahlige Optimierung; Produktionsplanung; Supply Chain Management
Pagenumber:150
Institutes:Naturwissenschaftliche Fakultät
Dewey Decimal Classification:Naturwissenschaften und Mathematik / Mathematik / Wahrscheinlichkeiten, angewandte Mathematik
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
open_access (DINI-Set):open_access
Licence (German):Keine Creative Commons Lizenz - es gilt der Veröffentlichungsvertrag und das deutsche Urheberrecht

$Rev: 13581 $