Integer programming theory has a busy Friday, and solvers move into practice
The day in optimization
Integer programming dominated the theory feed. Results on split cuts, corner polyhedra and mixed-integer quadratic problems all appeared on the same day. First-order methods had a quieter day, with accelerated primal-dual rates and new last-iterate bounds. On the practical side, vendor case studies keep describing optimization as a way to shrink scheduling and routing work.
Theory
Cutting planes and polyhedra. A split cut is a standard way to slice off fractional points in integer programming. The split rank counts how many rounds of such cuts are needed to reach the integer hull. A Polynomial Bound on Split Rank proves that for a rational pure-integer polyhedron, O((L+1)^9) rounds suffice, where L is the encoding length of the defining system. The bound is polynomial in the input size, and the authors say it resolves a conjecture of Basu, Conforti, Di Summa and Jiang. Separately, An upper bound on the number of edges of a Gomory corner polyhedron gives the first nontrivial bound on edges, O(n·6^n·(1+log₂(2δ))^(2n−3)). Here n is the dimension and δ the lattice determinant. The abstract presents it as only a small improvement over counting pairs of vertices: the log exponent drops from 2n−2 to 2n−3. The One-Skeleton of Multilinear Polytopes studies which vertices are adjacent, and the diameter, for binary polynomial optimization. That matters because simplex-style methods move along edges. It generalizes Padberg's quadratic-case result that two integral vertices are adjacent exactly when the variables where they differ form a connected subgraph.
Mixed-integer quadratic problems. Alberto Del Pia has several papers on these problems. Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time starts from Lenstra's classical result, which solves MILP in polynomial time when the number of integer variables is fixed. The abstract says the direct analogue for MIQP fails unless P = NP, so the paper looks for polynomial-time algorithms under restricted structure. Frank-Wolfe Theorems for Mixed Integer Quadratic Optimization asks when a quadratic bounded below still attains its infimum once integer variables are present. It gives a complete classification for sets defined by convex quadratic inequalities with rational data, and one integer variable never destroys attainment. Sparse PCA with Overlapping Supports shows NP-hardness and gives an FPTAS for a fixed-rank covariance matrix. An FPTAS is an approximation scheme that runs in time polynomial in both the input size and 1/ε. On the modeling side, Probabilistically Exact Convexification of MIQP with Indicators gives up exactness for every objective. It keeps exact optimality for statistically relevant objectives. That is a way around NP-hardness even at bandwidth two.
Solvers in the field. To Race or Not to Race? studies parallel replication of MIP solves across random seeds. It asks whether information from an ordinary root solve can decide when replication is worth the compute. RPX is an independent checker for AI-generated MILP reformulations. It verifies that feasible solutions of the original and reformulated models can be converted into each other with no worse objective.
First-order methods. Accelerated Transformed Primal Dual Methods targets smooth convex problems with affine equality constraints. In the strongly convex case the authors report an accelerated linear rate that matches known lower bounds in both gradient evaluations and matrix-vector products. A lower bound limits what any method can do. This matching result says the rate cannot be beaten in that oracle model. Improved last-iterate bounds for SGD tightens the interpolation-regime bound from O((log T)³/T) to O((log T)³/(T log log T)), for sampling with and without replacement. In plain words, it is a small gain: a log log T factor in the final iterate's error. Optimal higher order convergence rates for the MUON optimizer revisits Polyak's 1964 momentum rate for the MUON optimizer. The Query Complexity of Unknown Sparse Gradient Residuals considers predicted gradients that are exact except for at most k unknown components. It proves the optimal worst-case expected cost is Θ(min{nk+R, (n/k)R}), where R is the optimal cost when the exceptional components are known.
In practice
Slalom describes a rail repair scheduling tool built on NVIDIA cuOpt for Kawasaki. According to Slalom, it cut a multi-hour weekly scheduling job to a task of 10 minutes or less. This is a time saving, not a cost figure, and the source is a vendor partner's write-up.
Mayalogic reports that a client's cost per stop fell 19% in the first full quarter after it replaced a third-party routing engine with a custom solver. This is the vendor's claim, and no methodology is given. Neither item is dated this week.
Worth watching
- Fit-LRP fits linear relaxations to polytopes for neural network verification over non-convex regions, where box-based bounds become very loose.
- Quantifying the Cost of Restoring AC Feasibility looks at what it costs to repair DC optimal power flow solutions so they respect the AC equations before dispatch.
- Your Hypergradient is Skewed argues that truncated Neumann-series hypergradients carry skewness error, beyond bias and variance, and proposes an antithetic estimator.
- Adaptive Constraint Sampling for Stochastic Gradient Methods keeps per-iteration cost independent of the number of constraints by resampling recently violated ones.
Sources: - Slalom: cuOpt route optimization - Mayalogic logistics routing platform
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.