KUserConstraint

class KUserConstraint : public KConstraint

Abstract interface class for definition of user constraints

To create your own constraints in Artelys Kalis, you must create a specific class that inherits from the KUserConstraint class. Then, you need to implement the pruning scheme corresponding to the semantic of your constraint by overloading the propagate method or awakeOnXXX methods for incremental propagation of the constraint

  • the awake method is launched one time upon initialization of the constraint

  • the awakeOnInf method is launched when the lowerbound of a variable increase

  • the awakeOnSup method is launched when the upperbound of a variable decrease

  • the awakeOnRem method is lanched when a specific value has been removed from the domain of a variable

  • the awakeOnInst method is launched when a variable has been instantiated to a value

  • the awakeOnVar method is launched when the domain of one specific variable has changed

  • the propagate method is launched when one or more variables have seen their domain modified

  • askIfEntailed method is called when the constraints is used within a boolean connector (KGuard, KEquiv, KDisjunction, KConjunction). It should return :

    • CTRUE whenever the constraint is definitively verified

    • CFALSE whenever the constraint is definitively violated

    • CUNKNOWN otherwhise

The awake, propagate and print methods be overloaded (pure virtual functions). The default behavior of the awakeOnInf, awakeOnSup, awakeOnInst, awakeOnVar and awakeOnRem is to call the propagate method.

Additionally, it is necessary to implement the getInstanceCopyPtr(const KProblem& problem) that returns a copy pointer of the user constraint by calling the KProblem::getCopyPtr() on each modelling object used in the constraint.

Here is an example of user defined constraint definition : V1 == V2 % modulo

// ModuloConstraint class inherits from KUserConstraint class
class ModuloConstraint : public KUserConstraint {

private:
    // Modulo constant
    int _modulo;
    // Variables V1 and V2
    KIntVar* _v1;
    KIntVar* _v2;

public:
    // Primary constructor of the constraint V1 == V2 % modulo
    ModuloConstraint(KIntVar &v1, KIntVar &v2, const int modulo);
    // Destructor
    virtual ~ModuloConstraint();
    // Virtual copy method
    virtual KConstraint* getInstanceCopyPtr(const KProblem& problem) const;
    // Propagation methods
    virtual void awake(void);
    virtual void propagate(void);
    virtual void awakeOnInst(KIntVar & var);
    virtual void print();
    // For use within boolean connectors
    virtual int askIfEntailed(void);
};

// Main constructor
ModuloConstraint::ModuloConstraint(KIntVar &v1, KIntVar &v2, const int modulo) : KUserConstraint(v1,v2) {
    _modulo = modulo;
    _v1 = &v1;
    _v2 = &v2;
}

// Destructor
ModuloConstraint::~ModuloConstraint() {
}

// Virtual copy method
KConstraint * ModuloConstraintXYC::getInstanceCopyPtr(const KProblem& problem) const {
    return new ModuloConstraintXYC(*problem.getInstanceOf(_v1), *problem.getInstanceOf(_v2), _modulo);
}

// initial propagation of the constraint
void ModuloConstraint::awake() {
    propagate();
}

// Some variables of the constraints have seen their domain reduced... must propagate the changes
void ModuloConstraint::propagate() {
    int v0, v1;
    std::cout << "ModuloConstraint#Propagate()" << std::endl;
    // V1 is trivialy bounded by 0 <= V1 <= modulo - 1
    _v1.setInf(0);
    _v1.setSup(_modulo-1);
    // Arc consistent filtering
    // First from V1 to V2
    for ( v1 = _v2.getInf();v1<=_v2.getSup();v1 ++) {
        bool supporte = false;
        for ( v0 = _v1.getInf();v0<=_v1.getSup();v0 ++) {
            // check if v0 == v1 % _modulo hold
            if ( v0 == v1 % _modulo)  {
                // value v0 is a support for value v1 of variable V2
                supporte = true;
                break;
            }
        }
        if ( !supporte) {
        // no support was found for value v1 of variable V2 so we can safely remove it from its domain
        _v2.remVal(v1);
        }
    }
    // Then from V2 to V1
    for ( v0 = _v1.getInf(); v0 <= _v1.getSup(); v0++) {
        bool supporte = false;
        for ( v1 = _v2.getInf(); v1 <= _v2.getSup(); v1++) {
            // check if v0 == v1 % _modulo hold
            if ( v0 == v1 % _modulo)  {
                // value v1 is a support for value v0 of variable V1
                supporte = true;
                break;
            }
        }
        if ( !supporte) {
        // no support was found for value v0 of variable V1 so we can safely remove it from its domain
        _v1.remVal(v0);
        }
    }

}

int ModuloConstraint::askIfEntailed() {
    if (_v1.getIsInstantiated() && _v2.getIsInstantiated() ) {
        if ( _v1.getValue() == _v2.getValue() % _modulo ) {
            // The constraint is definitly verified
            return CTRUE;
        }
        else {
            // The constraint is definitly violated
            return CFALSE;
        }
    }
    else {
        // Don't know yet if the constraint is definitly violated or verified
        return CUNKNOWN;
    }
}

// The variable "var" has been instantiated to var.getValue()
void ModuloConstraint::awakeOnInst(KIntVar & var) {
    int v;

    std::cout << "ModuloConstraint#awakeOnInst" << std::endl;

    if ( var.isEqualTo(_v1) ) {
        //  V1 was instantiated
        for ( v = _v2.getInf();v<=_v2.getSup();v ++) {
            if (_v1.getValue() != v % _modulo)
                _v2.remVal(v);
        }
    }
    else if ( var.isEqualTo(_v2) ) {
        //  V2 was instantiated
        for ( v = _v1.getInf();v<=_v1.getSup();v ++) {
            if ( v != _v2.getValue() % _modulo)
                _v1.remVal(v);
        }
    }
}

// For pretty printing purposes
void ModuloConstraint::print() {
        std::cout << "ModuloConstraint";
}

KProblem problem(...);
KIntVar A(problem, "A", 0, 20);
KIntVar B(problem, "B", 0, 10);
// Now creating the constraint A == B % 7
ModuloConstraint modCst(A, B, 7);
// Now posting the constraint to the problem
problem.post(modCst);
// ...

See

KConstraint

Since

2016.1

Public Types

enum askRet

Return values for askIfEntailed

Values:

enumerator CUNKNOWN

Unkown status of constraint.

enumerator CFALSE

Constraint is proven false.

enumerator CTRUE

Constraint is proven true.

Public Functions

KUserConstraint(KIntVar &v1)

Constructor for unary constraints.

KUserConstraint(KIntVar &v1, KIntVar &v2)

Constructor for binary constraints.

KUserConstraint(KIntVarArray &vars)

Constructor for n-ary constraints.

KUserConstraint(const KUserConstraint &toCopy)

Copy constructor.

virtual KConstraint *getCopyPtr() const

Virtual copy method. Must be implemented by the user.

virtual KConstraint *getInstanceCopyPtr(const KProblem &problem) const

Virtual instance copy method. Each modeling elements stored (and used) in the user constraint must be copied using the KProblem::getInstanceOf() methods. Must be implemented by the user when solving problems in parallel.

virtual void propagate()

Virtual method called when the domain of some or several variables has changed.

virtual void awake()

Virtual method called upon initialization of the constraint.

virtual void awakeOnInf(KIntVar &var)

Virtual method called when the lower bound of var has been raised.

virtual void awakeOnSup(KIntVar &var)

Virtual method called when the upper bound of var has been lowered

Parameters

var – the variable with modified domain

virtual void awakeOnInst(KIntVar &var)

Virtual method called when the variable var has been instantiated

Parameters

var – the variable with modified domain

virtual void awakeOnRem(KIntVar &var, int removedValue)

Virtual method called when the value removedValue has been removed from the domain of var

Parameters
  • var – the variable with modified domain

  • removedValue – the value that has been removed from the domain of var

virtual void awakeOnVar(KIntVar &var)

Virtual method called when the domain of variable var has changed

Parameters

var – the variable with modified domain

virtual int askIfEntailed(void)

Virtual method for use within boolean connectors

Returns

CTRUE whenever the constraint is definitively satisfied

Returns

CFALSE whenever the constraint is definitively violated

Returns

CUNKNOWN otherwhise

virtual void print(std::ostream &fout) const

Pretty printing of the constraint

virtual void print(void) const

Pretty printing the constraint to standard output stream.

virtual KLinearRelaxation *getLinearRelaxation(int strategy)

Linear Relaxation.