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.
Semidefinite Programming Relaxations for Semialgebraic Problems 2: A Feasible Solution of the SDPs (7.7) Certifies That M Is Copositive, and the Test Is at Least as Strong as M = P + NResearch Paper
A real symmetric matrix is copositive when its quadratic form is nonnegative on the nonnegative orthant. Copositive matrices appear wherever a quadratic objective meets sign constraints: standard quadratic programs over the simplex, linear complementarity problems, and conic reformulations of combinatorial problems such as the stability number of a graph.…
The Primal-Dual Active Set Strategy as a Semismooth Newton Method II: Global Convergence and Monotonicity for M-MatricesResearch Paper
Obstacle problems, contact problems and box-constrained quadratic programs share one finite-dimensional core: the linear complementarity problem "find y≤ψ and λ≥0 with Ay+λ=f and λi(yi−ψi)=0". After discretization by finite differences or piecewise linear finite elements, the matrix A is typically an M-matrix,…
On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization II: Points of a Product of Quadratic and Rotated Cones Are Complementary Iff Their Arrow-Head Products VanishResearch Paper
Conic quadratic optimization (also called second-order cone programming) minimizes a linear function over the intersection of an affine subspace with a product of quadratic cones. It contains linear programming, convex quadratically constrained programming, robust linear programming with ellipsoidal uncertainty and many problems from engineering design; see…
On the Sample Complexity of Reinforcement Learning V: Exact Conservative Policy Iteration Improves at Every Update and Halts within 8H²/ε² Updates with Future Advantages at Most ε/HTextbook
Policy iteration replaces the current policy by the greedy policy with respect to its state-action values. With exact values this improves the policy at every state. When the improvement step is only approximate, or is restricted to a class of policies, a greedy replacement can make the policy worse, and the resulting error bounds are stated in max norm…
On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization I: Solutions of the Homogeneous Model Are Complementary and Give an Optimal Pair or an Infeasibility CertificateResearch Paper
Conic optimization minimizes a linear function over the intersection of an affine subspace with a closed convex cone. Linear programming (the nonnegative orthant), second-order cone programming (products of quadratic cones) and semidefinite programming (the positive semidefinite cone) are all instances. Primal–dual interior-point methods are the standard…
Ising Models on Locally Tree-Like Graphs 2: With a Positive Field, Belief Propagation Converges Exponentially Fast from Every Positive Initial ConditionResearch Paper
Belief propagation (BP) is the message-passing algorithm used throughout artificial intelligence, coding theory and statistical physics to approximate marginals of graphical models. On graphs with cycles it is a heuristic: it may fail to converge, and when it converges its output need not be the true marginal. Rigorous guarantees had mostly been confined to…
Inventory Management of a Fast-Fashion Retail Network 2: The Tangent-Envelope Approximation of Expected Sales Is an Upper BoundResearch Paper
Zara ships inventory from a central warehouse to each of its stores every week, and for a short-lived fashion item the warehouse holds a limited amount of each size. Deciding how many units of each size to ship to each store is therefore a constrained allocation problem whose objective is the expected sales a store will realize from a given inventory. Caro…
Distributionally Robust Optimization and Its Tractable Approximations 1: Under a Support Set and a Mean Set, the Bound π¹ Equals the Worst-Case Expected Positive PartResearch Paper
Linear decision rules are a standard device for making multistage optimization under uncertainty computationally tractable: a recourse decision is restricted to be an affine function of the uncertain data observed so far. Their weakness is that a recourse variable that must stay nonnegative forces the rule to be very conservative. Goh and Sim, Distributional…
Convex Quadratic and Semidefinite Programming Relaxations in Scheduling II: Randomized Rounding of the Time-Slot Convex Quadratic Relaxation (CQP) Is Within 2 for R | rᵢⱼ | Σ wⱼCⱼResearch Paper
Scheduling jobs on unrelated parallel machines to minimize the total weighted completion time is a basic model of machine scheduling: each job may take a different time on each machine, and a job becomes available on a machine only at a machine-dependent release date. In the three-field notation the problem is R∣rij∣∑wjCj. Already the…
The Price of Anarchy is Independent of the Network Topology: For a Standard Latency Class Containing the Constants, Two-Link Networks Attain the Worst Nash/Optimal Cost Ratio α(L)Research Paper
In a road or communication network where each unit of traffic picks its own route, the outcome is a Nash flow (Wardrop equilibrium): no traffic can lower its own latency by switching paths. It is well known since Pigou (1920) that such selfish routing can be inefficient: the total latency of a Nash flow may exceed that of the best centrally planned flow.…
Solving Project Scheduling Problems by Minimum Cut Computations: Finite-Capacity n-Cuts Are Exactly the Feasible Schedules, and a Minimum a-b-Cut Has the Optimal CostResearch Paper
Time-indexed formulations are a standard way to model scheduling problems as integer programs: a binary variable xjt records whether job j starts at time t. They were introduced by Pritsker, Watters and Wolfe (1969) and give strong linear relaxations, at the price of many variables. In project scheduling, jobs are linked by time lags: a lag (i,j) of…
Designing a Call Center with Impatient Customers III: Square-Root Staffing Is Equivalent to a Nondegenerate Delay Probability and to Abandonment of Order 1/√NResearch Paper
A telephone call center must decide how many agents N to staff against an offered load R=λ/μ (arrival rate over service rate). Staff too few and callers wait and hang up; staff too many and agents sit idle. For large centers the industry rule of thumb is square-root safety staffing, N≈R+βR, and the question is what service level…
Bounded-parameter Markov Decision Processes 2: Interval Policy Evaluation Converges to the Interval Value Function of Every PolicyResearch Paper
A Markov decision process (MDP) is evaluated by solving a linear fixed-point equation built from its transition probabilities. In practice those probabilities are rarely known exactly: they are estimated from data, elicited from experts, or obtained by aggregating the states of a larger model, and each estimate comes with an error band. Givan, Leach and…
Uncoupled Dynamics Do Not Lead to Nash Equilibrium 1: Near the Two-Player Unit-Disk Game Γ₀ of Section II, No Uncoupled Dynamic Is Nash-ConvergentResearch Paper
Learning in games asks whether players who adjust their strategies over time, by simple rules, end up at a Nash equilibrium. Many adaptive dynamics share one informational feature: each player's adjustment depends on the current play and on that player's own payoff function, but not on the payoffs of the others. Hart and Mas-Colell (AER 2003) call such…
The Primal-Dual Active Set Strategy as a Semismooth Newton Method I: Local Superlinear Convergence for P-Matrix Complementarity ProblemsResearch Paper
Many problems in optimization and in the discretization of partial differential equations reduce to a linear complementarity problem with an obstacle: find y,λ∈Rn with
Additive Logistic Regression: A Statistical View of Boosting 4: Population Gentle AdaBoost Takes Newton Steps on E[e^{−yF(x)}]Research Paper
Boosting combines many weak classifiers into a strong one by refitting, again and again, to reweighted data. AdaBoost (Freund and Schapire, 1997) and its confidence-rated variant Real AdaBoost (Schapire and Singer, 1999) were introduced through the theory of online learning. Friedman, Hastie and Tibshirani (2000) recast them as stagewise fitting of an…
Inventory Management of a Fast-Fashion Retail Network 1: Expected Sales Under the Major-Size Display Policy Are Non-Decreasing, Discretely Concave and SupermodularResearch Paper
Fast-fashion retailers such as Zara replenish their stores several times a week from a central warehouse, and the warehouse holds a limited stock of each garment that must be split across hundreds of stores. Caro and Gallien built the store-level sales model behind the shipment-allocation system they developed with Zara and tested in a live pilot (Caro and…
Reliable Facility Location Design Under the Risk of Disruptions 1: With R = J the Compact Level-Assignment Formulation Equals the Scenario-Based Stochastic ProgramResearch Paper
Facility location models decide where to open depots, warehouses or service centres and which customers each one serves. Classical models assume that an open facility always works. In practice facilities are disrupted by weather, strikes, power loss or supplier failure, and a network designed for normal operation can become very expensive when its nearest…
Reliable Facility Location Design Under the Risk of Disruptions 2: Optimal Solutions Order Each Customer's Assignment Levels by DistanceResearch Paper
A facility location plan decides which sites to open and which customers each site serves. Real facilities fail: plants are shut by strikes, warehouses by floods, distribution centres by power outages. When a customer's facility is down, she is served by a backup facility, or not served at all at a penalty. Reliable facility location chooses sites and…
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time I: Schrijver's Algorithm Returns a Minimizer of f After at Most |V|⁶ IterationsResearch Paper
Minimizing a submodular set function is one of the central tractable problems of combinatorial optimization. Minimum cuts in graphs and hypergraphs, matroid intersection and partition, the rank of a matroid union, and many problems in facility location, image segmentation and machine learning are special cases or subroutines of it. The question is…
On the Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs 1: At a Sharp Minimum the SAA Problem Is Solved Exactly W.P.1 for Large NResearch Paper
Most stochastic programs cannot be solved as stated, because the objective is an expectation over a distribution that is high-dimensional, continuous or known only through a simulator. The standard remedy is the sample average approximation (SAA), also called the Monte Carlo or sample-path method: draw an i.i.d. sample, replace the expectation by the sample…
Convex Quadratic and Semidefinite Programming Relaxations in Scheduling V: 3-Occurrence Max3Sat L-Reduces to R | rⱼ | Σ Cⱼ with Constants 32 and 1Research Paper
The scheduling problem R∣rj∣∑Cj asks for a nonpreemptive schedule of jobs on unrelated parallel machines, each job with a machine-dependent processing time and a release date, so that the total completion time is minimal. It is NP-hard, and the question that remains is how well it can be approximated in polynomial time. Positive results include…
The Power of Two Choices in Randomized Load Balancing II: T_d(λ)/log T_1(λ) → 1/log d as λ → 1⁻, an Exponential Improvement over One ChoiceResearch Paper
A dispatcher assigns each arriving job to one of n servers. Sending it to a uniformly random server is simple but produces long queues near capacity; sending it to the globally shortest queue requires full state information. The power of d choices sits between the two: each job samples d servers at random and joins the shortest of them. Mitzenmacher's…
The Sample Average Approximation Method for Stochastic Discrete Optimization 1: Under Assumption A, 1 − P(Ŝ^ε_N ⊂ S^ε) Decays Exponentially Fast in the Sample Size NResearch Paper
Many decision problems in operations research ask for the best element of a finite set of alternatives when each alternative's cost is random: which projects to fund when resource use is uncertain, which crew pairings to fly when delays are random, which items to pack into a knapsack whose overflow is penalized. The expected cost is rarely available in…
Designing a Call Center with Impatient Customers II: In the Halfin–Whitt Regime the Scaled Erlang-A Queue Converges to a Diffusion with Piecewise-Linear DriftResearch Paper
Telephone call centers are large service systems: hundreds of agents answer callers who wait in a queue and hang up when their patience runs out. Staffing them is a trade-off between the cost of agents and the quality of service, and in large centers both the efficiency (agents busy almost all the time) and the service level (most callers answered almost…