Advanced Algorithms for Optimization

lingi2266  2020-2021  Louvain-la-Neuve

Advanced Algorithms for Optimization
Due to the COVID-19 crisis, the information below is subject to change, in particular that concerning the teaching mode (presential, distance or in a comodal or hybrid format).
5 credits
30.0 h + 15.0 h
Q1

  This learning unit is not being organized during year 2020-2021.

Teacher(s)
Schaus Pierre;
Language
English
Main themes
  • tree research exploration
  • branch and bound
  • relaxation (Lagrangian) and calculation of terminals
  • local search
  • mathematical programming
  • constraint programming
  • graph algorithms
  • wide neighborhood research
  • dynamic programming
  • greedy algorithms and approximation algorithms
  • multi-criteria optimization
  • optimization without derivative
  • comparisons of algorithms
These methods will be applied to real problems like vehicle routing, scheduling and rostering confection, network design, scheduling and scheduling, etc..
Aims

At the end of this learning unit, the student is able to :

1
Given the learning outcomes of the "Master in Computer Science and Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
  • INFO1.1-3
  • INFO2.3-5
  • INFO5.3-5
  • INFO6.1, INFO6.4
Given the learning outcomes of the "Master [120] in Computer Science" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
  • SINF1.M4
  • SINF2.3-5
  • SINF5.3-5
  • SINF6.1, SINF6.4
Students completing this course successfully will be able to
  • explain the algorithms for solving discrete optimization problems by describing precisely specifying the problems they solve, indicating their advantages, disadvantages and limitations (computing time, accuracy, problems of scaling , etc.),
  • identify the algorithms that apply to a discrete optimization problem they are facing and make an arguedchoice among them ,
  • implement algorithms for solving discrete optimization problems.
 
Content
  • dynamic programming
  • branch and bound
  • linear programming
  • Lagrangian relaxation
  • column generation
  • local search
  • constraint programming and sat
  • graph algorithms: flows
  • comparisons of optimization algorithms
These methods will be applied to real problems like vehicle routing, scheduling and rostering confection, network design, scheduling and scheduling, etc..
Teaching methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

The presentation of the algorithms in the lecture will be accompanied by practical work (assignments / micro-projects) requesting the implementation of an algorithm to solve a practical optimization problem. The evaluation work will be partially automated on the basis of the quality of the solutions found by the algorithms.
Evaluation methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

Much of the evaluation is associated to pratical work (30% of points across three assignments). The remaining 70% will be assessed in a conventional manner with a written or oral examination. Projects can not be redone in the second session.
 
Other information
Background: 
  • LSINF1121
Online resources
https://moodleucl.uclouvain.be/course/view.php?id=9158
www.minicp.org
Faculty or entity
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Aims
Master [120] in Data Science : Statistic
DATS2M
5
Master [120] in Computer Science and Engineering
INFO2M
5
Master [120] in Computer Science
SINF2M
5
Master [120] in Data Science Engineering
DATE2M
5
Master [120] in Data Science: Information Technology
DATI2M
5