How to identify minizinc problem(Maximizing or Minimizing) has multiple answers

user_6575848 0
Viewed 298

I just did some experiment on what will happen if a optimisation problem has many solutions.I know that by MiniZinc we can identify multiple answers for satisfy problem.(Like map colouring in user guide). And MiniZinc always show a dotted double lines soon after we get the optimal answer.

Now I just ran below code and I noticed that if I use the gecode solver answers are different from when I use coin-bc or cplex solvers answers are different. Is there any feature in MiniZinc that we are notified when these kind of multiple optimum answers problems or else to get all solutions disregarding the solver we use.

    enum suppliers;
    suppliers={s1,s2,s3};
    set of int:sup=1..length(suppliers);
    array[sup] of float:price=[3.0,6.0,12.0];
    array[sup] of int:max=[2,3,1];
    int:demand=3;
    array[sup] of var 0..1000:qty;
    var float:cost;

    constraint sum(i in sup)(
    qty[i])=demand;

    constraint forall(i in sup)(
    qty[i]<=max[i]
    );

    constraint qty[2] != 1;
    constraint qty[1] != 1;

    constraint sum(i in sup)(
    price[i]*qty[i])=cost;

    solve minimize cost;
minizinc optimization
2 Answers

It does of happen that an optimisation problem has multiple correct optimal answers. It often happens that different solvers will provide different solutions; however, If the solvers functioned correctly, then the objective value (in your case cost) should be the same in both solutions.

One way that is often used in MiniZinc to find all (or at least more) optimal solutions is to add constraint cost = V;, where cost is the name given to the objective and V is the optimal value found for your problem. If we then change the problem to a satisfaction problem (solve satisfy), then a solver that supports find all solution (such as chuffed or gecode) can find all optimal solutions to the original problem.

Note that finding all optimal solutions can often be significantly harder than finding just one optimal solution.

user_13515970

Dekker already answered your question. I would like to add that OptiMathSAT has built-in support for finding all same optimal-value solutions.

The easiest way to try it out is to download, configure and install fzn2omt and then use the option --all-solutions-opt. e.g.

~$ fzn2optimathsat.py examples/flatzinc_allsolutions.fzn --all-solutions-opt
% allsat model
x = 3;
y = 0;
r1 = true;
r2 = false;
----------
% allsat model
x = 3;
y = 1;
r1 = true;
r2 = false;
----------
==========
user_60241220
Related