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

An exact column-generation approach for the lot-type design problem Miriam Kießling Sascha Kurz J¨org Rambau August 3, 2012 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. Keywords: p-median, facility location, lottype design, real world data, column generation Mathematics subjects classification: 90C06; 90C90; 90B99 1 Introduction Due to small profit margins of most fashion discounters, applying OR methods is mandatory for them. In order to reduce the handling costs and the error proneness in the central warehouse, our business partner orders all products in multiples of so-called lot-types from the suppliers and distributes them without any replenishing to its branches. A lot-type specifies a number of pieces of a product for each available size, e.g., lot-type (1,2,2,1) means two pieces of size M and L, one piece of size S and XL, if the sizes are (S,M,L,XL). We want to solve the following approximation problem: which (integral) multiples of which (integral) lot-types should be supplied to a set of branches in order to meet a (fractional) expected demand as closely as possible? We call this specific demand approximation problem the lot-type design problem (LDP) in [6]. In that paper, also a basic model for the LDP was introduced, accompanied by an integer linear programming formulation and a tailored heuristic, which turned out to perform very well for the real-world data of our partner. For many practical instances the set of applicable lot-types and thus the number of variables is so large that the ILP formulation from [6] cannot be solved directly.1In this paper, we therefore propose a column generation approach. For our problem adding a new variable or column requires the introduction 1E.g. for 12 different sizes, which is reasonable for lingerie or children’s clothing, there are 1 159 533 584 different lot-types, if we assume that there should be at most 5 items of each size and that the total number of items in a lot-type should be between 12 and 30. 1 of additional constraints in most cases. So we have to generate columns and cuts simultaneously. Similar problems and approaches have been addressed in [5, 10]. In order to overcome the integrality gap of the ILP relaxation we propose a tailored branching scheme complemented by the use of additional cover cuts. This results in an exact column generation approach for the LDP, which is enhanced by properly chosen algorithms for important subproblems. We apply this algorithm to a stochastic version SLDP of the LDP, where the expectation over more than one demand-scenario is optimized. The SLDP is of the same form as the LDP, and thus all optimization techniques viable for the LDP immediately apply to the SLDP. Since using the SLDP instead of the LDP can make decisions more robust against forecasting errors, we based our investigations in this paper on the SLDP. Branch-and-price algorithms are common for large-scale integer programming problems [8]. Unifying general remarks can be found in [2, 11]. Branchprice-and-cut algorithms are surveyed in [9]. The LDP is related to the p-median and the facility location problem: for recent computational results on large instances of the p-median problem we refer the reader to [1, 4, 7]. A formal problem statement is given in Section 2, followed by an ILP model in Section 3. Our algorithm is presented in Section 4. We show computational results on real-world data in Section 5, before we conclude with Section 6. 2 Formal problem statement We consider the distribution of supply for a single product and start with the formal problem statement in the deterministic context. Data. Let Bbe the set of branches, Sbe the set of sizes, and M ⊂ Nbe an interval of possible multiples. A lot-type is a vector (ls)s∈S ∈N|S|,lis applicable if minc≤ls≤maxcfor all s∈ S and mint≤Ps∈S ls≤maxt.2 By Lwe abbreviate the set of applicable lot-types. There is an upper bound Iand a lower bound Igiven on the total supply over all branches and sizes. Moreover, there is an upper bound k∈Non the number of lot-types used. By db,s ∈Q≥0we denote the expected demand at branch bin size s. Decisions. Consider an assignment of a unique lot-type l(b)∈ L and an assignment of a unique multiplicity m(b)∈ M to each branch b∈ B. These data specify that m(b) lots of lot-type l(b) are to be delivered to branch b. Objective. The goal is to find a subset L⊆ L of at most klot-types and assignments l(b)∈ L and m(b)∈ M such that the total supply is within the bounds I,I, and the deviation between inventory and demand is minimized. 2A parameterizable set of applicable lot-types is a practically relevant case: By setting minc= 1 we can enforce that each branch is supplied in each size with at least one item, a requirement which legally arises for advertised products. Since the main advantage of using lot-types lies in the reduction of the number of picks in the central warehouse, we should guarantee, that this effect does not dwindle away by selecting lot-types with too few items, which can be controlled by a suitable value for mint. There are practical reasons for the parameter maxt, too: combining too many winter coats in a lot would cause serious handling problems. 2 We call this optimization problem the Lot-Type Design Problem (LDP), see [6] for more details. Using the introduced decision variables we can express the relevant decision-dependent entities as follows. The inventory of branch b in size sgiven assignments l(b) and m(b) is given by Ib,s(l, m) = m(b)l(b)s. Moreover, the total supply resulting from l(b) and m(b) is given by I(l, m) = Pb∈B Ps∈S Ib,s(l, m). This deterministic model can slightly be enhanced to a stochastic model by considering a set Aof scenarios (for the success of the product). For each scenario a∈ A we denote by paits probability and with da b,s ∈Q≥0the demand at Branch bin Size sin Scenario afor all b∈ B and s∈ S. The goal then is to minimize the expected total deviation between inventory and demand. We call this single-stage stochastic optimization problem the Stochastic LotType Design Problem (SLDP). The SLDP is equivalent to an ordinary LDP with a modified objective function, since the expected total deviation ∆(l, m) can be written as Pb∈B Ps∈S Pa∈A paδa b,s(l, m), where δa b,s(l, m) := |da b,s −Ia b,s(l, m)|. In other words, the certainty equivalence principle (see e.g. [3, p. 28]) holds if the input data are the expected deviations for all branches and sizes. Certainty equivalence does not hold if the input data are the expected demands, though. 3 Modelling We use binary assignment variables xb,l,m indicating whether l(b) = land m(b) = mand binary selection variables ylindicating whether l∈Lin order to model the SLDP as the following integer linear program. As an abbreviation we utilize |l|:= P s∈S ls. min X b∈B X l∈L X m∈M cb,l,m ·xb,l,m (1) s.t. X l∈L X m∈M xb,l,m = 1 ∀b∈ B (2) X l∈L yl≤k(3) X m∈M xb,l,m ≤yl∀b∈ B, l ∈ L (4) I≤X b∈B X l∈L X m∈M m· |l| · xb,l,m ≤I(5) xb,l,m ∈ {0,1} ∀b∈ B, l ∈ L, m ∈ M (6) yl∈ {0,1} ∀l∈ L,(7) where cb,l,m =P a∈A pa·P s∈Sda b,s −m·ls≥0. 3 4 A custom-made branch-and-price algorithm Since the set of applicable lot-types and, thus, the set of binary variables in the stated ILP formulation may become quite large, a natural approach is to consider applicable lot-types dynamically in a branch-and-price algorithm. In this section we show how special structure can be used to obtain a fast branch-and-price algorithm for practically relevant instances: We typically have 300 ≤ |B| ≤ 1600 and 3 ≤ |M| ≤ 7 while |L| can be around 109, see the example stated in the introduction. The idea of our specialized exact branch-and-price algorithm is based on the following practical observations on real-world data: •The integrality gap of our SLDP model is small. •Solutions generated by heuristics perform very well (see [6]). •There seems to be a “small” set of good and a “large” set of bad solutions. •No mathematical structure of the set of good solutions is known a-priori. •A proof of optimality is wanted. This led us to the following branch-and-price algorithm: (1) Use the heuristics from [6] to determine a starting solution (x?, y?). (2) Initialize the restricted master problem RMP (see below), as follows: For each branch bwe compute the three (locally) best fitting lot-types and add them to ζb. Additionally we add all lot-types used in (x?, y?). We set L0=∪b∈B ζ(b). For each branch b∈ B and each lot-type l∈ζ(b) we compute the corresponding optimal multiplicity ˆmand set η(b, l) = {ˆm−1,ˆm, ˆm+ 1}∩M. (3) Let (x0, y0) be an optimal solution of RMP. If the costs are smaller than the costs of (x?, y?), then we set ¯ L={l∈ L0|y0 l≥ε}, where εis a small constant, e.g., ε= 0.15, and branch on ¯ L, i.e., we perform step (5). (4) We solve the pricing problem and possibly add lot-types from L0to a ζb, enlarge a η(b, l), or add a new lot-type to L0, i.e., we generate new columns and rows, go on with step (3), or stop otherwise. (5) Solve the lot-type design problem restricted to the set ¯ Lof applicable lottypes and possibly update the best solution (x?, y?). Add the cover-cut Pl∈Ciyl≤k−1 with Ci=¯ Lto RPM and go to step (3). Step (1) – the starting heuristics – is sketched and Subsection 4.7 and used in step (2) to initialize the set of columns and constraints of the RMP, see Subsection 4.6. The branching scheme of step (3) and (5) is described in Subsection 4.4. The pricing algorithm, i.e. step (4) can be found in Subsection 4.5. 4 In order to obtain fast implementations of the mentioned five steps we have identified some common subproblems which can be solved by purely combinatorial algorithms. Those workhorse methods for determining locally best fitting lot-types, determining optimal multipliers and solving the restriction of the SLDP to kapplicable lot-types are stated in subsections 4.1, 4.2, and 4.3, respectively. Before we start with the details let us first comment on the adapted branching scheme in steps (3) and (5). We generate two branches: One branch containing the completely enumerated decision options (this branch can be solved to optimality immediately, e.g., by complete enumeration), one branch with the remaining decision options only (this branch receives a single cover cut excluding the decision options considered in the other branch). Although this kind of branching seems weird at first glance – splitting off at most a usually constant number of feasible solutions asymptotically yields a linear depth of the full tree –, there is a rationale behind this: Whenever we can find all the few good solutions by solving promising subproblems, we can prune the remaining subtree as soon as all subproblems containing a good solution have been generated. Because of the small integrality gap, this can be detected by the LP relaxation value. And a pricing algorithm can prove LP optimality even if not all variables have been generated. Our branch-and-price algorithm must generate a promising subproblem in such a way that excluding that subproblem can be done efficiently in the restricted master problem. The master problem (MP) of a branch-and-price node is defined to consist of the static SLDP model plus some cover-cuts (14) (see Subsection 4.4) of the node, which exclude the decision options of subproblems. (MP) can be restricted to a manageable sized restricted master problem (RMP) by the following: We only consider a (small) subset L0⊆ L of the lot-types. For each branch b∈ B we consider a subset ζL0(b) = ζ(b)⊆ L0of these lot-types and for each l∈ζL0(b) we consider only a subset ηM(b, l) = η(b, l)⊆ M of the multiplicities. The restricted master problem (RMP) then reads as follows: min X b∈B X l∈ζ(b)X m∈η(b,l) cb,l,m ·xb,l,m (8) s.t. X l∈ζ(b)X m∈η(b,l) xb,l,m = 1 ∀b∈ B (9) X l∈L0 −yl≥ −k(10) X b∈B X l∈ζ(b)X m∈η(b,l) m· |l| · xb,l,m ≥I(11) X b∈B X l∈ζ(b)X m∈η(b,l) −m· |l| · xb,l,m ≥ −I(12) X m∈η(b,l) −xb,l,m +yl≥0∀b∈ B, l ∈ζ(b) (13) 5 X l∈Ci −yl≥ −γi∀i∈ I (14) xb,l,m ≥0∀b∈ B, l ∈ζ(b), m ∈η(b, l) (15) yl≥0∀l∈ L0.(16) The dual restricted master problem (DRMP) is then given by: max X b∈B αb−kπ +Iu −Iv −X i∈I γiµi(17) s.t. αb−βb,l +m|l|u−m|l|v≤cb,l,m ∀b∈ B, l ∈ζ(b), m ∈η(b, l) (18) −π+X b∈B :l∈ζ(b) βb,l −X i∈I :l∈Ci µi≤0∀l∈ L0(19) αb∈R∀b∈ B (20) π, u, v ≥0 (21) βb,l ≥0∀b∈ B, l ∈ζ(b) (22) µi≥0∀i∈ I.(23) The pricing problem is defined by finding those constraints in the dual (DMP) of the unrestricted master problem (MP) that are most violated by the current solution of (DRMP). 4.1 Workhorse 1: Finding best fitting lot-types for single branches The following optimization problem is extensively used in the pricing step, see Lemma 1, and in primal heuristics in Sections 4.6 and 4.7 (setting Ω = 0, L0=∅). For a given branch bwe show how to solve the optimization problem min l∈L\L0,m∈M cb,l,m −Ω·m· |l|,(24) where Ω = u−v∈Ris given. So let us assume that the cost coefficients cb,l,m are given by the expression in Section 2, the set of lot-types Lis parameterized using the integers minc, mint, maxc, maxt,L0is given by an explicit list, and M=m, mfor two integers m, m. In a preprocessing step we compute for each branch b∈ B, each size s∈ S, and each multiplicity m∈ M the values γ(b, s, m, ls) = Pa∈A pa·da b,s −m·ls, where minc≤ls≤maxc, and ψ(b, s, m) = minγ(b, s, m, ls) : minc≤ls≤ maxc. Let Λ be the value cb,ˆ l, ˜m−Ω·˜m·|ˆ l|of our current champion, where we initialize Λ = +∞. Next we fix the possible multiplicities m≤m≤mand in each case start a branch&bound tree. To describe the nodes of the branch&bound tree we use a set F ⊆ S, where we set F=∅for the root node. In each fixing step we 6 choose a size s∈ S\F and fix minc≤ls≤maxc, i.e., the number of items in size sof the emerging lot-type. If we either have Ps∈F ls+Ps∈S\F minc>maxtor Ps∈F ls+Ps∈S\F maxc<mint, we can prune the search tree, since the fixed values lscan not be continued to an admissible lot-type. Now let us estimate the minimal possible cost for the partially fixed lottype corresponding to F. The maximum number of items that can occur in the remaining sizes in S\F is given by r= min|S\F| · maxc,maxt−Ps∈F ls. Similarly the minimum number of items of the remaining sizes is given by r= max|S\F|·minc,mint−Ps∈F ls. If Ω >0 then we set r=r, otherwise we set r=r. With this, every extension of the partially fixed lot-type corresponding to Fresults in costs of at least X s∈F γ(b, s, m, ls) + X s∈S\F ψ(b, s, m)−Ω·m·X s∈F ls−Ω·m·r. If these costs are at least as large as the costs Λ of our current champion, we can prune the search tree. In the leafs, where the lot-type lis completely specified, we check whether l∈ L0. If this is not the case we have found a new champion. 4.2 Workhorse 2: Optimal multiplicities A rather easy but relevant subproblem of the SLDP is the determination of an optimal multiplicity ˆm, i.e., for a given branch band lot-type lwe ask for ˆm∈ M satisfying cb,l, ˆm≤cb,l,m for all m∈ M. The most simple way would be to check all |M| possibilities for mand pick the best one. As the deviations cb,l,m are convex in mand Mconsists of an interval of non-negative integers, we can determine ˆmin at most O(log |M|) evaluations using binary search. 4.3 Workhorse 3: Solving the SLDP-k In this subsection we present an efficient algorithm for the SLDP-k, which is the SLDP with only kapplicable lot-types. In other words we assume that the yiof the ILP formulation from Section 2 are already fixed and it remains to determine the optimal xb,l,m. If we drop Inequality (5) on the overall supply the resulting optimization problem becomes easy. Since the number kof lot-types is a small number we may check them all for each branch b∈ B and determine the corresponding optimal multiplicity using the methods from Subsection 4.2. This way, we can easily determine a best fitting lot-type l(b) and an optimal multiplicity m(b) for each branch separately. If accidentally Inequality (5) is valid, then we have an optimum solution for the SLDP-k. Or otherwise we have derived a lower bound for its optimum objective value. In the latter case we consider the SLDP-kand relax the integrality condition to 0 ≤xb,l,m ≤1. Due to the convexity of the objective function (1) this problem can be efficiently solved by greedily adjusting the multiplicities m(b) and the assignments l(b) in order to fulfill Inequality (5). 7 For brevity we discuss only the case where the overall supply is strictly larger than I. Here we have to iteratively take away items from some branches. To this end we introduce relative costs for each branch band each alternative. If m(b)−1 is also an element of Mthen we can simply reduce m(b) by one, which results in relative costs of cb,l(b),m(b)−1−cb,l(b),m(b) |l(b)|≥0 per item. Another possibility is to change the used lot-type l(b). Therefore we denote by ϕb(l0) the largest integer such that ϕb(l0)· |l0|< m(b)· |l(b)|, i.e., ϕb(l0) is the multiplicity mfor branch band lot-type lresulting in a minimal coefficient cb,l0,m while reducing the number of supplied items to branch b. If and only if ϕb(l0)∈ L we can modify the pair (l(b), m(b)) to (l0, ϕb(l0)) resulting in relative costs of cb,l,ϕb(l0)−cb,l(b),m(b) m(b)· |l(b)| − ϕb(l0)· |l0|≥0 per item. So, after at most O(1 + (k−1) log M) evaluations of coefficients cb,l,m we can determine the alternative with minimum relative costs ∆− bfor each branch b, where we set ∆− b=∞if there is no feasible alternative. If we have the relative costs ∆− bfor all b∈ B and the corresponding actions at hand, we can pick a ˆ b∈ B which minimizes ∆− b. Let δ > 0 denote the number of items which are removed by the corresponding action and Idenote the overall supply corresponding to the current pair of functions l, b. Due to the convexity of the objective function (1) we can state the following: (a) If ∆− ˆ b=∞, then the SLDP-ksubproblem is infeasible. (b) If I−δ≥I, then, after performing the greedily optimal action, the new assignments ˜ l(b) and ˜m(b) correspond to an optimal solution of SLDP-k, where Inequality (5) is replaced by P b∈B P l∈L P m∈M m· |l| · xb,l,m ≤I−δ. (c) If I−δ < I we obtain the optimal solution of the SLDP-kwith fractional variables xb,l,m by utilizing a suitable linear combination of the old assignment (l(b), m(b)) and the cheapest decreasing alternative (˜ l(b),˜m(b)). Thus, after a finite number of iterations, depending at most linearly on the difference between the initial overall supply and I, we obtain the optimal solution of the SLDP-kwith at most two fractional variables xb,l,m. To also solve the integral SLDP-kwe utilize a branch-bound approach. In order to obtain an efficient algorithm we maintain the ∆− b-values in a heap data structure, so that in each recursion step we only have to determine one new ∆− b-value, while the update of the heap can be done in O(log |B|). 4.4 Branching into the most promising subproblem and the rest At a node of Depth iof the branch-and-price tree we split the current node into two: one branch contains the most promising subproblem, the other branch contains the remaining decision options. 8 Let us now state how to determine the most promising subproblem: Given an optimal solution of the current (RMP), we consider the values of the attained yvariables. To simplify the notation we assume that they are ordered downwards, i.e., y1≥y2≥ · · · ≥ y|L0|. For a small constant ε > 0, e.g., ε= 0.15, we consider an index qsuch that yq≥εand yq+1 < ε. We call the subproblem of the SLDP with a given C:= {1, . . . , q}⊆Las its set of applicable lot-types the most promising subproblem SLDP|Cof SLDP. The node corresponding SLDP|Ciis then solved exactly. If Ci k≤100 000 then we completely enumerate all k-subsets of lot-types in Ciand subsequently solve the corresponding SLDP-k(see Subsection 4.3). Otherwise we solve the corresponding ILP formulation from Section 3 directly. The other node has to be worked on further by branch-and-price: Excluding the most promising subproblem in this branch can be achieved by adding a single cover cut Pl∈Ciyl≤γi:= k−1. 4.5 The combinatorial pricing algorithm We associate with the constraints of the master problem (MP) the dual variables αb,π,u,v,βb,l, and µi. With this, for each lot-type lthe reduced costs for a variable xb,l,m are given by cb,l,m −αb−m· |l| · (u−v) + βb,l,(25) and for a variable ylthe reduced costs are given by 0 + π−X b∈B βb,l +X i∈I:l∈Ci µi.(26) Lemma 1 If Si∈I Ci⊆ L0, min b∈B,l∈ζ(b),m∈M cb,l,m −αb−m· |l| · (u−v) + βb,l ≥0,(27) min b∈B,l∈L0\ζ(b),m∈M cb,l,m −αb−m· |l| · (u−v)≥0,and (28) max L\L0X b∈B max0,max m∈M αb+m· |l| · (u−v)−cb,l,m≤π(29) then the current optimal solution of (RMP) is optimal for (MP). Proof 1 If Inequality (27) is valid, then there is no variable xb,l,m with l∈ ζ(b)having negative reduced costs. For a given branch band a given lot-type l∈ L\ζ(b)(DRMP) does not contain the variable βb,l since (RMP) does not include the corresponding inequality. We extend the dual solution by setting βb,l =0 : l∈ L0\ζ(b), max (0,maxm∈M αb+m· |l| · (u−v)−cb,l,m) : l∈ L\L0 (30) 9