Originally posted by: SystemAdmin

Hi everybody, I'm solving a Constraint Satisfaction problem using the .NET Concert Technology and I would like to find all the solutions of my problem. I'm using a simple while loop which looks like

while(cp.Next()) 
{ \\ access solutions here 
}

However, I found out that cp.Next() often finds the same solutions for a large amount of iterations. This is probably due to me using a search heuristic manually defining the search phases in a particular way. The guide also states that "In the case of a satisfaction problem, next returns a solution usually different from those previously found but, it may occasionally find a solution that had been found already". Although Next() is guaranteed to terminate, i.e., not to infinitely loop returning the same solution, is there any way to make it return different solutions?

The only idea I have now is to record all of them in a list as soon as they are found and simply "continue;" the while loop if the solution found by Next() at a given iteration is already present in the list. Can I do better?

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
I'm assuming your problem is a satisfiability problem and not an optimization one (no objective).
If you are working with a model that only contains integer variables as decisions (no interval variables), you may use the DepthFirst search type that implements a classical tree search. This guarantees that with next() you traverse the set of all feasible solutions and each solution will be reported only once.
If your model contains some interval variables, with DepthFirst the things are a little bit different. The next() will traverse all feasible solutions but a given solution may be reported at most twice.

To set the DepthFirst search type, use:

cp.SetParameter(CP.IntParam.SearchType, CP.ParameterValues.DepthFirst);

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Thank you for your support. I confirm that my problem is a Constraint Satisfaction one (no objective), and before your reply I implemented a way to check if a solution found by cp.Next() was already found:

List<ISolution> solutions;   

while(cp.Next()) 
{ ISolution newSolution = InitializeSolution(); 
// InitializeSolution() is implemented by creating a new ISolution with cp.Solution() and then adding each pair variable/value of the model via Add() and SetValue()   

if(Contains(solutions, newSolution)) 
// Contains() is implemented by calling GetValue() on each solution of the List and on newSolution looking for a matches: two solutions are identical if each pair of variables is assigned to the same pair of values 

continue; 
// newSolution is a duplicate, and should be discarded 

else solutions.add(solution) 
// newSolution is not a duplicate, and should be kept   
// Do other things here   
}

By setting the DepthFirst search type, not only I noticed a downgrade in the performance (i.e., the search is slower), but still Next() finds duplicate solutions. I checked it by adding a breakpoint on the continue instruction and verifying that indeed it was still executed many times, meaning that that solution found by cp.Next() was a duplicate.

What could be the reason for that? Could it be that I'm defining some search phases, interfering with the way Next() computes results, regardless of Depth First search? What could be a solution?

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

You must have several cores on your machine and thus a number of effective workers that is at least 2. In this case, every worker run DFS independently in parallel and you will get the same solution several times. In fact it is not usefull to have several workers when searching for all solutions. The communication between workers is not usefull as each of them scans the full search tree. However if you want a set of, say 100 solutions, then it can be faster to use several workers due to the diversification that parallel search introduces.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Indeed, my machine has 8 cores and I was using all of them to find all the solutions of my CS problem. I was unaware of this detail you mentioned, but it pretty much answers my question and clarifies what was going on. Thank you very much for your help!

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer