A CLP Language Handling Disjunctions of Linear Constraints
Abstract
Many applications rely heavily on the efficient solving of problems modeled with disjunctions of linear constraints. CLP languages allow an easy expression of such problems. However, their solving strategy stumbles against the combinatorial aspect of the problems: all the possible alternatives are successively explored.
A new CLP language is proposed, whose solver deals directly with disjunctions of linear constraints. For this purpose, a range of tech- niques is presented:
The geometric aspect of the problem is covered by using two com- plementary methods: Firstly, each disjunction can be replaced by a tight linear relaxation. This allows an early detection of unsolvability. Secondly, a bound propagation algorithm taking the structure of the problem into account is used, which allows further reduction and the detection of new causes of unsolvability.
The logical structure is also used. Bound propagation allows to infer the values of some decision variables early. Finally, the algorithm learns more about the logical structure of the problem thanks to an explanation of the encountered failures.
All this adds up to a CLP language well suited to the expression and the solving of the class of combinatorial problems in which the geometrical aspect is of prime importance.
Keywords: Constraint Logic Programming. Combinatorial problems.
A new CLP language is proposed, whose solver deals directly with disjunctions of linear constraints. For this purpose, a range of tech- niques is presented:
The geometric aspect of the problem is covered by using two com- plementary methods: Firstly, each disjunction can be replaced by a tight linear relaxation. This allows an early detection of unsolvability. Secondly, a bound propagation algorithm taking the structure of the problem into account is used, which allows further reduction and the detection of new causes of unsolvability.
The logical structure is also used. Bound propagation allows to infer the values of some decision variables early. Finally, the algorithm learns more about the logical structure of the problem thanks to an explanation of the encountered failures.
All this adds up to a CLP language well suited to the expression and the solving of the class of combinatorial problems in which the geometrical aspect is of prime importance.
Keywords: Constraint Logic Programming. Combinatorial problems.
