6
$\begingroup$

Until now, I have used the Gurobi, CPLEX and OR-Tools (GCO) interface to formulate mixed-integer-programming models.

Recently, I have discovered MiniZinc and want to utilize it to formulate big models.

With GCO I would only initialize the decision variables I need and only give the data without all non-existent index combinations.

Scheduling Example

Indices:

  • $e$: employee
  • $d$: day
  • $s$: shift
  • $z$: skill

This means, there are different employees, that can work on different days and different shifts within each day and the employees may also have different skills.

The way I visualize the data is in a 2D matrix. The row has the employee index and the column the tuple of indices $(d,s,z)$.

If the employee Bob, is available on Monday, for the shift 2 pm to 8 pm and has the skill bartender he gets the value 1 otherwise 0.

To avoid saving 0-values, I would construct Lists/HashMaps/Dictionaries that only contain non-zero elements. If for a certain index combination there is no entry within the lists then I do not construct any constraint with it or take it in consideration, hopefully saving computing time.

I am not sure if this is the best way to optimize running-time, but after implementing this method it was much faster than giving the solver the whole matrix with 0 values (non-existent index combinations).

Now, I would like to implement something similar, within MiniZinc using Python. This means I have to somehow give the data in such a form to hopefully make the solver run faster, instead of giving a large 2D matrix with many 0-values.

$\endgroup$
2
  • $\begingroup$ I think in order for this to work in MiniZinc or AMPL, I would have to pass the whole data in a 4d Matrix. Then I would have to create sets containing indices of all employees $e$ that are available for each $d,s,z$. Thus, when creating constraints, I would use the upper created sets to limit the iterations. Furthermore, I would have to create sets such as $S_d$ since the shifts are day dependant and $S_z$ since skills are shift dependant. $\endgroup$ – Georgios Jan 19 '20 at 15:42
  • $\begingroup$ Unfortunately, I did not find a way to declare sets with indices, e.g., ($S_d)$ within Minizinc. An alternative would be to use arrays instead, which is suboptimal... $\endgroup$ – Georgios Jan 20 '20 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.