How to get All optimal solutions?

[csy1234]

Like the code below, I set a OBJ to minimize in my model, I do need to get the optimal OBJ, but I also want to get all optimal solutions. Furthermore, if I want to get all solutions corresponding to (OBJ + 1), how can I do this? I've already seen the Choco 4.0.0 documentation and Javadoc, but I still can't solve this two problems.

    model.setObjective(Model.MINIMIZE, OBJ);

    Solver solver = model.getSolver();

    int count = 1;
    while(solver.solve()){
    System.out.println("count = " + count);
    System.out.print(OBJ + "\n");
        count++;
    }

[jgFages]

Hi

Give a look at solver.findAllOptimalSolutions

[csy1234]

I've already used code above to get a optimal OBJ = 2; And this is the printStatistics:

** Choco 4.0.1 (2016-12) : Constraint Programming Solver, Copyleft (c) 2010-2016

• Model[Model-0] features: Variables : 163 Constraints : 56 Default search strategy : no Completed search strategy : no
• Complete search - 9 solution(s) found. Model[Model-0] Solutions: 9 MINIMIZE objective value = 2, Building time : 0.000s Resolution time : 0.204s Nodes: 2,398 (11,738.2 n/s) Backtracks: 4,779 Fails: 2,381 Restarts: 0 Running time: 218ms

But I used findAllOptimalSolutions like this:

    model.setObjective(Model.MINIMIZE, OBJ);
    Solver solver = model.getSolver();

    List<Solution> optimal_solutions;
    Criterion solcpt = new SolutionCounter(model, 1000000000);
    optimal_solutions = solver.findAllOptimalSolutions(OBJ, false, solcpt);
    System.out.println(optimal_solutions);
    solver.printStatistics();

I just got no solution:

[] ** Choco 4.0.1 (2016-12) : Constraint Programming Solver, Copyleft (c) 2010-2016

• Model[Model-0] features: Variables : 163 Constraints : 57 Default search strategy : no Completed search strategy : no
• Complete search - No solution. Model[Model-0] Solutions: 0 Building time : 0.000s Resolution time : 0.021s Nodes: 0 (0.0 n/s) Backtracks: 0 Fails: 1 Restarts: 0 Running time: 218ms

[jgFages]

This is strange. Can you:

• Try without the stop criterion (which is an optional argument)
• Make sure that you tried findAllOptimalSolutions instead of (and not after) the classical while(solve()) (you would need to reset the solver to perform two consecutive solving).
• If this still does not work, try with choco-solver-4.0.2?

[csy1234]

Yes, I tried findAllOptimalSolutions directly without while(solve()). By the way, tring without the stop criterion is just like this: optimal_solutions = solver.findAllOptimalSolutions(OBJ, false, null); ?

[jgFages]

optimal_solutions = solver.findAllOptimalSolutions(OBJ, false);

[csy1234]

Thanks, I will try it later with both versions

[csy1234]

Hi, I still get the same result with solver.findAllOptimalSolutions(OBJ, false) with both versions, and here is my code . Now I am really confused about this method.

[jgFages]

It seems to come from the table constraint implementation, which seems to not support solver resets. Use the CT+ (i.e. replace "STR2+" by "CT+") implementation and you will be fine.

Thank you for the feedback. Can we put you code in the regression tests suite ?

[csy1234]

Thanks and I think you can put my code in your tests suite :-)

I use all table constraints alogrithms listed, like CT+ . It seems can give some solutions, and I got some variables equal to 2147483647 = 2^31 - 1, but all my variables should be boolvars. And I also find some repeat solutions in solution list. So I wanna to know if I could get the solution as I wish (Like all optimal solution or all suboptimal solutions) using a stragety or something? Take my code as example, I run while(solve()) to get a optimal OBJ = 2, and I'm sure about this solve, but how to contruct a strategy to get all solutions corresponding to OBJ = 2 or OBJ = 3.

[cprudhom]

The first thing to fix is about the variables set to to Integer.MAX_VALUE in a solution. Either there are not constrained or they are decision variables not declared in the search, or both.

When I investigated, I found some variables not constrained, for instance in[1][0]. So first, you need to find why they are related to other variables by constraints.

BTW, we will fix the issue related to table contraints and reset.

[cprudhom]

Can I add your code to Choco's test list ?

[csy1234]

Sure, Thanks for your attention.

But I'm sure about that in[1][0] should be constrainted with other variables, in my code(line:71-76).

Anyway, I will still pay attention to this issue.

[cprudhom]

When I look at the propagators of this variable (in DEBUG mode), its list is empty.

for(IntVar var: model.retrieveIntVars(true)){
            System.out.printf("%s -> %d\n", var, var.getNbProps());
        }

it outputs:

in[0][0] = [0,1] -> 2
in[0][1] = [0,1] -> 2
in[0][2] = [0,1] -> 2
in[0][3] = [0,1] -> 2
in[0][4] = [0,1] -> 3
in[0][5] = [0,1] -> 3
in[0][6] = [0,1] -> 3
in[0][7] = [0,1] -> 3
in[0][8] = [0,1] -> 4
in[0][9] = [0,1] -> 4
in[0][10] = [0,1] -> 4
in[0][11] = [0,1] -> 4
in[0][12] = [0,1] -> 5
in[0][13] = [0,1] -> 5
in[0][14] = [0,1] -> 5
in[0][15] = [0,1] -> 5
in[1][0] = [0,1] -> 0
in[1][1] = [0,1] -> 0
in[1][2] = [0,1] -> 0
in[1][3] = [0,1] -> 0
in[1][4] = [0,1] -> 0
in[1][5] = [0,1] -> 0
in[1][6] = [0,1] -> 0
in[1][7] = [0,1] -> 0
in[1][8] = [0,1] -> 0
in[1][9] = [0,1] -> 0
in[1][10] = [0,1] -> 0
in[1][11] = [0,1] -> 0
in[1][12] = [0,1] -> 5
...

[csy1234]

I tried your debug and it do output like "in[1][0] = [0,1] -> 0"

But I added a constraint to in[1][0] at line 85:

model.arithm(input_at_round[1][0], "=", 1).post();

It output a little different:

in[0][0] = [0,1] -> 2
in[0][1] = [0,1] -> 2
in[0][2] = [0,1] -> 2
in[0][3] = [0,1] -> 2
in[0][4] = [0,1] -> 4
in[0][5] = [0,1] -> 3
in[0][6] = [0,1] -> 3
in[0][7] = [0,1] -> 3
in[0][8] = [0,1] -> 4
in[0][9] = [0,1] -> 4
in[0][10] = [0,1] -> 4
in[0][11] = [0,1] -> 4
in[0][12] = [0,1] -> 5
in[0][13] = [0,1] -> 5
in[0][14] = [0,1] -> 5
in[0][15] = [0,1] -> 5
in[1][0] = [0,1] -> 0
in[1][1] = [0,1] -> 0
in[1][2] = [0,1] -> 0
in[1][3] = [0,1] -> 0
in[1][4] = [0,1] -> 0
in[1][5] = [0,1] -> 0
in[1][6] = [0,1] -> 0
in[1][7] = [0,1] -> 0
in[1][8] = [0,1] -> 0
in[1][9] = [0,1] -> 0
in[1][10] = [0,1] -> 0
in[1][11] = [0,1] -> 0
in[1][12] = [0,1] -> 5
...

It seems all constraints added to in[1][0] goes to in[0][4] and I think the reason is at line 79-82:

            /*   the shift between two round    */
            for(int i = 0; i < 3 * quarter_block; i ++){
                input_at_round[r + 1][i] = input_at_round[r][quarter_block + i];
                }

This shift made in[1][0] = in[0][4]. But I am also confused about this counting.

[cprudhom]

What did you want to express with lines:

/*   the shift between two round    */
            for(int i = 0; i < 3 * quarter_block; i ++){
                input_at_round[r + 1][i] = input_at_round[r][quarter_block + i];
                }

Is it an equal constraint or just a transposition of input_at_round ?

[csy1234]

This should be just a transposition in two rounds in my model, so I just use

input_at_round[r + 1][i] = input_at_round[r][quarter_block + i]

to make this equal constraint. Then I use :

model.arithm(input_at_round[r + 1][i], "=", input_at_round[r][quarter_block + i]).post();

And it output right, but I think that the first way should have worked out according to my results.

[csy1234]

I also have a another question: If I want to enumerate all solutions under a fixed Objective Value, how to do this? By a strategy or something?

[jgFages]

Once you do that you have to understand that you no longer have an "objective" in your model, which turns into a classical satisfaction problem. The "objective" is just a variable, like any other.

You can fix the objective: m.arithm(obj,"=",42).post(); and then compute all solutions

m.getSolver().findAllSolutions();

or: m.clearObjectives(); while(m.getSolver().solve());

[cprudhom]

but I think that the first way should have worked out according to my results. No, because :

• the first instruction is a Java one, it states that the object in the specific position within the matrix is set to another one (by reference)
• the second is an instruction for Choco, it states that in a solution the two variables must take the same value.

[csy1234]

Thanks, It seems I've got two satisfied answers.

@jgFages And before I open this issue, I've already tried your way to enumerate all solutions under a fixed OBJ, which is surely not an optimization problem. And now I think by this way I don't need findAllOptimalSolutions() maybe :-)

[cprudhom]

Can I close the issue ?