Bin Packing with Relational Penalization
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.
modeling combinatorial-optimization quadratic-programming
TheSimpliFire♦
DunkelDunkel
$\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 '19 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 '19 at 21:57
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}
Rob PrattRob Pratt
$\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 '19 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 '19 at 16:49
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.
Marco LübbeckeMarco Lübbecke
$\begingroup$ Thank you for the paper, Marco! $\endgroup$ – Dunkel Jun 26 '19 at 13:10
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$$
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}
Renaud M.Renaud M.
$\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 '19 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 '19 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 '19 at 13:07
$\begingroup$ @RenaudM. aha I see. Thank you! $\endgroup$ – Dunkel Jun 26 '19 at 13:09
$\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 '19 at 18:37
Not the answer you're looking for? Browse other questions tagged modeling combinatorial-optimization quadratic-programming or ask your own question.
Mathematically creating the 'perfect' permutation for reservations in a hostel
How to reformulate (linearize/convexify) a budgeted assignment problem?
Static stochastic knapsack problem: unbounded version
Expressing a chain of boolean ORs using ILP involving different variables
Divisibility constraints in integer programming
Finding an Objective Function for Assigning Employees to Sequence Dates
Shipments consolidation - how to model mutually exclusive items with OR-Tools CP Solver in Python (multi-knapsack, updated)
Two-stage $k$-means clustering
How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?
Equivalence of formulations