You are here:

00884 - Operation Research

Academic Year 2022/2023

                
                        Docente:
                        Marco Antonio Boschetti
                    
                        Credits:
                        6
                    
                        SSD:
                        MAT/09
                    
                        Language:
                        Italian
                    
                        Teaching Mode:
                        Traditional lectures
                        
                            Campus:
                            Cesena
                        
                            Corso:
                            First cycle degree programme (L) in
                            Computer Science and Engineering (cod. 8615)

                            Teaching resources on Virtuale
                        
                                    Course Timetable
                                
from Feb 21, 2023 to Jun 06, 2023

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

1. 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 for real-world applications.

2. 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.

3. 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 teacher 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.
M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, Wiley.

Teaching methods

Lectures and exercises.

Implementation of algorithms and models by programming languages and use of solvers.

Assessment methods

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 the course.

Teaching tools

Teaching material, lecture notes, slides, exercises and examples available on Virtuale. Use of programming languages and solvers.

Office hours

See the website of Marco Antonio Boschetti