Bin Packing with Relational Penalization

Question

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 accommodated using the least amount of bins. Each object $x_i$ has a volume $ v_i < C $. However, there is a penalization $ p_{ij} $ for accommodating 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.

Answer 1

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}

Answer 2

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.

Answer 3

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 pointed 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}