Wiese, Sven
(2016)
On the interplay of Mixed Integer Linear, Mixed Integer Nonlinear and Constraint Programming, [Dissertation thesis], Alma Mater Studiorum Università di Bologna.
Dottorato di ricerca in
Automatica e ricerca operativa, 28 Ciclo. DOI 10.6092/unibo/amsdottorato/7612.
Documenti full-text disponibili:
Abstract
In this thesis we study selected topics in the field of Mixed Integer Programming (MIP), in particular Mixed Integer Linear and Nonlinear Programming (MI(N)LP). We set a focus on the influences of Constraint Programming (CP).
First, we analyze Mathematical Programming approaches to water network optimization, a set of challenging optimization problems frequently modeled as non-convex MINLPs. We give detailed descriptions of many variants and survey solution approaches from the literature. We are particularly interested in MILP approximations and present a respective computational study for water network design problems. We analyze this approach by algorithmic considerations and highlight the importance of certain convex substructures in these non-convex MINLPs. We further derive valid inequalities for water network design problems exploiting these substructures.
Then, we treat Mathematical Programming problems with indicator constraints, recalling their most popular reformulation techniques in MIP, leading to either big-M constraints or disjunctive programming techniques. The latter give rise to reformulations in higher-dimensional spaces, and we review special cases from the literature that allow to describe the projection on the original space of variables explicitly. We theoretically extend the respective results in two directions and conduct computational experiments. We then present an algorithm for MILPs with indicator constraints that incorporates elements of CP into MIP techniques, including computational results for the JobShopScheduling problem.
Finally, we introduce an extension of the class of MILPs so that linear expressions are allowed to have non-contiguous domains. Inspired by CP, this permits to model holes in the domains of variables as a special case. For such problems, we extend the theory of split cuts and show two ways of separating them, namely as intersection and lift-and-project cuts, and present computational results. We further experiment with an exact algorithm for such problems, applied to the Traveling Salesman Problem with multiple time windows.
Abstract
In this thesis we study selected topics in the field of Mixed Integer Programming (MIP), in particular Mixed Integer Linear and Nonlinear Programming (MI(N)LP). We set a focus on the influences of Constraint Programming (CP).
First, we analyze Mathematical Programming approaches to water network optimization, a set of challenging optimization problems frequently modeled as non-convex MINLPs. We give detailed descriptions of many variants and survey solution approaches from the literature. We are particularly interested in MILP approximations and present a respective computational study for water network design problems. We analyze this approach by algorithmic considerations and highlight the importance of certain convex substructures in these non-convex MINLPs. We further derive valid inequalities for water network design problems exploiting these substructures.
Then, we treat Mathematical Programming problems with indicator constraints, recalling their most popular reformulation techniques in MIP, leading to either big-M constraints or disjunctive programming techniques. The latter give rise to reformulations in higher-dimensional spaces, and we review special cases from the literature that allow to describe the projection on the original space of variables explicitly. We theoretically extend the respective results in two directions and conduct computational experiments. We then present an algorithm for MILPs with indicator constraints that incorporates elements of CP into MIP techniques, including computational results for the JobShopScheduling problem.
Finally, we introduce an extension of the class of MILPs so that linear expressions are allowed to have non-contiguous domains. Inspired by CP, this permits to model holes in the domains of variables as a special case. For such problems, we extend the theory of split cuts and show two ways of separating them, namely as intersection and lift-and-project cuts, and present computational results. We further experiment with an exact algorithm for such problems, applied to the Traveling Salesman Problem with multiple time windows.
Tipologia del documento
Tesi di dottorato
Autore
Wiese, Sven
Supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
28
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
MILP, MINLP, CP, Water networks optimization, Nonlinear network flows, Piecewise linear approximations, Indicator constraints, big-M constraints, Disjunctive Programming, Job Shop Scheduling, Cutting planes, Split cuts, Intersection cuts, Lift-and-project cuts, TSPMTW
URN:NBN
DOI
10.6092/unibo/amsdottorato/7612
Data di discussione
27 Maggio 2016
URI
Altri metadati
Tipologia del documento
Tesi di dottorato
Autore
Wiese, Sven
Supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
28
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
MILP, MINLP, CP, Water networks optimization, Nonlinear network flows, Piecewise linear approximations, Indicator constraints, big-M constraints, Disjunctive Programming, Job Shop Scheduling, Cutting planes, Split cuts, Intersection cuts, Lift-and-project cuts, TSPMTW
URN:NBN
DOI
10.6092/unibo/amsdottorato/7612
Data di discussione
27 Maggio 2016
URI
Statistica sui download
Gestione del documento: