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
• A* et ses variantes pour l'optimisation
• 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. The project grade will count for 10 points in the second session, and a new project will be proposed, also worth 10 points, to improve the grade. This new project will be an individual programming project. It will require a written report, and if the professor deems it necessary, an interview about the project may also be arranged to ensure all theoretical concepts are well understood.
Bonus:

An optimization contest will be offered during the semester. Depending on the student’s ranking, they can earn 0, 1, 2, 3, 4, or 5 points. A student who earns X points will have the final grade calculated as follows: (score_out_of_20 / 20 * (20 - X) + X). A score of zero in the contest will result in no loss of points in the final grade, but a score of 5 can help boost it. For example, if you get 12/20 on the project and 5 points in the contest, your final grade will be 12/20 * 15 + 5 = 14/20.
Use of Generative AI in Course Assignments (# Source: Written with the help ChatGPT and Prof. Schaus & Dupont for prompting)
Projects are invididual (not code exchange is permitted).
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