“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:

 

E. Balas, "Projection, Lifting and Extended Formulation in Integer Programming and Combinatorial Optimization",

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

 

Lista dei partecipanti

 

Slides del corso

 

Sono disponibili le slides del corso, rivedute e corrette, in formato pdf