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

This course introduces a range of techniques for exact and approximate solutions to combinatorial optimization problems. Among the techniques:

• 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

January:

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.

August:
For the second session, previously submitted projects will not be re-evaluated and cannot be resubmitted. Instead, students will be assigned a new individual programming project after the June session. This project will require a written report, and, if deemed necessary by the instructor, an interview about the project may also be conducted also to verify that all theoretical concepts are well understood.
Use of Generative AI in Course Assignments (# Source: Written with thehelp ChatGPT and Prof. Schaus & Dupont for prompting)
Projects are invididual.
Neverthess, In this course, we recognize the evolving nature of technology and the potential benefits of using generative AI tools in the programming process. However, academic honesty and originality remain paramount. To that end:

• Generative AI Usage: Students are permitted to use generative AI tools to assist with their assignments. Such tools can provide inspiration, suggest coding approaches, or help troubleshoot issues.
• Original Work: While AI can be a tool, it should not be the sole author of your assignment. Your submission should be primarily your own work. Directly copying and pasting solutions from AI outputs without understanding or modification is discouraged. Similarly, collaborating with fellow students is a valuable part of the learning process, but directly copying another student's work is considered plagiarism.
• Source Indication: Whenever you use generative AI to assist in your assignment, you are required to indicate so by providing a brief comment in your code on how the AI was used. For example:
  python
  
  
  
  # Used AI to suggest optimization for this loop.

           for i in range(10): ...
 
Failure to adhere to these guidelines may result in a reduction of marks or other academic penalties.
The same consequences will hold for a student that voluntarily shares his code or make available to other students (this includes sharing your code on a public or private repository).
If deemed necessary by the instructor, an interview about the projects may also be conducted.

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://moodle.uclouvain.be/course/view.php?id=1474

Faculty or entity

INFO