Section outline

  • Introduction

    Collapse all Expand all

    Lecture timetable

    Day
    		 
    Time
    		 
    Room
    		 
    Building
    		 
    Monday
    14.15-15.45
    		 
    I
    		 
    C1, Third floor
    		 
    Tuesday
    		 
    09.00-10.30
    		 
    I
    		 
    C1, Third floor
    		 
    Thursday
    		 
    11.15-12.45
    		 
    I
    		 
    C1, Third floor
    		 
    Friday
    		 
    11.15-12.45
    I
    		 
    C1, Third floor



    Textbooks
    Abbr.
    Title
    Author(s)
    Publisher
    Notes
    XP
    Applications of optimization with XPress - MP
    NW
    Integer and Combinatorial Optimization
    G. Nemhauser and L. Wolsey
    John Wiley and Sons
    Chapters 1 and 2
    IP
    Integer programming
    L. Wolsey
    John Wiley and Sons


    XPress resources 
    Software
    		 
    FICO Xpress Community License
    		 
    Exercises
    		 
    .mos and .dat files from XP
    		 
    Documentation
    		 
    XPress Mosel User Guide
    Optimizer



    Risultati e testi d'esame 
    Data
    		 
    Testo
    		 
    Soluzione 
    		 
    Voti
    		 
    2022.02.14
    		 
    T_220114
    		 
    S_220114 
    		 
    V_220114 
    		 
    2021.10.22
    		 
    T_211022 
    		 
    S_211022 
    		 
    V_211022 
    		 
    2021.09.17
    		 
    T_210917 
    		 
    S_210917 
    		 
    V_210917
    		 
    2021.07.29
    		 
    T_210729
    		 
    S_210729
    		 
    V_210729
    		 
    2021.06.22
    		 
    T_210422 
    		 
    S_210422 
    		 
    V_210422 
    		 
    2021.06.04
    		 
    T_210406
    		 
    S_210406
    		 
    V_210406






  • 1 March - 7 March 

    01 March 2021 - Course presentation - stream video and slides
    • Background
      • A few words on history of OR
      • Applications and operational contexts
      • Existing software
    • Some introductory definition and examples

    02 March 2021 - Modelling with binary variables (I) - stream video and slides
    • The Knapsack problem
    • The Assignment problem
    • The Matching problem
    • The Set-covering problem
    • The Set packing and set-partitioning problems

    04 March 2021 - Introduction to Xpress Mosel - stream video and model.mos, knapsack.mos file
    • Introduction
    • First example, the Chess problem and the knapsack problem. 

    05 March 2021 - Modelling with binary variables (II) - stream video and slides
    • The Facility location problem
      • Uncapacitated FLP
      • Capacitated FLP
    • The Network flow problem
    • The Fixed-Chaged network flow problem 
    • The Traveling salesman problem
      • Formulation with exponential number of constraints

  • 8 March - 14 March 

    8 March 2021 - Good and ideal formulations - stream video and slides
    • Definition of formulation
    • Definition of convex hull
    • Alternative formulations for the
      • Knapsack problem
      • Uncapacitated facility location problem

    11 March 2021 - Relaxations and bounds - stream video and slides
    • Definition of bounds
    • Definition of relaxation
    • Linear relaxations
    • Heuristics to find primal bounds (greedy algorithms)
      • Knapsack problem
      • Traveling salesman problem
      • Minimum spanning tree

    12 March 2021 - XPress Mosel - stream video and .mos file
    • Multiple problems in the same .mos file
    • How to define a 'procedure', 'set hidden' command, inline 'if'

  • 15 March - 21 March 

    15 March 2021 - Linear programming - stream video and slides
    • Definition of a LP problem
    • Possible outcomes of a LP problem
    • Fundamental theorem of LP
    • The simplex algorithm, key concepts and graphical solution. 

    16 March 2021 - Duality - stream video and slides
    • The dual problem
    • Primal-dual relationships
    • Weak and strong duality theorems
    • Complementary slackness conditions

    18 March 2021 - Duality and sensitivity analysis - stream video and slides
    • The dual problem as the lagrangian relaxation of the primal problem
    • Variation of a right hand side term and relationship with the dual problem
    • Variation of a cost coefficient in the objective function

    19 March 2021 - Using Excel to solve LP problems - stream video, .xlsx file and .mos file
    • Introduction to the Excel Solver for integer and continuous linear programming problems

  • 22 March - 27 March 

    22 April 2021 - Well solved problems - stream video and slides
    • Definition of total unimodularity (TU) and sufficient conditions for TU
    • Minimum cost network flow and its special cases
      • Shortest path problem
      • Maximum flow problem
      • Transportation problem
      • Assignment problem

    23 March 2020 - Branch and bound - stream video and slides
    • Branch and bound algorithm
      • Branching and stopping criteria
      • Lower and upper bounds
    • An example of the branch and bound algorithm for a two-dimension integer programming problem

    25 March 2021 - Branch and Bound (ii) - stream video and slides
    • An example of the branch and bound algorithm for a binary problem (knapsack problem)
      • Dantzig's upper bound
    • Node selection
    • Stopping criteria

    26 March 2021 -  XPress- MP (iii) - stream video

  • 29 March - 4 April 

    30 March 2021 - Pre-processing - stream video and slides
    • Pre-processing with continous variables
    • Pre-processing with binary variables

  • 5 April - 11 April 

    8 April 2021 - Valid inequalities - stream video and slides 
    • Definition of valid inequality and examples
    • Valid inequalities for LP problems
    • Valid inequalities for IP problems
    • Chvátal-Gomory procedure

    9 April 2021 - Linearisations and other modelling issues - stream video and slides
    • Problem linearisation 
      • with minimax objective function 
      • with absolute values in the objective function
      • with objective function expressed as a ratio
      • Logical relations (NOT, OR, AND, XOR) 
    • Formulation of the Bin Packing problem
    • Elimination of sub-tours for the TSP with a polynomial number of constraints

  • 12 April - 18 April 

    12 April 2021 - Local search and approximate algorithms - stream video and slides
    • Local search for the knapsack problem
    • Two-opt for the TSP
    • MST and Chirstofides algorithms

    13 April 2021 - XPressMP optimizer - stream video and .mos file + .dat file
    • XPress-MP Optimizer
    • Optimizer parameters
      • verbose, cutstrategy, nodeselection, presolve, miprelstop, maxtime, miplog

    15 April 2021 - XPressMP: Global entities - stream video and slides
    • Integer, partial integer, semi-continuous, semi-continuous integer, SOS1 and SOS2

    16 April 2021 - Multi-objective optimisation - stream video and slides 
    • Preferences and decisions
    • Pareto or non-dominated solutions
    • Objectives' linear combination
    • Constraints on objectives
    • Lexicographic order

  • 19 April - 25 April 

    19 April 2021 - Stochastic programming - stream video and slides
    • Introducing uncertainty
    • A deterministic model
    • Expected value solution
    • Scenario solution
    • Recourse model 
    • .mos file to solve slide 35
    20 April 2021 - Exercise - stream video

    22 April 2021 - Saving lives by efficient use of emergency medical response vehicles - Webinar link: https://mit.zoom.us/j/95032457938
    Speaker:  Karen Aardal, Delft University of Technology. Time: 17.00 CET
    In life-threatening situations each second counts. It is therefore of utmost importance that emergency medical response vehicles are used efficiently. This involves determining ambulance location sites, and the number of vehicles that should be stationed at these sites, as well as using dispatch policies that keep sufficient coverage even when a subset of vehicles are dispatched to calls. In this seminar we will review emergency medical response vehicle location models and dispatch algorithms with a focus on ambulances on wheels and helicopters. A brief extension to fire fighter services will also be made. The main body of the work presented here is an outcome of a large Dutch research project involving university researchers, representatives from various emergency regions of the Netherlands, and the National Institute for Public Health and the Environment in the Netherlands.

    23 April 2021  - Xpress: SOS1 & SOS2 examples - stream video and slides
    • Two modelling examples
    • Alternative formulations using SOS1 and SOS2 variable types.

  • 26 April - 2 May 

    26 April 2021  - Robust optimisation - stream video and slides
    • Representing uncertainty - scenarios
    • Interval and polyherdral representation
    • A robust solution
      • Absolute robustness
      • Absolute robustness with control parameter

    27 April 2021 - Phython for optimisation - stream video 1 and stream video 2
    • A very brief introduction to python

    29 April 2021 - Robust optimisation & Optimisation overview - stream video and slides (robust & overview)
    • Relative robustness
    • Optimisation overview
      • Objective function
      • Feasible region
      • Variables
      • Parameters
      • Solving algorithms

    30 April 2021 - Xpress: CALLBACK function - stream video and slides

  • 3 May - 9 May 

    3 May 2021 - Python for optimisation (ii)  - stream video
    • Python for Xpress

    4 May 2021 - Xpress: tutorial


    6 May 2021 - Python for optimisation (iii)  - stream video

    7 May 2021 - Python for optimisation (iv) - stream video


  • 10 May - 16 May 

     10 May 2021 - Research and thesis opportunities at the Operations Research Lab @ UNITS - stream video and slides