When to use Set Variables and Constraints...

The subset-sum example shows that the general principle of solving problems using set domain constraints works just like finite domains:

• Stating the variables and assigning an initial set domain to them.
• Constraining the variables. In the above example the constraint is just a built-in constraint but usually one needs to define additional constraints.
• Labeling the variables, i.e., assigning values to them. In the set case it would not be very efficient to select one value for a set variable for the size of a set domain is exponential in the upper bound cardinality and thus the number of backtracks could be exponential too. A second reason is that no specific information can be deduced from a failure (backtrack) whereas if (like in the refine predicate) we add one by one elements to the set till it becomes ground or some failure is detected, we benefit much more from the constraint propagation mechanism. Every domain modification activates some constraints associated to the variable (depending on the modified bound) and modifications are propagated to the other variables involved in the constraints. The search space is then reduced and either the goal succeeds or it fails. In case of failure the labeling procedure backtracks and removes the last element added to the set variable and tries to instanciate the variable by adding another element to its lower bound. In the subset-sum example the labeling only concerns a single set, but it can deal with a list of set terms like in the steiner example. Although the choice for the element to be added can be done without specific criterion like in the steiner example, some user defined heuristics can be embedded in the labeling procedure like in the subset-sum example. Then the user needs to define his own refine procedure.

Set constraints propose a new modelling of already solved problems or allows (like for the subset-sum example) to solve new problems using CLP. Therefore, one should take into account the problem semantics in order to define the initial search space as small as possible and to make a powerful use of set constraints. The objective of this library is to bring CLP to bear on graph-theorical problems like the steiner problem which is a hypergraph computation problem, thus leading to a better specification and solving of problems as, packing and partitioning which find their application in many real life problems. A partial list includes: railroad crew scheduling, truck deliveries, airline crew scheduling, tanker-routing, information retrieval,time tabling problems, location problems, assembly line balancing, political districting,etc.

Sets seem adequate for problems where one is not interested in each element as a specific individual but in a collection of elements where no specific distinction is made and thus where symmetries among the element values need to be avoided (eg. steiner problem). They are also useful when heterogeneous constraints are involved in the problem like weight constraints combined with some disjointness constraints.