- Docente: Alberto Caprara
- Credits: 6
- SSD: MAT/09
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Engineering Management (cod. 0936)
Learning outcomes
Illustration of the most common mathematical models that are used within the organization and management of complex systems, as well as the general methods for their solution. Outilne of the solution methods, generally available as commercial or public domain software.
Course contents
Basic OR notions
Linear programming, integer linear programming, graph theory.
Duality in linear programming. Complexity theory: polynomial and
exponential algorithms, polynomial and NP-complete problems. Exact
and heuristic algorithms.
Integer linear programming models for basic NP-complete
problems
Models for capacitated facility location, uncapacitated facility
location, knapsack, bin packing, clique, coloring, set packing, set
covering, set partitioning, traveling salesman.
"Strong" and "weak" models. General methids to define "strong"
models. Implications on the problem solution.
Advanced solution methods
Review of the simplex algorithm and the branch-and-bound method.
Heuristic algorithms based on the continuous relaxation.
Models with exponentially many constraints and separation. Models
with exponentially many variables and column generation.
Applications
Crew scheduling, vehicle routing, sequencing and scheduling,
multidimensional cutting and packing.
Use of public-domain software
The AMPL package and its use for the solution of the models presented.
Readings/Bibliography
Lecture notes written by the teacher.
Teaching methods
Lectures on the blackboard.
Illustration of the software use by PC demonstrations.
Assessment methods
Written exam.
AMPL project.
Teaching tools
Use of Universibo, Dropbox and/or Almachannel to exchange information comncerning the AMPL projects.
Office hours
See the website of Alberto Caprara