Consider a digraph described by the collection. is equal to the number of circuits for covering in such a way that each vertex of belongs to one single circuit. can also be interpreted as the number of cycles of the permutation associated with the successor variables of the collection.
In this example we have the following 2 () cycles: and . Consequently, the constraint holds.
Items of are permutable.
The PhD thesis of Éric Bourreau [Bourreau99] mentions the following applications of extensions of the constraint:
The balanced Euler knight problem where one tries to cover a rectangular chessboard of size by knights that all have to visit between and distinct locations. For some values of , and there does not exist any solution to the previous problem. This is for instance the case when . Figure 5.89.1 depicts the graph associated with the chessboard as well as examples of balanced solutions with respectively 1, 2, 3, 4 and 5 knights.
Some pick-up delivery problems where a fleet of vehicles has to transport a set of orders. Each order is characterised by its initial location, its final destination and its weight. In addition one also has to take into account the capacity of the different vehicles.
Figure 5.89.1. Graph of potential moves of the chessboard and corresponding balanced tours
In the original constraint of CHIP the attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.
Given a complete digraph of vertices as well as an unrestricted number of circuits , the total number of solutions of the corresponding constraint corresponds to the sequence A000142 of the On -Line Encyclopedia of Integer Sequences [Sloane10]. Given a complete digraph of vertices as well as a fixed number of circuits between 1 and , the total number of solutions of the corresponding constraint corresponds to the so called Stirling number of first kind.
Since all variables have to take distinct values one can reuse the algorithms associated with the constraint. A second necessary condition is to have no more than strongly connected components. Pruning for enforcing this condition, as soon as we have strongly connected components, can be done by forcing all strong bridges to belong to the final solution, since otherwise we would have more than strongly connected components. Since all the vertices of a circuit belong to the same strongly connected component an arc going from one strongly connected component to another strongly connected component has to be removed.
- See also
specialisation: ( set to 1).
- Arc input(s)
- Arc generator
- Arc arity
- Arc constraint(s)
- Graph property(ies)
- Graph class
- Graph model
From the restrictions and from the arc constraint, we deduce that we have a bijection from the successor variables to the values of interval . With no explicit restrictions it would have been impossible to derive this property.
In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices. This is why the constraint considers objects that have two attributes:
One fixed attribute that is the identifier of the vertex,
One variable attribute that is the successor of the vertex.
The graph property 0 is used in order to avoid having vertices that both do not belong to a circuit and have at least one successor located on a circuit. This concretely means that all vertices of the final graph should belong to a circuit.
Parts (A) and (B) of Figure 5.89.2 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, we show the two connected components of the final graph. The constraint holds since all the vertices belong to a circuit (i.e., 0) and since 2.
Figure 5.89.2. Initial and final graph of the constraint