A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
On Augmented Lagrangian Methods with General Lower-Level Constraints I: Bounded Penalties Give Feasible Limit Points; Otherwise KKT for the Infeasibility Problem or CPLD FailsResearch Paper
Augmented Lagrangian methods (the method of multipliers of Hestenes, Powell and Rockafellar) solve a constrained nonlinear program by a sequence of easier subproblems in which some constraints are moved into the objective through a penalty term plus a multiplier estimate. Andreani, Birgin, Martínez and Schuverdt (SIAM J. Optim. 18 (2007); preprint HAL…
Hardness of Approximating Flow and Job Shop Scheduling Problems 1: Every Schedule of the Flow Shop Instance F(r,d) Has Makespan at Least min(r, d/4)·lbResearch Paper
In shop scheduling, jobs consist of chains of operations, each to be processed on a prescribed machine, and the goal is to minimize the makespan, the time at which the last operation finishes. Almost every approximation algorithm for job shops, acyclic job shops and flow shops is analysed against one quantity: the trivial lower boundlb=max(C,D),…
Spectral Sparsification of Graphs 2: Every Graph with m Edges Has a (6 log_{4/3} 2m)⁻¹-Conductance Decomposition Cutting at Most Half of Its EdgesResearch Paper
A sparse graph that approximates a dense one, in the sense that both have nearly the same Laplacian quadratic form, can stand in for it in every algorithm that only reads cuts or solves Laplacian linear systems. Spielman and Teng introduced such spectral sparsifiers and built them in nearly linear time; the construction is the sparsification step of their…
Graph Sparsification by Effective Resistances 1: Sampling O(n log n/ε²) Edges by Effective Resistance Yields a (1±ε) Spectral Sparsifier with Probability 1/2Research Paper
Many graph algorithms run in time proportional to the number of edges. A sparsifier of a weighted graph G is a graph H on the same vertices with far fewer edges that approximates G for the purpose at hand, so that the algorithm can be run on H instead. Benczúr and Karger (1996) showed that every graph has a sparsifier with O(nlogn/ε2) edges…
Efficient Algorithms for Online Decision Problems 3: Follow the Lazy Leader (FLL, FLL*) Matches FPL, FPL* in Expectation Each Period and Updates with Probability at Most εAResearch Paper
In an online linear decision problem a decision maker chooses, on each period t=1,2,…, a decision dt from a set D⊂Rn, and only then learns a state vector st∈S⊂Rn and pays the cost dt⋅st. The online shortest path problem, the experts problem, online binary search trees and list update…
Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization 2: With Random Recourse, the SDP (3.14) Conservatively Approximates the Linear Decision Rule Problem, Exactly for l = 1Research Paper
In a one-stage stochastic program a decision maker observes a random outcome ξ and then picks a decision x(ξ), subject to constraints that depend on ξ, so as to minimize expected cost. The optimization variable is a whole function x, and computing the optimal value is #P-hard even for a uniform distribution on the unit cube (Dyer and Stougie, 2006,…
Stochastic Machine Scheduling with Precedence Constraints 1: LP-Based Delayed List Scheduling Is a (1 + β)(1 + 1/β + max{1, (m − 1)Δ/m})-Approximation for P|r_j, prec|E[Σ w_j C_j]Research Paper
Scheduling jobs whose processing times are not known in advance is a basic problem of production planning, project management and computing systems. In the stochastic machine scheduling model only the distribution of each processing time is known beforehand; the actual duration of a job is revealed when the job completes. A solution is then not a schedule…
Conditional Risk Mappings: A Positively Homogeneous Lower Semicontinuous Conditional Risk Mapping Is the Supremum of Countably Many Conditional ExpectationsResearch Paper
Risk measures quantify the danger of an uncertain cost X by a single number. The axiomatic theory of coherent and convex risk measures (Artzner, Delbaen, Eber and Heath, Coherent measures of risk, 1999; Föllmer and Schied, Convex measures of risk and trading constraints, 2002) is static: the risk is evaluated once, with no information beyond what is known…
Efficient Algorithms for Online Decision Problems 2: For Nonnegative Decisions and States, FPL*(ε/2A) Has Expected Cost at Most (1 + ε)·min-cost_T + 4AD(1 + ln n)/εResearch Paper
Many sequential decision problems have a combinatorial decision set and a linear cost: choosing a path in a graph whose edge delays change every day, choosing a binary search tree for a stream of requests, or choosing one of n experts whose losses are revealed after each round. Classical weighted-majority algorithms keep one weight per decision, which is…
Efficient Algorithms for Online Decision Problems 1: Follow the Perturbed Leader FPL(ε) Has Expected Cost at Most min-cost_T + εRAT + D/εResearch Paper
In an online decision problem a decision maker chooses actions one period at a time, and only after each choice learns what that choice cost. The classical instance is prediction with expert advice: each day one of n experts is followed, and afterwards every expert's loss is revealed. The goal is a strategy whose total cost is close to that of the best…
Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 3: With N = k Variables Fixed and Equal Population Eigenvalues, √M(λ₁ − ℓ₁)/ℓ₁ Converges to G_kResearch Paper
Principal component analysis estimates the eigenvalues of a population covariance matrix Σ by those of the sample covariance matrixS. Before random matrix theory turned to the regime where the dimension grows with the sample size, the classical question was the opposite one: the number of variables N is fixed and the number of samples M tends to…
Theoretical and Numerical Comparison of Relaxation Methods for Mathematical Programs with Complementarity Constraints 2: MPEC-MFCQ Implies MFCQ for the Scholtes Relaxed Problems LocallyResearch Paper
A mathematical program with complementarity constraints (MPEC, also called MPCC) is a nonlinear program in which some pairs of constraint functions must be nonnegative with at least one of each pair equal to zero. Such programs model bilevel optimization, Stackelberg games, contact problems in mechanics, and traffic equilibrium design; see Luo, Pang and…
Randomized quasipolynomial-time mean-payoff gamesOpen Problem
Mean-payoff games ask which starting positions allow a player to guarantee a nonnegative long-run average reward. Binary-encoded weights make the bit cost of solving the complete winning set a central part of the question. The source manuscript presents the surrounding research claim.
Theoretical and Numerical Comparison of Relaxation Methods for Mathematical Programs with Complementarity Constraints 1: Scholtes Relaxation Limits Are C-Stationary under MPEC-MFCQResearch Paper
A mathematical program with complementarity constraints (MPCC, also called MPEC, mathematical program with equilibrium constraints) is a nonlinear optimization problem in which some pairs of constraint functions must be nonnegative with at least one of each pair equal to zero. Such constraints model equilibria inside an optimization problem: bilevel…
What Can We Learn Privately? V: Masked Parity Is Learnable by Adaptive but Not by Nonadaptive Statistical Queries Under the Uniform DistributionResearch Paper
In the local model of differential privacy, each individual randomizes their own data before handing it to an untrusted learner. Local protocols are the deployed form of private data collection, and in practice every round of interaction with the population is expensive: the learner must broadcast new instructions and wait for new reports. Kasiviswanathan,…
Flows and Decompositions of Games: Harmonic and Potential Games 4: Changing Only the Nonstrategic Component Makes the Pure Nash Equilibria Coincide with the Pareto Optimal ProfilesResearch Paper
A finite strategic game can be changed in ways that no player can detect strategically. Adding to player m's utility any function that does not depend on player m's own strategy leaves every unilateral comparison "is strategy a better for me than strategy b, given what the others do?" unchanged, so it leaves every best response and every pure Nash…
Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 2: Spikes above 1+γ⁻¹ Give √M Fluctuations of the Largest Eigenvalue with Limit G_k, the k×k GUE LawResearch Paper
Sample covariance matrices are the basic object of multivariate statistics: principal component analysis, signal detection and factor models all start from the eigenvalues of S=M1∑k=1Mykyk∗ computed from M samples of an N-dimensional vector. When N is comparable to M, the eigenvalues of S no longer approximate those of the…
A Multiple-Choice Secretary Algorithm with Applications to Online Auctions: The Recursive k-Choice Secretary Algorithm Earns at Least (1 − 5/√k) Times the Sum of the k Largest ValuesResearch Paper
The secretary problem asks how well an online decision maker can do when items arrive one at a time in random order and each must be accepted or rejected on the spot. With a single selection, the classical rule (observe a 1/e fraction, then take the first item better than everything seen) selects the best item with probability about 1/e, and no rule does…
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem: The Integer Points of P1 ∩ P2 Are Exactly the CVRP Solutions, and the Dantzig–Wolfe Master Describes P1 ∩ P2Research Paper
The capacitated vehicle routing problem (CVRP) asks for K delivery routes from a depot that serve every client exactly once without exceeding a vehicle capacity, at minimum total length. It was introduced by Dantzig and Ramser in 1959 and is the reference problem of the vehicle routing literature: most exact methods for richer routing models (time windows,…
Mitigating Supply Risk: Dual Sourcing or Process Improvement? 3: Late Commitment Strictly Beats Early Commitment When the Costlier Supplier's Improved Gain Exceeds mz/(θ(1−θ))Research Paper
Firms that buy from unreliable suppliers can protect themselves in two ways: they can spread orders across several suppliers, or they can invest in improving a supplier's reliability, for example through supplier-development programmes or joint process-improvement projects. Wang, Gilland and Tomlin (MSOM 12(3):489–510, 2010) compare the two strategies in a…
Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper
Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…
Linearly Parameterized Bandits 3: For Any Compact Set of Arms, the Uncertainty Ellipsoid Policy Has Regret at Most a₄r‖z‖ + a₅r√T log^{3/2} TResearch Paper
In a linearly parameterized bandit a decision maker repeatedly chooses an arm u from a set Ur⊂Rr and observes a noisy reward whose mean is linear in an unknown vector Z. The model covers problems in which many arms share a few underlying features: products described by a handful of characteristics, prices, or routes whose costs…
On Metric Generators of Graphs 1: An Isometry Given on a Strong Metric Generator T of H, With H − T a Forest, Extends to All of H Exactly When H Has a Representation in GResearch Paper
A set of vertices T of a graph is a metric generator when every vertex is determined by its vector of distances to the elements of T. The minimum size of such a set is the metric dimension, studied in graph theory since the 1970s and surveyed by Chartrand, Eroh, Johnson and Oellermann (Discrete Appl. Math. 2000). Metric generators also appear in…
Distributionally Robust Optimization and Its Tractable Approximations 3: The Infimal Convolution of π¹, π², π³ Bounds the Worst Case over the Intersected Families and Improves on EachResearch Paper
Two-stage and multistage stochastic programs ask for decisions that react to uncertainty revealed over time. When the distribution of the uncertainty is known only partially, one optimizes against the worst distribution in a familyF consistent with what is known: a support set, a range for the mean, a covariance matrix, bounds on how fast the tails…