Originally posted by: albalkum

I've been trying to understand how search phases work in regards to a feasibility problem but I've hit a roadblock.  For a small number of feasible solutions (out of the entire pool), I'd like to have a subset of my decision variables have a certain degree of diversity in their results. Here's an explanation of a simple scenario:

Here's my decision variables:

dvar int options[1..12] in 0..1;

Given my constraints, I call cp.next() to obtain 5 feasible solutions (out of 23 possible).  It took me a while, but I learned to use cp.param.SearchType = "DepthFirst" and cp.param.Workers = 1 to make sure duplicate solutions were not given.  Without search phases, the 5 solutions are:

 [0 1 0 0 0 0 1 1 0 0 1 0]
 [0 1 0 0 0 0 1 1 0 1 0 0]
 [0 1 0 0 0 1 0 1 0 0 1 0]
 [0 1 0 0 0 1 0 1 0 1 0 0]
 [0 0 0 1 0 1 0 1 0 1 0 0]

options[9] and options[12] are 0 for all 5 solutions.  I wish to have a more diverse set of solutions for those 2 variables, i.e. more 1s.  How can I go about doing this?  I'm able to use setSearchPhases() to make certain variables all 0s or all 1s for 5 solutions.

int optionEval[1..12] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1];

execute {

        var f = cp.factory;
        var eval = f.selectLargest(f.explicitVarEval(options, optionEval, 0));
        var chooser = f.selectLargest(f.value());
        var phase = f.searchPhase(options, eval, chooser);
        cp.setSearchPhases(phase);
}

Is there a way to use search phases to make certain variables have more diversity in their solutions?

Thanks for the help!

Originally posted by: ChrisBr

Hello Alexander,

One way to introduce more diversity can be to use selectRandomValue as valueSelector.
You could also use "Restart" instead of "DephFirst", but in this case, you may get some duplicate solutions.

Regards,

Chris.

Originally posted by: albalkum

Thanks for your answer Chris.

One of my first attempts to figure this out was to use selectRandomValue instead.  However, it doesn't seem to produce the result I desire.  This is the result I get:

 [0 0 0 1 0 0 1 1 0 1 0 0]
 [0 0 0 1 0 0 1 1 0 0 1 0]
 [0 0 0 1 0 1 0 1 0 1 0 0]
 [0 0 0 1 0 1 0 1 0 0 1 0]
 [0 1 0 0 0 1 0 1 0 0 1 0]

The individual solutions appear to be different but my variable subset (8 and 12) are still only 0.  I would think that, in the realm of search phases, the evaluator figures out which decision variables to search on, and the chooser/selector decides what value to look for.  Why isn't selectRandomValue working then?  Does the selector choose a random value for each .next() solution call, or just once at the beginning?

Thanks

Originally posted by: PhilippeLaborie

Hello,

I think that in the general case, uniformly sampling the solutions of a combinatorial problem (without enumerating them all) is a very difficult task. So I suppose you just need a "reasonable" enough sampling. The problem if you only use selectRandomValue with DepthFirst is that the value of the variables selected at the top of the search tree will never be changed (unless you enumerate a very large number of solutions) and you will have a terrible bias because you just ignore a big part of the solution space. If you use the Restart search type instead of DepthFirst, that can be a bit better because the search will explore not just a tree but a forest. But still, you will have some bias, if only because of the possibly quite limited number of explored trees. You can decrease the bias by also selecting the variables in a random way (using variable selector selectRandomVar). You can also completely restart the search yourself (by calling cp.solve()) and change the random seed of the engine (search parameter RandomSeed) at each solve. But here also, as with all methods except for a single DepthFirst, you can get duplicate solutions.

Philippe

Originally posted by: albalkum

Philippe,

While I've almost exclusively using DepthFirst and cp.next() to generate solutions.  So, I've been toying around with selectRandomVar (I hadn't thought of using this yet) and using cp.solve() multiple times using a different random seed.  It's been helping me understand the workings of searchphases and has given me better results.  I suppose duplicate solutions will emerge as the pool of random variable combinations decreases, but it's a good start.

Thanks for the help.