Originally posted by: SystemAdmin

[tony.lopes said:]

Hi everybody!
I'm have some doubts about how the IloIfThen constraint propagates... See the following code:


// g++ -Wall -fPIC -DIL_STD -fexceptions -DILOUSEMT -D_REENTRANT -I/usr/ilog/solver62/include  -I/usr/ilog/concert22/include  -Wno-non-virtual-dtor -g -lpthread -m32 cp_test.cpp -L/usr/ilog/solver62/lib/x86_rhel4.0_3.4/static_pic -L/usr/ilog/concert22/lib/x86_rhel4.0_3.4/static_pic -lsolver -lsolverfloat -lilsolverdebug -lildebug -lconcert -o

#include <ilsolver/ilosolverint.h>
ILOSTLBEGIN

int main() {
  IloEnv env;
  try {
    IloModel model(env);
    IloIntVarArray vars(env, 4, 0, 10);

    --- INSERT MODELs HERE ---
 
    IloSolver solver(model);
    solver.solve(IloInstantiate(env,vars[0]));

    solver.out() << solver.getValue(vars&#91;0&#93;) << endl;<br />    solver.out() << solver.getValue(vars&#91;1&#93;) << endl;<br />    solver.out() << solver.getValue(vars&#91;2&#93;) << endl;<br />  }
  catch (IloException& ex) {
    cout << "Error: " << ex << endl;<br />  }
  env.end();
  return 0;
}



Ok, now I have 2 different models that you should insert in the indicated position:

First Model:

    model.add(IloIfThen(env,vars[3]==5, vars[1]==0 && vars[2]==1 ));
    model.add(IloIfThen(env,vars[0]<3,vars[3]==5));


Second Model:

    model.add(IloIfThen(env,vars[1]<vars[2], vars[1]==0 && vars[2]==1 ));   
    model.add(IloIfThen(env,vars[0]<3,vars&#91;1&#93;<vars&#91;2&#93;));<br />

The difference between the two models is that the second one uses an inequality to close the model.

Well, accordingly to my knowledge, IfThen constraints should use some internal binary variables. Being it that way, I thought that both models should be completely solved by only instantiating the first variable. But, it seems that this is not the case. I think that when the left part is an inequality (or some other kind of expression), the right part will only be valid when we can affirm the left part based on the domains, but not over a valid expression.

I don't know... but I think It's pretty bad. I know I should avoid IfThen, but It's really unavoidable for me, and I'd like to get the most of them.

Am I misunderstanding something here? Is there a way to make IloIfThen propagation better?

Thanks for the attention.
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[Sylvain said:]

I think you are facing one disadvantage of constraint programming, at least in its current commercial implementation. That is communication between different constraints is performed only through variable domains.
Here is what probably happens when you solve the two models :

First Model:
- If vars[0] is instantiated to a value lower than 3, then vars[3] is set to 5 (2nd IfThen).
  Then, vars[1] is set to 0 and vars[2] is set to 1 (1st IfThen).
- If vars[0] is instantiated to a value higher or equal to 3, then the domain of vars[3] becomes {0, 1, 2, 3, 4, 6, 7, 8, 9, 10} (2nd IfThen). No other propagation is performed (1st IfThen is useless)

Second Model:
- If vars[0] is instantiated to a value lower than 3, then the respective domains of vars[1] and vars[2] become {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (2nd IfThen).
  Then no more inference can be performed as the 1st IfThen only knows the domains of vars[1] and vars[2].
- If vars[0] is instantiated to a value higher or equal to 3, no propagation is performed.

I hope this is clear.
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

Being it that way, I thought that both models should be completely solved by only instantiating the first variable.

Tony,

I tested your models with ILOG CP Optimizer, in OPL, and -unless I misunderstood something- I think that what you expected happens.

The first model is

using CP;

dvar int vars[0..3] in 0..10;

constraints {

  vars[3] == 5 => (vars[1] == 0 && vars[2] == 1);
  vars[3] == 5;
  vars[0] < 3;<br />}


When you run it, you see that three variables are fixed at initial propagation, and only one decision closes the model

! ----------------------------------------------------------------------------
! Satisfiability problem - 4 variables, 7 constraints
! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
!  . Log search space  : 13.8 (before), 1.6 (after)
!  . Memory usage      : 315.4 Kb (before), 315.4 Kb (after)
!  . Variables fixed  : 3
! ----------------------------------------------------------------------------
!  Branches  Non-fixed                Branch decision                     
*          1      0.00s                vars(0)  =    0   
! ----------------------------------------------------------------------------
! Solution status        : Terminated normally, solution found
! Number of branches    : 1
! Number of fails        : 0
! Total memory usage    : 473.2 Kb (331.4 Kb CP Optimizer + 141.7 Kb Concert)
! Time spent in solve    : 0.00s (0.00s engine + 0.00s extraction)
! Search speed (br. / s) : 100.0
! ----------------------------------------------------------------------------



The second model is

using CP;

dvar int vars[0..3] in 0..10;

constraints { 
  vars[1]<vars[2] => (vars[1]==0 && vars[2]==1);
  vars[0] < 3;<br />  vars[1]<vars&#91;2&#93;; <br />}


And has the same behavior (except that vars[3] is unused which changes the search space size)

! ----------------------------------------------------------------------------
! Satisfiability problem - 3 variables, 7 constraints
! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
!  . Log search space  : 10.4 (before), 1.6 (after)
!  . Memory usage      : 315.4 Kb (before), 315.4 Kb (after)
!  . Variables fixed  : 2
! ----------------------------------------------------------------------------
!  Branches  Non-fixed                Branch decision                     
*          1      0.00s                vars(0)  =    0   
! ----------------------------------------------------------------------------
! Solution status        : Terminated normally, solution found
! Number of branches    : 1
! Number of fails        : 0
! Total memory usage    : 474.2 Kb (331.4 Kb CP Optimizer + 142.7 Kb Concert)
! Time spent in solve    : 0.00s (0.00s engine + 0.00s extraction)
! Search speed (br. / s) : 100.0
! ----------------------------------------------------------------------------


#CPOptimizer
#DecisionOptimization