Bin packing: config LP is not affected by grouping identical items

Dependencies:

1. Bin packing: configuration LP

$$ $$ $$ $$ $$ $$ $$ $$ The optimal objective value of the configuration LP of a bin packing instance doesn't depend on how identical items are grouped into types.

Formally, let $I$ be a bin packing instance with $n$ items such that there are $m$ types of items, and all items of the same type are identical. Let $b_i$ be the number of items of type $i$. Let $f:[n]\mapsto [m]$ be a function that takes an item $i$ and returns its type. For an item of type $i$, define $f^{-1}(i):=\{j\in I:f(j)=i\}$ i.e., $f^{-1}(i)$ is the set of items whose type is $i$.

An expanded configuration $C$ is an $n$-tuple $(r_1,\dots ,r_n)\in \{0,1{\}}^n$, where the items $\{i\in I:r_i=1\}$ can fit into a bin. For an $n$-tuple $C$, define $f(C):=(t_1,\dots ,t_m)$, where $t_i:=\sum _{j\in f^{-1}(i)}{r}_i$. $f(C)$ is called the compact version of $C$. Let $\mathcal{C}$ be the set of all expanded configurations and $f(\mathcal{C})=\{f(C):C\in \mathcal{C}\}$ be the set of all compact configurations. Note that a compact representation can correspond to multiple expanded representations. Let $N:=|\mathcal{C}|$ and $N^{\prime }:=|f(\mathcal{C})|$. Let $T\in \{0,1{\}}^{n\times N}$ be the expanded configuration matrix of $I$, i.e., $T[i,C]=1$ if expanded configuration $C$ contains item $i$. Let $f(T)\in {\mathbb{Z}}_{\ge 0}^{m\times N^{\prime }}$ be the compact configuration matrix of $I$, i.e., $f(T)[i,C]$ is the number of items of type $i$ in compact configuration $C$.

Then the following two linear programs, called the expanded configuration LP (denoted by $\mathrm{LP}$) and the compact configuration LP (denoted by $f(\text{LP})$) have the same optimal objective value: $$\underset{x\in {\mathbb{R}}^N}{min}\mathrm{sum}(x)\text{ where }Tx\ge b,x\ge 0.$$ $$\underset{x\in {\mathbb{R}}^{N^{\prime }}}{min}\mathrm{sum}(x)\text{ where }f(T)x\ge \mathbf{1},x\ge 0.$$

Proof that $\mathrm{opt}(f(\text{LP}))\le \mathrm{opt}(\mathrm{LP})$

Let $x\in [0,1{]}^N$ be an optimal solution to $\mathrm{LP}$.

For a compact configuration $C$, define $f^{-1}(C):=\{D\in \mathcal{C}:f(D)=C\}$ and define $y_C:=\sum _{D\in f^{-1}(C)}{x}_D$. Then for the vector $y:=[y_C:y\in f(\mathcal{C})]$, we have $\mathrm{sum}(y)=\mathrm{sum}(x)=\mathrm{opt}(\mathrm{LP})$. We will prove that $y$ is a feasible solution to $f(\text{LP})$, which would imply that $\mathrm{opt}(f(\text{LP}))\le \mathrm{sum}(y)=\mathrm{opt}(\mathrm{LP})$.

Let $A\in {\mathbb{Z}}_{\ge 0}^{m\times N}$ where $A[i,D]$ is the number of items of type $i$ in expanded configuration $D$. Then $f(T)[i,f(D)]=A[i,D]=\sum _{j\in f^{-1}(i)}T[j,D]$.

For any $i\in [m]$, we get $$\begin{array}{rl}(f(T)y{)}_i& =\sum _{C\in f(\mathcal{C})}f(T)[i,C]y_C\\ & =\sum _{C\in f(\mathcal{C})}\sum _{D\in f^{-1}(C)}f(T)[i,C]x_D\\ & =\sum _{D\in \mathcal{C}}A[i,D]x_D\\ & =\sum _{j\in f^{-1}(i)}\sum _{D\in \mathcal{C}}T[j,D]x_D\\ & \ge \sum _{j\in f^{-1}(i)}1=b_i.\end{array}$$ Hence, $f(T)y\ge b$, so $y$ is feasible for $f(\text{LP})$.

Proof that $\mathrm{opt}(\mathrm{LP})\le \mathrm{opt}(f(\text{LP}))$

Without loss of generality, assume $b_i\ge 1$ for each $i\in [m]$. We will show how to convert $f(\text{LP})$ to $\mathrm{LP}$ by gradually increasing the number of types.

Let $f$ be the function that gives the type of each item. Let $\{i_1,i_2,\dots ,i_{b_m}\}$ be items of type $m$. Without loss of generality, assume $b_m\ge 2$. We'll pick an item of type $m$ and change its type to $m+1$. Formally, define $f^{\prime }:[n]\mapsto [m+1]$ be defined as $$f^{\prime }(i)=\{\begin{array}{ll}f(i)& f(i)\ne m\\ m& f(i)=m& i\ne i_{b_m}\\ m+1& f(i)=m& i=i_{b_m}\end{array}.$$

Let $x$ be an optimal solution to $f(\text{LP})$. For $C\in f(\mathcal{C})$, let $g(C):=\{f^{\prime }(D):D\in f^{-1}(C)\}$. Note that for any $C\in f(\mathcal{C})$, we have $1\le |g(C)|\le 2$. We will define a vector $y$, and show that it's a solution to $f^{\prime }(\mathrm{LP})$. We will also show that for any $C\in f(\mathcal{C})$, $\sum _{D\in g(C)}{y}_D=x_C$. This will imply $\mathrm{opt}(f^{\prime }(\mathrm{LP}))\le \mathrm{sum}(y)=\mathrm{sum}(x)=\mathrm{opt}(f(\text{LP}))$.

Let $i\le m-1$ and $D\in g(C)$. Then $f^{\prime }(T)[i,D]=f(T)[i,C]$. Hence, $$\begin{array}{rl}(f^{\prime }(T)y{)}_i& =\sum _{D\in f^{\prime }(\mathcal{C})}{f}^{\prime }(T)[i,D]y_D\\ & =\sum _{C\in f(\mathcal{C})}\sum _{D\in g(C)}{f}^{\prime }(T)[i,D]y_D\\ & =\sum _{C\in f(\mathcal{C})}f(T)[i,C]\sum _{D\in g(C)}{y}_D\\ & =\sum _{C\in f(\mathcal{C})}f(T)[i,C]x_C\\ & =(f(T)x{)}_i\ge 1.\end{array}$$ Therefore, $y$ satisfies the first $m-1$ constraints of $f^{\prime }(\mathrm{LP})$.

Let $\mathcal{S}:=\{C\in f(\mathcal{C}):f(T)[m,C]\ge 1\}$, i.e, $\mathcal{S}$ is the set of configurations containing at least one item of type $m$. Order the configurations in $\mathcal{S}$ in decreasing order of number of items of type $m$ ($f(T)[m,C]$). Let $C_1,C_2,\dots ,C_p$ be the resulting configurations. We know that $f(T)[m,C]\le b_m$, so $$\begin{array}{rl}& b_m\le \sum _{C\in f(\mathcal{C})}f(T)[m,C]x_C\le \sum _{j=1}^p{b}_m{x}_{C_j}\\ & ⟹\sum _{j=1}^p{x}_{C_j}\ge 1.\end{array}$$ Let $k$ be the smallest number such that $\sum _{j=1}^k{x}_{C_j}\ge 1$. Let $k^{\prime }$ be the largest number such that $f(T)[m,C_j]=b_m$.

Case 1: $k\le k^{\prime }$: Let $$y_D:=\{\begin{array}{ll}{x}_{C_j}& D\in g(C_j)\text{ and }j\le k^{\prime }\text{ and }{f}^{\prime }(T)[m+1,D]=1\\ 0& D\in g(C_j)\text{ and }j\le k^{\prime }\text{ and }{f}^{\prime }(T)[m+1,D]=0\\ 0& D\in g(C_j)\text{ and }j>k^{\prime }\text{ and }{f}^{\prime }(T)[m+1,D]=1\\ x_{C_j}& D\in g(C_j)\text{ and }j>k^{\prime }\text{ and }{f}^{\prime }(T)[m+1,D]=0\\ x_C& D\in g(C)\text{ and }C\notin \mathcal{S}\end{array}.$$ When $j>k^{\prime }$, $\mathrm{\exists }D\in g(C_j)$ such that $f^{\prime }(T)[m+1,D]=0$. This implies that for any $C\in f(\mathcal{C})$, we have $\sum _{D\in g(C)}{y}_D=x_C$.

$$\begin{array}{rl}(f^{\prime }(T)y{)}_{m+1}& =\sum _{D\in f^{\prime }(\mathcal{C})}{f}^{\prime }(T)[m,D]y_D\\ & =\sum _{j=1}^{k^{\prime }}{x}_{C_j}\\ & \ge \sum _{j=1}^k{x}_{C_j}\\ & \ge 1.\end{array}$$ For $C\in \mathcal{S}$, let $g_1(C)$ be the unique configuration $D\in g(C)$ such that $f^{\prime }(T)[m+1,D]=1$. Then $$\begin{array}{rl}(f^{\prime }(T)y{)}_m& =\sum _{D\in f^{\prime }(\mathcal{C})}{f}^{\prime }(T)[m,D]y_D\\ & \ge \sum _{j=1}^{k^{\prime }}{f}^{\prime }(T)[m,g_1(C_j)]x_{C_j}\\ & =\sum _{j=1}^{k^{\prime }}(b_m-1)x_{C_j}\\ & \ge (b_m-1)\sum _{j=1}^k{x}_{C_j}\\ & \ge (b_m-1).\end{array}$$ Therefore, $y$ is feasible for $f^{\prime }(\mathrm{LP})$.

Case 2: $k>k^{\prime }$: Hence, $f(T)[m,C_k]\le b_m-1$. $$y_D:=\{\begin{array}{ll}{x}_{C_j}& D\in g(C_j)\text{ and }j<k\text{ and }{f}^{\prime }(T)[m+1,D]=1\\ 0& D\in g(C_j)\text{ and }j<k\text{ and }{f}^{\prime }(T)[m+1,D]=0\\ 1-\sum _{j=1}^{k-1}{x}_{C_j}& D\in g(C_k)\text{ and }{f}^{\prime }(T)[m+1,D]=1\\ x_{C_k}-1+\sum _{j=1}^{k-1}{x}_{C_j}& D\in g(C_k)\text{ and }{f}^{\prime }(T)[m+1,D]=0\\ 0& D\in g(C_j)\text{ and }j>k\text{ and }{f}^{\prime }(T)[m+1,D]=1\\ x_{C_j}& D\in g(C_j)\text{ and }j>k\text{ and }{f}^{\prime }(T)[m+1,D]=0\\ x_C& D\in g(C)\text{ and }C\notin \mathcal{S}\end{array}.$$ When $j\ge k>k^{\prime }$, $\mathrm{\exists }D\in g(C_j)$ such that $f^{\prime }(T)[m+1,D]=0$. This implies that for any $C\in f(\mathcal{C})$, we have $\sum _{D\in g(C)}{y}_D=x_C$.

$$(f^{\prime }(T)y{)}_{m+1}=\sum _{D\in f^{\prime }(\mathcal{C})}{f}^{\prime }(T)[m,D]y_D=1.$$ Let $n_j:=f(T)[m,C_j]$ and $z_j:=x_{C_j}$. Then $$\begin{array}{rl}(f^{\prime }(T)y{)}_m& =\sum _{D\in f^{\prime }(\mathcal{C})}{f}^{\prime }(T)[m,D]y_D\\ & =\sum _{j=1}^{k-1}(n_j-1)z_j+(n_k-1)(1-\sum _{j=1}^{k-1}{z}_j)+n_k(z_k-1+\sum _{j=1}^{k-1}{z}_j)+\sum _{j=k+1}^p{n}_j{z}_j\\ & =\sum _{j=1}^p{n}_j{z}_j-1\\ & =\sum _{j=1}^{p}f(T)[m,C_j]x_{C_j}-1\\ & =(f(T)x{)}_m-1\\ & \ge b_m-1.\end{array}$$ Therefore, $y$ is feasible for $f^{\prime }(\mathrm{LP})$.

Dependency for:

1. 1BP: Karmarkar-Karp algorithm (broken)

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. Bin packing and Knapsack
2. Bin packing: configuration LP