[BUG] Search.randomStrategy uses the same seed for VariableSelector and ValueSelector

[MathieuVavrille]

Hello,

The issue

I found a bug in the way the random seed is used when creating a Search.randomStrategy. The same seed is used for the VariableSelector and the ValueSelector. This makes the two selectors not independent, and is an issue, for example in the next model:

long seed = XXX;
Model model = new Model("RandomIssue");
IntVar x = model.intVar("x", 0, 2, false);
IntVar y = model.intVar("y", 0, 2, false);
IntVar z = model.intVar("z", 0, 2, false);
model.allDifferent(new IntVar[]{x,y,z}).post();
Solver solver = model.getSolver();
solver.setSearch(Search.randomSearch(new IntVar[]{x,y,z}, seed));

Whatever the value of the seed, the first solution returned by the solving process will be [0,1,2]. This happens because on this particular example, the calls to the random will always be done on the same values on the ValueSelector and on the VariableSelector.

Some possible fixes

Modifying the body of Search.randomSearch(...)

Replace the body of the function by

    public static IntStrategy randomSearch(IntVar[] vars, long seed) {
        java.util.Random random = new java.util.Random(seed);
        long valueSelectorSeed = random.nextLong();
        IntValueSelector value = new IntDomainRandom(valueSelectorSeed);
        IntValueSelector bound = new IntDomainRandomBound(valueSelectorSeed);
        IntValueSelector selector = var -> {
            if (var.hasEnumeratedDomain()) {
                return value.selectValue(var);
            } else {
                return bound.selectValue(var);
            }
        };
        return intVarSearch(new Random<>(random.nextLong()), selector, vars);
    }

By generating seeds with the random generator, the seeds will be independent.

Modifying the type of Search.randomSearch(...)

An other solution is to give an instance of java.util.Random to Search.randomSearch(...), and proceed as the previous . That way, the user would input the random generator.

Having a global random generator

Maybe the best but most expensive way to do is to have a random generator initialized at the beginning of the program (either by a seed given by the user, or another random generator given by the user), and pass this random generator to all the classes that need to generate random numbers. The same random generator will be used by every class, ensuring that each call to generate a new number is independent from the previous ones. This fix raises a big problem on how to deal with parallelism.

I hope you will be able to find a solution. I don't know if there is a canonical way to deal with randomness in software, my solutions may not be the best ones.

Have a great day.

[arnaud-m]

Hi,

Just a comment on the global random generator proposal. Using a single global random generator could break reproducibility even without parallelism.

I would suggest to use a global random generator only to generate the seeds of internal random generators used by the classes.

[jgFages]

Hi,

I agree with Arnaud that the seed should remain fixed to ensure reproducibility.

Note that only the first decision will always be of the form xi = i, then decisions will be xi = ith value in the domain which, because of constraint propagation, will not always be i. This being said, it is true there is a bias here.

I am not expert in seeds but I guess giving to the value selector the variable selector seed +1 would do the job. At least there is a 100% guarantee to have a different seed...