Originally posted by: valkiri

Hi,

I want know how to implement a custom search algorithm in IBM's ILOG CP optimizer.For example , if i do cp.solve(CustomSearch(env)); how can i get the model in the IlcGoalI::execute() to perform the custom search . 

Can you show it to me by a small model and Depth First Search example ?

Thanks.

Originally posted by: rdumeur

Dear valkiri,

As you define your own IlcGoal you can associate whatever data with it. The  ILOCPGOALWRAPPER macro creates an IloGoal that will extract the model data that will be used during search performed by the ILCGOAL. Here is a small example that I hope will help you:

#include <ilcp/cpext.h>

using namespace std;

ILCGOAL1(AssignGoal, IlcIntVarArray, array) {
  IlcGoal       goal;
  for(IlcInt i = 0; i < array.getSize(); ++i) {
    if(! array[i].isFixed()) {
      goal = IlcAnd(IlcOr(array[i] == array[i].getMin(),
                          array[i] != array[i].getMin()), this);
      break;
    }
  }
  return goal;
}

ILOCPGOALWRAPPER1(AssignWrapper, cp, IloIntVarArray, array) {
  return AssignGoal(cp, cp.getIntVarArray(array));
}

int main() {
  IloEnv                env;
  IloModel              model(env);
  IloIntVarArray        array(env, 10, 1, 10);
  model.add(IloAllDiff(env, array));
  IloCP                 cp(model);
  cp.setParameter(IloCP::Workers, 1); // single worker mode.
  if(cp.solve(AssignWrapper(env, array))) {
    for(IloInt i = 0; i < array.getSize(); ++i) 
      cout << "var#" << i << "= " << cp.getValue(array[i]) << endl;
  }
  return 0;
}

Edit: suppressed the search type parameter which is useless when specifying a search goal

Originally posted by: valkiri

Thank you very much for your suggestion.  

I have another   question about parallel search . I resume this in this steps :

1-I extract the model data in my IlcGoal and begin the search (first search).

2-I make a copy of this model data and solve this copy without change the original model.

3-Use the result of this copy model to add a constraint  on the objective function of the first search (second search).

Thanks .

Originally posted by: rdumeur

Dear valkiri,

I am a bit confused, because you seem to describe a sequential process, where the result of the first solve is exploited to change initial the model and perform a second solve.

If you actually need to preserve a copy of the initial model, I suggest you wrap your model-building code in a function (e.,g, IloModel BuildMyModel(IloEnv)).

But what you describe can be achieved by modifying the initial model after the first solve:

  if(cp.solve(FirstWrapper(env, array))) {
    ... // get desired information from the foun solution
    model.add(IloMinimize(<some criterion made up from the info>));
    if(cp.solve(SecondWrapper(env, array)) {
       // process final result
    }
  }

Is that what you mean?

Cheers,

Originally posted by: valkiri

Thanks a lot Dear rdumeur.

I want to implement  this sequence process in my IlcGoal not in the main function.

IlcGoal1(SolveGoal,IlcIntVarArray,x){

IloModel copyModel= getCopy(OriginalModel);

Change(copyModel);

Solve(copyModel);

getInformaion();

addConstraint( to the OriginalModel);

return solve(OriginalModel);

}

I want to know also how can i change a model during a search by adding a new constraint.

thanks.

Originally posted by: rdumeur

Dear valkiri,

You don't need to copy the model because you can use internal solves that will restore the state of the solver. Please consider the following code where a single goal RootGoal performs 3 internal solves (one that sets new constraints to the model). Please have a look to the CP optimizer C++ API methods IloCP::add and IloCP::solve(IlcGoal, IlcBool).

I hope this helps,

ILCGOAL1(AssignGoal, IlcIntVarArray, array) {
  IlcGoal       goal;
  for(IlcInt i = 0; i < array.getSize(); ++i) {
    if(! array[i].isFixed()) {
      goal = IlcAnd(IlcOr(array[i] == array[i].getMin(),
                          array[i] != array[i].getMin()), this);
      break;
    }
  }
  return goal;
}

ILCGOAL2(StoreResult, IlcIntVarArray, array, IlcIntArray, values) {
  for(IlcInt i = 0; i < array.getSize(); ++i) 
    values[i] = array[i].getValue();
  return 0;
}

ILCGOAL2(AssignWithConstraints, IlcIntVarArray, array, IlcIntArray, values) {
  IloCP cp = getCP();
  for(IlcInt i = 0; i < array.getSize()/2; ++i) 
    cp.add(array[i] != values[i]);
  return AssignGoal(cp, array);
}

ILCGOAL1(RootGoal, IlcIntVarArray, array) {
  IloCP         cp = getCP();
  IlcIntArray   values(cp, array.getSize());
  cp.solve(IlcAnd(AssignGoal(cp, array), StoreResult(cp, array, values)), IlcTrue);
  cp.out() << "without constraint: ";
  for(IlcInt i = 0; i < values.getSize(); ++i) cp.out() << " " << values[i];
  cp.out() << endl;
  cp.solve(IlcAnd(AssignWithConstraints(cp, array, values), StoreResult(cp, array, values)), IlcTrue);
  cp.out() << "with constraint";
  for(IlcInt i = 0; i < values.getSize(); ++i) cp.out() << " " << values[i];
  cp.out() << endl;
  cp.solve(IlcAnd(AssignGoal(cp, array), StoreResult(cp, array, values)), IlcTrue);
  cp.out() << "again without constraint";
  for(IlcInt i = 0; i < values.getSize(); ++i) cp.out() << " " << values[i];
  cp.out() << endl;
  return 0;
}

ILOCPGOALWRAPPER1(RootWrapper, cp, IloIntVarArray, array) {
  return RootGoal(cp, cp.getIntVarArray(array));
}

int main() {
  IloEnv                env;
  IloModel              model(env);
  IloIntVarArray        array(env, 10, 1, 10);
  model.add(IloAllDiff(env, array));
  IloCP                 cp(model);
  cp.setParameter(IloCP::Workers, 1); // single worker mode.
  cp.solve(RootWrapper(env, array));
  cp.end();
  env.end();
  return 0;
}

Originally posted by: valkiri

Hi .

I'm beginner in CP Optimizer. I know that CP Optimizer internal solver use parallel search to solve a problem .

I want to know how to use workers to write a parallel search algorithm.

Thanks.

Originally posted by: PhilippeLaborie

If you can implement your search by only changing the parameters of the automatic search of CP Optimizer (search parameters, search phases, starting point solutions) then you can directly benefit from the parallel search implemented by the automatic search.

If not, then CPO does not provide support for implementing your own parallel search. You will have to do it yourself. Note that IloCP is multi-thread safe so there is no problem in having different instances of IloCP running in parallel.

Originally posted by: valkiri

.Hi.

I try the suggestion of rdumeur for   cp.solve(IlcGoal,IlcTrue) in my own goal and notice two things when i execute  cp.solve(RootWrapper(env, array)); in  the main function:

1-cp.solve(IlcGoal,IlcTrue) get only the first solution.

2-When i add an objective function the goal RootWrapper(env, array) is executed twice and i don't understand why.

My goal is to solve the first model M1( who is built  in the main function)  in my ILCGOAL and get the decision variable value and the objective function value. After that create another model M2(who is the copy of M1 with change of decision variables domain ) in the same ILCGOAL  and solve M2 and get the optimal solution.

I don't know if it possible to do this in CP Optimizer . If anyone can help me.

Thanks.

Originally posted by: PhilippeLaborie

Hello,

Could you clarify what you are trying to achieve?

You write:

IlcGoal1(SolveGoal,IlcIntVarArray,x){
  IloModel copyModel= getCopy(OriginalModel);
  Change(copyModel);
  Solve(copyModel);
  getInformaion();
  addConstraint( to the OriginalModel);
  return solve(OriginalModel);
}

But what do you mean by OriginalModel? The concert IloModel that was extracted by the IloCP and is currently being solved (but this model is not impacted by the search, so it is really the original model) or the original model WITH the current decisions taken in the search goal (Goal1) ?

If it is really the original model, then why don't you use another instance of IloCP to solve it?

If it is the current state of the solver, then the situation will depend on what you mean by Change(copyModel): it is a monotonous change that add some constraint or restrict the range of some variable or can it be any change (like removing a constraint, enlarging the domain of variables...). If it is monotonous you can use an internal solve and just post the additional constraints/variables restriction at the beginning of the internal goal. If the change is not monotonous, you would again better work with another instance of IloCP.

Originally posted by: valkiri

Dear PhilipeLaboire i really  want to achieve this process and i think that parallel search can perhaps achieve this . I don't know how to implement this in cp optimizer . 

Thanks.

Originally posted by: PhilippeLaborie

Thank you, but it does not really say what you are doing in the search goal MySearch. Usually one creates a search goal to explore a search tree, which search tree are you exploring here? Are you trying to implement some sort of Large Neighborhood Search where you iteratively solve a model M' that is build from a solution by locally relaxing some variables (so a more constrained form of the original model M) ?  In this case you do not really need to do it inside a search goal.

Originally posted by: valkiri

Thank you dear PhilippeLaboire .

I think that  you are right it's a  sort of Large Neighborhood Search.I'm working on my final project in computer study. And my goal is to implement this in a search goal.But i don't know if CP Optimizer allow to implement it. If it's possible how to  iteratively build and  solve the model M'.

Thanks. 

Originally posted by: PhilippeLaborie

Then you could write this algorithm outside of an IlcGoal. Something like:
 

IloNumExpr objective  = YOUR OBJECTIVE EXPRESSION
IloModel   model      = YOUR ORIGINAL MODEL

IloSolution currentSolution(env); // YOU CAN USE IloSolution OR ANYTHING ELSE TO STORE CURRENT SOLUTION

IloCP cp(model);

// Initial solution 
cp.startNewSearch();
if (cp.next()) {
  cp.store(currentSolution);
} else {
  REPORT PROBLEM IS INFEASIBLE AND STOP
}
IloNum currentObjective = cp.getObjValue();

while ( ! STOP CONDITION ) {
  
  IloConstraint restrictions = IloAnd(
    objective <= currentObjective, // Objective cut
    ANY ADDITIONAL CONSTRAINT / VARIABLE RESTRICTION ON ORIGINAL MODEL, TYPICALLY DEPENDING ON currentSolution
  );
  model.add(restrictions);
  if (cp.solve()) {
    cp.store(currentSolution);
    currentObjective = cp.getObjValue();
  }
  mode.remove(restrictions);
  
}

Originally posted by: valkiri

Thank you PhilippeLaboire  

I try it and it work  thanks again for your help.

This is a code i try 

ILCGOAL1(Generer, IlcIntVarArray, array){
        IloCP cp = getCP();
        IlcInt index = IlcChooseFirstNonFixedInt(array);
        if (index == -1) return 0;
    cp.solve(IlcOr(array[index] == val, IlcAnd(array[index] != val, this)));
        return 0;
}

ILOCPGOALWRAPPER1(NCSearch,cp, IloIntVarArray, x){
        return Generer(cp, cp.getIntVarArray(x));
}

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(x >0);
        model.add(y <5);
        model.add(x <= y);
        model.add(IloMaximize(env,IloSum(array)));
        IloCP cp(model);
        cp.startNewSearch(NCSearch(env,x));
        while(cp.next()){
                cp.out() << "x=" << cp.getValue(x) << endl;
                cp.out() << "y=" << cp.getValue(y) << endl;        
               cp.out() << "objective=" << cp.getObjValue() << endl;
 
             }

        cp.endSearch();
        env.end();
        system("PAUSE");
        return 0;
}

When i execute this code i get   x=1, y=2, objective=3  (who is the first solution) in the tree search . 

What can i add for explore all the tree and get all solution and the optimal solution.

Thanks.

Originally posted by: PhilippeLaborie

Hello,

You should not use an internal solve for doing that, just do something like:
 

ILCGOAL1(Generer, IlcIntVarArray, array){
    IloCP cp = getCP();
    IlcInt index = IlcChooseFirstNonFixedInt(array);
    if (index == -1) return 0;
    return IlcAnd( IlcOr(array[index] == val, array[index] != val), // Fix array[index]
                   this );                                          // Fix the other variables
}

Originally posted by: valkiri

Thanks PhilippeLaborie.

If i want to control the search by making myself the backtracking after found a solution . I read that it's possible to use  "  IlcOr(goal1,goal2, label1) "    or     " cp.solve(IlcAnd(goal,IlcGoalFail(cp)) " to force a backtracking  but i don't know how to use them because the IBM users manual is not explicit. 

Thanks.