Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
Back to discussions
Expand all | Collapse all

Lazy constraints in CP Optimizer

  • 1.  Lazy constraints in CP Optimizer

    Posted Wed December 06, 2017 03:43 AM

    Originally posted by: Fab10


    Hi,

    I was wondering if it is possible to use something like CPLEX lazy constraints also in CP OPTIMIZER.

    Basically, I need to add a constraint on a variable iff another variable is set to a specific value.

    Thank you in advance

    Fabio


    #CPOptimizer
    #DecisionOptimization


  • 2.  Re: Lazy constraints in CP Optimizer

    Posted Wed December 06, 2017 05:22 AM

    Originally posted by: ol


    Hello,

    The usual way is to use a "meta-constraint" linking the truth values of x==a and of the constraint C you want to add, for example:
      model.add(IloIfThen(env, x==a, C));

    Note that 
    1/ C must be compatible with meta constraint (some global constraints like IloPack are not compatible),
    2/ C is checked even if x is not set to "a", and if C is false, then x!=a is enforced. So, this is not exactly what you ask for.

    If you rather want to have a guarded constraint, which ignores totally C until x is set to "a", you can define a custom constraint that reacts on assignments on x (thanks to the function whenValue()). When x is assigned a value "v", a "demon" is awaken to check whether "v" equals "a", in which case the constraint C is added.
    Note that, before to be added, the constraint C may become unsatisfiable due to domains reductions, but the value "a" will stay in the domain of x. If x is then assigned value "a", C will be added, will fail and lead to a backtrack.

    In case your need is the 2nd approach, and you want some help for defining a custom constraint, just tell us. 
    Regards,
    ol


       


    #CPOptimizer
    #DecisionOptimization


  • 3.  Re: Lazy constraints in CP Optimizer

    Posted Wed December 06, 2017 06:12 AM

    Originally posted by: Fab10


    Hi ol, thank you very much for your answer.

    My need is exactly the 2nd approach.

    I have to check whether two variables are set to true and if it's the case I have to add a constraint.

    I have tried the IloIfThen yet and I've noticed exactly what you pointed out, the constraint C is always checked and somehow added to the model thus this way was not good for me.

    What I need to do is the following

     

    if a== true && b==true

    then add the following constraint

    (diff[cnt] == z-k) || (diff[cnt] == 100 - (z-k))

     

    but I have also to increment the counter "cnt" by 1 iff the constraint is added.

    I know in advance the size of the IntVarArray diff.

     

    Could you please give me a hint on how to construct such constraint?

     

    Thank you again.

     

    Fabio


    #CPOptimizer
    #DecisionOptimization


  • 4.  Re: Lazy constraints in CP Optimizer

    Posted Thu December 07, 2017 09:40 AM

    Originally posted by: ol


    Hi Fabio,

    the counter is the main difficulty. I assume you have several pairs (a_i,b_i), which share the same counter cnt. Am I right?

    you want a kind of dominance rule, the first  pair (a_i,b_i) that is equal to (1,1) takes the current value of the counter. 

    This may be tricky to handle in CP, and if you can express the same behavior by using only modeling object (variables, constraints, objectives) it would be safer. I cannot help you to do that as it needs to have a complete view of your problem (hint: use objectives!). In the rest of the post, I assume you know exactly what you are doing, and I show you how to use such a counter.

     

    The counter must backtrack. There is no modeling objects to do that, but at the low level you have engine objects like IlcRevInt that you can use.

    At backtrack, the IlcRevInt object will restore its previous values. 

    You will find below an example of how to do this kind of thing. An IloConstraint is defined on IloVariables (indeed on arrays of variables to regroup all the pair (a_i,b_i) that share the same counter). This is mainly a wrapper around an IlcConstraintI which does the job. The counter is created when the corresponding IlcConstraint is created.

    If you run the test you will see that, in all solutions, when several pairs (a_i,b_i) are set to 1, then the value of the counter is incremented as you asked and used to set the corresponding variables v_i. 

    Note the parameter AutomaticReplay is set to off: the last solution found is replayed in CP Optimizer by default, but this is not compatible with the fact that depending on the order of the propagation, the value v_i can be different due to your dominance rule. So we need to set AutomaticReplay to off. 

    Do not hesitate if you need more explanations.

    Regards,

    ol

     

     

     

     


    #CPOptimizer
    #DecisionOptimization


  • 5.  Re: Lazy constraints in CP Optimizer

    Posted Thu December 07, 2017 03:45 PM

    Originally posted by: Fab10


    Hi ol,

    you are right, I've attached the piece of code so as to be more clear with my question (sorry for some italian comments).

    The part I would like to modify is the IloIfThen at line 44.

    What I would like to do is to add the constraint "(difference[cnt++] == (k*elements[k][j] - i*elements[i][j])) || (difference[cnt++]==(size-1 -(k*elements[k][j] - i*elements[i][j]))))" if and only if (elements[k][j] == true) && (elements[i][j] == true).

    If I use "cnt++" in conjunction with "IloIfThen" the counter cnt is incremented every time the "if" part is checked but this is not what I wanted thus I've asked for lazy constraints in CP optimizer. 

    I do not have pairs of variables sharing the same cnt, because I know in advance the number of times a pair of variables will be true.

    My need is to add that constraint iff the two variables are true and consequently increment the counter for the next two variables being true.

    I hope I've been a little more clear.

    Kind regards.

    Fabio 


    #CPOptimizer
    #DecisionOptimization


  • 6.  Re: Lazy constraints in CP Optimizer

    Posted Fri December 08, 2017 04:26 PM

    Originally posted by: ol


     Hi Fabio,
     
      
            > If I use "cnt++" in conjunction with "IloIfThen" the counter cnt is incremented 
            > every time the "if" part is checked 
            
            not exactly, the IloIfThen constraint does not see "cnt++". cnt++ is a C++ instuction, 
            and IloIfThen, from the c++ viewpoint is a function. Thus, cnt is incremented twice when the line 44 is executed: this is simply the c++ parameter evaluation process.
            
            I think the file I sent last time should do what you have in mind: just replace the IloIfThen by the constraint defined in the file, after having filled the arrays a and b as follows:
     
      IloIntVarArray a(env);
      IloIntVarArray b(env);        
      for (int j = 0; j < numBlocks; j++)
        for (int i = 0; i < elements.getSize() - 1; i++)
          for (int k = i + 1; k < elements.getSize(); k++) {
            IloInt delta=k-i;
            a.add(elements[k][j]);
            b.add(elements[i][j]);
          }
      model.add(IloMyConstraint(env, a, b, differences, delta));
      
      You aslso need:
      - to add a parameter (IlcInt delta) to the constraint
      - to modify the propagate and the demon of the constraint by
      
          if (_xa[i].isFixed() && _xa[i].getValue() == 1 && _xb[i].isFixed() && _xb[i].getValue() == 1) {
            IlcInt cntVal = _cnt->getValue();
            getCP().add(_v1[cntVal] == delta || _v1[cntVal] == size-1 - delta); 
            //size must be also given in parameter...
            //is it really size-1 - delta? I would think size - delta, since delta=k-i ranges from 1 to size-1
            _cnt->setValue(getCPEngine(), cntVal + 1);
          }
          
      I sent you this code last time because I thought you had a special need. By looking at your file, I am not sure defining a custom constraint like that is not an overkill. It depends on what you want to do with the array differences.
      Maybe you can just replace the iloIfThen constraints by computing a 3D array of gaps, the non-zeros will be the differences you want to compute (if we have size - delta and not  size-1 - delta).
     
            
            model.add(
              gap[i][j][k]== elements[k][j]*elements[i][j]*(k-i) || 
              gap[i][j][k]== elements[k][j]*elements[i][j]*(size-1 -(k-i)));
              
            After that you can for example flatten the gaps array in another array flatgap and use    
            other constraints or expression like IloCount(flatgap, 0). 

    #CPOptimizer
    #DecisionOptimization


  • 7.  Re: Lazy constraints in CP Optimizer

    Posted Sat December 09, 2017 11:35 AM

    Originally posted by: Fab10


    Dear ol,

    thank you very much for your answer. I will try your code and let you know.

    I know I can use a 3D array and there is another way to model my problem which uses two int arrays, but I was seeking for a model that implies the least number of constraint possible. I want to benchmark the three models to check which is the easiest to solve. 

    Thank you again. 

    Best regards.

    Fabio


    #CPOptimizer
    #DecisionOptimization


Related Content