“Advanced Course on Discrete Optimization”
Prof. Egon Balas
Tepper
School of Business, Carnegie-Mellon University
3 – 6 giugno
2008
Scuola
Superiore Santa Chiara - Università degli Studi di Siena
Il
corso sarà incentrato sul concetto di lift and project, dalle sue radici -- disjunctive programming – fino ad
alcuni dei suoi sviluppi più recenti nella teoria dei piani di taglio, come la
generazione di tagli lift-and-project dal tableau del
simplesso.
Organizzazione del corso
Il
corso consisterà di:
·
4
lezioni da due ore ciascuna (intervallate da una pausa di 15 minuti), nei
giorni 3-4-5-6 giugno, dalle 10 alle 12,30
·
Alcuni
esercizi (“homework assignments”),
aventi lo scopo di far assimilare meglio il contenuto delle due ore mattutine,
che andranno svolti al di fuori dell’orario delle lezioni. Per quest’ultima
attività, il prof. Balas sarà coadiuvato da Andrea
Pacifici e Paolo Detti.
A
richiesta, sarà rilasciato un attestato di partecipazione al corso (e.g. per i
dottorandi).
La
partecipazione al corso è gratuita, ma chi è interessato a partecipare è
pregato di inviare un messaggio di posta elettronica ad Alessandro
Agnetis (agnetis@dii.unisi.it) e Paolo Detti (detti@dii.unisi.it).
Syllabus
1. Basic properties and uses of projection
- Extended
formulations
-
Projection techniques
- Dimension
of projected polyhedra
- Comparing different formulations
- Proving
integrality by projection
2. Disjunctive programming
-
Intersection cuts
- Disjunctive
sets, conjunctive and disjunctive normal forms
- The
convex hull of a union of polyhedra
-
Sequential convexification
- Monoidal strengthening
3. Lift-and-Project cuts for mixed integer
programming
- Cut
generating linear programs (CGLP)
- Connection
with matrix cones
- Cut
strengthening from integrality of nonbasics
- Cut
lifting, globally versus locally valid cuts
- Single
cuts versus rounds of cuts
- Cutting
versus branching
4. Solving the CGLP on the LP simplex tableau
- Precise
correspondence between CGLP bases and LP bases
- Mimicking
sequences of CGLP pivots by single LP pivots
-
Lift-and-project cuts and mixed integer Gomory cuts
- Cuts from
non-optimal and infeasible LP tableaux
- The role
of normalization in avoiding accuracy problems
Riferimenti bibliografici
Il corso coprirà prevalentemente gli argomenti contenuti nel survey:
Annals of Operations Research,
140, 2005, 125-161.
Molti
dettagli che saranno presentati nel corso si trovano nei paper
citati nel survey.
Luogo
Il
corso si terrà presso la Scuola Superiore Santa Chiara (via Valdimontone
1). È situata in centro, facilmente raggiungibile a piedi da qualsiasi punto
entro le mura. (Clicca qui per visualizzare una
cartina che indica la posizione)
Contatti
Per
domande o ulteriori informazioni, potete scrivere ad Alessandro Agnetis o Paolo Detti
Slides del corso
Sono
disponibili le slides del corso,
rivedute e corrette, in formato pdf