Local Search and Constraint Programming: LS and CP illustrated on a transportation problem

Real-world combinatorial optimization problems 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 appliedto solve real-world problems, whereas incomplete algorithms, and among them Local Search and Metaheuristic methods, have proved to obtain very good results in practice. Moreover, real-world applications typically lead to frequent update/addition of constraints, thus the algorithmic approach requires flexibility, and this flexibility can be guaranteed by Constraint Programming. In this chapter we review hybrid algorithms combining Local Search and Constraint Programming Using a didactic transportation problem to illustrate the techniques. © Kluwer Academic Publishers 2004.