Combinatorial Optimization at Work
Objectifs
Combinatorial optimizations aims at modeling and solving some real-world optimization problems.
In this course, we discuss real-world applications from two different fields:
- transport problems (based on the project VIPAfleet of the LaBEX ImobS3)
- frequency assignment problems in telecommunication (based on two projects with BOSCH telecom and Orange).
Plan du cours
For each of the presented applications, we undergo the so-called model-solution-cycle, that is, we
- discuss how to mathematically model the problems,
- develop different solution strategies, and
- analyze the quality of the obtained solutions.
In general, one has the choice between declarative programming and imperative programming.
It turns out that the presented
- transport problems can be modeled as flow problems and declarative programming is best suitable,
- frequency assignment problems can be modeled as coloring problems and both combinatorial algorithms and encoding as integer linear programs will be discussed.
Description des TP
no TP
Connaissances requises
How to model some real-world problems as optimization problems in graphs and how to solve them either by combinatorial algorithms or using integer linear programs