- Docente: Aristide Mingozzi
- Credits: 6
- SSD: MAT/09
- Language: Italian
- Moduli: Aristide Mingozzi (Modulo 1) Enrico Bartolini (Modulo 2)
- Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
- Campus: Cesena
- Corso: Second cycle degree programme (LM) in Computer Science and Information Technology (cod. 8030)
Learning outcomes
The main objective of this course is to provide some of the mathematical methods and algorithms necessary for tacking practical problems than can be formulated using integer programming.
Course contents
Introduction to
Integer Programming:
Integer formulations
Mixed integer formulations
Alternative formulations
Examples
Well Solved Problems:
Properties of easy problems
Integer problems with totally unimodular matrices
Examples of easy problems
Relaxation and Lower Bounds:
Linear Programming relaxation
Combinatorial relaxations
Surrogate relaxation
Lagrangean relaxation
Optimality
Examples
Dynamic Programming:
Motivations
Shortest paths
Knapsack problem
Traveling salesman problem (TSP)
Implementation methods of the TSP recursion
2-D cutting
State space relaxation
Lower bounds
Examples
Branch and Bound Methods (B&B):
LP-based Branch and Bound
Branching methods
Dominance
Examples of B&B algorithms:
- Knapsack problem
- TSP
- Generalized assignment problem
- Set covering/partitioning
Cutting plane Algorithms:
Introduction
Valid inequalities
Gomory cuts
Cutting plane algorithm
Examples
Strong inequalities
Introduction to branch and cut algorithms
Examples
Heuristic Algorithms:
Introduction
Greedy and local search methods
Improved local search:
- Tabu search
- Simulated annealing
- Genetic and bionomic algorithms
Examples
Readings/Bibliography
- M.S.Bazaraa, J.J.Jarvis, H.D.Sherali, "Linear programming and network flows", John Wiley & Sons.
- C.H. Papadimitriou, K. Steiglitz, "Combinatorial Optimization, Algorithms and Complexity", Prentice-Hall.
- L.A. Wolsey, "Integer Programming", John Wiley & Sons.
Teaching methods
During the lessons both theoretical and practical aspects are presented. Examples, exercises and projects help the student to learn the use of the mathematical tools.
Assessment methods
Project and written and oral examinations.
Teaching tools
Lecture notes, projector, PC and labs.
Office hours
See the website of Aristide Mingozzi
See the website of Enrico Bartolini