Metodi e Modelli per l'Ottimizzazione Combinatoria [SC01122975]

and

Methods and Models for Combinatorial Optimization [INP5070470, SCP7079402]

A.A 2019/2020

Exams during COVID-19 emergency

The examination method for next exams (June to September, at the moment) remains the same as usual (see Course information, page 3), with the only difference that the oral examination will take place via Zoom (or similar).

Please, reserve as soon as possible via Uniweb (exam's list will expire about one week before the examination date), in order to let the teacher arrange and communicate further details to the students in the list.

Notice

  • Next exams:
      Tuesday September 15th, 9:00 am (deadline for exercise delivery: September 13th)
  • The course will be taught in English (il corso sarà erogato in inglese)
  • The course will start on Thursday, October 3rd (8:30 am, room 1BC50): during the first lesson, additional information on the course (content, exams etc.) will be discussed.
  • For further information, email the teacher.
  • Presentation of the course.

  • 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. Implementing an Integer Linear Programming model with the Cplex API or OPL: text. posted 17-Oct-2019
  2. Part II. Implementing an alternative solution method: text. posted 13-Dec-2019
  • 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 (unique for Parts I and II) in pdf format
    • the source code files (with related makefiles, if needed)
    • some (two or three!) small instances among the 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 about 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 on this webpage some days before the class itself: students are warmly invited to read them in advance.

  1. Course information posted 01-Oct-2019
  2. Introduction to the course update 03-Oct-2019
  3. Modeling by linear programming: slides update 18-Oct-2019
  4. Modeling by linear programming: text posted 03-Oct-2019
  5. Linear Programming and the simplex method: an overview posted 22-Oct-2019
  6. Review of duality in linear programming posted 05-Nov-2019
  7. Column generation methods posted 05-Nov-2019
  8. Solution Methods for Integer Linear Programming posted 13-Nov-2019
  9. The assignment problem and totally unimodular matrices posted 27-Nov-2019
  10. Exact methods for the Traveling Salesman Problem posted 27-Nov-2019
  11. Cover inequalities posted (4-Dec-2019)
  12. Meta-heuristics: lecture notes (part I, up to slide 20) update 04-Dec-2019, slides (complete) update 09-Jan-2020
  13. Papers on metaheuristics (optional reading, free link from the Department network): posted 19-Dec-2019

Labs

  1. Getting started posted 9-Oct-2019
  2. Introduction to OPL and the Cplex API posted 9-Oct-2019
  3. OPL sample models posted 9-Oct-2019 (OPL "Iron rods" solution posted 23-Oct-2019)
  4. Cplex API sample models (to be completed) posted 9-Oct-2019
    Model solution values to compare to yours posted 9-Oct-2019
  5. Complete implementation models (solutions to OPL and Cplex models) posted 31-Oct-2019
    The solution to the "Italian friend" excercise using variable maps is available here posted 31-Oct-2019
  6. Column generation based heuristic for the 1D-cutting stock problem posted 14-Nov-2019 Complete posted 18-Nov-2019
  7. Neighbourhood search for the symmetric TSP: source codes posted 19-Dec-2019