Programma

Decision making process. Introduction to Integer Linear Programming (ILP): relation between ILP and LP, equivalent formulations, relaxations, totally unimodular matrices, standard techniques for ILP modelling. Typical ILP formulations: plant location, investment problem, sequencing problems, network optimization, transportation problems, set covering, set partitioning, set packing, crew scheduling. Exact algorithms: Branch and Bound, Cutting Planes, dynamic programming. Exact algorithms for binary and integer knapsack problems. Optimization on graphs: matching, vertex cover, max flow, independent set, Eulerian graphs and bipartite graphs. Use of an ILP commercial solver.

Testi Adottati

[1] M. FISCHETTI, "LEZIONI DI RICERCA OPERATIVA", EDIZIONI LIBRERIA PROGETTO PADOVA, ITALIA, 1995. (CHAPT. 2, 5, PART of 6 and 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] Lecture notes

Modalità Erogazione

Mostly lectures on blackboard plus some classes in the lab

Modalità Valutazione

The exam is in two parts: the written exam usually lasts 2 hours and the oral exam follows. The written exam consists of a number of exercises (typically, from 3 to 5), aimed at veryfing the level of understanding of the theoretical concepts and the students' ability to apply the techniques explained in class.

Programma

Decision making process. Introduction to Integer Linear Programming (ILP): relation between ILP and LP, equivalent formulations, relaxations, totally unimodular matrices, standard techniques for ILP modelling. Typical ILP formulations: plant location, investment problem, sequencing problems, network optimization, transportation problems, set covering, set partitioning, set packing, crew scheduling. Exact algorithms: Branch and Bound, Cutting Planes, dynamic programming. Exact algorithms for binary and integer knapsack problems. Optimization on graphs: matching, vertex cover, max flow, independent set, Eulerian graphs and bipartite graphs. Use of an ILP commercial solver.

Testi Adottati

[1] M. FISCHETTI, "LEZIONI DI RICERCA OPERATIVA", EDIZIONI LIBRERIA PROGETTO PADOVA, ITALIA, 1995. (CHAPT. 2, 5, PART of 6 and 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] Lecture notes

Modalità Erogazione

Mostly lectures on blackboard plus some classes in the lab

Modalità Valutazione

The exam is in two parts: the written exam usually lasts 2 hours and the oral exam follows. The written exam consists of a number of exercises (typically, from 3 to 5), aimed at veryfing the level of understanding of the theoretical concepts and the students' ability to apply the techniques explained in class.

Programma

Decision making process. Introduction to Integer Linear Programming (ILP): relation between ILP and LP, equivalent formulations, relaxations, totally unimodular matrices, standard techniques for ILP modelling. Typical ILP formulations: plant location, investment problem, sequencing problems, network optimization, transportation problems, set covering, set partitioning, set packing, crew scheduling. Exact algorithms: Branch and Bound, Cutting Planes, dynamic programming. Exact algorithms for binary and integer knapsack problems. Optimization on graphs: matching, vertex cover, max flow, independent set, Eulerian graphs and bipartite graphs. Use of an ILP commercial solver.

Testi Adottati

[1] M. FISCHETTI, "LEZIONI DI RICERCA OPERATIVA", EDIZIONI LIBRERIA PROGETTO PADOVA, ITALIA, 1995. (CHAPT. 2, 5, PART of 6 and 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] Lecture notes

Modalità Erogazione

Mostly lectures on blackboard plus some classes in the lab

Modalità Valutazione

The exam is in two parts: the written exam usually lasts 2 hours and the oral exam follows. The written exam consists of a number of exercises (typically, from 3 to 5), aimed at veryfing the level of understanding of the theoretical concepts and the students' ability to apply the techniques explained in class.

Programma

Decision making process. Introduction to Integer Linear Programming (ILP): relation between ILP and LP, equivalent formulations, relaxations, totally unimodular matrices, standard techniques for ILP modelling. Typical ILP formulations: plant location, investment problem, sequencing problems, network optimization, transportation problems, set covering, set partitioning, set packing, crew scheduling. Exact algorithms: Branch and Bound, Cutting Planes, dynamic programming. Exact algorithms for binary and integer knapsack problems. Optimization on graphs: matching, vertex cover, max flow, independent set, Eulerian graphs and bipartite graphs. Use of an ILP commercial solver.

Testi Adottati

[1] M. FISCHETTI, "LEZIONI DI RICERCA OPERATIVA", EDIZIONI LIBRERIA PROGETTO PADOVA, ITALIA, 1995. (CHAPT. 2, 5, PART of 6 and 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] Lecture notes

Modalità Erogazione

Mostly lectures on blackboard plus some classes in the lab

Modalità Valutazione

The exam is in two parts: the written exam usually lasts 2 hours and the oral exam follows. The written exam consists of a number of exercises (typically, from 3 to 5), aimed at veryfing the level of understanding of the theoretical concepts and the students' ability to apply the techniques explained in class.