Metodi e Modelli per l'Ottimizzazione Combinatoria [SC01122975]

and

Methods and Models for Combinatorial Optimization [INP5070470]

A.A 2016/2017

Notice

  • The course will be taugth in English (il corso sarà erogato in inglese)
  • Next classes: Thursday January 19th, room 1bc50 -- Friday January 20th, LabTA.
  • 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: text. posted (26-Oct-2016)
  2. Part II. Implementing an alternative solution method: text. posted (17-Nov-2016)
  • 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 file containing
    • the report in pdf format
    • the source code files (with related makefiles)
    • some (two or three!) sample instances
    • 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 invited to read them in advance.

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

Labs

  1. Introduction to CPLEX API update (27-Oct-2016)

  2. Solutions (completed source code) update (27-Oct-2016)
  3. Neighbourhood search for the symmetric TSP: source codes posted (17-Nov-2016)
  4. Column generation based heuristic for the 1D-cutting stock problem: source code posted (11-Jan-2017)
  5. Branch-and-Cut example: cover inequalites posted (19-Jan-2017)