Originally posted by: valkiri

Hello .

My is if it is possible to implement integrally Implement MAC(Maintain Arc Consistency) on CP Optimizer.

Thanks.

Originally posted by: ol

Hello,

Not sure I understand exactly what you mean by "implementing integrally". I see 3 kinds of answers:

you can write a depth first search that achieves arc consistency at each node very simply by using IlcGoal to build the tree search and adding constraints in the goals. Goals are combined with "and" and "or" and adding constraints is reversible on backtrack.

Maybe you mean arc consistency on CSP constraints, i.e., constraint given in extension. In this case you can use allowed assignments constraints.

If you want to implement yourself the propagation of the constraints given in extension, you can define your own constraints.

Regards,

Olivier

Originally posted by: valkiri

Thanks ol.

I want to implement something like branch and bound. And i want to control which decision will be take if the search fund a solution.

I want  to control the backtracking after search fund a solution in order to explore all solution and when i  want. I know that it's possible to achieve this in intern with trick of CP engine and Concert Technology. But in my case i want to implement it in a goal. For this reason i search to know it possible to achieve this with CP Optimizer.

Thanks.

Regards,

valkiri.

Originally posted by: ol

Hello,

you may want to start with:

ILCGOAL2(MyIntInstantiate,
                IlcIntVar, var,
                IlcIntSelectI*, select) {
    if (var.isFixed()) return 0;
    IlcInt val = (select)? select->select(var) : var.getMin();
    return IlcOr(var == val, IlcAnd(var != val,
                                    this));
}
 
 
ILCGOAL3(MyIntGenerate,
         IlcIntVarArray, vars,
         IlcChooseIntIndex,   chooseIndex,
         IlcIntSelectI*, select){
  IlcInt index = chooseIndex(vars);
  if(index == -1) return 0;
  return IlcAnd(MyIntInstantiate(getCP(),
                                     vars[index],
                                     select),
                this);
}

IlcGoal MyGenerate(const IlcIntVarArray array,
                    IlcChooseIntIndex chooseIndex){
  return MyIntGenerate(array.getCP(),
                        array,
                        chooseIndex,
                        0);
}

IlcGoal MyGenerate(const IlcIntVarArray array,
                    IlcChooseIntIndex chooseIndex,
                    IlcIntSelect select){
  return MyIntGenerate(array.getCP(),
                        array,
                        chooseIndex,
                        select.getImpl());

Originally posted by: valkiri

Thanks ol.

I understand how this code work . Now what can i do after to control the search. 

Thanks.

ILCGOAL2(MyIntInstantiate,      IlcIntVar, var, IlcIntSelectI*, select) {
        if (var.isFixed()) return 0;
        IlcInt val = (select) ? select->select(var) : var.getMin();
        return IlcOr(var == val, IlcAnd(var != val,     this));
}

ILCGOAL3(MyIntGenerate, IlcIntVarArray, vars,   IlcChooseIntIndex, chooseIndex, IlcIntSelectI*, select){
        IlcInt index = chooseIndex(vars);
        if (index == -1) return 0;
        return IlcAnd(MyIntInstantiate(getCP(), vars[index],select),this);
}

IlcGoal MyGenerate(const IlcIntVarArray array,  IlcChooseIntIndex chooseIndex){
        return MyIntGenerate(array.getCP(),     array,chooseIndex,0);
}

IlcGoal MyGenerate(const IlcIntVarArray array, IlcChooseIntIndex chooseIndex, IlcIntSelect select){
        return MyIntGenerate(array.getCP(), array, chooseIndex, select.getImpl());
}

ILOCPGOALWRAPPER1(NCSearch,cp, IloIntVarArray, x){
        return MyGenerate( cp.getIntVarArray(x), IlcChooseFirstNonFixedInt, 0);
}

int main(){
        IloEnv env;
        IloIntVar x(env, -1, 3);
        IloIntVar y(env, 2, 5);
        IloIntVarArray array(env);
        array.add(x);
        array.add(y);
        IloModel model(env);
        model.add(array[0] >0);
        model.add(array[1] <5);
        model.add(array[0] <= array[1]);
        model.add(IloMaximize(env,IloSum(array)));
        IloCP cp(model);
        if(cp.solve(NCSearch(env,array))){
                cp.out() << "obj=" << cp.getObjValue() << endl;
                cp.out() << "x1=" << cp.getValue(array[0]) << endl;
                cp.out() << "x2=" << cp.getValue(array[1]) << endl;
        }
        env.end();
        system("PAUSE");
        return 0;
}

Originally posted by: Petr Vilím

Hello Valkiri,

reading through the whole thread I want to comment first a few things.

You mentioned you want to implement something like branch and bound. That's not what CP Optimizer is doing. CP Optimizer use simple depth-first tree search. There's no list of open nodes and possibility to jump from one part of the search tree to a completely different part of the search tree. You can only further explore the current node by branching on some decision (and IloOr goal). In that case CP Optimizer will explore the subnodes in the order specified by IloOr. Then when "fail" occurs (either because infeasibility was detected or because you call fail explicitly from a goal) then CP Optimizer first backtracks to the nearest IloOr with an open branch and takes that open branch. This way the whole search tree is explored in depth-first way. The main reason why CP Optimizer is using pure depth-first search is that internally it has a lot of reversible data structures that allows fast dives and backtracks, but not jumps from one state to another.

When you change a domain of a variable in a goal (e.g. assign it some value) then it automatically triggers constraint propagation. Constraints are propagated until no more changes could be inferred or until an infeasibility is detected (fail). So functions such as IlcIntVar::setMin or IlcIntVar::setValue not only affect the current variable, but through constraint propagation also other variables.

To answer your question, if you mean by "controlling the search" that you want to do "something like branch and bound" then the answer: there is no useful way to do it. All the power of CP Optimizer thanks to the reversible data structures would go away.

Another answer to ask is why do you want branch and bound in the first place. Default search in CP Optimizer doesn't work well for your problem? The first thing we usually advice is to try to model the problem differently. Could you share with us what problem do you want to solve? Maybe we can give you better advice.

Petr

Originally posted by: valkiri

Thanks Petr Vilim for your reply.

sorry  i just see your other  reply. I think that it's what  i've need . To be more clear I want to implement some search strategy in CP Optimizer . For this reason i have to understand how  CP Optimizer work in low level. Then i can use these knowledge to implement my search strategy. IBM cp optimizer extension manual don't  give enough information on CP optimizer low level function. So i want you to advice me what i need to know in CP Optimizer low level classes  and  functions  in order to implement a basic search strategy. If there is a book who explain this, he  can help me. If i can have an example with code it can help me on how to use fail() function because  cp optimizer user manual extension  don't provide an example of use of void fail() . Thanks very much .

Valkiri.

Originally posted by: Petr Vilím

It seems that you insist on calling fail() in your goal. The thing is *you should not* call fail in the goal. That's why there is not example and why I'm not going to give you any example. As I wrote earlier, fail should be called from constraints, not from goals. There are some very very specific cases when it makes sense to call fail from a goal (namely "dominance rules"), but I don't want to confuse you with it.

You asked about "low level". There is no lower level than IlcAnd and IlcOr. That's really all, everything else is done automatically for you, and so CP Optimizer doesn't even provide a lower level API than IlcOr and IlcAnd. Fail is called automatically by constraint propagation (and you normally should not call it yourself). Fail automatically triggers backtracking. Solutions are remembered automatically once you're goal finishes. Objective cuts are added automatically once a solution is found so that constraint propagation makes sure that only better solutions could be find in the rest of the search. If you want to write your own search, the only thing you have to specify is how to branch: should we assign first a value to variable x or variable y? And what value should we try first? For example, your procedure may choose to first assign value to variable x and do x=2 in left branch and x<>2 in right branch (using IlcOr). Please reconsider in this regard the examples above.

Best regard, Petr

Originally posted by: valkiri

Thanks a lot Petr Vilim.

You avoid me to waste my time with fail() function. 

Please ,with Depth first search strategy in CP Optimizer, i assume that i have a search tree ST1 which i want to explore. Is it possible on CP Optimizer if i fund a solution s1 in ST1 , i create another search tree ST2  with ST1 decisions variables with smaller domain size and i explore integrally ST2. After explore ST2 i continue explore ST1 at the point s1 and so on util  i explore integrally ST1.

ILCGOALn(){

IlcAnd(IlcAnd(Search_One_Solution_In_ST1,Create_And_Explore_Allsolution_In_ST2),this);

}

Best regard 

Valkiri

Originally posted by: Petr Vilím

Hello,

yes, it is possible. You just need two IloCP objects: one for ST1 and and the second for ST2. In order to avoid big amount of unused memory I also recommend to use to IloEnv objects, one for each IloCP. The two models should not share objects. Here is a sketch of the code:

IloEnv env1;
IloModel model1(env1);
// Create model1
IloCP cp1(model1);
cp1.startSearch(/* no parameter, search phases or a goal here*/);
while (cp1.next()) {
  // We just found a solution in ST1.
  // The solution in ST1 is accessible by functions such as cp1.getValue.
  IloEnv env2;
  IloModel model2(env2);
  // Create model2, possibly using the information from the current solution in ST1
  cp2.solve();
  // ...
  env2.end(); // Important, otherwise there will be memory leak.
}


Petr