Many decision problems in industry, logistics, and telecommunications can be viewed as satisfiability or optimization problems. Two paradigms have reached a high degree of sophistication from the point of view of both theory and implementation: Constraint Programming (CP) and Mixed Integer Programming (MIP). The CP and MIP paradigms have strengths and weaknesses that complement each other. On the one hand, CP, through the use of sophisticated propagation techniques, privileges primal inference. On the other hand, MIP, through the techniques of relaxation and strengthening through cutting planes, privileges dual inference. This thesis presents several studies in Mixed Integer Programming, with emphasis on computational aspects and integration with the Constraint Programming paradigm. In particular, CP concepts and techniques, such as nogoods, minimal infeasiblity and constraint propagation, are used to improve different MIP solving components, namely, dominance detection, Benders cuts selection strategy and primal heuristics. This cross-fertilization of techniques and ideas has proven very effective. Finally, an appendix is given covering a MIP application to robust railway timetabling.

Molti problemi decisionali nell'industria, nella logistica e nelle telecomunicazioni possono essere formulati come problemi di soddisfacibilita' o di ottimizzazione. Due paradigmi per la modellazione e la risoluzione di tali problemi hanno raggiunto un elevato grado di sviluppo, sia dal punto di vista teorico che implementativo: la Programmazione a Vincoli (Constraint Programming, CP) e la Programmazione Lineare Intera Mista (Mixed Integer Programming, MIP). I paradigmi CP e MIP hanno vantaggi e debolezze complementari. Da una parte, la CP privilegia l'inferenza primale, attraverso sofisticate tecniche di propagazione. Dall'altra, la MIP privilegia l'inferenza duale, attraverso i rilassamenti e il loro rafforzamento mediante piani di taglio. Questa tesi presenta alcuni studi in Programmazione Lineare Intera Mista, con enfasi sugli aspetti computazionali e sull'integrazione col paradigma della Programmazione a Vincoli. In particolare, concetti e tecniche CP, quali nogood, insoddisfacibilita' minimale e propagazione, sono usati per migliorare varie componenti risolutive per la MIP, quali procedure di dominanza, strategia di selezione dei tagli di Benders e euristiche primali. Questo scambio di idee e tecniche si e' dimostrato molto efficace. Infine, un'applicazione MIP alla generazione di orari robusti in ambito ferroviario e' presentata in appendice.

Constraint Programming Techniques for Mixed Integer Linear Programs / Salvagnin, Domenico. - (2009).

Constraint Programming Techniques for Mixed Integer Linear Programs

Salvagnin, Domenico
2009

Abstract

Molti problemi decisionali nell'industria, nella logistica e nelle telecomunicazioni possono essere formulati come problemi di soddisfacibilita' o di ottimizzazione. Due paradigmi per la modellazione e la risoluzione di tali problemi hanno raggiunto un elevato grado di sviluppo, sia dal punto di vista teorico che implementativo: la Programmazione a Vincoli (Constraint Programming, CP) e la Programmazione Lineare Intera Mista (Mixed Integer Programming, MIP). I paradigmi CP e MIP hanno vantaggi e debolezze complementari. Da una parte, la CP privilegia l'inferenza primale, attraverso sofisticate tecniche di propagazione. Dall'altra, la MIP privilegia l'inferenza duale, attraverso i rilassamenti e il loro rafforzamento mediante piani di taglio. Questa tesi presenta alcuni studi in Programmazione Lineare Intera Mista, con enfasi sugli aspetti computazionali e sull'integrazione col paradigma della Programmazione a Vincoli. In particolare, concetti e tecniche CP, quali nogood, insoddisfacibilita' minimale e propagazione, sono usati per migliorare varie componenti risolutive per la MIP, quali procedure di dominanza, strategia di selezione dei tagli di Benders e euristiche primali. Questo scambio di idee e tecniche si e' dimostrato molto efficace. Infine, un'applicazione MIP alla generazione di orari robusti in ambito ferroviario e' presentata in appendice.
2009
Many decision problems in industry, logistics, and telecommunications can be viewed as satisfiability or optimization problems. Two paradigms have reached a high degree of sophistication from the point of view of both theory and implementation: Constraint Programming (CP) and Mixed Integer Programming (MIP). The CP and MIP paradigms have strengths and weaknesses that complement each other. On the one hand, CP, through the use of sophisticated propagation techniques, privileges primal inference. On the other hand, MIP, through the techniques of relaxation and strengthening through cutting planes, privileges dual inference. This thesis presents several studies in Mixed Integer Programming, with emphasis on computational aspects and integration with the Constraint Programming paradigm. In particular, CP concepts and techniques, such as nogoods, minimal infeasiblity and constraint propagation, are used to improve different MIP solving components, namely, dominance detection, Benders cuts selection strategy and primal heuristics. This cross-fertilization of techniques and ideas has proven very effective. Finally, an appendix is given covering a MIP application to robust railway timetabling.
constraint programming, integer programming
Constraint Programming Techniques for Mixed Integer Linear Programs / Salvagnin, Domenico. - (2009).
File in questo prodotto:
File Dimensione Formato  
thesis.pdf

accesso aperto

Tipologia: Tesi di dottorato
Licenza: Non specificato
Dimensione 1.36 MB
Formato Adobe PDF
1.36 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3425690
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact