Solving mixed-integer programs arising in production planning

dc.contributorMartin, Alexander
dc.contributorBixby, Robert E.
dc.contributorWolsey, Laurence A.
dc.contributor.authorWeninger, Dieter
dc.date.accessioned2017-02-20
dc.date.available2017-02-09
dc.date.created2016
dc.date.issued2017-02-20
dc.description.abstractIn 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.en
dc.description.abstractVor 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.de
dc.format.extent150
dc.identifier.opus-id8226
dc.identifier.urihttps://open.fau.de/handle/openfau/8226
dc.identifier.urnurn:nbn:de:bvb:29-opus4-82264
dc.language.isoen
dc.rights.urihttp://www.gesetze-im-internet.de/urhg/index.html
dc.subjectPresolving
dc.subjectDecomposition
dc.subjectAggregation
dc.subjectLot-sizing
dc.subject.ddcDDC Classification::5 Naturwissenschaften und Mathematik :: 51 Mathematik :: 519 Wahrscheinlichkeiten, angewandte Mathematik
dc.titleSolving mixed-integer programs arising in production planningen
dc.titleOptimierung gemischt-ganzzahliger Programme in der Produktionsplanungde
dc.typedoctoralthesis
dcterms.publisherFriedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
local.date.accepted2016-10-26
local.sendToDnbfree*
local.subject.fakultaetNaturwissenschaftliche Fakultät
local.subject.gndGemischt-ganzzahlige Optimierung
local.subject.gndProduktionsplanung
local.subject.gndSupply Chain Management
local.thesis.grantorFriedrich-Alexander-Universität Erlangen-Nürnberg (FAU) 
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
8226_DieterWeningerDissertation.pdf
Size:
2.84 MB
Format:
Adobe Portable Document Format
Description:
Faculties & Collections