29. Propagators for set constraints¶
This chapter shows how to implement propagators for constraints over set variables. We assume that you have worked through the chapters on implementing integer propagators, as most of the techniques readily carry over and are not explained again here.
We also assume a basic knowledge of propagation for set constraints. To read more about this topic, please refer to [18, 60].
Overview. A simple example demonstrates a propagator that implements set interesection. Set views and their related concepts are summarized in Modification events, propagation conditions, views, and advisors.
29.1. A simple example¶
#include <gecode/set.hh>
using namespace Gecode;
class Intersection
: public TernaryPropagator<Set::SetView,Set::PC_SET_ANY> {
public:
Intersection(Home home, Set::SetView x0, Set::SetView x1,
Set::SetView x2)
: TernaryPropagator<Set::SetView,Set::PC_SET_ANY>(home,
x0,x1,x2) {}
...
virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
using namespace Iter::Ranges; using namespace Set;
bool assigned = x0.assigned() && x1.assigned() && x2.assigned();
// [intersection:rule 1]
// [intersection:rule 2]
// [intersection:rule 3]
// [intersection:rule 4]
// [intersection:rule 5]
// [intersection:rule 6]
// [intersection:cardinality]
return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
}
};
void intersection(Home home, SetVar x0, SetVar x1, SetVar x2) {
GECODE_POST;
GECODE_ES_FAIL(Intersection::post(home,x0,x1,x2));
}
Download: intersection.cpp
Program 29.1 shows a propagator for the ternary intersection constraint \(\mathtt{x}_0\cap\mathtt{x}_1=\mathtt{x}_2\) for three set variables \(\mathtt{x}_0\), \(\mathtt{x}_1\), and \(\mathtt{x}_2\).
As you can see, propagators for set constraints follow exactly the same structure as propagators for integer or Boolean constraints. The same propagator patterns can be used (see Using propagator patterns). The appropriate views and propagation conditions are defined in the namespace Gecode::Set.
In order to understand the propagate() function, we have to look at how set variable domains are represented.
The set bounds approximation. We already saw in Set variables and constraints that set variable domains are represented as intervals in order to avoid an exponential representation. For example, recall that
cannot be captured exactly by an interval, but is instead approximated by the smallest enclosing interval \(\left[\{\}\;..\;\{1,2,3\}\right]\).
Set propagators therefore access and modify the interval bounds. Naturally, set-valued domain operations similar to the ones for integer variables (see Domain propagation) play an important role for set propagators.
For each set view, Set::GlbRanges provides a range iterator for its lower bound, and Set::LubRanges iterates the upper bound. The main iterator-based modification operations on set views are includeI (adding a set to the lower bound), excludeI (removing a set from the upper bound), and intersectI (intersecting the upper bound with a set).
Filtering rules. Coming back to the example propagator for ternary intersection, we have to devise filtering rules that express the constraint in terms of the interval bounds. In the following, we write \(\underline{x}\) and \(\overline{x}\) for the lower bound resp. upper bound of a view \(x\). Then, ternary intersection can be propagated with the following rules and implemented with set domain operations:
\(\underline{\mathtt{x}_0}\cap\underline{\mathtt{x}_1}\subseteq\mathtt{x}_2\)
{
GlbRanges<SetView> x0lb(x0), x1lb(x1);
Inter<GlbRanges<SetView>, GlbRanges<SetView> > i(x0lb,x1lb);
GECODE_ME_CHECK(x2.includeI(home,i));
}
\(\overline{\mathtt{x}_0}\cap\overline{\mathtt{x}_1}\supseteq\mathtt{x}_2\)
{
LubRanges<SetView> x0ub(x0), x1ub(x1);
Inter<LubRanges<SetView>, LubRanges<SetView> > i1(x0ub,x1ub);
GECODE_ME_CHECK(x2.intersectI(home,i1));
}
\(\underline{\mathtt{x}_2}\subseteq\mathtt{x}_0\)
{
GlbRanges<SetView> x2lb(x2);
GECODE_ME_CHECK(x0.includeI(home,x2lb));
}
\(\underline{\mathtt{x}_2}\subseteq\mathtt{x}_1\)
{
GlbRanges<SetView> x2lb(x2);
GECODE_ME_CHECK(x1.includeI(home,x2lb));
}
\(\underline{\mathtt{x}_0}\setminus\overline{\mathtt{x}_2}\not\subseteq\mathtt{x}_1\)
{
GlbRanges<SetView> x0lb(x0); LubRanges<SetView> x2ub(x2);
Diff<GlbRanges<SetView>, LubRanges<SetView> > diff(x0lb, x2ub);
GECODE_ME_CHECK(x1.excludeI(home,diff));
}
\(\underline{\mathtt{x}_1}\setminus\overline{\mathtt{x}_2}\not\subseteq\mathtt{x}_0\)
{
GlbRanges<SetView> x1lb(x1); LubRanges<SetView> x2ub(x2);
Diff<GlbRanges<SetView>, LubRanges<SetView> > diff(x1lb, x2ub);
GECODE_ME_CHECK(x0.excludeI(home,diff));
}
integer-valued bounds operations |
|
|
return minimum/maximum of lower bound |
|
return minimum/maximum of upper bound |
|
return size of lower/upper bound |
|
return number of elements in upper but not in lower bound |
|
test whether lower bound contains element |
|
test whether upper bound does not contain element |
|
add element (or range) to lower bound |
|
remove element (or range) from upper bound |
|
intersect upper bound with element or range |
set-valued bounds modifications |
|
|
add elements to lower bound |
|
remove elements from upper bound |
|
intersect upper bound with given set |
cardinality operations |
|
|
return/modify minimum cardinality |
|
return/modify maximum cardinality |
Figure 29.1 Set view operations¶
The first four rules should be self-explanatory. The last two rules state that anything that is in \(\mathtt{x}_0\) but not in \(\mathtt{x}_2\) cannot be in \(\mathtt{x}_1\) (and the same for \(\mathtt{x}_0\) and \(\mathtt{x}_1\) swapped). The full list of operations on set views appears in Figure 29.1.
Fixpoint. Note how the propagator determines which execution status to return. Before applying any of the filtering rules, it checks whether all of the variables are already assigned. If they are, then propagation will compute a fixpoint and the propagator can return that it is subsumed after applying the filtering rules. Otherwise, it has not necessarily computed a fixpoint (e.g. rule 6 may modify the upper bound of \(\mathtt{x}_0\), making it necessary to apply rule 2 again).
Cardinality. In addition to the interval bounds, set variables store cardinality bounds, that is, the minimum and maximum cardinality of the set variable. These bounds are stored and modified independently of the interval bounds, but of course modifications to these different bounds affect each other.
For example, consider a set variable with a domain represented by the interval \(\left[\{\}\;..\;\{1,2\}\right]\) and the cardinality \(\#\left[1\;..\;2\right]\). Adding \(1\) to the lower bound would result in the cardinality lower bound being increased to \(1\). Removing \(1\) from the upper bound would result in \(2\) being added to the lower bound to satisfy the minimum cardinality of \(1\).
Using cardinality information, propagation for some set constraints can be strengthened. For the ternary intersection example, we can for instance add the following filtering rules:
LubRanges<SetView> x0ub(x0), x1ub(x1);
Union<LubRanges<SetView>, LubRanges<SetView> > u_lub(x0ub,x1ub);
unsigned int s_lub = size(u_lub);
if (x0.cardMin() + x1.cardMin() > s_lub)
GECODE_ME_CHECK(x2.cardMin(home, x0.cardMin()+x1.cardMin()-s_lub));
GlbRanges<SetView> x0lb(x0), x1lb(x1);
Union<GlbRanges<SetView>, GlbRanges<SetView> > u_glb(x0lb,x1lb);
unsigned int s_glb = size(u_glb);
GECODE_ME_CHECK(x2.cardMax(home,x0.cardMax()+x1.cardMax()-s_glb));
GECODE_ME_CHECK(x0.cardMin(home,x2.cardMin()));
GECODE_ME_CHECK(x1.cardMin(home,x2.cardMin()));
When dealing with cardinality, it is important to handle overflow or signedness issues. In the above example, we have to check whether x0.cardMin()+x1.cardMin()>s, because otherwise the expression x0.cardMin()+x1.cardMin()-s may underflow (as we are dealing with unsigned integers here). This is not the case for the second cardinality rule. Here, we can be sure that the size of the union of the lower bounds is always greater than the sum of the maximum cardinalities.
29.2. Modification events, propagation conditions, views, and advisors¶
This section summarizes how these concepts are specialized for set variables and propagators.
Modification events and propagation conditions.
[p]
set modification events |
|
|
the view has not been changed |
|
the domain has become empty |
|
the view has been assigned to a single set |
|
the view has been assigned to a single set |
|
the upper bound has been changed |
|
the lower bound has been changed |
|
both bounds have been changed |
|
cardinality and upper bound have changed |
|
cardinality and lower bound have changed |
|
cardinality and both bounds have changed |
set propagation conditions |
|
|
schedule when the view is assigned |
|
schedule when the cardinality changes |
|
schedule when the cardinality or the upper bound changes |
|
schedule when the cardinality or the lower bound changes |
|
schedule at any change |
|
do not schedule |
Figure 29.2 Set modification events and propagation conditions¶
The modification events and propagation conditions for set propagators (see Figure 29.2) capture the parts of a set variable domain that can change.
One could imagine a richer set, for example distinguishing between lower and upper bound changes of the cardinality, or separating the cardinality changes from the interval bound changes. However, the number of propagation conditions has a direct influence on the size of a variable, see Costs and limits for modification events and propagation conditions.. Just like for integer views, this set of modification events and propagation conditions has been chosen as a compromise between expressiveness on the one hand, and keeping the set small on the other.
Set variable views. In addition to the basic Set::SetView class, there are five other set views: Set::ConstSetView, Set::EmptyView, Set::UniverseView, Set::SingletonView, and Set::ComplementView.
The first three are constant views. A SingletonView wraps an integer view \(x\) in the interface of a set view, so that it acts like the singleton set \(\{x\}\). A ComplementView is like Boolean negation, it provides the set complement with respect to the global Gecode universe for set variables (defined as \(\left[\mathtt{Set::Limits::min}\;..\;\mathtt{Set::Limits::max}\right]\), see Set::Limits).
Advisors for set propagators. Advisors for set constraints get informed about the domain modifications using a Set::SetDelta. The set delta provides only information about the minimum and maximum values that were added to the lower bound and/or removed from the upper bound.