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.

Given a group of machines, the objective is to decide each machine's production schedule, and when maintenance actions should be performed. Our focus is on variants where the (independent) machines are complex, with many interacting components, and their joint production must satisfy a predetermined demand. Furthermore, the production load of a machine impacts its need for maintenance.

A direct formulation can be very slow, especially when there are many identical machines, which increases the model’s symmetry. The machines being complex also leads to some very dense blocks in the otherwise sparse constraint matrix.

A reasonable initial approach is a Dantzig-Wolfe reformulation, given the model’s block-diagonal structure. While it can be faster than the compact formulation when there are many identical machines, it remains prohibitively slow when that is not the case, as its pricing problems remain difficult mixed-integer (nonlinear) programs.

This problem can be thought of as two connected subproblems. In one, we need an assignment to the continuous production variables (a production pattern), and in the other an assignment to the integer maintenance variables (a maintenance pattern).

Thinking of these two subproblems, decomposing the original problem in a way that handles them separately might be beneficial. We would have an easy subproblem that produces production patterns and a hard subproblem that produces maintenance patterns. This comes with additional difficulties, as it requires simultaneous column-and-row generation, and the introduction of a third, more difficult, subproblem (which is essentially the same as the subproblem of the original reformulation). The hope is that by only calling a subproblem whenever its easier peers have exhausted all negative reduced cost columns, the overall algorithm is faster. As in our problem one maintenance pattern can be feasibly completed by many production patterns, we expect that the easy subproblems will be called much more often.

This idea of generating partial columns in different subproblems can also be applied in some other Dantzig-Wolfe decompositions.

To model the physics of the used vehicles in trajectory planning problems, Newton’s equations of motion must be incorporated, discretized by numerical solution schemes. Thus, the position of the vehicle is in the model known only at a discrete set of points. Due to this lack of information, corner cutting can occur, i.e., the vehicle can abbreviate through an obstacle if it remains outside at every evaluation point again. Increasing the number of discrete time steps cannot resolve this problem completely and leads to higher computation times. To obtain always realistic solutions, corner cutting must be restricted, yielding so called inter-sample avoidance methods. We present a new approach to ensure inter-sample avoidance for polyhedral obstacles. The hyperplanes describing the obstacle divide the mission space into a set of subareas which can be encoded by binary vectors. These are used to ensure feasible movements without requiring more evaluation points or additional variables. We give a procedure to generate an integer polytope containing the feasible movements and derive an upper bound on the number of necessary constraints to describe it. The new approach is qualitatively tested against other inter-sample avoidance methods from the literature and its computational efficiency is studied in numerical experiments, using a mixed-integer linear program for trajectory planning of unmanned aerial vehicles and the state-of-the-art solver Gurobi.

In supply chain management a challenging task is to find an efficient allocation of safety stocks which are sufficient to maintain a reliable supply process. In the presence of multiple supply options at each stage this becomes even more interesting because the selection of suppliers influences the internally propagated demands which the upstream safety stock requirements rely on. The Stochastic Guaranteed Service Model with Demand Propagation (SGSM-DP) models the safety stock requirements in a multi-echelon inventory network by bilinear constraints on replenishment times and propagated demands bounding the base stock levels at each node in multiple static demand scenarios. Applying a standard big-M-linearization leads to a mixed integer linear program which is compact but intractable in practice due to a large integrality gap. Regarding the flow conservation structure of the demand propagation, an equivalent formulation (F-SGSM-DP) was developed acting on a time-expanded flow network. Although larger in size, solvers show a consistently better performance caused by the almost tight reformulation. Using this approach, realistic instances could be solved to optimality for the first time and evaluated in a dynamic simulation environment. With these insights, further improvement potential on dynamic demand characteristics was revealed. A novel generalization based on periodic time cycles (P-SGSM-DP) corresponding to periodic demand-sequence scenarios makes it finally possible to reach cost-efficient results on a real-world spare-parts distribution system with highly dynamic demand (rare over time but substantial in amount) compared to the approximate approaches usually applied in practice.