30. Propagators for float constraints¶
This chapter shows how to implement propagators for constraints over float 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.
Overview. A simple example demonstrates a propagator that implements a ternary linear constraint. Float views and their related concepts are summarized in Modification events, propagation conditions, views, and advisors.
30.1. A simple example¶
#include <gecode/float.hh>
using namespace Gecode;
class Linear
: public TernaryPropagator<Float::FloatView,Float::PC_FLOAT_BND> {
public:
Linear(Home home, Float::FloatView x0, Float::FloatView x1,
Float::FloatView x2)
: TernaryPropagator<Float::FloatView,Float::PC_FLOAT_BND>
(home,x0,x1,x2) {}
...
virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
using namespace Float;
// [linear:create rounding object]
// [linear:prune upper bounds]
// [linear:prune lower bounds]
return (x0.assigned() && x1.assigned()) ?
home.ES_SUBSUMED(*this) : ES_NOFIX;
}
};
void linear(Home home, FloatVar x0, FloatVar x1, FloatVar x2) {
GECODE_POST;
GECODE_ES_FAIL(Linear::post(home,x0,x1,x2));
}
Download: linear.cpp
Program 30.1 shows a propagator for the ternary linear constraint \(\mathtt{x}_0+\mathtt{x}_1+\mathtt{x}_2=0\) for three float variables \(\mathtt{x}_0\), \(\mathtt{x}_1\), and \(\mathtt{x}_2\).
As you can see, propagators for float 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::Float.
Operations on float views.
access operations |
|
|
return lower bound (a float number) |
|
return upper bound (a float number) |
|
return width of domain (a float number) |
|
whether view is assigned |
|
whether float number |
|
whether float value |
modification operations |
|
|
restrict values to be equal to |
|
restrict values to be less or equal than |
|
restrict values to be greater or equal than |
Figure 30.1 Most important float view operations¶
The most important operations on float views for programming propagators are summarized in Figure 30.1, the full information can be found in Float::FloatView. The lack of operations such as gr() (for greater), le() (for less), and nq() (for disequality) is due to the fact that domains are closed intervals, see Float values and numbers and Weak propagation for strict inequalities (<, >) and disequality (≠).
Creating a rounding object.
function |
meaning |
default |
|---|---|---|
|
l/u bound of \(\mathtt{x}+\mathtt{y}\) |
yes |
|
l/u bound of \(\mathtt{x} - \mathtt{y}\) |
yes |
|
l/u bound of \(\mathtt{x} \times \mathtt{y}\) |
yes |
|
l/u bound of \(\mathtt{x} / \mathtt{y}\) |
yes |
|
l/u bound of \(\sqrt{\mathtt{x}}\) |
yes |
|
next downward-rounded integer of \(\mathtt{x}\) |
yes |
|
next upward-rounded integer of \(\mathtt{x}\) |
yes |
|
l/u bound of \(\exp(\mathtt{x})\) |
|
|
l/u bound of \(\log(\mathtt{x})\) |
|
|
l/u bound of \(\sin(\mathtt{x})\) |
|
|
l/u bound of \(\cos(\mathtt{x})\) |
|
|
l/u bound of \(\tan(\mathtt{x})\) |
|
|
l/u bound of \(\arcsin(\mathtt{x})\) |
|
|
l/u bound of \(\arccos(\mathtt{x})\) |
|
|
l/u bound of \(\arctan(\mathtt{x})\) |
|
|
l/u bound of \(\sinh(\mathtt{x})\) |
|
|
l/u bound of \(\cosh(\mathtt{x})\) |
|
|
l/u bound of \(\tanh(\mathtt{x})\) |
|
|
l/u bound of \(\operatorname{arcsinh}(\mathtt{x})\) |
|
|
l/u bound of \(\operatorname{arccosh}(\mathtt{x})\) |
|
|
l/u bound of \(\operatorname{arctanh}(\mathtt{x})\) |
Figure 30.2 Rounding operations on float numbers (x and y are float numbers)¶
The propagation rules of the Linear propagator will require that it can be controlled whether to round downwards or upwards in a floating point operation on a float number. Access to operations with explicit rounding control is provided by an object of class Float::Rounding. The creation of an object of this class initializes the underlying floating point unit such that it performs exact rounding in the required direction. Note, that explicit rounding is only required if rounding provided by operations on float values is not sufficient.
Figure 30.2 lists the supported operations with explicit rounding, where the _down() variants round downwards and the _up() variants round upwards. The functions marked as default are always supported, the others are only supported if Gecode has been built accordingly, see Transcendental and trigonometric functions and constraints.
Hence, the first thing that the propagate() function of the Linear propagator does is to create a rounding object r as follows:
Rounding r;
Pruning lower and upper bounds. The propagation rules for Linear are quite straightforward. As \(\mathtt{x}_0+\mathtt{x}_1+\mathtt{x}_2=0\) we can isolate \(\mathtt{x}_0\) (\(\mathtt{x}_1\) and \(\mathtt{x}_2\) are of course analogous):
The upper bound of \(\mathtt{x}_0\) can be constrained following:
and, accordingly, the lower bound of \(\mathtt{x}_0\) can be constrained following:
The equations can be translated directly into update operations, where \(\min\) corresponds to rounding downwards:
GECODE_ME_CHECK(x0.lq(home,-r.add_down(x1.min(),x2.min())));
GECODE_ME_CHECK(x1.lq(home,-r.add_down(x0.min(),x2.min())));
GECODE_ME_CHECK(x2.lq(home,-r.add_down(x0.min(),x1.min())));
and \(\max\) corresponds to rounding upwards:
GECODE_ME_CHECK(x0.gq(home,-r.add_up(x1.max(),x2.max())));
GECODE_ME_CHECK(x1.gq(home,-r.add_up(x0.max(),x2.max())));
GECODE_ME_CHECK(x2.gq(home,-r.add_up(x0.max(),x1.max())));
30.2. Modification events, propagation conditions, views, and advisors¶
This section summarizes how these concepts are specialized for float variables and propagators.
Modification events and propagation conditions.
float modification events |
|
|
the view has not been changed |
|
the domain has become empty |
|
the view has been assigned |
|
the bounds have changed (the domain has changed) |
float propagation conditions |
|
|
schedule when the view is assigned |
|
schedule when the domain changes |
|
do not schedule |
Figure 30.3 Float modification events and propagation conditions¶
The modification events and propagation conditions for float propagators (see Figure 30.3) capture how the variable domain of a float view can change.
Float variable views. In addition to the basic Float::FloatView class, there are two other float views: Float::MinusView, and Float::ScaleView. The two latter views are defined similarly to minus view for integers (see Minus views) and scale views for integers (see Constant and scale views).
Advisors for float propagators. Advisors for float constraints get informed about the domain modifications using a float delta of class Float::FloatDelta.
Float deltas are also represented by a minimum and maximum float number and hence also constitute a closed interval (like float values and float variables). That means that a float delta cannot describe exactly which values have been removed. For example, assume that x is a float view and that the domain of x is \(\left[-1.0\;..\;1.0\right]\). Then, executing
GECODE_ME_CHECK(x.lq(home,0.0));
will generate a float delta d such that x.min(d) returns 0.0 and x.max(d) returns 1.0 even though the domain of x is now \(\left[-1.0\;..\;0.0\right]\) and still includes \(0.0\).