At the confluence of algorithmics and modeling
A million-dollar problem: finding a solution, is it as easy as verifying it? Written in the form 'P = NP?', this problem remains open for now. Thus, showing that a schedule satisfies the imposed constraints is easy, but finding one that works? If one must enumerate them one by one to test them, one risks spending more time than the age of the Sun, whereas we would like to have the solution in five minutes or twenty-four hours. We first seek to identify problems that we know how to solve quickly. For the others, we will use if possible intelligent tree searches, efficient exact algorithms of the combinatorial path-finding type, or approximate methods (metaheuristics).
All articles in this folder
Integer linear programming | Tangente
Solving optimization problems may require formulating them as mathematical models. Integer linear programming does this using only linear polynomials whose variables must take integer values.
Is P equal to NP?
The question has kept the scientific community on tenterhooks for more than forty years. It is one of the "Millennium Prize Problems," a list of seven major mathematical puzzles posed by the Clay Mathematics Institute in 2000. Here is a closer look.
Metaheuristics: approximate optimization | Tangente
NP-hard problems, combinatorial explosion, models with millions of variables and exponentially many inequalities… What can we do when no optimization method works? Which method should we use when we want to solve a problem quickly?
Combinatorial paths: shortest paths | Tangente
When we choose our route as we go, we must decide between several paths, just as in a maze. The same question arises at every new junction, creating a combinatorial explosion in the number of possible routes. How can we circumvent this explosion?
Tree search
Optimizing how a telescope is used—and deciding which part of the sky to observe—is crucial. This challenge can be reduced to a coloring problem, but finding a solution requires more trials than even a modern computer has time to test exhaustively.