Assignment problem with nonlinear constraint

69 Views Asked by At

Consider $N$ different items and $M$ different slots.

$x_{ij} \in \{0,1\}$ puts the $i$-th item into the $j$-th slots.

Each slot can hold $c_j$ items, i.e. $\sum_i x_{ij} \leq c_j \forall j$

And obviously I want to assign every item only once.

The hard bit is this constraint:

Every item has size $s_i$ and I want items of sufficiently different sizes in my slots. To be precise: i want for every two $x_.$ that $|s_k - s_l| \geq D$

How do I go about this, seems pretty nonlinear to me...

Is there a solver that can handle this for me?

1

There are 1 best solutions below

6
On

In other words, you want to disallow assigning items $k$ and $\ell$ to the same slot if $|s_k-s_\ell| < D$. You can enforce this with a "conflict" constraint for each such incompatible pair $k<\ell$ and slot $j$: $$x_{k,j} + x_{\ell,j} \le 1. \tag1$$

Alternatively, you could impose $$|s_k-s_\ell|\ge D(x_{k,j} + x_{\ell,j}-1) \tag2$$ for all $k<\ell$ and all $j$, but a presolver would likely reduce $(2)$ to $(1)$ anyway.