An exact column-generation approach for the lot-type design problem

Abstract

We consider a fashion discounter distributing its many branches with integral multiples from a set of available lot-types. For the problem of approximating the branch and size dependent demand using those lots we propose a tailored exact column generation approach assisted by fast algorithms for intrinsic subproblems, which turns out to be very efficient on our real-world instances as well as on random instances.

A compact model for parameterizable sets of lot-types

For completeness, we want to mention that the large number of variables of our ILP formulation from Sect. 3 is far from being inavoidable. In the case of a parametrized set of lot-types, as described in Sect. 2, we can model the SLDP with fewer variables. However, the LP relaxation of the subsequent compact model yields large integrality gaps.

$$\begin{aligned} \min&\sum _{b\in {\mathcal {B}}}\sum _{s\in {\mathcal {S}}}\sum _{a\in {\mathcal {A}}} \delta _{b,s}^a\\ s.t.&\sum _{i\in {\mathcal {K}}}\sum _{m\in {\mathcal {M}}} x_{b,i,m}&= 1&\forall b\in {\mathcal {B}}\\&v_{b,s,i,m} -max_c\cdot x_{b,i,m}&\le 0&\forall (b,s,m,i)\in {\mathcal {U}}\\&v_{b,s,i,m}-l_{i,s}&\le 0&\forall (b,s,m,i)\in {\mathcal {U}}\\&v_{b,s,i,m} -l_{i,s}-max_c\cdot x_{b,i,m}&\ge -max_c&\forall (b,s,m,i)\in {\mathcal {U}}\\&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! {\underline{I}} \le \sum _{b\in {\mathcal {B}}}\sum _{s\in {\mathcal {S}}}\sum _{m\in {\mathcal {M}}} \sum _{i\in {\mathcal {K}}} m\cdot v_{b,s,i,m}&\le {\overline{I}}\\&l_{i,s}&\le max_c&\forall i\in {\mathcal {K}}, s\in {\mathcal {S}}\\&l_{i,s}&\ge min_c&\forall i\in {\mathcal {K}}, s\in {\mathcal {S}}\\&\sum _{s\in {\mathcal {S}}} l_{i,s}&\le max_t&i\in {\mathcal {K}}\\&\sum _{s\in {\mathcal {S}}} l_{i,s}&\ge min_t&\forall i\in {\mathcal {K}}\\&\delta _{b,s}^a+\sum \limits _{i\in {\mathcal {K}}}\sum \limits _{m\in {\mathcal {M}}}m\cdot v_{b,s,i,m}&\ge d_{b,s}^a&\forall b\in {\mathcal {B}},s\in {\mathcal {S}},a\in {\mathcal {A}}\\&\delta _{b,s}^a-\sum \limits _{i\in {\mathcal {K}}}\sum \limits _{m\in {\mathcal {M}}}m\cdot v_{b,s,i,m}&\ge -d_{b,s}^a&\forall b\in {\mathcal {B}},s\in {\mathcal {S}},a\in {\mathcal {A}}\\&x_{b,i,m}&\in \{0,1\}&\forall b\in {\mathcal {B}}, i\in {\mathcal {K}}, m\in {\mathcal {M}}\\&v_{b,s,i,m}&\ge 0&\forall (b,s,m,i)\in {\mathcal {U}}\\&l_{i,s}&\in {\mathbb {Z}}&\forall i\in {\mathcal {K}}, s\in {\mathcal {S}}\\&\delta _{b,s}^a&\ge 0&\forall b\in {\mathcal {B}},s\in {\mathcal {S}}, a\in {\mathcal {A}}, \end{aligned}$$

where we use the abbreviations ${\mathcal {K}}:=\{1,\dots ,k\}$ and ${\mathcal {U}}:={\mathcal {B}}\times {\mathcal {S}}\times {\mathcal {M}}\times {\mathcal {K}}$. Obviously, both the number of variables and the number of constraints is polynomial in the input parameters, in contrast to the model in Sect. 3. The meaning of the variables and constraints is as follows. We utilize the binary variable $x_{b,i,m}$ to model the assignment of the lot-type and multiplicity to a certain branch b, i.e., we have $x_{b,i,m}=1$ if and only if branch b is supplied with the ith selected lot-type in multiplicity m. Of course, for each branch b only one $x_{b,i,m}$ is one. In order to incorporate the bounds on the total number of supplied items we utilize the auxiliary variables $v_{b,s,i,m}$. For a given branch b and size s we set $v_{b,s,i,m}=l_{i,s}\cdot x_{b,i,m}$, i.e. $v_{b,s,i,m}=l_{i,s}$ if branch b is supplied with lot-type i in multiplicity m and $v_{b,s,i,m}=0$ otherwise. The linearization of this non-linear equation is quite standard using suitable big-M constants. The deviations $\delta _{b,s}^a$ then are given by

$$\begin{aligned} \delta _{b,s}^a=\left| d_{b,s}^a-\sum \limits _{i=1}^k\sum \limits _{m\in {\mathcal {M}}}m\cdot v_{b,s,i,m}\right| . \end{aligned}$$

Again the linearization of this non-linear equation is standard.³

Since the symmetric group on k elements acts on the k different lot-types one should additionally destroy the symmetry in the stated ILP formulation. This can be achieved by assuming that the lot-types $\left( l_{i,s}\right) _{s\in {\mathcal {S}}}$ are lexicographically ordered. For the ease of notation we assume that the set of sizes ${\mathcal {S}}$ is given by $\{1,\dots ,s\}$. As an abbreviation we set $t:=\max _c-\min _c+1$. With this the additional inequalities

$$\begin{aligned}&\sum _{j=1}^s \left( l_{i,j}-\min _c\right) \cdot t^{s-j}&\ge 1+\sum _{j=1}^s \left( l_{i+1,j}-\min _c\right) \cdot t^{s-j}&\forall 1\le i\le k-1, \end{aligned}$$

which are equivalent to $\sum _{j=1}^s \left( l_{i,j}-l_{i+1,j}\right) \cdot t^{s-j}\ge 1$ for all $1\le i\le k-1$, will do the job. We remark that using some additional auxiliary variables a numerical stable variant can be stated easily. (This becomes indispensable if $t^s$ gets too large.)

We remark that the LP relaxation of the compact model yields large integrality gaps.⁴ The typical approach would now be to solve a Dantzig-Wolfe decomposition of the compact model by dynamic column generation, leading to a master problem very similar to the SLDP model we presented in the first place. And column generation on that SLDP model is what we proposed in the paper.