Hard-constraint stochastic methods, sharper robust sets, and a 5/2 inventory guarantee
The day in optimization
Feasibility guarantees were the theme: methods that keep hard constraints satisfied in every run, and certificates that say how far a sampled solution can be trusted. Robust optimization and scenario methods both asked how to use data without being overly cautious. Complexity results also arrived, on both the easy and hard sides of combinatorial problems. Practice news was mostly vendor case studies.
Theory
Hard constraints in stochastic optimization. Lu and Xiao study constrained convex finite-sum problems where the constraints are imperative. They aim for an "ε-surely feasible stochastic optimal" solution: the constraint violation is bounded by ε deterministically, not just on average, while the objective error is bounded in expectation. Their method is an inexact stochastic variance-reduced gradient scheme (Lu, Xiao). The same concern, safety by construction, appears in reinforcement learning. Sharma and Sivaranjani restrict stochastic policies to safe control sets between sampling instants, using control barrier functions (safe RL with hard constraints). A companion paper from the same authors gives global-convergence guarantees for model-free policy gradient on undiscounted LQR (LQR policy gradient).
Less conservative robust and scenario methods. Bertsimas, de Moor, den Hertog and coauthors apply limit theorems (such as the central limit theorem) directly to each uncertain linear expression, with the decision variables as weights. Earlier approaches applied them to unweighted sums of the uncertain parameters. They report that this gives sharper formulations and so less conservative robust models (Decision-weighted limit theorems). Crawford and Ayanian look at the other data-driven route, scenario optimization. They show that certificates can depend on how the same samples are grouped. For an equal-allocation support-subsample certificate, regrouping distorts the bound by a factor k²(1−ε)^(k−1), where k is the number of groups and ε the violation level (scenario representation). In plain words, the guarantee depends on bookkeeping choices that do not change the information.
Complexity: where problems turn hard. Fang, Shao and Wu give a polynomial-time algorithm for binary linear optimization when each constraint-matrix column has at most 2 nonzeros. They prove NP-hardness when columns have exactly 3. They also give fixed-parameter algorithms that depend on how far the matrix is from "graphic" (binary affine optimization). Li, Xia and Xu prove strong NP-completeness of weighted maximin dispersion over the unit ℓ₁-ball. They also give exact algorithms that run in polynomial time for every fixed dimension (maximin dispersion). Both results mark where the tractable cases end. Neither says anything about practical solver performance.
Inventory. Ming Hu constructs a deterministic echelon-stock (s,S) policy for a one-warehouse multi-retailer system. Its long-run average cost is at most 5/2 times the optimum over all nonanticipative policies, under stated conditions on the cost ratios (5/2 guarantee). This is a worst-case upper bound on the policy's cost. Typical performance may be much better.
Other methods. - Stochastic convex optimization with heavy-tailed gradients in ℓp geometries, with parallel queries per round (Nie, Shyam, Bullins). - A subspace cubic Newton method for sparse nonconvex problems, with convergence under the KL property (Xia, Tao, Yin). - An inexact proximal gradient method for multiobjective problems (Fan, Tang, Yang). - A shadow Douglas–Rachford splitting method for L-infimal convolutions (Vu, Vu).
Control and games. Vignola, Zeilinger and Lee show polylogarithmic regret via certainty equivalence in degenerate LQR, where the input penalty is singular (degenerate LQR). Lei, Nesic and Pu give finite-sample suboptimality and closed-loop guarantees for MPPI control (MPPI). A separate paper analyses MPC without terminal constraints by optimizing a weighted finite tail online (MPC). Bayraktar, Ekren, Vy and coauthors prove an O(1/K) ergodic bound and an O(1/K^½) approximate-equilibrium bound for a KL mirror-prox method for dynamic mean field games (mirror-prox).
In practice
Gurobi's case-study pages are vendor-published, so the figures below are self-reported. They are dated October 2026, not this week.
- Gurobi reports that the utility SPP can solve its grid optimization problems up to four times faster using Gurobi's PDHG algorithm. PDHG is a first-order method suited to very large LPs (Gurobi case studies).
- The same pages report that M2P Consulting's airline tail-assignment work saw up to a 14x performance boost (Gurobi case studies).
- Gurobi's resources page also lists a 14.0 release, with faster solves and broader PDHG support. A separate page dates a 14.0 resource to 13 November (Gurobi resources).
Worth watching
- Multi-year stochastic planning of transmission and storage for Great Britain to 2050 (Cao, He, Bukhsh).
- Colombo, an "autoresearch" system for oracle-based optimization that looks for the gap between achievable guarantees and unavoidable limits (Colombo).
- A PDE analysis of anisotropic consensus-based optimization, proving global existence and uniqueness of weak solutions (Huang, Li, Wang).
- Projector-based conic formulations and exact decompositions for continuous multifacility location (Blanco et al.).
Sources: - Gurobi case studies - Gurobi resources
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.