Decomposition algorithms for stochastic combinatorial optimization: Computational experiments and extensions

Persistent Link:
http://hdl.handle.net/10150/280638
Title:
Decomposition algorithms for stochastic combinatorial optimization: Computational experiments and extensions
Author:
Ntaimo, Lewis
Issue Date:
2004
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Some of the most important and challenging problems in computer science and operations research are stochastic combinatorial optimization (SCO) problems. SCO deals with a class of combinatorial optimization models and algorithms in which some of the data are subject to significant uncertainty and evolve over time, and often discrete decisions need to be made before observing complete future data. Therefore, under such circumstances it becomes necessary to develop models and algorithms in which plans are evaluated against possible future scenarios that represent alternative outcomes of data. Consequently, SCO models are characterized by a large number of scenarios, discrete decision variables and constraints. This dissertation focuses on the development of practical decomposition algorithms for large-scale SCO. Stochastic mixed-integer programming (SMIP), the optimization branch concerned with models containing discrete decision variables and random parameters, provides one way for dealing with such decision-making problems under uncertainty. This dissertation studies decomposition algorithms, models and applications for large-scale two-stage SMIP. The theoretical underpinnings of the method are derived from the disjunctive decomposition (D 2) method. We study this class of methods through applications, computations and extensions. With regard to applications, we first present a stochastic server location problem (SSLP) which arises in a variety of applications. These models give rise to SMIP problems in which all integer variables are binary. We study the performance of the D2 method with these problems. In order to carry out a more comprehensive study of SSLP problems, we also present certain other valid inequalities for SMIP problems. Following our study with SSLP, we also discuss the implementation of the D2 method, and also study its performance on problems in which the second-stage is mixed-integer (binary). The models for which we carry out this experimental study have appeared in the literature as stochastic matching problems, and stochastic strategic supply chain planning problems. Finally, in terms of extensions of the D 2 method, we also present a new procedure in which the first-stage model is allowed to include continuous variables. We conclude this dissertation with several ideas for future research.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering, Industrial.; Engineering, System Science.; Operations Research.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems and Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Sen, Suvrajeet

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleDecomposition algorithms for stochastic combinatorial optimization: Computational experiments and extensionsen_US
dc.creatorNtaimo, Lewisen_US
dc.contributor.authorNtaimo, Lewisen_US
dc.date.issued2004en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractSome of the most important and challenging problems in computer science and operations research are stochastic combinatorial optimization (SCO) problems. SCO deals with a class of combinatorial optimization models and algorithms in which some of the data are subject to significant uncertainty and evolve over time, and often discrete decisions need to be made before observing complete future data. Therefore, under such circumstances it becomes necessary to develop models and algorithms in which plans are evaluated against possible future scenarios that represent alternative outcomes of data. Consequently, SCO models are characterized by a large number of scenarios, discrete decision variables and constraints. This dissertation focuses on the development of practical decomposition algorithms for large-scale SCO. Stochastic mixed-integer programming (SMIP), the optimization branch concerned with models containing discrete decision variables and random parameters, provides one way for dealing with such decision-making problems under uncertainty. This dissertation studies decomposition algorithms, models and applications for large-scale two-stage SMIP. The theoretical underpinnings of the method are derived from the disjunctive decomposition (D 2) method. We study this class of methods through applications, computations and extensions. With regard to applications, we first present a stochastic server location problem (SSLP) which arises in a variety of applications. These models give rise to SMIP problems in which all integer variables are binary. We study the performance of the D2 method with these problems. In order to carry out a more comprehensive study of SSLP problems, we also present certain other valid inequalities for SMIP problems. Following our study with SSLP, we also discuss the implementation of the D2 method, and also study its performance on problems in which the second-stage is mixed-integer (binary). The models for which we carry out this experimental study have appeared in the literature as stochastic matching problems, and stochastic strategic supply chain planning problems. Finally, in terms of extensions of the D 2 method, we also present a new procedure in which the first-stage model is allowed to include continuous variables. We conclude this dissertation with several ideas for future research.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineering, Industrial.en_US
dc.subjectEngineering, System Science.en_US
dc.subjectOperations Research.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSen, Suvrajeeten_US
dc.identifier.proquest3145114en_US
dc.identifier.bibrecord.b47210151en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.