Decision-dependent demand, restricted transport sets and reshuffled minibatches
The day in optimization
Today's items were all modelling-and-guarantees papers. Two of them tighten the link between a model and the quality of its answer: a quantified loss from restricting transport in robust optimization, and certified gaps for an auction heuristic. The other two extend a standard model: demand that depends on the decision, and minibatch reshuffling. No new solver release turned up.
Theory
Facility location when demand reacts to the decision. A new Optimization Online paper treats single-source capacitated facility location, where each customer is served by exactly one facility. Customer demand is uncertain, and its joint distribution depends on which facility the customer is assigned to. The number of possible distributions therefore equals the number of feasible allocations. The authors present a model and an exact solution method. The abstract excerpt does not say how the method handles that count, so the details are worth checking in the paper.
Wasserstein DRO on a smaller space. Price-aware transport subspaces for Wasserstein DRO asks what robust value is lost if the adversary may move data only inside a shared low-dimensional subspace. In distributionally robust optimization (DRO), the adversary picks the worst distribution within a Wasserstein ball, meaning a set of distributions within a given transport cost of the nominal one. The abstract reports exact bounds for quadratic losses with nonsingular nominal covariance, using affine transport sets and outer moment sets. It also describes a spectral rule that extends a chosen base subspace and reaches a sharp, base-dependent approximation factor for the aggregate first-order restriction loss. The restriction makes the problem cheaper, and the paper puts a number on what it costs.
Winner determination with sparse pursuit. Winner determination in combinatorial auctions is weighted set packing, which is NP-hard. This paper combines the LP relaxation with CoSaMP-style steps (identify, merge, re-estimate, prune), a method borrowed from sparse signal recovery. Only a logarithmic-size moving window of bid variables is kept integral at a time, and the rest stay fractional. The title promises approximation guarantees and certified optimality gaps. The excerpt does not give the actual ratios, so none are stated here.
Minibatch random reshuffling. Random reshuffling (RR) goes through the data in a fresh random order each epoch, without replacement. It is the usual ordering in practice and is almost always run with minibatches. This note says recent work by Liu shows single-sample RR beats SGD in smooth convex optimization for every stepsize below 2/L̂ (a stepsize cap set by the smoothness constant). The role of batch size had not been worked out. The note studies it, and its title points to finite-population variance and quadratic growth as the tools. The excerpt does not state the results.
In practice
No news from this week turned up, so this is a vendor case study. AWS and Timefold describe e-Switch's operational planning, which uses the Timefold planning solver. The write-up reports more than $100 million in cost savings and over 10 million kg less CO₂ emissions per year. In a railroad maintenance case, it says dispatcher coordination that took 60–70% of 120 dispatchers' time now takes a few hours. These are vendor-reported figures, and the baseline is not independently verified.
Worth watching
- Swissport's airport staff scheduling with Gurobi: Gurobi reports savings above $1 million a year and employee scheduling preferences met 95–100% of the time. This is a vendor claim.
Sources: - A Solution Method for Single-Source Capacitated Facility Location Problems Under Decision-Dependent Demand - Price-aware transport subspaces for Wasserstein DRO - Winner Determination by Polynomial Sparse Pursuit - Minibatch Random Reshuffling for Smooth Convex Optimization - e-Switch with Timefold and AWS - Swissport automating airport staff scheduling
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.