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.

Improve this question
$\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, 2020 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, 2020 at 14:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.