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 nonstandard
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

Der Vortrag findet um 17.15 Uhr im Raum 210 des Mathematik-Gebäudes 48 statt.

Studierende, Doktorandinnen und Doktoranden sowie Wissenschaftlerinnen und Wissenschaftler des Fachbereichs Mathematik der RPTU und des Fraunhofer ITWM sind herzlich zum Kolloquium eingeladen!