IBM ILOG Solver User's Manual > Extending the Library > Writing a Constraint: Allocating Frequencies > Writing a constraint: Two examples > A new class of constraint using demons |
A new class of constraint using demons |
INDEX
![]() |
Let's consider the constraint x <= y + c, where x and y are constrained integer expressions, and c is a constant integer. Here's a rule to serve as a model of the semantics of that constraint.
The constraint must be propagated when one of the boundaries of x or y is modified.
The negation of the constraint is y <= x - c - 1.
With that semantic model in mind, you can define the corresponding class of constraints like this:
class IlcLeConstraint: public IlcConstraintI { // x <= y + c IlcIntExp _x; IlcIntExp _y; IlcInt _c; public: IlcLeConstraint(IloSolver solver, IlcIntExp x, IlcIntExp y, IlcInt c=0) : IlcConstraintI(solver), _x(x), _y(y), _c(c){} void post(); void propagate(); IlcBool isViolated() const; void metaPostDemon(IlcDemonI*); IlcConstraintI* makeOpposite() const; }; void IlcLeConstraint::post(){ _x.whenRange(this); _y.whenRange(this); } void IlcLeConstraint::metaPostDemon(IlcDemonI* demon){ _x.whenRange(demon); _y.whenRange(demon); } IlcBool IlcLeConstraint::isViolated() const { return _x.getMin() > _y.getMax() + _c; } void IlcLeConstraint::propagate(){ _y.setMin(_x.getMin() - _c); _x.setMax(_y.getMax() + _c); } IlcConstraintI* IlcLeConstraint::makeOpposite() const { IloSolver solver=getSolver(); return new (solver.getHeap()) IlcLeConstraint(solver,_y,_x,-_c -1); } IlcConstraint IlcLeConstraint(IlcIntExp x, IlcIntExp y, IlcInt c){ IloSolver solver=x.getSolver(); return IlcConstraint(new (solver.getHeap()) IlcLeConstraint(solver,x,y,c)); }
The constraint is defined with IlcIntExp
, and not with IlcIntVar
, in order to avoid the creation of new constrained integer variables.
You can use auxiliary demons for this constraint, instead of calling propagate
for all propagations. Indeed, when the minimum of x is modified, you only need to apply the first of the two rules:
The new definition is thus:
class IlcLeConstraint: public IlcConstraintI { // x <= y + c IlcIntExp _x; IlcIntExp _y; IlcInt _c; public: IlcLeConstraint(IloSolver solver, IlcIntExp x, IlcIntExp y, IlcInt c=0) : IlcConstraintI(solver), _x(x), _y(y), _c(c){} void post(); void propagate(); IlcBool isViolated() const; void metaPostDemon(IlcDemonI*); IlcConstraintI* makeOpposite() const; void xDemon(){ _y.setMin(_x.getMin() - _c); } void yDemon(){ _x.setMax(_y.getMax() + _c); } }; ILCCTDEMON0(IlcLeConstraintXDemon,IlcLeConstraint,xDemon); ILCCTDEMON0(IlcLeConstraintYDemon,IlcLeConstraint,yDemon); void IlcLeConstraint::post(){ _x.whenRange(IlcLeConstraintXDemon(getSolver(),this)); _y.whenRange(IlcLeConstraintYDemon(getSolver(),this)); } void IlcLeConstraint::metaPostDemon(IlcDemonI* demon){ _x.whenRange(demon); _y.whenRange(demon); } IlcBool IlcLeConstraint::isViolated() const { return _x.getMin() > _y.getMax() + _c; } void IlcLeConstraint::propagate(){ xDemon(); yDemon(); } IlcConstraintI* IlcLeConstraint::makeOpposite() const { IloSolver solver=getSolver(); return new (solver.getHeap()) IlcLeConstraint(solver,_y,_x,-_c -1); } IlcConstraint IlcLeConstraint(IlcIntExp x, IlcIntExp y, IlcInt c){ IloSolver solver=x.getSolver(); return IlcConstraint(new (solver.getHeap()) IlcLeConstraint(solver,x,y,c)); }
The differences from the previous definition appear in the member functions xDemon
, yDemon
, and propagate
, and in the two demons IlcLeConstraintXDemon
and IlcLeConstraintYDemon
.
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |