Metodi e Modelli per l'Ottimizzazione Combinatoria [SC01122975]

and

Methods and Models for Combinatorial Optimization [INP5070470]

A.A 2017/2018

Notice

  • Presentation for Data Science
  • Next exams: Wednesday September 19th, 10:00 am, teacher office
  • For the exam of September 19th, the exercise (both Part I and Part II) has to be sent via email to the teacher (zip file, report in pdf) within September 17th
  • The course will be taught in English (il corso sarà erogato in inglese)
  • The course will start on Thursday, October 7th (room 1BC50): during the first lesson, additional information on the course (content, exams etc.) will be discussed.
  • For further information, email the teacher.
  • To gain access to the optimisation software for labs, you need to click here and register to the "CPLEX Academic" user list, using the key provided by the teacher.

Office hours: info


Lab exercises

  1. Part I. Implenting an Integer Linear Programming model with the Cplex API or OPL: text. posted (7-Nov-2017)
  2. Part II. Implementing an alternative solution method: text. posted (21-Dec-2017)
  • How to deliver the exercise (Part I and Part II)
    The exercises must be sent by email to the teacher.
    The email must have attached a compressed ZIP file containing
    • the report in pdf format
    • the source code files (with related makefiles, id needed)
    • some (two or three!) small instances among te ones used for testing
    • clear and simple instruction on how to compile and to run your executables on different instances. Notice: the exercises must not have errors when compiled and tested on the computers of LabTA.
  • Deadline: You should send the exercises to the teacher one week before the date of the exam you are going to do: a notice indicating the exact deadline will be posted on this webpage before each exam date.

Lecture notes

The lecture notes of each class will be provided some days before the class itself: students are warmly invited to read them in advance.

  1. Course information posted (29-Sep-2017)
  2. Introduction to the course posted (29-Sep-2017)
  3. Modeling by linear programming: slides posted (29-Sep-2017)
  4. Modeling by linear programming: text posted (29-Sep-2017)
  5. Additional notes on linear programming models (optional reading, in Italian): posted (29-Sep-2017) (i) Introduction (ii) Sample models
  6. Linear Programming and the simplex method: an overview posted (18-Oct-2017)
  7. Review of duality in linear programming posted (19-Oct-2017)
  8. Column generation methods posted (19-Oct-2017)
  9. Solution Methods for Integer Linear Programming posted (19-Oct-2017)
  10. The assignment problem and totally unimodular matrices posted (29-Nov-2017)
  11. Exact methods for the Traveling Salesman Problem posted (05-Dec-2017)
  12. Cover inequalities posted (05-Dec-2017)
  13. Meta-heuristics: lecture notes (part I) posted (14-Dec-2017) slides (complete) updated (11-Jan-2018)
  14. Papers on metaheuristics (optional reading, free link from the Department network): posted (14-Dec-2017)
    (i) Overview (C. Blum and A. Roli)
    (ii) The metaphor exposed (K. Sörensen)

Labs

  1. Introduction to OPL posted (11-Oct-2017)
  2. Introduction to CPLEX API posted (12-Oct-2017)
  3. Column generation based heuristic for the 1D-cutting stock problem posted (15-Nov-2017) Complete posted (29-Nov-2017)
  4. Complete implementation models (solutions to OPL and Cplex models) posted (29-Nov-2017)
    The solution to the "Italian friend" excercise using variable maps is available here posted (15-Jan-2018)
  5. Neighbourhood search for the symmetric TSP: source codes posted (21-Dec-2017)
  6. Branch-and-Cut example (additional material): cover inequalites - posted (19-Jan-2017)