Combinatorial problem solving in constraint logic programming with cooperating solvers
Abstract
Combinatorial problems are widespread enough to motivate the de- velopment of always more flexible and powerful tools. Constraint Logic Programming is a framework which is suitable to the solving of many combinatorial problems because it allows to combine easily heuristic methods with implicit enumeration.
However, when constraints of various types are needed to better control the search, the standard CLP architecture is not optimal be- cause cooperation between solvers is only done by value propagation. In particular, an integer solver based on domain reduction should be able to exchange information with a real linear solver through variable bounds.
This leads to new requirements for constraint solvers. The design of these solvers in the CLAIRE language is presented and justified. In particular, the real linear solver, based on a revised simplex, is shown to overcome the already proposed implementations both in efficiency and numerical precision. It is also explained how an inter-solver bound propagation can efficiently be implemented.
However, when constraints of various types are needed to better control the search, the standard CLP architecture is not optimal be- cause cooperation between solvers is only done by value propagation. In particular, an integer solver based on domain reduction should be able to exchange information with a real linear solver through variable bounds.
This leads to new requirements for constraint solvers. The design of these solvers in the CLAIRE language is presented and justified. In particular, the real linear solver, based on a revised simplex, is shown to overcome the already proposed implementations both in efficiency and numerical precision. It is also explained how an inter-solver bound propagation can efficiently be implemented.
