Metodi e Modelli per l'Ottimizzazione Combinatoria [SC01122975]

and

Methods and Models for Combinatorial Optimization [INP5070470]

A.A 2018/2019

Notice

  • 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.
  • Next exam: Thursday February 21st, 9:30 am, room 1BC45
    For the exam of February 21st, the exercise (both Part I and Part II) has to be sent via email to the teacher (zip file, report in pdf) within February 19 (early delivery are appreciated).
  • The course will be taught in English (il corso sarà erogato in inglese)
  • The course will start on Thursday, October 4th (room 1BC50): during the first lesson, additional information on the course (content, exams etc.) will be discussed.
  • For further information, email the teacher.
  • Presentation for Data Science

Office hours: info


Lab exercises

  1. Part I. Implenting an Integer Linear Programming model with the Cplex API or OPL: text. posted (8-Nov-2018)
  2. Part II. Implementing an alternative solution method: text. posted (13-Dec-2018)
  • 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 instructions on how to compile and/or to run your executables on different instances. Notice: the exercises must not have errors when compiled and/or 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 (03-Oct-2018)
  2. Introduction to the course posted (03-Oct-2018)
  3. Modeling by linear programming: slides posted (03-Oct-2018)
  4. Modeling by linear programming: text posted (03-Oct-2018)
  5. Additional notes on linear programming models (optional reading, in Italian): posted (03-Oct-2018) (i) Introduction (ii) Sample models
  6. Linear Programming and the simplex method: an overview posted (18-Oct-2018) Video
  7. Review of duality in linear programming posted (22-Oct-2018)
  8. Column generation methods posted (22-Oct-2018)
  9. Solution Methods for Integer Linear Programming posted (16-Nov-2018)
  10. The assignment problem and totally unimodular matrices posted (27-Nov-2018)
  11. Exact methods for the Traveling Salesman Problem posted (27-Dec-2018)
  12. Cover inequalities posted (27-Nov-2018)
  13. Meta-heuristics: lecture notes (part I) posted (06-Dec-2018), slides (complete) posted (06-Dec-2018), annotated slides posted (11-Jan-2019)
  14. Papers on metaheuristics (optional reading, free link from the Department network): posted (14-Dec-2017)

Labs

  1. Introduction to OPL posted (10-Oct-2018)
    Location with fixed cost: OPL basic model posted (11-Oct-2018)
  2. Introduction to CPLEX API posted (10-Oct-2018)
    Makefile for CPLEX API version 12.8.0 posted (11-Oct-2018)
    Model solution values to compare to yours posted (26-Oct-2018)
  3. Complete implementation models (solutions to OPL and Cplex models) posted (14-Nov-2018)
    The solution to the "Italian friend" excercise using variable maps is available here posted (14-Nov-2018)
  4. Column generation based heuristic for the 1D-cutting stock problem posted (14-Nov-2018) Complete posted (19-Dec-2018)
  5. Neighbourhood search for the symmetric TSP: source codes posted (20-Dec-2018)
  6. Introducion to a Python interface to Cplex: examples with DOcplex bindings posted (17-Jan-2019)