Advanced Algorithms for Optimization

Teacher(s)

Schaus Pierre;

Language

English
> French-friendly

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..

Learning outcomes

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
• 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

The presentation of the algorithms will be either proposed in the form of lectures, videos or reading and will be accompanied by practical work (assignments / micro-projects) requesting the implementation algorithms to solve a practical optimization problem and the writing of reports.

Evaluation methods

For the first session, the global grade for the course is solely based on the grades of the computing projects, submitted and evaluated during the semester.
The projects are not evaluated again for the second session and may not be resubmitted.
The grades for projects are kept as such representing 50% and the other 50% are evaluated with a written exam, or when appropriate, on a computer.
Projects are invididual. It means that any source code of a project estimated to be
- copied or inspired by the one of another student, or
- copied or inspired by a source code found on the internet or another source,
will result in a zero grade for the student at the projects and the exam
The same consequences will hold for a student that voluntarily shares his code or make available to other students.

Other information

Background: a good knowledge of data structures and algorithms (for instance obtained by having followed the course LINFO121) and a good knowledge of Java language

Online resources

https://moodleucl.uclouvain.be/course/view.php?id=8280

Faculty or entity

INFO