4

I am newbie in CP but I want to solve problem which I got in college.

I have a Minizinc model which minimize number of used Machines doing some Tasks. Machines have some resource and Tasks have resource requirements. Except minimize that number, I am trying to minimize cost of allocating Tasks to Machine (I have an array with cost). Is there any chance to first minimize that number and then optimizate the cost in Minizinc?

For example, I have 3 Task and 2 Machines. Every Machine has enough resource to allocate 3 Task on them but I want to allocate Task where cost is lower.

Sorry for my English and thanks for help. If there is such a need I will paste my code.

Dekker1
  • 5,565
  • 25
  • 33
badej60
  • 57
  • 5
  • 1
    I don't have the time to write a full answer now. One option is to extend the FlatZinc file after it has been generated, extending the optimization goal with a list of objectives, and then convert the problem to OMT with [fzn2omt](https://github.com/PatrickTrentin88/fzn2omt). The README.md contains an example of lexicographic optimization. – Patrick Trentin Dec 01 '20 at 23:06

1 Answers1

8

The technique that you are referring to is called lexicographic optimisation/objectives. The idea is to optimise for multiple objectives, where there is a clear ordering between the objectives. For example, when optimising (A, B, C) we would optimise B and C, subject to A. So if we can improve the value of A then we would allow B and C to worsen. Similarly, C is also optimised subject to B.

This technique is often used, but is currently not (yet) natively supported in MiniZinc. There are however a few workarounds:

  • As shown in the radation model, we can scale the first objective by a value that is at least as much as the maximum of the second objective (and so on). This will ensure that any improvement on the first objective will trump any improvement/stagnation on the second objective. The result of the instance should then be the lexicographic optimal.
  • We can seperate our models into multiple stages. In each stage we would only concern ourselves with a single objective value (working from most important to least important). Any subsequent stage would fix the objectives from earlier stages. The solution of the final stage should give you the lexicographic optimal solution.
  • Some solvers support lexicographic optimisation natively. There is some experimental support for using these lexicographic objectives in MiniZinc, as found in std/experimental.mzn.

Note that lexicographic techniques might not always (explicitly) talk about both minimisation and maximisation; however, you can always convert from one to the other by negating the intended objective value.

Dekker1
  • 5,565
  • 25
  • 33
  • Thank you very much! It's not easy to do - that's how I thought. Option 1 seems to be the easiest way but I have no connection between number of used machines and cost so I will resigne from optimization both variables for now. – badej60 Dec 02 '20 at 14:32
  • +1 @Dekker1 Is there any further documentation on the experimental annotations? Also including the supported solvers? – Phonolog Dec 04 '20 at 08:34
  • I'm unsure if there is currently any official documentation on the experimental feature, but there is some information on it available on the MiniZinc forum. (Look for goal_hierarchy). I'll check on Monday to see if there is any official information that I can point to in the answer. – Dekker1 Dec 05 '20 at 10:34
  • hello @Dekker1, I'm trying to solve a similar problem where I need to optimize by two parameters. Did something change in terms of supporting "lexicographic optimization/objectives" in minizinc? maybe you could explain a bit more about how it works in the radiation model? – Eosfor Nov 25 '21 at 08:37