Course Unit Page
-
Teacher Daniele Vigo
-
Learning modules Daniele Vigo (Modulo 1)
Roberto Baldacci (Modulo 2)
-
Credits 6
-
SSD MAT/09
-
Teaching Mode Traditional lectures (Modulo 1)
Traditional lectures (Modulo 2)
-
Language Italian
-
Campus of Cesena
-
Degree Programme First cycle degree programme (L) in Computer Science and Engineering (cod. 8615)
-
Course Timetable from Sep 22, 2021 to Oct 28, 2021
Course Timetable from Nov 03, 2021 to Dec 09, 2021
SDGs
This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.
Academic Year 2021/2022
Learning outcomes
At the end of the course, the student knows the main models and algorithms for linear and integer programming and graph theory.
Course contents
Module 1
a. Mathematical models of optimization problems
Definition of a mathematical model, decision variables, objective function and requirements or constraints. Mathematical modeling techniques.
Examples of mathematical models, taken from systems and networks, data mining, logistics, computational biology and computer applications.
b. Continuous Linear Programming (PLC) and Integer Programming (PLI).
Mathematical models with continuous variables. Geometric resolution. PLC theory and simplex algorithm
Mathematical models with integer variables. Geometric interpretation. Properties of PLI problems. Relaxation techniques. Cutting-plane algorithms (CP). Branch-and-bound method (B&B). Applications of the B&B technique.
Module 2
Elements of graph theory and its main problems.
Main definitions of graph theory. Minimum cost spanning trees (SST). Minimal paths (CM). Network flow problems (FR), maximum flow, minimum cost flow. Linear assignment.
Readings/Bibliography
- Lecture notes and slides by teachers available online
Texts for consultation only
- Matteo Fischetti, Operations Research Lessons, Project Library.
- C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, NY.
- R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
- M. Gondran, M. Minoux, "Graphs and Algorithms", John Wiley.
Teaching methods
Frontal lessons. Numerical exercises on the various algorithms for solving PL, PLI, SST, CM and FR problems.
Implementation of algorithms and models in laboratory through programming languages and use of solvers.
Assessment methods
- Exercises based on solving SST, CM and FR problems. Exercises on the different illustrated algorithms.
- The learning assessment takes place through a written test, which has the purpose of examining the acquisition of the knowledge required by the program of both modules of the course.
Teaching tools
Teaching material, lecture notes, slides, exercises and code examples available on the net. Use of programming languages and solvers.
Office hours
See the website of Daniele Vigo
See the website of Roberto Baldacci
Alumni