Tightening MILPs by Reformulation

Titelangaben

Kießling, Miriam ; Kurz, Sascha ; Rambau, Jörg:
Tightening MILPs by Reformulation.
2024
Veranstaltung: 25th International Symposium on Mathematical Programming (ISMP 2024) , 21.-26.07.2024 , Montreal, Kanada.
(Veranstaltungsbeitrag: Kongress/Konferenz/Symposium/Tagung , Vortrag )

Weitere URLs

Abstract

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.