Multi-objective minimization issue

[evare...@kpler.com]

Hi all,

I would like some precision about issues I am encountering with my minizinc model. 

I have a model with a multi-objective (two variables) minimization. I am using soft constraints, and the first variable to minimize is the sum of soft constraints not satisfiable. The second variable is another sum, defined with some "normal" constraints. 

In some cases, the problem has no solution and I just get the "========" chain characters, which means (if I understood well) that the solution space has been covered. 

I do not understand what is the difference between saying that the problem is UNSATISFIABLE and giving no solution but say that the entire solution space has been covered.

A solution exists for this problem, as when I add a constraint which is the solution I would like to obtain, the solution is well found.

Also, I would like to have some information about how the space solution is built and how it is explored, if possible.

Thanks for your time and answers,

Emma

[Gleb Belov]

Hi Emma,

can you send an (ideally small) example and explain what seems wrong?

Best

--
You received this message because you are subscribed to the Google Groups "MiniZinc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/8356b163-825f-4e52-94ed-4dc53ac138f1%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[evare...@kpler.com]

Hello Gleb, 

thank you for your answer. 

If I understand well, minisearch is not able to say whether the whole problem has been explored and no solution was found, or if the problem is UNSATISFIABLE. I succeeded to solve most cases of my problem, by adding new constraints to my model that was clearly not enough constrained. 

However, I now face a new issue, which is that my solver is not converging rapidly enough to find a solution. 

My problem is composed of volumes, the variable I am trying do deduce, penSum the sum of not satisfied soft constraints and x another sum of certains volumes, which I want to minimize.

Here is my objective: 

array[int] of var int: objective = [penSum, x];

solve search time_limit(time_boundary, minimize_lex(objective));

and in some cases here is the result: 

[210, 0, 210, 0, 210, 0, 0, 0, 210, 790, 0, 790, 0, 790, 0, 0, 0, 790, -1000, 0, -1000, 0, -1000, 0, 0, 0, -1000]  # volumes

2      # penSum

0      # x

----------

[210, 0, 210, 0, 210, 0, 0, 0, 210, 790, 11, 790, 0, 790, 0, 0, 0, 779, -1000, -11, -1000, 0, -1000, 0, 0, 0, -989] # volumes

2        # penSum

-22    # x

----------

[210, 0, 210, 0, 210, 0, 0, 0, 210, 790, 12, 790, 0, 790, 0, 0, 0, 778, -1000, -12, -1000, 0, -1000, 0, 0, 0, -988] # volumes

2        # penSum

-24     # x

----------

I tried to use the variable annotations, but it seems I am missing something.

Here is my new objective:

solve :: seq_search([

    int_search([penSum], input_order, indomain_min, complete),

     int_search([volumes[i, j] | i in N, j in M where input_volumes[i] > 0], input_order, indomain_max, complete)

])

search time_limit(time_boundary, minimize_lex(objective));

This approach helps me, for this case, to directly converge to the good solution, but other problems are not solved anymore.

I am not sure about this objective, and especially the way of annotating. If I change indomain_max to indomain I have the same results as previous. If I change it to indomain_random, I have this solutions, which does not seems to be random:

[210, 0, 210, 0, 210, 0, 210, 0, 0, 790, 410, 790, 253, 790, 0, 99, 0, 28, -1000, -410, -1000, -253, -1000, 0, -309, 0, -28]   # volumes

2        # penSum

-820   # x 

----------

[210, 0, 210, 0, 210, 0, 210, 0, 0, 790, 425, 790, 243, 790, 0, 95, 0, 27, -1000, -425, -1000, -243, -1000, 0, -305, 0, -27]   # volumes

2        # penSum

-850   # x 

----------

[210, 0, 210, 0, 210, 0, 210, 0, 0, 790, 439, 790, 234, 790, 0, 91, 0, 26, -1000, -439, -1000, -234, -1000, 0, -301, 0, -26]   # volumes

2        # penSum

-878   # x 

----------

I would like to have more info on how to force the exploration of solutions, and the variable annotation. Especially, in my case, I would like to force the exploration for some variable from the max domain value to the min domain value, and for some other variables from the min domain value to the max domain value.

Sorry for the long message, thanks for reading it !

Best,

Emma