LS and CP illustrated on a transportation problem
Filippo Focacci, François Laburthe · 2004
Real-world combinatorial optimizationproblems have two main characteristics which make them difficult: they are usually large, and they are not pure, i.e., they involve a heterogeneous set of side constraints. Hence, in most cases, exact approaches cannot be applied to solve real-world problems, whereas incomplete algorithms, and among them Local Search and Metaheuristic methods, have provedto obtainvery good resultsin practice. Moreover, real-world applications typicallylead to frequent update/addition of constraints, thus the algorithmic ap proach requires flexibility, and this flexibility can be guaranteed by Constraint Programming. In this chapter we review hybrid algorithms combining Local Search and Con straintProgramm ing usinga didactictransportation problemto illustratethe tech niques.