Felix-Klein-Kolloquium: Augmented Subproblem Grinding for the Lot-Type Design Problem

We consider a fashion discounter supplying its many branches with integral multiples from a set of available lot-types. The lot-type design problem (LDP) [Gaul et al. 2010] asks: which (integral) multiples of which (integral) lot-types (assortments of sizes) should be supplied to a set of branches in order to meet a (fractional) expected demand as closely as possible? There is a compact LDP-model; however, its integral gap is so large that it cannot be solved for most practical instances. On the other hand, the tightest LDP-model known so far [Gaul et al. 2010] can have billions of variables. (For 12 different sizes, reasonable for lingerie or children’s clothing, there are 1,159,533,584 different lot-types, if we assume at most 5 items of each size and a total number of items in a lot-type between 12 and 30.) Thus, not for all instances the tight model can be fed to a computer statically.

We show how the tight model, which can be interpreted as a Dantzig-Wolfe decomposition (a standard-reformulation to tighten ILP-models) of the compact model, can be solved by Augmented Subproblem Grinding, which is a new Branch-and-Cut-and -Price variant, well-suited for tight models. It enforces a binary branch-and-price tree. One branch consists of a single promising subproblem that is solved immediately ("ground off"). The other branch is tightened by a new constraint ("augmented") that excludes all solutions consisting of only known columns (a non- standard reformulation).

The theoretical core component is the identification of a characteristic lifting of dual variables in the reduced master problem for all the constraints that would emerge with new variables. Computational results on real-world instances as well as on randomized stress-tests show that for the tight LDP-model Augmented Subproblem Grinding speeds up the solution by a factor of more than 100 on average compared to the solution of the static model and solves instances (up to 9,867,114,720,320 variables) that cannot be solved statically at all.

Referent: Prof. Dr. Jörg Rambau, Universität Bayreuth

Ort: Gebäude 48, Raum 210

Die Vorträge des Felix-Klein-Kolloquiums finden jeweils um 17.15 Uhr im Raum 210 des Mathematik-Gebäudes 48 statt. Zuvor gibt es ab 16.45 Uhr die Gelegenheit, die Sprecherin oder den Sprecher beim Kolloquiumstee in Raum 580 zu treffen.