34. Getting started¶
This chapter outlines how a new variable type can be programmed with Gecode. The chapter (and the entire part on programming variables) chooses integer interval variables as its running example.
Overview. An overview of what needs to be designed and programmed is presented in Overview. The structure of how the implementation of a variable type is organized is presented in Structure.
Important
Programming variables requires to configure and recompile Gecode from its source code. More details can be found in Putting everything together.
34.1. Overview¶
We are going to use integer interval variables as the running example for programming variables. Integer interval variables take integer values (like the integer variables that come pre-defined with Gecode do) but their domain is defined by a lower and an upper bound only. That is, the domain is always an interval. This is in contrast to the integer variables that come with Gecode, where their domain can be any finite set of integer values.
The focus of this part is on understanding what needs to be done for implementing new variables, so we deliberately choose very simple variables together with very few operations on them as an example.
Even though integer interval variables seem not very interesting, variants of them could in fact be interesting. For example, the integer values used for the lower and upper bound could be integers of arbitrary precision, or instead of integer values one could choose floating point values.
What must be programmed. Programming variables includes the following tasks:
Variable implementations (Variable implementations): Programming a variable implementation consists of two tasks.
The first task is to specify domain-independent aspects of a variable implementation. This includes specifying a name for the variable implementation type, scope information, modification events, and propagation conditions. From a simple specification file containing this information a domain-independent base class for a variable implementation and the corresponding C++ definitions of modification events and propagation conditions is generated.
The generated base class together with the definition of modification events and propagation conditions actually become part of Gecode’s kernel. The kernel needs these definitions to schedule propagators that have subscribed to a variable implementation and to maintain these subscriptions during cloning.
The second task consists of programming the domain-dependent operations of a variable implementation. This is achieved by defining a class for a variable implementation that inherits from the generated, domain-independent base class and defines the respective domain operations.
Variables and variable arrays (Variables and variable arrays): As a variable is nothing but a simple and read-only interface to a variable implementation, a variable is obtained by inheriting from a base class for variables that depends on the variable implementation type. The actual programming amounts to defining read-only variable operations that invoke the corresponding operations on the variable’s variable implementation.
Variable arrays and variable argument arrays are, as variables, needed for modeling. Their programming requires the definition of several traits classes so that the defined arrays can be used with Gecode-provided functionality (for example, with the matrix interface for arrays, see Matrix interface for arrays).
Views (Views): Programming a view depends on the type of the view: whether the view is a direct interface to a variable implementation (a variable implementation view), whether it is a constant view, or whether it is derived (a derived view) from some other view. As examples, we are going to implement an integer view as a variable implementation view, minus and offset views as derived views, and an integer constant view as a constant view.
In addition to the classes for views, some additional functions on views must be defined for testing in which order views are and whether two views are shared or the same (see shared versus ==.).
Constraints and branchings: typically, when implementing variables one also needs to implement constraints and branchings for them. The implementation of constraints for a new variable type is not in any way different from what is described in Programming propagators.
The situation for implementing branchings is quite different: here one would want to offer at least a common set of variable-value branchings similar to those for integer variables (see Branching on integer and Boolean variables). Gecode offers substantial support for implementing variable-value branchings, including support for the specification of variable and value selection strategies, random and action-based selection of variables, tie-breaking, filter functions, no-goods, and much more. How to use Gecode’s support for implementing variable-value branchings is detailed in Variable-value branchings.
In case one implements reified constraints, it is possible to use these reified constraints together with Boolean expressions and relations as provided by the MiniModel modeling support. For an example, please consider Extending Boolean expressions and relations.
Tracing support (Variable tracing support): in order to support variable tracing, one needs to implement a few classes.
Only so-called trace views require some effort, the remaining functionality that needs to be implemented is straightforward and can be done by following a simple recipe.
Putting everything together. Even though we are presenting the implementation of integer interval variables only as an example, Putting everything together shows how everything is put together. This includes examples of propagators, post functions using various views, and a simple script (Golomb rulers, see Golomb rulers) using integer interval variables.
It also shows how Gecode must be configured and compiled such that integer interval variables are supported by Gecode’s kernel.
34.2. Structure¶
#ifndef __MPG_INT_HH__
#define __MPG_INT_HH__
...
#include <gecode/kernel.hh>
using Gecode::Advisor;
...
// [int.hh:exceptions]
// [int.hh:variable implementation]
// [int.hh:var:variable]
// [int.hh:array traits]
// [int.hh:variable arrays]
// [int.hh:integer view]
// [int.hh:constant integer view]
// [int.hh:minus view]
// [int.hh:offset view]
// [int.hh:branching]
// [int.hh:tracing]
#endif
Figure 34.1 The header file for integer interval variables¶
The implementation of integer interval variables is contained in a single header file int.hh, which is shown in The header file for integer interval variables.
Namespaces. The implementation is contained in the namespace MPG (for Modeling and Programming with Gecode) to avoid name-clashes with functionality provided by Gecode. To keep the implementation of integer interval variables concise, some important definitions in the Gecode namespace are made available by using declarations (see The header file for integer interval variables).
Similar to the organization of namespaces in Gecode, definitions that are used for modeling (variables and variable arrays) are contained in the namespace MPG, while definitions that are used for programming (variable implementations, views, branchers, and additional support) are in the namespace MPG::Int.
As the structure of namespaces matters (part of the support for variable arrays must be defined inside the Gecode namespace), each program fragment is shown in its appropriate namespace.
As an example, consider the definition of exceptions. Two are thrown by the constructor of the integer interval variable, in case the variable domain is ill-specified. The third exception is thrown when the variable or value selection for a branching is unknown.
The exceptions are defined as follows:
namespace MPG { namespace Int {
class OutOfLimits : public Exception {
public:
OutOfLimits(const char* l)
: Exception(l,"Number out of limits") {}
};
class VariableEmptyDomain : public Exception {
...
};
class UnknownBranching : public Exception {
...
};
}}
As discussed above, Exception is Gecode::Exception (see Exception) and has been introduced by a using declaration.
Naming scheme. The naming scheme follows the same naming scheme for integer variables as defined by Gecode (albeit defined in the namespace MPG instead of Gecode):
Variable implementations: The base class is named
IntVarImpBasewhereas the variable implementation class is namedIntVarImp. The names of modification events start withME_INT_whereas the names of propagation conditions start withPC_INT_. As mentioned above, these classes and identifiers are defined within the namespaceMPG::Int.Variables and variable arrays: Integer interval variables are implemented by the class
IntVar. Variable arrays of integer interval variables are implemented by the classIntVarArray, whereas the corresponding variable argument array is implemented by the classIntVarArgs. These classes are defined in the namespaceMPG.Views: the respective views are implemented by classes
IntView,ConstIntView,MinusView, andOffsetView. They are all defined within the namespaceMPG::Int.Branchings: how variables and values are selected is implemented by functions such as
INT_VAR_NONE()orINT_VAL_MIN()and the actual branching is implemented by a singlebranch()function. The good news is that no actual brancher must in fact be implemented, even though a number of rather straightforward support definitions must be implemented (which are contained in the namespaceMPG::Int).Variable tracing: variable tracers are implemented by the class
IntTracer(a type definition), a standard variable tracer is implemented by the classStdIntTracer, a variable trace recorder by a classIntTraceRecorder(also a type definition), and an integer trace delta by a classIntTraceDelta. Additionally, trace views are implemented by a classInt::IntTraceViewand some traits must be defined.
Inline functions as simplification. All functions, be they member or non-member functions are defined as inline. The reason for this is to make it easier to follow the example, as only the single header file int.hh is needed. In a real implementation one would move the definitions of some functions to a source file and only leave the declaration of the functions in the header file. This is in particular true for many of the functions defined in Variable-value branchings.
35. Variable implementations¶
This chapter describes how variable implementations can be programmed with Gecode. The chapter uses integer interval variables as introduced in Getting started as its running example.
Overview. The design of integer interval variables is detailed in Design decisions. After having finalized the design, Base definitions explains how the domain-independent base class for the variable implementation together with definitions of modification events and propagation conditions can be generated from a simple specification. Variable implementation shows how the actual variable implementation is programmed from the generated base class for a variable implementation. Additional specification options provides an overview of additional options for generating a variable implementation base class from its specification.
35.1. Design decisions¶
Before starting with the description of the implementation of integer interval variables, let us detail their design. This includes the design of the variable domain including access and modification operations, deltas for advisors (see Advisors), modification events, and propagation conditions.
Variable domain and operations. Unsurprisingly, the variable domain of an integer variable implementation is represented by two integers l (lower bound) and u (upper bound). The variable implementation provides access operations min() and max() that return these integers.
To modify an integer interval variable implementation, the operation gq(home,n) modifies the domain such that its values must be greater or equal to n, whereas the operation lq(home,n) modifies the domain such that its values must be less or equal to n.
The values l and u can only be initialized (when creating a new variable, see Variables) and modified such that they obey the following invariants:
The domain is never empty, that is, \(\mathtt{l}\leq\mathtt{u}\).
The domain values never exceed the limits defined by (
INT_MAXis the largest possible value for anint):namespace Limits { const int max = (INT_MAX / 2) - 1; const int min = -max; }
That is, \(\mathtt{Int::Limits::min}\leq \mathtt l\leq \mathtt u\leq\mathtt{Int::Limits::max}\).
The choice of values for Limits::min and Limits::max are motivated by simplicity only. To keep the example propagators used in Putting everything together simple, the limits are chosen such that the addition and subtraction of two integer values within the limits do not lead to numerical overflow. A real-life variable implementation would try to make as many values as possible available for a variable domain, see for example Limits for integer values.
Domains of Gecode integer variables. The integer interval variables developed here need only the two bounds l
and u. Gecode’s predefined integer variables also admit holes in their
domains. They use two representations for this. A domain without holes stores
its lower and upper bound directly in the variable implementation and needs no
additional range buffer. A domain with holes stores a contiguous sequence of
inclusive (min,max) range pairs in memory managed by its space. These
ranges are ordered, disjoint, and non-adjacent, so there is exactly one
canonical sequence for a domain. This compact representation replaces the
XOR-linked doubly linked range list used by earlier versions of Gecode.
The representation is private to the variable implementation. Public range and value iterators expose the domain, but not the range-pair storage. The operations that assign a value, remove a value, restrict a bound, or intersect or subtract ranges maintain the canonical sequence and its cached cardinality. They also report the same integer modification events as the corresponding domain changes require. Operations accepting an iterator take care not to overwrite storage on which that iterator still depends.
This distinction also affects copying during search. Copying a variable whose domain has no holes copies only its inline state. A sparse domain receives a new range buffer sized to the ranges that are live at the time of the copy; unused buffer capacity is not copied. Recomputation instead reconstructs a space by replaying choices and their domain modifications. Both mechanisms therefore preserve the same domains, while the common interval case remains cheap to copy.
Assigned variables. An integer interval variable is assigned iff \(\mathtt l=\mathtt u\).
Deltas for advisors. We design the delta information for an advisor computed by a modification operation on the variable implementation to be an interval as well. The interval defines the values that are removed by a modification operation. Due to the nature of the modification operations lq() and gq(), the removed values always form an interval.
The design of deltas to be used by advisors for a variable implementation depends directly on the design of the modification operations provided by a variable implementation. For example, if our integer interval variable implementation also featured an operation eq() to assign a variable implementation to a value, then one also would have to choose a different design for the delta information. Assume a variable implementation with domain \([\mathtt{l},\mathtt{u}]\) and that the modification operation eq(home,n) is executed where \(\mathtt{l}<\mathtt n<\mathtt u\). Then one could design the delta information to either accurately represent the set of removed values \([\mathtt{l},\mathtt{n-1}]\cup[\mathtt{n+1},\mathtt{u}]\) or to provide support for signaling that the domain has changed arbitrarily (this is the design chosen for integer variables in Gecode, see Delta information for integer views.).
Modification events. Any variable implementation must support the mandatory events for no modification (to be implemented as ME_INT_NONE), for failure (to be implemented as ME_INT_FAILED), and for assignment to a value (to be implemented as ME_INT_VAL).
The additional events must be chosen such that they take the following two aspects into account:
The modification operations should return meaningful values that describe how the domain of a variable implementation has changed. They must return
ME_INT_VALif the variable implementation becomes assigned. Otherwise, we choose to returnME_INT_MINif the lower bound changes and to returnME_INT_MAXif the upper bound changes.When a new propagator is posted and the propagator subscribes to some views (and hence to some variable implementations), the propagator must be scheduled with respect to some modification event. This modification event should capture that “somehow the variable has changed for the propagator”. In case an integer interval variable implementation is not yet assigned (otherwise the propagator will be scheduled with the modification event
ME_INT_VALanyway), we use an additional modification eventME_INT_BNDcapturing that one or both of the bounds have changed.
Again, there is quite some degree of freedom in the choice of modification events. Another design would be to only provide the modification event ME_INT_BND instead (apart from the mandatory modification events). An important aspect in which design to choose is the relation between modification events and propagation conditions to be discussed below.
Propagation conditions. To make our example variable implementations sufficiently interesting, we design the propagation conditions such that they can take full advantage of the modification events.
That is, apart from the mandatory propagation condition for not creating any subscription (to be implemented as PC_INT_NONE) and the mandatory propagation condition for an assigned variable implementation (to be implemented as PC_INT_VAL), we have three propagation conditions as follows:
PC_INT_MIN: schedule a propagator if the lower bound of a variable implementation changes.PC_INT_MAX: schedule a propagator if the upper bound changes.PC_INT_BND: schedule a propagator if lower or upper bound changes.
This design can also be reformulated in terms of modification events that are generated by a modification operation:
PC_INT_MIN: schedule a propagator forME_INT_VAL,ME_INT_MIN, andME_INT_BND.PC_INT_MAX: schedule a propagator forME_INT_VAL,ME_INT_MAX, andME_INT_BND.PC_INT_BND: schedule a propagator forME_INT_VAL,ME_INT_MIN,ME_INT_MAX, andME_INT_BND.
A simpler design would be to have the single non-mandatory propagation condition PC_INT_BND. The decision which design is best is not straightforward, as the tradeoff between the cost for additional propagation conditions (see below) and the gain from avoiding propagator executions depends on many different aspects. For a discussion and an evaluation in the context of Gecode’s integer variables, see [51].
Costs and limits for modification events and propagation conditions. The cost per each individual modification event and propagation condition is as follows:
Assume that a variable implementation uses \(n\) different modification events (including the mandatory ones). The size of \(n\) does not affect efficiency. To represent these modification events, the Gecode kernel reserves \(\lceil\log_2 (n-1)\rceil\) bits in each propagator for maintaining modification event deltas, see Modification event deltas.
The totally available number of bits for all variable implementation types used by Gecode is \(32\) (independent of whether Gecode is run on a \(32\) bit or \(64\) bit platform). That is, if we assume less than ten modification events per variable implementation type, the Gecode kernel can support at least ten different variable implementation types. [1]
The number of different propagation conditions \(m\) per variable implementation type is only limited by the largest value of an unsigned integer in C++.
For each propagation condition, every variable implementation needs a \(32\)-bit word, that is a variable implementation requires at least \(O(m)\) space (which is typically dwarfed by the space consumed for actually storing the subscriptions of a propagator or an advisor to a variable implementation).
Subscribing to a variable implementation requires \(O(m)\) time. Canceling a subscription with propagation condition \(p\) requires \(O(m+k)\) time, where \(k\) is the number of subscriptions with propagation condition \(p\).
35.2. Base definitions¶
The variable implementation base class together with definitions of modification events and propagation conditions are not programmed but are generated from a simple specification file. The specification contains three sections: a general section for naming, a section for modification events, and a section for propagation conditions.
In the following we describe how to turn the parts of the design from the previous section that is concerned with modification events and propagation conditions into the specification. The member functions of the generated base class are used and explained in the next section.
General section.
variable implementation specification
[General]
Name: Int
Namespace: MPG::Int
modification events
propagation conditions
[End]
Figure 35.1 Variable implementation specification¶
The specification file (named int.vis, where vis stands for variable implementation specification; however the file extension does not matter) is shown in Variable implementation specification. The specification file must start with [General] defining the start of the general section and must end with a line [End]. The Name option defines the names of the entities to be generated. In our example, a variable implementation base class IntVarImpBase (that is, the specified name is prepended to VarImpBase) generated, the identifiers for modification events start with ME_INT_ (that is, the specified name is put after the ME_ in capital letters), and the identifiers for propagation conditions start with PC_INT_. All these definitions are contained within the namespace as defined by the Namespace option.
The general section (and also the other sections discussed below) supports additional specification options, see Additional specification options for a summary and a specification file template for download.
Modification event section.
modification events
[ModEvent]
Name: FAILED=FAILED
[ModEvent]
Name: NONE=NONE
[ModEvent]
Name: VAL=ASSIGNED
Combine: VAL=VAL, MIN=VAL, MAX=VAL, BND=VAL
[ModEvent]
Name: BND=SUBSCRIBE
Combine: VAL=VAL, MIN=BND, MAX=BND, BND=BND
[ModEvent]
Name: MIN
Combine: VAL=VAL, MIN=MIN, MAX=BND, BND=BND
[ModEvent]
Name: MAX
Combine: VAL=VAL, MIN=BND, MAX=MAX, BND=BND
Figure 35.2 Modification event section¶
Every modification event requires a definition that is preceded by a line containing [ModEvent] as shown in Modification event section. The option Name defines the name of the modification event (in fact, just the part after ME_INT_ for our example). The values on the right-hand side of = specify that some modification events are special:
The modification events named
FAILED(that is,ME_INT_FAILED) andNONE(that is,ME_INT_NONE) are defined to be the events for failure (=FAILED) and no change (=NONE).The modification event named
VALis defined to be the event when a variable implementation becomes assigned (=ASSIGNED) to a value.The modification event named
BNDis defined to be used for scheduling a propagator when the propagator subscribes to a non-assigned variable implementation (=SUBSCRIBE).
Any variable implementation must define special events with =NONE, =FAILED, =ASSIGNED, and =SUBSCRIBE. In case there are only three modification events (all of them special with =NONE, =FAILED, =ASSIGNED), the modification event used for scheduling a propagator (that is, =SUBSCRIBE) is defined to be the event for a variable becoming assigned (that is, =ASSIGNED).
The section for modification events also defines how modification events are combined with a Combine option. The combination of modification events is needed for the correctness of scheduling propagators and also for modification event deltas, see Modification event deltas. An entry \(l=r\) for the modification event \(m\) defines that \(m\) combined with \(l\) is \(r\).
The definition of the combination of modification events can be expressed as a table:
VAL |
MIN |
MAX |
BND |
|
|---|---|---|---|---|
VAL |
VAL |
VAL |
VAL |
VAL |
MIN |
VAL |
MIN |
BND |
BND |
MAX |
VAL |
BND |
MAX |
BND |
BND |
VAL |
BND |
BND |
BND |
This table is exactly what is specified by the Combine options. The special modification events NONE and FAILED do not have a Combine option.
We will not present the full mathematical detail of the properties that must hold for the combination of modification events, the theory is presented in [60].
Propagation condition section.
propagation conditions
[PropCond]
Name: NONE=NONE
[PropCond]
Name: VAL=ASSIGNED
ScheduledBy: VAL
[PropCond]
Name: BND
ScheduledBy: VAL, BND, MIN, MAX
[PropCond]
Name: MIN
ScheduledBy: VAL, BND, MIN
[PropCond]
Name: MAX
ScheduledBy: VAL, BND, MAX
Figure 35.3 Propagation condition section¶
Every propagation condition requires a definition that is preceded by a line containing [PropCond] as shown in Propagation condition section. The option Name defines the name of the propagation condition (in fact, just the part after PC_INT_ for our example). The values on the right-hand side of = specify that some propagation conditions are special:
The propagation condition named
NONE(that is,PC_INT_NONE) is defined to be the propagation condition for not creating any subscription (=NONE).The propagation condition named
VAL(that is,PC_INT_VAL) is defined to be the condition when a propagator wants to subscribe to the event that a variable implementation becomes assigned (=ASSIGNED).
Any variable implementation must define the special propagation conditions =NONE and =ASSIGNED.
For each propagation condition (but for =NONE), it must be defined by a ScheduledBy option which modification events schedule a propagator for execution. That is, when defining a propagation condition \(p\), an entry \(m\) in the list of modification events defines the following: a propagator subscribed to a variable implementation \(x\) with propagation condition \(p\) is scheduled for execution when a modification operation on \(x\) returns the modification event \(m\). The modification events in our example correspond to the design presented in Propagation conditions..
35.3. Variable implementation¶
namespace MPG { namespace Int {
// [int.hh:limits]
// [int.hh:varimp:delta for advisors]
class IntVarImp : public IntVarImpBase {
protected:
int l, u;
public:
IntVarImp(Space& home, int min, int max)
: IntVarImpBase(home), l(min), u(max) {}
// [int.hh:varimp:access operations]
// [int.hh:varimp:assignment test]
// [int.hh:varimp:modification operations]
// [int.hh:varimp:subscriptions]
// [int.hh:varimp:re-scheduling]
// [int.hh:varimp:copying]
// [int.hh:varimp:delta information]
};
}}
Figure 35.4 Variable implementation¶
The variable implementation for integer interval variables is shown in Variable implementation. As discussed in the previous sections, the variable implementation inherits from the generated base class IntVarImpBase and implements a lower bound l and an upper bound u.
Access operations. Every variable implementation must implement a member function assigned() that tests whether the variable is assigned to a value:
bool assigned(void) const {
return l == u;
}
The test for assignment is used in the implementation of other member functions of the variable implementation. Furthermore, variables and views automatically provide implementations of a member function assigned() that calls the assigned() function of their variable implementation.
The access operations for the lower and upper bound are straightforward. Here, and in the following, we only show one of the operations, the operation for the other bound is analogous:
int min(void) const {
return l;
}
...
Modification operations. The modification operations must notify the Gecode kernel if a variable implementation is modified. As a description how a variable implementation changes, they must pass a modification event and delta information for advisors to a member function notify(). The notify() function executes subscribed advisors and schedules subscribed propagators (depending on the passed modification event and the propagators’ propagation conditions). The notify() function is inherited from the generated variable implementation base class and depends on the specified modification events and propagation conditions.
The delta information is implemented as discussed in Design decisions as an interval with lower and upper bound:
class IntDelta : public Delta {
private:
int l, u;
public:
IntDelta(int min, int max) : l(min), u(max) {}
int min(void) const {
return l;
}
...
};
The actual modification operations first test whether the variable implementation does not require modification or whether the operation fails and only then perform the actual modification. Before updating the upper bound u to n, the lq() operation creates the delta information d that describes that values between n+1 and u are being removed.
The notify() function is given the home space, a modification event, and the variable delta d as argument. The modification event passed to notify() must capture how the domain has changed. In particular, it must reflect whether the variable implementation has been assigned. The notify() function executes the advisors subscribed to this variable implementation and schedules all subscribed propagators with appropriate propagation conditions. Note that the notify() function returns a modification event. In case an advisor reports failure after its execution, notify() returns ME_INT_FAILED. Otherwise it returns the modification event that has been passed as argument:
ModEvent lq(Space& home, int n) {
if (n >= u) return ME_INT_NONE;
if (n < l) return fail(home);
IntDelta d(n+1,u); u = n;
return notify(home, assigned() ? ME_INT_VAL : ME_INT_MAX, d);
}
...
If a modification operation fails it must return ME_INT_FAILED as modification event and must call the fail() function. The fail() function is similar to notify() and executes advisors that have registered to be executed on failure. For convenience, the fail() function itself returns ME_INT_FAILED.
Delta information access. The variable implementation must also implement functions that provide access to the delta information:
static int min(const Delta& d) {
return static_cast<const IntDelta&>(d).min();
}
...
This construction appears nonsensical at first sight, however there are two good reasons why a variable implementation interprets the information stored in the delta information (of course, in that case one would have to declare the operation as const but not static). First, the variable implementation can change the information based on its own state. Second, the very same idea is needed for views (see Offset views for an example) and hence this design keeps the interfaces of views and variable implementations as similar as possible.
Subscriptions. A variable implementation must implement subscribe() operations for both propagators and advisors. The implementation of these operations always follow the same structure as shown below.
The reason why these functions have to be implemented in the variable implementation class even though they are (in slightly different form) already defined in the variable implementation base class is that they require information about whether a variable implementation is assigned. The definitions are as follows:
void subscribe(Space& home, Propagator& p, PropCond pc,
bool schedule=true) {
IntVarImpBase::subscribe(home,p,pc,assigned(),schedule);
}
void subscribe(Space& home, Advisor& a, bool fail) {
IntVarImpBase::subscribe(home,a,assigned(),fail);
}
Re-scheduling. A variable implementation must implement a reschedule() operation for propagators. The implementation of this operation is almost identical to the subscribe() member function discussed previously. The definition is as follows:
void reschedule(Space& home, Propagator& p, PropCond pc) {
IntVarImpBase::reschedule(home,p,pc,assigned());
}
Copying during cloning. Copying a variable implementation during cloning is implemented by a constructor and a copy() function. The constructor is straightforward and the copy() function only creates a new variable implementation if the variable implementation has not been copied before. If it has been copied before (that is, copied() returns true), the copy() function must return the forwarding pointer to the previously created copy as follows:
IntVarImp(Space& home, IntVarImp& y)
: IntVarImpBase(home,y), l(y.l), u(y.u) {}
IntVarImp* copy(Space& home) {
if (copied())
return static_cast<IntVarImp*>(forward());
else
return new (home) IntVarImp(home,*this);
}
Additional inherited member functions.
access operations |
||
|
returns degree (number of subscriptions) |
|
|
returns accumulated failure count |
|
subscriptions |
||
|
cancel subscription of propagator |
|
|
cancel subscription of advisor |
|
scheduling support |
||
|
schedule propagator |
|
|
re-schedule propagator |
|
modification event deltas |
||
|
extract modification event |
|
|
construct modification event delta |
|
delta information access |
||
|
return modification event from delta |
Figure 35.5 Summary of member functions predefined by variable implementations¶
In addition to the constructor and the member functions defined and used by our variable implementation, several other member functions are typically just inherited and are defined by the class VarImp. The most important inherited member functions are summarized in Summary of member functions predefined by variable implementations. For an explanation of degree and accumulated failure count, see Local versus shared variable selection criteria.
35.4. Additional specification options¶
This section provides an overview of additional specification options not discussed in Base definitions.
Comments. Any line starting with # is discarded and hence can serve as a comment in the specification file.
Generating headers, footers, and comments. Any text after the options for a [ModEvent] and [PropCond] definition until the next definition is added to the generated C++-code before the generated identifier definition. This can be used for defining comments to be added to the generated C++-code. For example, by
[PropCond]
Name: NONE=NONE
// Propagation condition to be ignored
[PropCond]
...
the comment
// Propagation condition to be ignored
is put before the definition of the generated propagation condition.
Related support exists for putting a header before (or a footer after) all generated definitions for modification events and propagation conditions: The text following [ModEventHeader], [ModEventFooter], [PropCondHeader], and [PropCondFooter] is inserted at the respective places in the generated code.
Conditional compilation. Giving an option Ifdef in the general section followed by some C++-preprocessor identifier IDENT wraps the entire generated code in preprocessor directives as follows:
#ifdef IDENT
...
#endif
By this, the Gecode kernel can be compiled with or without a particular variable type without being forced to reconfigure the Gecode kernel, see also Configuring and compiling Gecode.
Explicitly disposing variable implementations. Our example variables are entirely space-allocated and do not require external memory or other resources. However, for some variable types, the variable implementation might use external resources or memory that is not space-allocated and must explicitly be freed.
For an example, suppose the integer interval variables had been implemented by using arbitrary precision integers for the lower and upper bound and that these bounds must explicitly be freed.
By specifying in the general section
Dispose: true
and implementing in the variable implementation class a dispose(Space& home) member function, all variable implementations are disposed by calling their dispose() functions. The variable implementations are disposed when their home space is deleted.
Additionally, an object must be created that controls the disposal of variable implementations. Assume that our example integer variables used external memory and that its specification file contains
Dispose: true
and that MPG::IntVarImp implements a dispose() function. Then, your program must create a variable implementation disposer as follows:
Gecode::VarImpDisposer<MPG::IntVarImp> disposer;
The disposer object must be initialized before the first variable using MPG::IntVarImp is created.
Reserving bits. A limited number of bits \(b\) can be reserved within each variable implementation by specifying in the general section
Bits: $b$
Then, the variable implementation can get a reference to a value of type unsigned int by calling the member function bits() where the least \(b\) bits can be used freely. However, the maximal number of subscriptions (both propagators and advisors) for that variable implementation type is reduced from \(2^{31}-1\) to \(2^{31-b}-1\). Furthermore, any attempt to use more than the specified number of bits will crash Gecode in a truly spectacular fashion!
Specification file template. The specification template contains all possible specification options to assist in defining your own variable types.
36. Variables and variable arrays¶
This chapter describes how variables can be programmed from variable implementations and how variable arrays and variable argument arrays can be programmed. The chapter uses integer interval variables as introduced in Getting started together with their implementations as defined in Variable implementations as its running example.
Overview. How integer interval variables are implemented is detailed in Variables. Variable arrays and variable argument arrays are discussed in Variable arrays and variable argument arrays.
36.1. Variables¶
namespace MPG {
class IntVar : public VarImpVar<Int::IntVarImp> {
protected:
using VarImpVar<Int::IntVarImp>::x;
public:
IntVar(void) {}
IntVar(const IntVar& y)
: VarImpVar<Int::IntVarImp>(y.varimp()) {}
IntVar(Int::IntVarImp* y)
: VarImpVar<Int::IntVarImp>(y) {}
// [int.hh:var:variable creation]
// [int.hh:var:access operations]
};
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os, const IntVar& x) {
...
}
}
Figure 36.1 Variable programmed from a variable implementation¶
As a variable is just a read-only interface to a variable implementation, its implementation is straightforward. The definition of integer variables is shown in Variable programmed from a variable implementation. The copy constructor uses the member function varimp() that returns the pointer to the variable’s variable implementation. Note that every variable must have a constructor that takes a pointer to the corresponding variable implementation as argument.
Note that within the class IntVar, a pointer to the corresponding variable implementation is available as protected member x (see Using using clauses for information on using).
One also must define an output operator << for a variable as shown in Variable programmed from a variable implementation.
It is important to remember that variables are defined in the namespace MPG. This is in contrast to variable implementations, which are defined in the namespace MPG::Int.
Variable creation. Creating a new variable is done with the following constructor that creates a new variable implementation as follows:
IntVar(Space& home, int min, int max)
: VarImpVar<Int::IntVarImp>
(new (home) Int::IntVarImp(home,min,max)) {
if ((min < Int::Limits::min) || (max > Int::Limits::max))
throw Int::OutOfLimits("IntVar::IntVar");
if (min > max)
throw Int::VariableEmptyDomain("IntVar::IntVar");
}
Note that the constructor ensures the invariants for the lower and upper bound of a variable as discussed in Design decisions by possibly throwing exceptions.
Access operations. In addition to constructors, variables typically implement the same access operations as their corresponding variable implementation:
int min(void) const {
return x->min();
}
...
Additional inherited member functions.
access operations |
||
|
returns pointer to variable implementation |
|
|
whether variable is assigned |
|
|
returns degree (number of subscriptions) |
|
|
returns accumulated failure count |
|
update during cloning |
||
|
updates variable during cloning |
Figure 36.2 Summary of member functions predefined by variables¶
In addition to the constructor and member functions defined by our variables, several other member functions are typically just inherited and are defined by the class VarImpVar. The most important inherited member functions are summarized in Summary of member functions predefined by variables. For an explanation of degree and accumulated failure count, see Local versus shared variable selection criteria.
36.2. Variable arrays and variable argument arrays¶
Defining variable arrays and variable argument arrays (see also Variable and argument arrays) requires the implementation of the arrays proper together with some traits. The traits classes for variable arrays and variable argument arrays ensure that Gecode-provided functionality for arrays can be used with the newly defined arrays.
Array traits.
namespace MPG {
class IntVarArgs; class IntVarArray;
}
namespace Gecode {
template<>
class ArrayTraits<Gecode::VarArray<MPG::IntVar> > {
public:
typedef MPG::IntVarArray StorageType;
typedef MPG::IntVar ValueType;
typedef MPG::IntVarArgs ArgsType;
};
template<>
class ArrayTraits<MPG::IntVarArray> {
...
};
template<>
class ArrayTraits<Gecode::VarArgArray<MPG::IntVar> > {
public:
typedef MPG::IntVarArgs StorageType;
typedef MPG::IntVar ValueType;
typedef MPG::IntVarArgs ArgsType;
};
template<>
class ArrayTraits<MPG::IntVarArgs> {
...
};
}
Figure 36.3 Array traits for variable arrays¶
The definition of the array traits classes is shown in Array traits for variable arrays. The definition is done in two steps. The first step provides forward declarations of the array types IntVarArgs and IntVarArray in the namespace MPG (because that is where these arrays will be defined).
The second step requires to define traits for these two array types. The trait classes must be defined in the namespace Gecode. For each array type, two traits classes are needed: one for the base class (for example, Gecode::VarArray<MPG::IntVar>) and one for the class to be implemented (for example, MPG::IntVarArray). The definitions for the array type and its base class must be identical and follow the examples shown in Array traits for variable arrays.
Variable arrays.
namespace MPG {
class IntVarArgs : public VarArgArray<IntVar> {
public:
IntVarArgs(void) {}
explicit IntVarArgs(int n) : VarArgArray<IntVar>(n) {}
IntVarArgs(const IntVarArgs& a) : VarArgArray<IntVar>(a) {}
IntVarArgs(const VarArray<IntVar>& a) : VarArgArray<IntVar>(a) {}
IntVarArgs(Space& home, int n, int min, int max)
: VarArgArray<IntVar>(n) {
for (int i=0; i<n; i++)
(*this)[i] = IntVar(home,min,max);
}
};
class IntVarArray : public VarArray<IntVar> {
public:
IntVarArray(void) {}
IntVarArray(const IntVarArray& a)
: VarArray<IntVar>(a) {}
IntVarArray(Space& home, int n, int min, int max)
...
}
};
}
Figure 36.4 Variable arrays¶
The implementation of variable arrays and variable argument arrays typically only require the implementation of various constructors when inheriting from the base classes VarArray and VarArgArray. The minimal set of constructors such that the arrays are compatible to arrays as used by Gecode is shown in Variable arrays.
37. Views¶
This chapter describes how views as needed for programming propagators and branchers can be programmed. The chapter uses integer interval variables as introduced in Getting started together with their implementations as defined in Variable implementations as its running example.
Overview. View types provides an overview of the different types of views available in Gecode. The remaining sections provide examples for each different view type: Variable implementation views: integer view shows how an integer view IntView is constructed as a variable implementation view; Constant views: constant integer view shows how a constant integer view ConstIntView is programmed as a constant view; Derived views shows how a minus view MinusView and an offset view OffsetView are programmed as derived views.
37.1. View types¶
Gecode provides three different types of views:
Variable implementation views: a variable implementation view is nothing but a direct interface to a variable implementation. A variable implementation view must inherit from VarImpView. The class VarImpView is parametric with respect to a variable and not a variable implementation (as one might expect). This is due to the fact that the type of the variable implementation can be obtained automatically from the type of a variable. Making a variable implementation view parametric with respect to a variable type has the advantage that information on both the variable type and variable implementation type become available.
Constant views: a constant view must implement the same interface and must perform the same operations as some assigned variable implementation view. This particular variable implementation view is called the corresponding variable implementation view. A constant view must inherit from ConstView which is parametric with respect to the corresponding variable implementation view.
Derived views: a derived view is a view that is implemented in terms of some other view (all view types are possible: variable implementation, constant, and derived). The view from which the derived view is derived, is called the base view. A derived view must inherit from DerivedView which is parametric with respect to the base view.
Predefined member functions.
access operations |
||
|
returns pointer to variable implementation |
|
|
whether variable is assigned |
|
|
returns degree (number of subscriptions) |
|
|
returns accumulated failure count |
|
subscriptions |
||
|
subscribe propagator/advisor |
|
|
cancel propagator/advisor |
|
scheduling support |
||
|
schedule propagator |
|
|
re-schedule propagator |
|
modification event deltas |
||
|
extract modification event |
|
|
construct modification event delta |
|
delta information access |
||
|
return modification event from delta |
|
update during cloning |
||
|
updates view during cloning |
Figure 37.1 Summary of member functions predefined by views¶
The classes VarImpView, ConstView, and DerivedView define already many member functions that simplify the implementation of new views. The most important predefined member functions are summarized in Summary of member functions predefined by views.
Note that the varimp() function for a constant view or for a view derived from a constant view returns NULL, as no variable implementation exists.
View test functions. There are three different functions predefined for views:
The function
shared(x,y)returnstrue, if both viewsxandyshare a common variable implementation (see shared versus ==.). Typically, the definition ofshared()does not need to be overloaded for newly defined views.The operator
x==yreturnstrue, if both viewsxandyare identical (see shared versus ==.). For constant views and derived views, the definition ofoperator ==()must be overloaded for newly defined views (see Constant views: constant integer view and Offset views for examples). The operatorx!=yis analogous.The operator
x<yreturnstrue, ifxcomes beforeyin some arbitrary total and strict order for ordering views. The function is mainly used for sorting arrays of views into some order (in particular for detecting duplicate views). For constant views and derived views, the definition ofoperator <()must be overloaded for newly defined views (see Constant views: constant integer view and Offset views for examples).
Output operator. For every view also an output operator << must be defined. We sketch this only for integer views in Variable implementation views: integer view, for all other views the definition is analogous.
37.2. Variable implementation views: integer view¶
namespace MPG { namespace Int {
class IntView : public VarImpView<IntVar> {
protected:
using VarImpView<IntVar>::x;
public:
IntView(void) {}
IntView(const IntVar& y)
: VarImpView<IntVar>(y.varimp()) {}
IntView(IntVarImp* y)
: VarImpView<IntVar>(y) {}
// [int.hh:intview:access operations]
// [int.hh:intview:modification operations]
// [int.hh:intview:delta information]
};
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator<<(std::basic_ostream<Char,Traits>& os, const IntView& x) {
...
}
}}
Figure 37.2 Integer view¶
Integer view shows the definition of the class IntView for integer views from the class VarImpView for variable implementation views. Please remember that a variable implementation view is parametric with respect to a variable type (IntVar in our example, such that IntView uses the same variable implementation type IntVarImp as IntVar does).
Similar to variables obtained from variable implementations, a variable implementation view has a protected member x that is a pointer to its variable implementation (see Using using clauses for information on using). A variable implementation view must implement at least the shown constructors such that it can be initialized both from the corresponding variable type and from the corresponding variable implementation type.
The remaining implementation tasks for variable implementation views are straightforward: all operations that are specific to a variable type (in our case, specific to integer interval variables) must be implemented. The implementation is straightforward as only the corresponding operations of the variable implementation are invoked:
The access operations must be implemented:
int min(void) const { return x->min(); } ...
The modification operations must be implemented:
ModEvent lq(Space& home, int n) { return x->lq(home,n); } ...
Finally, the operations for accessing delta information must be implemented:
int min(const Delta& d) const { return IntVarImp::min(d); } ...
37.3. Constant views: constant integer view¶
namespace MPG { namespace Int {
class ConstIntView : public ConstView<IntView> {
protected:
int x;
public:
ConstIntView(void) : x(0) {}
ConstIntView(int n) : x(n) {}
int min(void) const {
return x;
}
...
ModEvent lq(Space& home, int n) {
return (x <= n) ? ME_INT_NONE : ME_INT_FAILED;
}
...
// [int.hh:constintview:delta information]
// [int.hh:constintview:update during cloning]
};
// [int.hh:constintview:view tests]
...
}}
Figure 37.3 Constant integer view¶
Constant integer view shows the implementation of a constant integer view with IntView as the corresponding variable implementation view. A constant integer view ConstIntView stores an integer value x and must implement all variable-specific operations that are implemented by the corresponding IntView class (as shown in Constant integer view).
Slightly less obvious is the implementation of operations that access delta information. While these operations must be implemented such that constant integer views can be used instead of integer views, they will never be executed (by definition, a constant view can never change). Hence we use the macro GECODE_NEVER (see Never execute) to clarify that the delta information operations are never executed:
int min(const Delta& d) const {
GECODE_NEVER; return 0;
}
...
Update during cloning. The definition of the update() member function of ConstView does not take care of the integer value x. Hence we need to provide a new update() function that updates the value of x as follows:
void update(Space& home, ConstIntView& y) {
ConstView<IntView>::update(home,y);
x = y.x;
}
View tests. Also the default definitions of the view test operators ==, !=, and < for constant views do not take the integer value x of the view into account. Overloaded versions for constant integer views are as follows:
inline bool operator ==(const ConstIntView& x, const ConstIntView& y) {
return x.min() == y.min();
}
inline bool operator !=(const ConstIntView& x, const ConstIntView& y) {
return !(x == y);
}
inline bool operator <(const ConstIntView& x, const ConstIntView& y) {
return x.min() < y.min();
}
37.4. Derived views¶
This section exemplifies two different derived views: minus views and offset views. Why these views are useful and what their semantics is can be seen in Minus views for minus views and in Offset views for offset views.
37.4.1. Minus views¶
namespace MPG { namespace Int {
class MinusView : public DerivedView<IntView> {
protected:
using DerivedView<IntView>::x;
// [int.hh:minusview:modification events and propagation conditions]
public:
MinusView(void) {}
explicit MinusView(const IntView& y)
: DerivedView<IntView>(y) {}
// [int.hh:minusview:access operations]
// [int.hh:minusview:modification operations]
// [int.hh:minusview:support operations]
// [int.hh:minusview:subscriptions]
// [int.hh:minusview:re-scheduling]
// [int.hh:minusview:delta information]
};
inline bool operator ==(const MinusView& x, const MinusView& y) {
return x.base() == y.base();
}
...
...
}}
Figure 37.4 Minus view¶
Minus view shows that a minus view is derived from an integer view IntView. The protected member x refers to the base view, that is the integer view from which the minus view is derived (see Using using clauses for information on using).
Access operations. The access operations are as to be expected for a minus view. That is, the lower bound of the derived view is the negation of the upper bound of the base view:
int min(void) const {
return -x.max();
}
...
Modification operations.
static ModEvent minusme(ModEvent me) {
switch (me) {
case ME_INT_MIN: return ME_INT_MAX;
case ME_INT_MAX: return ME_INT_MIN;
default: return me;
}
}
static PropCond minuspc(PropCond pc) {
...
}
Figure 37.5 Negation of modification events and propagation conditions¶
The modification operations are slightly more involved than the access operations as they return a modification event. If the modification event of the base view is ME_INT_MAX (the upper bound of the base view has changed), then the modification event for the derived view must be ME_INT_MIN (the lower bound of the derived view has changed).
Negation of modification events and propagation conditions shows functions minusme() and minuspc() that return the negation of modification events and propagation conditions (to be discussed later).
Using the function minusme, the modification operations can be defined as follows:
ModEvent lq(Space& home, int n) {
return minusme(x.gq(home,-n));
}
...
Accessing delta information. Accessing delta information must also take into account that the modification event stored in a delta must be converted with minusme(). Also the other operations for accessing delta information must be adopted accordingly:
static ModEvent modevent(const Delta& d) {
return minusme(IntView::modevent(d));
}
int min(const Delta& d) const {
return -x.max(d);
}
...
Additional operations. Any operation that is concerned with either modification events or propagation conditions must be implemented to take the switch between lower bound and upper bound into account. These operations include the operations for handling subscriptions of propagators (the function minuspc() is defined analogously to minusme() in Negation of modification events and propagation conditions):
void subscribe(Space& home, Propagator& p, PropCond pc,
bool schedule=true) {
x.subscribe(home,p,minuspc(pc),schedule);
}
void subscribe(Space& home, Advisor& a) {
x.subscribe(home,a);
}
...
Note that the operations that subscribe advisors must be re-implemented even though they are unchanged. This is due to inheritance in C++: as the overloaded functions for propagators are redefined, also the functions for advisors are considered to be redefined.
Likewise, the member function for re-escheduling must also be implemented following the same idea:
void reschedule(Space& home, Propagator& p, PropCond pc) {
x.reschedule(home,p,minuspc(pc));
}
The remaining operations to be implemented are support operations:
static void schedule(Space& home, Propagator& p, ModEvent me) {
return IntView::schedule(home,p,minusme(me));
}
static ModEvent me(const ModEventDelta& med) {
return minusme(IntView::me(med));
}
static ModEventDelta med(ModEvent me) {
return IntView::med(minusme(me));
}
37.4.2. Offset views¶
namespace MPG { namespace Int {
class OffsetView : public DerivedView<IntView> {
protected:
using DerivedView<IntView>::x;
int c;
public:
OffsetView(void) {}
OffsetView(const IntView& y, int d)
: DerivedView<IntView>(y), c(d) {}
int offset(void) const {
return c;
}
int min(void) const {
return x.min()+c;
}
...
ModEvent lq(Space& home, int n) {
return x.lq(home,n-c);
}
...
int min(const Delta& d) const {
return x.min(d)+c;
}
...
// [int.hh:offsetview:update during cloning]
};
// [int.hh:offsetview:view tests]
...
}}
Figure 37.6 Offset view¶
Offset view shows that an offset view is derived from an integer view IntView and stores an additional integer value c for the offset. The protected member x refers to the base view, that is the integer view from which the offset view is derived (see Using using clauses for information on using). The access, modification, and delta information access operations of an offset view are as to be expected.
The update() function must also update the integer offset c as follows:
void update(Space& home, OffsetView& y) {
x.update(home,y.x);
c=y.c;
}
Likewise, the view test operators ==, != and < must take into account the integer offset c:
inline bool operator ==(const OffsetView& x, const OffsetView& y) {
return (x.base() == y.base()) && (x.offset() == y.offset());
}
inline bool operator !=(const OffsetView& x, const OffsetView& y) {
return !(x == y);
}
inline bool operator <(const OffsetView& x, const OffsetView& y) {
return (x.base() < y.base())
|| ((x.base() == y.base()) && (x.offset() < y.offset()));
}
38. Variable-value branchings¶
This chapter explains how to program common variable-value branchings using the abstractions provided by Gecode.
Overview. Type, traits, action, and more explains which simple types must be defined for variable-value branchings. How functions for variable selection and value selection are implemented is demonstrated in Variable and value selection. View selection creation shows how a function that creates an object for selecting views during branching is implemented. How functions for selecting values and committing to these values are implemented is shown in Value selection and commit creation. This section also explains how to add support for no-goods to a variable-value brancher. How the actual branchings are implemented is then detailed in Branchings.
// [int.hh:branch function types]
// [int.hh:branch traits]
// [int.hh:variable AFC]
// [int.hh:variable action]
// [int.hh:variable CHB]
namespace MPG {
// [int.hh:variable selection class]
// [int.hh:variable selection functions]
// [int.hh:value selection functions]
}
namespace MPG { namespace Int {
// [int.hh:view selection creation function]
// [int.hh:value selection and commit creation function]
}}
namespace MPG {
// [int.hh:branch function]
// [int.hh:branch function with tie-breaking]
}
Figure 38.1 Part of header file concerned with branching¶
This structure is reflected in the part of the int.hh header file that is concerned with branching (shown in Part of header file concerned with branching).
38.1. Type, traits, action, and more¶
The way how a variable-value branching works can to some extent be controlled by the user by functions:
A branching filter function defines which variables are actually considered for branching, see Using branch filter functions.
A variable value print function defines how to print information on alternatives of variable value branchers during search. Variable value branchers print some default information even if the user does not supply a variable value print function, see Using variable-value print functions.
A branch merit function can define which variable is selected for branching, see User-defined variable selection.
A branch value function selects a value that is used for branching, see User-defined value selection.
A branch commit function constrains a variable with respect to a value passed as argument, see User-defined value selection.
In the following type definitions, the type IntVar of the argument x, the return type int of the branch value function of type IntBranchVal, and the type int of the argument n is dependent on our integer interval variables (they are of type IntVar and they take values of type int).
The remaining argument and return types are required by Gecode and are as follows:
namespace MPG {
typedef std::function<bool(const Space& home,
IntVar x, int i)>
IntBranchFilter;
typedef std::function<void(const Space &home,
const Brancher& b, unsigned int a,
IntVar x, int i, const int& n,
std::ostream& o)>
IntVarValPrint;
typedef std::function<double(const Space& home,
IntVar x, int i)>
IntBranchMerit;
typedef std::function<int(const Space& home,
IntVar x, int i)>
IntBranchVal;
typedef std::function<void(Space& home, unsigned int a,
IntVar x, int i, int n)>
IntBranchCommit;
}
These function type definitions must be connected to the variable type IntVar by means of a traits-class of type BranchTraits. As the functionality for variable-value branching is defined in the Gecode namespace, the trait class must also be defined there:
namespace Gecode {
template<>
class BranchTraits<MPG::IntVar> {
public:
typedef MPG::IntBranchFilter Filter;
typedef MPG::IntBranchMerit Merit;
typedef MPG::IntBranchVal Val;
typedef int ValType;
typedef MPG::IntBranchCommit Commit;
};
}
The last remaining definitions specializes AFC, action, and CHB information for integer interval variables by defining a class IntAFC as follows:
namespace MPG {
class IntAFC : public AFC {
public:
IntAFC(void);
IntAFC(const IntAFC& a);
IntAFC& operator =(const IntAFC& a);
IntAFC(Home home, const IntVarArgs& x, double d=1.0);
void init(Home home, const IntVarArgs& x, double d=1.0);
};
...
}
a class IntAction as follows:
namespace MPG {
class IntAction : public Action {
public:
IntAction(void);
IntAction(const IntAction& a);
IntAction& operator =(const IntAction& a);
IntAction(Home home, const IntVarArgs& x, double d=1.0,
bool p=true, bool f=true,
IntBranchMerit bm=nullptr);
void init(Home home, const IntVarArgs& x, double d=1.0,
bool p=true, bool f=true,
IntBranchMerit bm=nullptr);
};
...
}
and a class IntCHB as follows:
namespace MPG {
class IntCHB : public CHB {
public:
IntCHB(void);
IntCHB(const IntCHB& c);
IntCHB& operator =(const IntCHB& c);
IntCHB(Home home, const IntVarArgs& x,
IntBranchMerit bm=nullptr);
void init(Home home, const IntVarArgs& x,
IntBranchMerit bm=nullptr);
};
...
}
The actual implementations are omitted as they contain nothing more than the type specialization and creation of view arrays in the initializing constructor and the init() function.
38.2. Variable and value selection¶
An important part of the interface of the branching is support for specifying how variables and values are selected for branching. This is implemented by a set of variable and value selection functions that are used for specification. These functions return objects that are then used for creating the appropriate branchers. In this section we are not interested in describing a complete set of variable and value selection functions but in a set that demonstrates the features of variable-value branchings.
Variable selection. The variable selection functions we are considering here are defined as follows (their names and what they do coincides with the variable selection functions for normal integer variables in Gecode, see Branching on integer and Boolean variables):
IntVarBranch INT_VAR_NONE(void);
IntVarBranch INT_VAR_RND(Rnd r);
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm,
BranchTbl tbl=nullptr);
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl=nullptr);
IntVarBranch INT_VAR_ACTION_MAX(double d=1.0,
BranchTbl tbl=nullptr);
IntVarBranch INT_VAR_ACTION_MAX(IntAction a,
BranchTbl tbl=nullptr);
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr);
// [int.hh:variable selection function implementation]
All but INT_VAR_NONE() take arguments: unsurprisingly, a random number generator must be passed to INT_VAR_RND() and a double as decay-factor or an integer action object to INT_VAR_ACTION_MAX(). Both INT_VAR_NONE() and INT_VAR_RND() are special in that they are not useful for tie-breaking. All other variable selection functions take an optional argument of type BranchTbl as a branch tie-breaking limit function (we will abbreviate this here as tbl-function), see Tie-breaking for a description of tie-breaking and tbl-functions.
class IntVarBranch : public VarBranch<IntVar> {
public:
enum Select {
SEL_NONE, SEL_RND, SEL_MERIT_MAX,
SEL_DEGREE_MAX, SEL_ACTION_MAX, SEL_SIZE_MIN
};
protected:
Select s;
public:
IntVarBranch(void) ;
IntVarBranch(Rnd r);
IntVarBranch(Select s0, BranchTbl t);
IntVarBranch(Select s0, double d, BranchTbl t);
IntVarBranch(Select s0, Action a, BranchTbl t);
IntVarBranch(Select s0, IntBranchMerit mf, BranchTbl t);
Select select(void) const;
// [int.hh:expand action]
};
...
Figure 38.2 Variable selection class¶
The implementation of the variable selection functions is simple: each function returns an object of class IntVarBranch that stores all necessary information required for creating the appropriate brancher. As an example of an implementation consider the following, the other functions are similar:
inline IntVarBranch
INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl) {
return IntVarBranch(IntVarBranch::SEL_MERIT_MAX,bm,tbl);
}
...
The implementation of the class IntVarBranch is shown in Variable selection class. It defines an enumeration of all variable selection strategies and a set of constructors for the different types of arguments the variable selection functions take. The select() function returns a value of the enumeration type that is stored by the object. All other information is handled by the base class VarBranch that is parametric with respect to the variable type.
The class must also implement an expand() member function. It checks whether INT_VAR_ACTION_MAX() had been called just with a decay-factor instead of an integer action object. In this case it creates an integer action object and stores it as follows:
void expand(Home home, const IntVarArgs& x) {
if ((select() == SEL_ACTION_MAX) && !action())
action(IntAction(home,x,decay()));
}
Value selection. Value selection functions are implemented similarly to variable selection functions. They return an object of class IntValBranch (inheriting from the template base class ValBranch) which stores the necessary information for creating the appropriate brancher. We are considering the following value selection functions as examples:
class IntValBranch : public ValBranch<IntVar> {
...
};
IntValBranch INT_VAL_MIN(void);
IntValBranch INT_VAL_RND(Rnd r);
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c=nullptr);
...
Note that the last argument of the value selection function INT_VAL() is optional, the default behavior will be defined in Value selection and commit creation.
38.3. View selection creation¶
// [int.hh:size merit class]
inline ViewSel<IntView>*
viewsel(Space& home, const IntVarBranch& ivb) {
if (ivb.select() == IntVarBranch::SEL_NONE)
return new (home) ViewSelNone<IntView>(home,ivb);
if (ivb.select() == IntVarBranch::SEL_RND)
return new (home) ViewSelRnd<IntView>(home,ivb);
if (ivb.tbl()) {
// [int.hh:view selection with tbl-function]
} else {
// [int.hh:view selection without tbl-function]
}
throw UnknownBranching("Int::branch");
}
Figure 38.3 View selection creation function¶
The view selection creation function shown in View selection creation function takes an object ivb of class IntVarBranch as an argument, creates an object of class ViewSel and returns a pointer to it. The object ivb is a specification of which object should be returned. The returned object is used to select views during brancher execution.
Selection of the first unassigned view (corresponding to SEL_NONE, that is, the object ivb has been created by calling the function INT_VAR_NONE()) is implemented by the Gecode-defined class ViewSelNone. Also random view selection is provided by Gecode through the class ViewSelRnd. Both classes are parametric with respect to a view type.
View selection with tbl-function. The other strategies for view selection exist in two variants: one variant that uses a tbl-function and one variant that does not. In case a tbl-function has been supplied as additional argument to one of the variable selection functions, the following creates the appropriate object for view selection:
switch (ivb.select()) {
case IntVarBranch::SEL_MERIT_MAX:
return new (home) ViewSelMaxTbl<MeritFunction<IntView>>(home,ivb);
case IntVarBranch::SEL_DEGREE_MAX:
return new (home) ViewSelMaxTbl<MeritDegree<IntView>>(home,ivb);
case IntVarBranch::SEL_ACTION_MAX:
return new (home) ViewSelMaxTbl<MeritAction<IntView>>(home,ivb);
case IntVarBranch::SEL_SIZE_MIN:
return new (home) ViewSelMinTbl<MeritSize>(home,ivb);
default: ;
}
Depending on how the view is to be selected, different objects are created. An object of class ViewSelMaxTbl selects a variable with maximal merit (for the definition of merit, see Branching on integer and Boolean variables), whereas an object of class ViewSelMinTbl selects a variable with minimal merit. Objects of both classes take a tbl-function during selection into account. Both classes expect a class as template argument that computes the actual merit value for a given view.
The classes MeritFunction, MeritDegree, and MeritAction are defined by Gecode and are parametric with respect to the actual view type.
class MeritSize : public MeritBase<IntView,unsigned int> {
public:
MeritSize(Space& home, const VarBranch<IntVar>& vb)
: MeritBase<IntView,unsigned int>(home,vb) {}
MeritSize(Space& home, MeritSize& m)
: MeritBase<IntView,unsigned int>(home,m) {}
unsigned int operator ()(const Space& home, IntView x, int i) {
return x.max() - x.min();
}
};
Figure 38.4 Size merit class¶
Selecting a view with minimal size is specific to our integer interval variables and views. The implementation of the class MeritSize inherits from MeritBase and is shown in Size merit class.
The class MeritBase is parametric with respect to the view type (IntView in our case) and the type of the merit value (unsigned int in our case). The constructors are as to be expected and the call operator must return the merit value of type unsigned int (the same as the second template argument to MeritBase) of the view x (i refers to the position of the view x in the array of views used in the brancher).
In case the merit class uses members that must be deallocated when the home-space is deleted, the merit class must redefine the member functions notice() and dispose(), for example by:
bool notice(void) const {
return true;
}
void dispose(Space& home) {
...
}
View selection without tbl-function. Implementing view selection without a tbl-function is analogous, the only difference is that the classes ViewSelMax (instead of ViewSelMaxTbl) and ViewSelMin (instead of ViewSelMinTbl) must be used:
switch (ivb.select()) {
case IntVarBranch::SEL_MERIT_MAX:
return new (home) ViewSelMax<MeritFunction<IntView>>(home,ivb);
...
}
38.4. Value selection and commit creation¶
// [int.hh:value selection classes]
// [int.hh:value commit class]
inline ValSelCommitBase<IntView,int>*
valselcommit(Space& home, const IntValBranch& ivb) {
switch (ivb.select()) {
case IntValBranch::SEL_MIN:
return new (home)
ValSelCommit<ValSelMin,ValCommitLq>(home,ivb);
case IntValBranch::SEL_RND:
return new (home)
ValSelCommit<ValSelRnd,ValCommitLq>(home,ivb);
case IntValBranch::SEL_VAL_COMMIT:
// [int.hh:user-defined value selection and commit functions]
default:
throw UnknownBranching("Int::branch");
}
}
Figure 38.5 Value selection and commit creation function¶
The value selection and commit creation function is very similar to the variable selection creation function from the previous section. It creates and returns an object that performs value selection and value commit during branching depending on a specification object of class IntValBranch.
The function is shown in Value selection and commit creation function and returns an object of class ValSelCommitBase. Again, this class is parametric with respect to the view type (IntView) and the value type (int). Depending on which value selection strategy is defined by the argument ivb, a corresponding object of class ValSelCommit is created.
The class ValSelCommit is parametric with respect to a value selection class and a value commit class (to be discussed below). The classes ValSelMin, ValSelRnd, and ValCommitLq are specific to integer interval variables and views and are discussed below.
Value selection classes. A value selection class must inherit from the class ValSel which again is parametric with respect to the view and value type. The constructors (one for creation and for cloning) are exactly the same as for merit classes discussed in the previous section.
Also, similar to merit classes, a value selection class can redefine the member functions notice() and dispose() if explicit disposal is required when the home-space is deleted.
In addition, the classes must define a member function val() that returns a value for a given view x as follows (i again is the position in the view array):
class ValSelMin : public ValSel<IntView,int> {
...
int val(const Space& home, IntView x, int i) {
return x.min();
}
};
...
Value commit classes. For our integer interval variables and views we need a single value commit class only (how many classes are needed depends of course on which value selection strategies are provided). A value commit class must inherit from the parametric class ValCommit and must implement one constructor for creation and one for cloning. In addition, it must define a commit() function, an ngl() function (to be discussed later), and a default print() function. The commit() function returns a modification event and takes the number of the alternative a, a view x, its position i, and a value n as arguments. The print() function takes an output stream o as additional argument:
// [int.hh:no-good literal class]
...
class ValCommitLq : public ValCommit<IntView,int> {
public:
...
ModEvent commit(Space& home, unsigned int a,
IntView x, int i, int n) {
return (a == 0) ? x.lq(home,n) : x.gq(home,n+1);
}
void print(const Space&, unsigned int a,
IntView, int i, int n,
std::ostream& o) const {
o << "x[" << i << "] "
<< ((a == 0) ? "<=" : ">") << " " << n;
}
// [int.hh:no-good literal creation]
};
No-good support. The value commit class must also implement a function ngl() that returns a no-good literal for an alternative. The idea is exactly the same as described in Supporting no-goods, the only difference is that the ngl() function here gets a view and a value as arguments rather than a choice.
The ngl() function of the ValCommitLq class returns a no-good literal implemented by the class LqNGL for the first alternative and NULL for the second alternative as follows:
NGL* ngl(Space& home, unsigned int a,
IntView x, int n) const {
return (a == 0) ? new (home) LqNGL(home,x,n) : nullptr;
}
The no-good literal class LqNGL used by the ngl() function is defined as follows:
class LqNGL : public ViewValNGL<IntView,int,PC_INT_BND> {
using ViewValNGL<IntView,int,PC_INT_BND>::x;
using ViewValNGL<IntView,int,PC_INT_BND>::n;
public:
LqNGL(Space& home, IntView x, int n);
LqNGL(Space& home, LqNGL& ngl);
virtual NGL* copy(Space& home);
virtual NGL::Status status(const Space& home) const;
virtual ExecStatus prune(Space& home);
};
It inherits from the template class ViewValNGL, which expects a view type, a value type, and a propagation condition as argument. The definition of the constructors, the copy() function, the status() function, and the prune() function are exactly as discussed in Supporting no-goods. The remaining functions for disposal and subscription are pre-defined by ViewValNGL.
User-defined value selection and commit functions. For the value selection function INT_VAL(v,c) for a user-defined value selection function v and a user-defined commit function c it is possible to leave out c, as it has been declared as an optional argument. When the argument is not provided, c is equal to nullptr. This is taken into account as follows:
if (!ivb.commit()) {
return new (home)
ValSelCommit<ValSelFunction<IntView>,
ValCommitLq>(home,ivb);
} else {
return new (home)
ValSelCommit<ValSelFunction<IntView>,
ValCommitFunction<IntView> >(home,ivb);
}
The classes ValSelFunction and ValCommitFunction are defined by Gecode and are parametric with respect to a view. They use the functions as specified by the object ivb.
38.5. Branchings¶
Implementing the actual branch() functions with and without tie-breaking is straightforward. They only have to create a brancher that uses the view selection creation function viewsel() from View selection creation and the value selection and commit creation function valselcommit() from Value selection and commit creation function.
Branching without tie-breaking.
inline void
branch(Home home, const IntVarArgs& x,
IntVarBranch vars, IntValBranch vals,
IntBranchFilter bf=nullptr,
IntVarValPrint vvp=nullptr) {
using namespace Int;
if (home.failed()) return;
vars.expand(home,x);
ViewArray<IntView> xv(home,x);
ViewSel<IntView>* vs[1] = {
viewsel(home,vars)
};
postviewvalbrancher<IntView,1,int,2>
(home,xv,vs,valselcommit(home,vals),bf,vvp);
}
Figure 38.6 Branch function¶
The branch() function is shown in Branch function. It creates an array of integer views IntView, expands a possibly missing integer action object, creates an array with a single view selector object returned by the function viewsel() as discussed in View selection creation and posts the view-value brancher of class ViewValBrancher through the function postviewvalbrancher(). The function is parametric, where the arguments describe the following:
The view type which is
IntViewin our case.The number of view selection objects to be used during view selection. As we are not using tie-breaking, the number is
1and corresponds to the number of elements in the arrayvs.The value type which is
intin our case.The number of alternatives that should be created during branching, which is
2in our example [2].
Branching with tie-breaking.
inline void
branch(Home home, const IntVarArgs& x,
TieBreak<IntVarBranch> vars, IntValBranch vals,
IntBranchFilter bf=nullptr,
IntVarValPrint vvp=nullptr) {
using namespace Int;
if (home.failed()) return;
vars.a.expand(home,x);
// [int.hh:normalizing tie-breaking]
ViewArray<IntView> xv(home,x);
if (vars.b.select() == IntVarBranch::SEL_NONE) {
...
} else if (vars.c.select() == IntVarBranch::SEL_NONE) {
ViewSel<IntView>* vs[2] = {
viewsel(home,vars.a), viewsel(home,vars.b)
};
postviewvalbrancher<IntView,2,int,2>
(home,xv,vs,valselcommit(home,vals),bf,vvp);
} else if (vars.d.select() == IntVarBranch::SEL_NONE) {
ViewSel<IntView>* vs[3] = {
viewsel(home,vars.a), viewsel(home,vars.b),
viewsel(home,vars.c)
};
postviewvalbrancher<IntView,3,int,2>
(home,xv,vs,valselcommit(home,vals),bf,vvp);
} else {
...
}
}
Figure 38.7 Branch function with tie-breaking¶
The branch() function with tie-breaking is shown in Branch function with tie-breaking. It takes an object vars of class TieBreak as argument, where vars.a is the first variable selection strategy of class IntVarBranch, vars.b the second, vars.c the third, and vars.d the forth and last to be used during tie-breaking.
Before creating the brancher, the variable selection strategies are normalized. As mentioned earlier, there should be no tie-breaking after the variable selection strategies INT_VAR_NONE() and INT_VAR_RND() (corresponding to SEL_NONE and SEL_RND, respectively). The normalization first tries to normalize var.b, then var.c and finally var.d as follows (the var.c and var.d case is analogous and hence omitted):
if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
(vars.a.select() == IntVarBranch::SEL_RND))
vars.b = INT_VAR_NONE();
vars.b.expand(home,x);
if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
(vars.b.select() == IntVarBranch::SEL_RND))
vars.c = INT_VAR_NONE();
vars.c.expand(home,x);
if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
(vars.c.select() == IntVarBranch::SEL_RND))
vars.d = INT_VAR_NONE();
vars.d.expand(home,x);
After normalization, the branch() function shown in Branch function with tie-breaking posts a brancher of class ViewValBrancher with the appropriate number of view selection objects by calling the postviewvalbrancher() function. In Branch function with tie-breaking, only the cases for two and three objects is shown, the other cases are analogous.
39. Variable tracing support¶
This chapter shows how to add variable tracing support for a new variable type.
namespace MPG { namespace Int {
// [int.hh:trace view]
}}
namespace MPG {
// [int.hh:trace delta]
}
namespace Gecode {
// [int.hh:trace traits]
}
namespace MPG {
// [int.hh:tracer and trace recorder]
// [int.hh:standard tracer]
// [int.hh:trace post function]
// [int.hh:trace post function convenience]
}
Figure 39.1 Part of header file concerned with tracing¶
Overview. Part of header file concerned with tracing shows the part of the header file concerned with tracing. Trace views are used to save the state of a view’s domain after it has been modified by a prune-event and trace deltas are used to compute the values that have been removed by a prune-event. They are discussed in Trace views and deltas. How tracers and trace recorders are instantiated is described in Tracers and trace recorders. Finally, Trace post functions describes how to actually post trace recorders through trace post functions.
39.1. Trace views and deltas¶
Trace views are used to save the domain of a view after a prune-event has occurred. When another prune event occurs, a trace view is used to compute a trace delta between the previously recorded domain and the current domain of the view. For our integer interval variables, the integer trace view stores the lower and upper bound as follows:
class IntTraceView {
protected:
int l, u;
public:
IntTraceView(void) {}
IntTraceView(Space& home, IntView x)
: l(x.min()), u(x.max()) {}
int min(void) const {
return l;
}
...
void update(Space& home, IntTraceView x) {
l=x.l; u=x.u;
}
// [int.hh:prune function]
// [int.hh:slack function]
};
The trace view is initialized by its constructor. It does not have to implement all functions of a view, only an update() function is needed and two functions that are specific to trace views.
Prune function. The prune function is executed when a prune-event has occurred. Here the integer view x is the view after the prune event and the modification delta d contains information about the prune-event. For integer interval variables it is sufficient to update the lower and upper bound of the trace view as follows:
void prune(Space& home, IntView x, const Delta& d) {
l=x.min(); u=x.min();
}
Slack function. For all other event types, the slack of a variable must be available, computed by a slack() function as follows:
static unsigned long long int slack(IntView x) {
return static_cast<unsigned long long int>(x.max() - x.min());
}
Here the slack is defined as the values that are still to be removed and to avoid numeric overflow for several views the return type is defined as unsigned long long int.
Trace delta. The trace delta provides information about which values have been removed by a prune-event. For integer interval variables, the trace delta is defined and computed as follows:
class IntTraceDelta {
protected:
int l, u;
public:
IntTraceDelta(Int::IntTraceView o, Int::IntView n, const Delta& d) {
if (n.min() > o.min()) {
l=o.min(); u=n.min()-1;
} else {
l=n.max()+1; u=o.max();
}
}
int min(void) const {
return l;
}
...
};
Note as integer interval variables are so simple, it would also have been possible to not store the lower and upper bound in the trace view but to extract the information from the modification delta d directly.
39.2. Tracers and trace recorders¶
For tracers and trace recorders it is sufficient to define some traits for tracing as follows:
template<>
class TraceTraits<MPG::Int::IntView> {
public:
typedef MPG::Int::IntTraceView TraceView;
typedef MPG::IntTraceDelta TraceDelta;
typedef unsigned long long int SlackValue;
};
Here the type names are self explanatory.
An integer tracer and trace recorder can be obtained by simple type definitions as follows:
typedef ViewTracer<Int::IntView> IntTracer;
typedef ViewTraceRecorder<Int::IntView> IntTraceRecorder;
If desired, one can also define a standard tracer for convenience:
class StdIntTracer : public IntTracer {
protected:
std::ostream& os;
public:
StdIntTracer(std::ostream& os0 = std::cerr) : os(os0) {}
...
static StdIntTracer def;
};
StdIntTracer StdIntTracer::def;
The implementation is not detailed here, see Programming general tracers for details.
39.3. Trace post functions¶
The trace post function is like a constraint post function: it creates integer views for the variables and then posts the trace recorder as follows:
inline void
trace(Home home, const IntVarArgs& x, TraceFilter tf,
int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
IntTracer& t = StdIntTracer::def) {
GECODE_POST;
ViewArray<Int::IntView> xv(home,x);
GECODE_ES_FAIL(IntTraceRecorder::post(home,xv,tf,te,t));
}
For convenience, the following post function allows to post a trace recorder without specifying any trace filter:
inline void
trace(Home home, const IntVarArgs& x,
int te = (TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE),
IntTracer& t = StdIntTracer::def) {
trace(home,x,TraceFilter::all,te,t);
}
40. Putting everything together¶
This chapter finally explains how integer interval variables can be used with Gecode.
Overview. Golomb rulers à la integer interval variables sketches an example script together with implementations of constraints and branchings using integer interval variables. The following section, Configuring and compiling Gecode, shows how Gecode can be configured to use integer interval variables and how to compile and run the example script.
Important
Please make sure to carefully read Compiling Gecode, before reading any further in this chapter!
40.1. Golomb rulers à la integer interval variables¶
#include "int.hh"
#include <gecode/search.hh>
using namespace MPG;
...
class GolombRuler : public Gecode::Space {
...
};
int main(int argc, char* argv[]) {
...
}
Figure 40.1 Golomb rulers à la integer interval variables¶
Golomb rulers à la integer interval variables shows the top-level structure of a single C++-file containing a script together with all required implementations of post functions, propagators, and branchers. The example script implements a naive version of the Golomb ruler model presented in Golomb rulers. The reason to package everything into a single C++-file is to simplify compiling the example.
The implementations of the constraints in the C++-file are carefully constructed to exercise most of the functionality described in the previous chapters in this part. In particular, some constraints have a slightly non-standard implementation to exercise all views presented in Views.
40.2. Configuring and compiling Gecode¶
The following steps configure and compile Gecode with integer interval variables:
Start a POSIX shell (for example, Bash or Zsh).
Create a new directory, say
MPG, and make it the current directory:mkdir MPG; cd MPGDownload the Gecode 6.4.0 source release from the Gecode GitHub releases page. Unpack it in the current directory and rename the extracted source directory to
gecode.If you have not yet done so, download and copy all files required for integer interval variables and the example into the current directory:
The header file
int.hhcontaining the implementation of integer interval variables.The variable implementation specification file
int.vis.The file
putting-everything-together.cppfrom the previous section.
Configure Gecode to incorporate integer interval variables and install into a local prefix:
cmake -S gecode -B gecode/build \ -DCMAKE_BUILD_TYPE=Release \ -DGECODE_WITH_VIS="$PWD/int.vis" \ -DCMAKE_INSTALL_PREFIX="$PWD/gecode-install"
After this step, Gecode has been configured to incorporate the generated definitions as described by the specification file
int.vis. Add any other CMake options required by your build environment.Compile and install Gecode:
cmake --build gecode/build --config Release cmake --install gecode/build --config Release
Add the local installation’s executables to the search path:
export PATH="$PWD/gecode-install/bin:$PATH"
On systems that require it, also add the installation’s
libdirectory to the library search path; for example, on Linux:export LD_LIBRARY_PATH="$PWD/gecode-install/lib${LD_LIBRARY_PATH:+:$LD_LIBRARY_PATH}"
Finally, compile, link, and run putting-everything-together.cpp as described in Compiling, linking, and executing, using gecode-install as the installation prefix. Its include and lib directories contain the headers and libraries for the custom variable implementation.