- Docente: Aristide Mingozzi
- Credits: 9
- SSD: MAT/09
- Language: Italian
- Moduli: Aristide Mingozzi (Modulo 1) Roberto Roberti (Modulo 2)
- Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
- Campus: Cesena
- Corso: First cycle degree programme (L) in Computer Science and Information Technology (cod. 8013)
Learning outcomes
Objective of the course is the study of optimization methods and algorithms in linear programming and integer programming.
Course contents
- Linear models
- Linear models with integer variables
- Notes on linear algebra
- Notes on convexity theory
- Primal simplex method
- Two-phase simplex method
- Degeneracy: lexicographic method to avoid cycling
- Duality
- Complementary slackness
- Primal simplex interpretation
- Dual simplex method
- Primal-dual simplex method
- Maximum flow problem
- Transportation problem
- Hungarian method for the transportation problem
- Introduction to integer programming
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".
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
Computer 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 Roberto Roberti