Although they are rarely identified by industry, combinatorial optimization
problems are extremely frequent in business life. For example, given
a fleet of vehicles and a number of journeys to make, what is the
optimal way to divide the journeys among the vehicles respecting legal
speed limits and fixed delivery times? How can one construct a school
timetable to satisfy the constraints of both teachers and pupils?
Philippe Baptiste, a researcher from the CNRS "Heuristics and
Diagnostics of Complex Systems"* ("Heuristique et diagnostic
des systèmes complexes") research unit has addressed these
problems using a complementary approach combining Operations Research
and Artificial Intelligence.
Complexity
theory has enabled the definition of a certain class of "hard"
problems, for which no method exists to solve them efficiently. Unfortunately,
it turns out that most problems in the real world are "hard."
An arsenal of mathematical techniques are used to find solutions to
these problems in a reasonable time frame. Exact methods aim to find
the best of all solutions, whereas approximate methods such as simulated
annealing or genetic algorithms furnish an acceptable solution with
no guarantee that it is the best possible solution.
Because
of the enormous complexity of combinatorial problems, exact methods
are often limited to relatively small problems. However, an efficient
method of exact resolution can be integrated into a more general approximate
method. The originality of the approach used by the Heuristics and
Diagnostics of Complex Systems laboratory is the combination of classical
techniques with extremely flexible tools from artificial intelligence.
This allows the creation of optimization tools that are both powerful
and easy to use by non-specialists. Practical management problems
have been successfully solved for several industry partners.
*
CNRS-University of Technology of Compiègne
