6. Float variables and constraints

This chapter gives an overview over float variables and float constraints in Gecode. Just like Integer and Boolean variables and constraints does for integer and Boolean variables, this chapter serves as a starting point for using float variables. For the reference documentation, please consult Using float variables and constraints.

Overview. Float values and numbers explains float values whereas Float variables explains float variables. The sections Constraint overview and Synchronized execution provide an overview of the constraints that are available for float variables in Gecode.

Important

Do not forget to add

#include <gecode/float.hh>

to your program when you want to use float variables. Note that the same conventions hold as in Integer and Boolean variables and constraints.

6.1. Float values and numbers

A floating point value (short, float value, see FloatVal) is represented as a closed interval of two floating point numbers (short, float number, see Float variables). That is, a float value is a closed interval \(\left[a..b\right]\) which includes all real numbers \(n\in\RR\) such that \(a\leq n\) and \(n\leq b\). The float number type FloatNum is defined as double.

The reason why a float value is not represented by a single floating point number is that real numbers cannot be represented exactly and that operations on floating point numbers perform rounding. All operations (see below) on float values try to be as accurate as possible (so the interval \(\left[a..b\right]\) for a float value is as small as possible) while being correct (no possible real number is ever excluded due to rounding). The classical reference on interval arithmetic is [38], for more information see also the Wikipedia article on interval arithmetic.

A float value x represented by the interval \(\left[a..b\right]\) provides many member functions such as min() (returning \(a\)) and max() (returning \(b\)), see FloatVal. The float value x is called tight if \(a\) equals \(b\) or if \(b\) is the smallest representable float number larger than \(a\). If x is tight, x.tight() returns true.

A float value can be initialized from a single float number such as in

FloatVal x(1.0);

or from two float numbers such as in

FloatVal x(0.9999,1.0001);

Float numbers (and other numbers) are automatically cast to float values if needed, for example in

FloatVal x=1.0;

or

FloatVal x=1;

Predefined float values. The static member functions pi_half(), pi(), and pi_twice() of FloatVal return float values for \(\frac{\pi}{2}\), \(\pi\), and \(2\pi\) respectively.

Arithmetic operators. For float values, the standard arithmetic operators +, -, *, and / and their assignment variants +=, -=, *=, and /= are defined with the obvious meaning.

Comparison operators. The usual float value comparisons ==, !=, <=, <, >, and >= are provided with entailment semantics (or subsumption semantics).

For example, the comparison

x < y

returns true if and only if x.max()<y.min() returns true. That means, x<y returns false if either x is larger or equal than y or it cannot yet be decided: both x and y still represent values which are both smaller and greater or equal.

Functions on float values.

function

meaning

default

max(x,y)

maximum \(\max(\mathtt{x},\mathtt{y})\)

yes

min(x,y)

minimum \(\max(\mathtt{x},\mathtt{y})\)

yes

abs(x)

absolute value \(|\mathtt{x}|\)

yes

sqrt(x)

square root \(\sqrt{x}\)

yes

sqr(x)

square \(\mathtt{x}^2\)

yes

pow(x,n)

\(\mathtt{n}\)-th power \(\mathtt{x}^{\mathtt{n}}\)

yes

nroot(x,n)

\(\mathtt{n}\)-th root \(\sqrt[n]{x}\)

yes

fmod(x,y)

remainder of \(\mathtt{x}/\mathtt{y}\)

exp(x)

exponential \(\exp(\mathtt{x})\)

log(x)

natural logarithm \(\log(\mathtt{x})\)

sin(x)

sine \(\sin(\mathtt{x})\)

cos(x)

cosine \(\cos(\mathtt{x})\)

tan(x)

tangent \(\tan(\mathtt{x})\)

asin(x)

arcsine \(\arcsin(\mathtt{x})\)

acos(x)

arccosine \(\arccos(\mathtt{x})\)

atan(x)

arctangent \(\arctan(\mathtt{x})\)

sinh(x)

hyperbolic sine \(\sinh(\mathtt{x})\)

cosh(x)

hyperbolic cosine \(\cosh(\mathtt{x})\)

tanh(x)

hyperbolic tangent \(\tanh(\mathtt{x})\)

asinh(x)

hyperbolic arcsine \(\arcsinh(\mathtt{x})\)

acosh(x)

hyperbolic arccosine \(\arccosh(\mathtt{x})\)

atanh(x)

hyperbolic arctangent \(\arctanh(\mathtt{x})\)

Figure 6.1 Functions on float values (x and y are float values; n is a non-negative integer)

Figure 6.1 lists the available functions on float values. The functions marked as default are always supported, the others only if Gecode has been built accordingly, see Transcendental and trigonometric functions and constraints.

6.2. Float variables

Float variables in Gecode model sets of real numbers and are instances of the class FloatVar.

Representing float domains as intervals. The domain of a float variable is represented exactly as a float value: a closed interval \(\left[a..b\right]\) which represents all real numbers \(n\in\RR\) such that \(a\leq n\) and \(n\leq b\). A float variable is assigned if the interval \(\left[a..b\right]\) is tight (see Float values and numbers). [1]

Creating a float variable. New float variables are created using a constructor. A new float variable x is created by

FloatVar x(home, -1.0, 1.0);

This declares a variable x of type FloatVar in the space home, creates a new float variable implementation with domain \(\left[-1.0..1.0\right]\), and makes x refer to the newly created float variable implementation.

You find the full interface in the reference documentation of the class FloatVar. An attempt to create a float variable with an empty domain throws an exception of type Float::VariableEmptyDomain.

As for integer variables, the default and copy constructors do not create new variable implementations. Instead, the variable does not refer to any variable implementation (default constructor) or to the same variable implementation (copy constructor). For example in

FloatVar x(home, -1.0, 1.0);
FloatVar y(x);
FloatVar z;
z=y;

the variables x, y, and z all refer to the same float variable implementation.

Limits. Float numbers range from \(\mathtt{Float::Limits::min}\) to \(\mathtt{Float::Limits::max}\) which also define the numbers that can represent float values and float variables. The limits are defined in the namespace Float::Limits.

Variable access functions. You can access the current domain of a float variable x using member functions such as x.min() and x.max(). Furthermore, you can print a float variable’s domain using the standard output operator <<.

Updating variables. Float variables behave exactly like integer variables during cloning of a space. A float variable is updated by

x.update(home, y);

where y is the variable from which x is to be updated. While home is the space x belongs to, y belongs to the space which is being cloned.

Variable and argument arrays. Float variable arrays can be allocated using the class FloatVarArray. The constructors of this class take the same arguments as the float variable constructors, preceded by the size of the array. For example,

FloatVarArray x(home, 4, -1.0, 1.2);

creates an array of four float variables, each with domain \(\left[-1.0..1.2\right]\).

To pass temporary data structures as arguments, you can use the FloatVarArgs class. Some float constraints are defined in terms of arrays of float values. These can be passed using the FloatValArgs class. Float variable and value argument arrays support the same operations introduced in Argument arrays but FloatValArgs do not support the initialization with a variable number of float values.

6.3. Constraint overview

This section introduces the different groups of constraints over float variables available in Gecode. The section serves only as an overview. For the details and the full list of available post functions, the section refers to the relevant reference documentation.

Reified constraints. Some float constraints (relation constraints, see Simple relation constraints, and linear constraints, see Linear constraints) also exist as a reified variant. If a reified version does exist, the reification information combining the Boolean control variable and an optional reification mode is passed as the last non-optional argument, see Half reification.

6.3.1. Domain constraints

Domain constraints constrain float variables and variable arrays to values from a given domain. For example, by

dom(home, x, -2.0, 12.0);

the values of the variable x (or of all variables in a variable array x) are constrained to be between the float numbers \(-2.0\) and \(12.0\). Domain constraints also take float values as argument.

The domain of a float variable x can be constrained according to the domain of another float variable d by

dom(home, x, d);

Here, x and d can also be arrays of float variables.

Domain constraints for a single variable also support reification.

6.3.2. Simple relation constraints

FRT_EQ

equality (\(=\))

FRT_NQ

disequality (\(\neq\))

FRT_LE

strictly less inequality (\(<\))

FRT_LQ

less or equal inequality (\(\leq\))

FRT_GR

strictly greater inequality (\(>\))

FRT_GQ

greater or equal inequality (\(\geq\))

Figure 6.2 Float relation types

Simple relation constraints over float variables enforce relations between float variables and between float variables and float values. The relation depends on a float relation type FloatRelType (see Simple relation constraints over float variables). Figure 6.2 lists the available float relation types and their meaning.

Binary relation constraints. Assume that x and y are float variables. Then

rel(home, x, FRT_LE, y);

constrains x to be strictly less than y. Similarly, by

rel(home, x, FRT_LQ, 4.0);

x is constrained to be less than 4.0. Both variants of rel also support reification.

Constraints between variable arrays and a single variable. If x is a float variable array and y is an float variable, then

rel(home, x, FRT_LQ, y);

constrains all variables in x to be less than or equal to y. Likewise,

rel(home, x, FRT_GR, 7.0);

constrains all variables in x to be larger than 7.0.

If-then-else constraint. An if-then-else constraint can be posted by

ite(home, b, x, y, z);

where b is a Boolean variable and x, y, and z are float variables. In case b is one, then \(\mathtt{x}=\mathtt{z}\) must hold, otherwise \(\mathtt{y}=\mathtt{z}\) must hold.

6.3.3. Arithmetic constraints

post function

constraint posted

default

min(home, x, y, z);

\(\min(\mathtt x, \mathtt y)=\mathtt z\)

yes

max(home, x, y, z);

\(\max(\mathtt x, \mathtt y)=\mathtt z\)

yes

abs(home, x, y);

\(|\mathtt x|=\mathtt y\)

yes

mult(home, x, y, z);

\(\mathtt x \cdot \mathtt y=\mathtt z\)

yes

div(home, x, y, z);

\(\mathtt{x} / \mathtt{y}=\mathtt{z}\)

yes

sqr(home, x, y);

\({\mathtt x}^2=\mathtt y\)

yes

sqrt(home, x, y);

\(\sqrt{\mathtt x}=\mathtt y\)

yes

pow(home, x, n, y);

\({\mathtt x}^{\mathtt n}=\mathtt y\)

yes

nroot(home, x, n, y);

\(\sqrt[{\mathtt n}]{\mathtt x}=\mathtt y\)

yes

exp(home, x, y)

\(\exp(\mathtt{x})=\mathtt y\)

pow(home, b, x, y)

\(\mathtt{b}^\mathtt{x}=\mathtt y\)

log(home, x, y)

\(\log(\mathtt{x})=\mathtt y\)

log(home, b, x, y)

\(\log_{\mathtt{b}}(\mathtt{x})=\mathtt y\)

sin(home, x, y)

\(\sin(\mathtt{x})=\mathtt y\)

cos(home, x, y)

\(\cos(\mathtt{x})=\mathtt y\)

tan(home, x, y)

\(\tan(\mathtt{x})=\mathtt y\)

asin(home, x, y)

\(\arcsin(\mathtt{x})=\mathtt y\)

acos(home, x, y)

\(\arccos(\mathtt{x})=\mathtt y\)

atan(home, x, y)

\(\arctan(\mathtt{x})=\mathtt y\)

Figure 6.3 Arithmetic constraints (x, y, and z are float variables; n is a non-negative integer; b is a float number)

In addition to the constraints summarized in Figure 6.3 (see also Arithmetic constraints), the minimum and maximum constraints are also available for float variable arrays. That is, for a float variable array x and a float variable y

min(home, x, y);

constrains y to be the minimum of the variables in x (max is analogous).

The constraints marked as default in Figure 6.3 are always supported, the others only if Gecode has been built accordingly, see Transcendental and trigonometric functions and constraints.

6.3.4. Linear constraints

Linear constraints over float variables provide constraint post functions for linear constraints over float variables. The most general variant

linear(home, a, x, FRT_EQ, c);

posts the linear constraint

\[\sum_{i=0}^{|\mathtt x|-1} \mathtt{a}_i \cdot \mathtt{x}_i = \mathtt c\]

with float value coefficients a (of type FloatValArgs), float variables x, and a float value c. Note that a and x must have the same size. Of course, all other float relation types are supported, see Figure 6.2 for a table of float relation types (note that, linear constraints also show poor propagation for strict inequalities and disequality as discussed in Tip 6.4). Multiple occurrences of the same variable in x are explicitly allowed and common terms \(a\cdot y\) and \(b\cdot y\) for the same variable \(y\) are rewritten to \((a+b)\cdot y\) to increase propagation.

The array of coefficients can be omitted if all coefficients are one. That is,

linear(home, x, FRT_GR, c);

posts the linear constraint

\[\sum_{i=0}^{|\mathtt x|-1} \mathtt{x}_i > \mathtt c \]

for a variable array x and a float value c.

Instead of a float value c as the right-hand side of the linear constraint, a float variable can be used as well. All variants of linear support reification.

6.3.5. Channel constraints

Channel constraints channel float variables to integer variables. To express that a float variable x is equal to an integer variable y is by posting either

channel(home, x, y);

or

channel(home, y, x);

6.4. Synchronized execution

Gecode offers support in Synchronized execution for executing a function when float variables become assigned.

The following code

wait(home, x, [] (Space & home) { ...; });

posts a propagator that waits until the float variable x (or, if x is an array of float variables: all variables in x) is assigned. If x becomes assigned, the function passed as argument is executed with the current home space passed as argument. The type of the function must be

  std::function<void(Space& home)>