Advanced Algorithms for Optimization

linfo2266  2025-2026  Louvain-la-Neuve

Advanced Algorithms for Optimization
5.00 credits
30.0 h + 15.0 h
Q1
> Schedule
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 :

With regard to the AA reference framework of the “Master in Civil Engineering in Computer Science” program, this course contributes to the development, acquisition, and assessment of the following learning outcomes:
  • AA1.1: When faced with a computing problem, the student identifies the applicable concepts, algorithms, and data structures to solve it; they leverage these to break down the problem into subproblems and develop computational methods to solve them.
  • AA1.3: When confronted with results obtained through reasoning and the implementation of tools and concepts, the student takes the necessary step back to verify their relevance in terms of functionality and quality of the intended solution. In this context, they will develop relevant tests and verifications to ensure the quality of the developed solution.
  • AA2.4: During the implementation phase of the solution, the student demonstrates mastery of the principles, techniques, and development tools at their disposal. They create a software prototype to verify that it meets client expectations. They set up a testing environment and a suite of tests to ensure the developed solution meets the functional requirements. By applying validation and verification techniques, they identify, locate, and fix bugs.
  • AA5.4: The student is proficient in using reference books or manuals related to programming languages or software, both in English and French. They understand technical presentations given in English.
  • AA5.5: During the development of a software application, the student ensures traceability and documentation in a concise and precise manner, covering specifications, software and data structures, and operational procedures. They also apply this approach when writing a summary report explaining and justifying design and technology choices in project development.
With regard to the AA reference framework of the “Master [120] in Computer Science” program, this course contributes to the development, acquisition, and assessment of the following learning outcomes:
  • AA1: Demonstrate mastery of a solid body of knowledge in computer science, enabling the resolution of problems within the discipline.
  • AA2.1: Analyze the problem to be solved or the functional requirements to be met and formulate the corresponding specifications.
  • AA2.2: Model the problem and design one or more original technical solutions that meet these specifications.
  • AA2.4: Implement and test the selected solution.
  • AA3.2: Propose a model and/or an experimental framework to simulate and test hypotheses related to the problem in all its complexity.
  • AA6.5: Self-evaluate and independently develop the knowledge necessary to remain competent in the field.
Students who successfully complete this course will be able to:
  • explain algorithms for solving discrete optimization problems by describing them precisely, specifying the problems they solve, and discussing their advantages, disadvantages, and limitations (e.g., computation time, accuracy, scalability issues);
  • identify the appropriate algorithms for a given discrete optimization problem and make a reasoned selection among them;
  • implement algorithms for solving discrete optimization problems;
  • evaluate and compare different optimization algorithms.
 
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


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

Title of the programme
Sigle
Credits
Prerequisites
Learning outcomes
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