CODEWITHSUNDEEP
optimizationmodelingconstraint-programmingchoco
Dora
Dora

Reputation: 47

resource allocation with penalties in choco

For my model I have about 120 people and 650 tasks. I now want to allocate those tasks with choco 3.3.3. For that I have a boolMatrix "assignment" 120x650 where there is a 1 if the task is assigned to the person and a 0 otherwise. But now I have to optimize with different criteria, for example minimize overtime, abide to wishes from the people and so on. What is the best way to do that?

My intuition: I don't see a way to just accumulate penalties, so my intuition is having a matrix where for every person there is an array of "penalties" so that if person i has overtime, penalties[i][0] has penalty 5 for example and if he doesn't want to do the task penalties[i][1] has penalty 4. Then I have an IntVar score, that is the sum of penalties and I optimize over score.

  1. Is the penalty matrix the way to go?
  2. And how can I initialize these Variables?
  3. Is that optimizable (every feasible solution has a score) in a reasonable time with choco?
    In the nurse scheduling example this strategy was used: solver.set(IntStrategyFactory.domOverWDeg(ArrayUtils.flatten(assignment), System.currentTimeMillis()));
  4. What strategy should I use? Reading the choco user guide didn't help me get a good idea...

Upvotes: 0

Views: 203

Answers (1)

Jean-Guillaume Fages
Jean-Guillaume Fages

Reputation: 249

It seems from your questions that you have not tried yet to implement and test your model so we cannot help much. Anyway:

Q1) I did not understand clearly your approach but there may be many ways to go. It is by testing it that you will know whether it solves your problem or not. Maybe you could also use and integer variable x where x=k means task x is done by resource k. You could also use a set variable to collect all the tasks of each resource.

Regarding penalties, you should formalize how they should be computed in a mathematical way (from the problem specifications) before wondering how to encode it with the library. More generally, you must make very clear and formal what you want to get before working on how to get it.

Q2) To create variables, you shall use VariableFactory. Initial domains should contain all possible values.

Q3) It depends of the precise problem and of your model. Presumably, yes you can get very good solutions in a very short time. If you want a mathematically optimal solution, with a proof it is optimal, then this could be long.

Q4) It is not mandatory to specify a search strategy. Choosing the best one requires experience and benchmarking so you should try some of them to figure out yourself which one is best in your case. You can also add LNS (a kind of local search) to boost optimization...

Hope this helps

Upvotes: 2

Related Questions