34895 - Optimisation Algorithms M

Learning outcomes

   At the end of the course, the students are able to analyze the computational complexity and to define the Mixed Integer Linear Programming (MILP) models of the Combinatorial Optimization problems. The students are able to obtain tight relaxations of the MILP models, and to design exact enumerative algorithms (based on the branch-and-bound, branch-and-cut and branch-and-price approaches)  for determining the optimal solution of the Combinatorial Optimization problems. The students are also able to solve the MILP models by using the software package CPLEX.

Course contents

Classification of the Combinatorial Optimization Problems. Mathematical models of the Combinatorial Optimization Problems (and analysis of their Computational Complexity). Utilization of the Software Package CPLEX for the solution of Linear Programming and Mixed Integer Linear Programming models.    Exact Algorithms for the solution of NP-Hard problems:  “Branch-and-Bound”: Relaxations, Branching Schemes, Dominance Criteria. Large Size Problems, Knapsack Problem (KP), Subset Sum Problem, Asymmetric Traveling Salesman Problem (ATSP);  “Branch-and-Cut”: Separation Procedures , ATSP; “Branch-and-Price”: Pricing Procedures, Column Generation, Bin Packing Problem, Vertex Coloring Problem.

Readings/Bibliography

• S. Martello, P. Toth, Knapsack Problems: Algortihms and Computer Implementations, J. Wiley, 1990.   
  • R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.  
  • G. Gutin, A. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer, 2002. 
  • P. Toth, D. Vigo (editors), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 2002.  
  • C. Barnhart, G. Laporte (editors), Transportation, Handbooks in Operations Research and Management Science, North Holland, 2007. 
  • Wiley Encyclopedia in Operations Research and Management Science, Wiley, 2011.

Teaching methods

Lessona in the lecture-room. Exercizes in the lecture-room. Exercizes in the laboratory.

Assessment methods

Written tests concerning the definition of mathematical models, the study of the computational complexity, definition and solution of the relaxed problems, design of excat algorithms, implementation of the mathematical models in CPLEX.

Teaching tools

Copies of the slides used during the lessons are available on the web site   www.UniversiBo.it

Office hours

See the website of Paolo Toth