1
$\begingroup$

I would like to assign items to a box over a time horizon where each box has an associated deadline. I was wondering if my formulation and / or variable definition can be improved. In other words, what other alternative way can I use to formulate my problem?

One important detail is that if not all required item arrive at the box, then I do not want to assign any item.

Variables:

$X_{ijt}$ = amount of items $i$ assigned to box $j$ at time $t$.

$Y_{ijt}$ = binary variable indicating if any item $i$ is assigned to box $j$ at time $t$.

$Z_{ij}$ = binary variable indicating if total demand of $i$ is met for box $j$.

$L_{j}$ = binary variable indicating if total demand is met for box $j$.

Inputs:

$d_j$ = given deadline for box j.

$c_{ij}$ = total demand of item $i$ for box $j$.

My constraints are defined as:

$t Y_{ijt} \leq d_j$. This guarantees that each item arrive by the deadline per box.

$ X_{ijt} \leq c_{ij} Y_{ijt}$. This is a big M constraint deciding if any amount of item $i$ is assigned to box $j$ at time $t$.

$ \sum_{t \in T} X_{ijt} \geq c_{ij} Z_{ij}$. This is constraint ensuring that the total demand is covered if any amount of item $i$ is assigned to box $j$.

$ \sum_{i \in I} Z_{ij} \geq |J| L_{j}$. Here, we decide if a box gets all the required parts. Then, I maximize the sum of $L$ to make sure the model aims for meeting all the demands for each box.

Overall, the goal is to make sure that the partial coverage is not allowed. Can there any improvements to avoid big M constraints?

$\endgroup$

1 Answer 1

1
$\begingroup$

Rather than impose your first constraint explicitly, it is better to define a sparse set $(j,t)$, where $t \le d_j$, to be used for both $Y_{ijt}$ and $X_{ijt}$.

Your last constraint goes in the wrong direction, so maximizing $\sum_j L_j$ will just yield $L_j=1$ for all $j$.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer. The direction of the last constraint was a typo, I just fixed it. As for your first comment, I'll definitely avoid creating index pairs where $t> d_j$, should I just drop the first two constraints and variable $Y$? $\endgroup$
    – whitepanda
    Nov 6, 2023 at 18:53
  • $\begingroup$ Yes, with the sparse formulation, you can omit $Y$ altogether. $\endgroup$
    – RobPratt
    Nov 6, 2023 at 19:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.