15
$\begingroup$

There are $ N $ bins with equal capacity $ C $. In addition, there are $ N $ objects $x_1, x_2, \dots, x_N $ that need to be accomodated using the least amount of bins. Each object $x_i$ has a volume $ v_i < C $. However, there is a penalization $ p_{ij} $ for accomodating any two objects $x_i, x_j$ together. This penalization is related to the shape incompatibility among objects, which causes capacity waste.

To summarize, the objective is to minimize the number of bins used while taking into consideration the capacity constraints and penalization due to grouping.

I need help to formulate this problem. My ultimate objective is to use dynamic programming to solve this problem but I cannot come up with a formulation, mainly due to the penalization policy. Also, if you have seen a similar problem before, please point me to the source.

Further information: For instance, if three objects $ x_1, x_2, x_3$ are put together in the same bin, the overall occupied volume is $ v_1 + v_2 + v_3 + p_{12} + p_{13} + p_{23}$.

Update: I just want to thank you all for your help. Thank you @MarcoLübbecke for the paper you shared about bin packing with conflicts. Thank you @RenaudM for the two formulations you proposed and for pointing me to this article in your blog https://orandtricks.wordpress.com/2013/08/12/planning-your-wedding-is-not-easy-and-i-am-not-even-speaking-of-handling-the-brides-moods/ about the issue with symmetric formulations. Thank you @RobPratt for your simplified formulation. I have implemented @RobPratt's formulation and @RenaudM's first approach, and for small-scale problems they perform the same. I aim at developing a dynamic programming solution for either of these two formulations. If I succeed I will post the solution. Thank you again for your time and help in this matter.

$\endgroup$
  • 1
    $\begingroup$ Looks like you'll have to model the interaction between two objects which will render the model much more difficult compared the classical problem. I doubt that this will be possible to solve via a dynamic programming approach. You could try to model it as a mathematical program and then use a MIP solver. $\endgroup$ – JakobS Jun 26 at 11:15
  • $\begingroup$ @prubin I posted this question initially at math.exchange but it received no attention. I made the mistake of not deleting it before opening a new question here. $\endgroup$ – Dunkel Jun 26 at 21:57
11
$\begingroup$

Here is a simpler symmetry-less formulation based on the one proposed by @RenaudM. For $i \le j$, let binary variable $r_{i,j}$ indicate that the bin represented by item $i$ contains item $j$. (Here, $r_{i,i}$ corresponds to $b_i$ in the other formulation.) For $i \le j < k$, let binary variable $t_{i,j,k}$ indicate that the bin represented by item $i$ contains both items $j$ and $k$. Then we want to minimize $\sum_i r_{i,i}$ subject to: \begin{align} \sum_{i \le j} r_{i,j} &= 1 &&\text{for all $j$}\\ r_{i,j} &\le r_{i,i} &&\text{for all $i<j$}\\ r_{i,j} + r_{i,k} - 1 &\le t_{i,j,k} &&\text{for all $i \le j < k$}\\ \sum_{j \ge i} v_j r_{i,j} + \sum_{i \le j < k} p_{j,k} t_{i,j,k} &\le C r_{i,i} &&\text{for all $i$} \end{align}

$\endgroup$
  • 1
    $\begingroup$ That's indeed a much nicer formulation than mine. I would guess that you could decide to not declare the $t_{i,j,k}$ as binaries but as linear variable, if all $r_{i,j}$ are integer then the $t_{i,j,k}$ should be integer too. I do not know if this would have a large impact on the performances. $\endgroup$ – Renaud M. Jun 27 at 6:46
  • $\begingroup$ Thanks. Yes, you can relax $t$, and doing so could help or hurt, depending on whether branching on $t$ is useful. Also, if $p_{j,k} = 0$ for some $(j,k)$ pair, you can omit $t_{i,j,k}$ for all $i$. $\endgroup$ – Rob Pratt Jun 27 at 16:49
10
$\begingroup$

This is very related to the bin packing with conflicts problem (see eg. here), where you model the conflict as "soft" (with a binary variable to indicate violation, with a penalty in the objective function).

The literature about this problem may contain a DP, too.

$\endgroup$
  • 1
    $\begingroup$ Thank you for the paper, Marco! $\endgroup$ – Dunkel Jun 26 at 13:10
7
$\begingroup$

If you are just looking for a formulation here is one (not particularly good due to symmetries, I'll rework it if I can think of something better in this regard).

Let $K$ be an arbitrary upper bound on the minimum number of bins needed.

Let $a_{i,k} \in [0,1]$ be a binary variable representing the assignment of object $x_i$ to bin $k$.

Let $b_{i,j,k} \in [0,1]$ be a binary variable representing if object $x_i$ and $x_j$ are both assigned to bin $k$

Let $u_k \in [0,1]$ be a binary variable representing if bin $k$ is used.

We then have the following model:

\begin{align}\min&\quad \sum_{k \leq K} u_k\\\text{s.t.}&\quad a_{i,k} \leq u_k, &&\forall i \leq N, \forall k \leq K\\&\quad b_{i,j,k} \geq a_{i,k} + a_{j,k} - 1, &&{\small\forall i \leq N-1, \forall i+1 \leq j \leq N, \forall k \leq K}\\&\quad\sum_{i \leq N}a_{i,k}\cdot v_i + \sum_{i \leq N-1, j \geq i+1}b_{i,j,k}\cdot p_{i,j} \leq C, &&\forall k \leq K\end{align} Edit 1: As pointed out by @RobPratt I am missing the following constraint:

$$\sum_{k \leq K}a_{i,k} = 1, \forall i \leq N$$

Also the last constraint is tighter with the following formulation: $$\sum_{i \leq N}a_{i,k}.v_i + \sum_{i \leq N-1, j \geq i+1}b_{i,j,k}.p_{i,j} \leq C\cdot u_k, \forall k \leq K$$

Edit 2:

I think I could find a symmetry less model (would be grateful to anybody pointing out errors in it).

Let us call $t_{i,j} \in [0,1], \forall i < j \leq N$ the binary (decision) variable indicating that $i$ and $j$ are put in the same bin.

Let us call $b_i \in [0,1], \forall i \leq N$ a helper variable letting us find out that $i$ is used to represent one bin.

Let us call $r_{i,j} \in [0,1], \forall i < j \leq N$ a helper variable indicating that $i$ and $j$ are put in the same bin and that $i$ is used to represent that bin.

We then have the following model: \begin{alignat}{2}\min&\quad\sum_{i \leq N}b_i\\\text{s.t.}&\quad\sum_{j < i}t_{j,i}\cdot(v_j + p_{j,i}) + \sum_{j > i}t_{i,j}\cdot(v_j + p_{i,j}) \leq C - v_i, &&\,\,\forall i \leq N\tag1\\&\quad\sum_{j < i}r_{j,i} + b_i = 1, &&\,\,\forall i \leq N\tag2\\&\quad r_{i,j} \leq t_{i,j}, &&\,\,\forall i < j \leq N\tag3\\&\quad r_{i,j} \leq b_i, &&\,\,\forall i < j \leq N\tag4\\&\quad t_{i,k} \geq t_{i,j} + t_{j,k} - 1, &&\,\,\forall i < j < k \leq N\tag5\end{alignat}

Edit 3: As correctly point out by @RobPratt constraint $(1)$ is not constraining enough. To tackle that let’s add an extra variable:

Let $s_{i,j,k} \in [0,1], \forall i < j < k \leq N$ be a helper variable indicating if $i$, $j$ and $k$ are in the same bin.

Constraint $(1)$ then becomes:

$$\small\sum_{j < i}t_{j,i}\cdot(v_j + p_{j,i}) + \sum_{j > i}t_{i,j}\cdot(v_j + p_{i,j}) +\sum_{i < j < k}s_{i,j,k}\cdot p_{j,k} + \sum_{j < i < k}s_{j,i,k}\cdot p_{j,k} + \sum_{j < k < i} s_{j,k,i}\cdot p_{j,k} \leq C - v_i, \forall i \leq N$$

We also need the following extra constraints:

\begin{alignat}{2}s_{i,j,k} &\geq t_{i,j} + t_{j,k} - 1, &&\,\,\forall i < j < k \leq N\tag6\\t_{i,j} &\geq t_{i,k} + t_{j,k} - 1, &&\,\,\forall i < j < k \leq N\tag7\\t_{j,k} &\geq t_{i,j} + t_{i,k} - 1, &&\,\,\forall i < j < k \leq N\tag8\end{alignat}

$\endgroup$
  • $\begingroup$ This formulation still needs a constraint to force items to be assigned to bins. Also, the final constraint can be strengthened by replacing $C$ with $C u_k$. $\endgroup$ – Rob Pratt Jun 26 at 12:40
  • $\begingroup$ @RobPratt the constraint that forces items to be assigned to the bins is not, $a_{i,k} \leq u_k $? $\endgroup$ – Dunkel Jun 26 at 13:05
  • $\begingroup$ @Dunkel no, RobPratt is correct, this one only ensure that you can only assign to a bin you use. I’ll edit the answer later today to address the remarks of RobPratt $\endgroup$ – Renaud M. Jun 26 at 13:07
  • $\begingroup$ @RenaudM. aha I see. Thank you! $\endgroup$ – Dunkel Jun 26 at 13:09
  • 1
    $\begingroup$ @Dunkel Interesting question. It makes the job of the solver harder, because it will end up revisiting the same solution multiple times (just swap the contents of any two boxes and you have another solution). If you are interested about this symmetry topic I wrote a two part blog post about it some years ago (orandtricks.wordpress.com/2013/08/12/…) where I compared two model for the same problem, with and without symmetries. The speed up without symmetries is significant. $\endgroup$ – Renaud M. Jun 26 at 18:37

Your Answer

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

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