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.
Calibrated Learning and Correlated Equilibrium I: Calibrated Forecasts with Best Responses Converge to the Set of Correlated EquilibriaResearch Paper
A correlated equilibrium (Aumann 1974) is a joint distribution over the players' strategy profiles such that no player gains by deviating from the strategy the distribution recommends to them. It is the equilibrium notion that learning dynamics in repeated games most naturally reach, and a basic question in learning in games is which simple rules, played…
Competitive Paging Algorithms I: The Marking Algorithm Is 2H_k-CompetitiveResearch Paper
Paging is the problem of managing a two-level memory: a fast cache holds k pages out of an address space of n pages, requests to pages arrive one at a time, and a request to a page outside the cache (a page fault) forces the algorithm to bring that page in and, when the cache is full, to evict another. The cost is the number of faults. An on-line algorithm…
A Threshold of ln n for Approximating Set Cover II: The Inapproximability of Max k-CoverResearch Paper
Max k-cover is the basic coverage problem of combinatorial optimization. The input is a collection of subsets of a finite ground set and a number k; the task is to choose k subsets that together cover as many points as possible. It models facility and sensor placement, the selection of a small committee or feature set representing a population, and budgeted…
A Threshold of ln n for Approximating Set Cover I: The ln n Inapproximability of Set CoverResearch Paper
Set cover is the problem of covering a finite ground set with as few members of a given family of subsets as possible. It models facility location, crew scheduling, test-suite minimization and many other selection problems in operations research, and it is one of the canonical NP-hard problems. The greedy algorithm, which repeatedly picks the subset…
Bargaining under Incomplete Information I: Class A Equilibrium Offer Strategies Satisfy the Linked Differential EquationsResearch Paper
A buyer and a seller negotiate over a single indivisible good. Each knows how much the good is worth to them, but not how much it is worth to the other side. Whether the two will trade, and at what price, then depends on how each party shades its offer to exploit the other's uncertainty. Chatterjee and Samuelson (Bargaining under Incomplete Information,…
The Generalized Quasi-Variational Inequality Problem I: Existence for the Generalized Implicit Complementarity Problem under Strong CopositivityResearch Paper
Variational inequalities and complementarity problems are the standard formulation of equilibrium in operations research and mathematical economics: traffic equilibria, spatial price equilibria, Nash equilibria of convex games, and the optimality conditions of constrained optimization all take this form. Many applications have two features that the…
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 2: The Augmentation Bound for Maximum-Augmentation PathsResearch Paper
The maximum flow problem asks how much of a commodity can be sent from a source to a sink through a network whose arcs have capacities. It underlies bipartite matching, transportation, scheduling and many reductions in combinatorial optimization. The classical method for it, the labeling method of Ford and Fulkerson (Flows in Networks, 1962), repeatedly…
Monotone Mappings with Application in Dynamic Programming I: Compactness Gives Convergence of the DP Algorithm and an Optimal Stationary Policy under Uniform IncreaseResearch Paper
Infinite-horizon optimal control problems with nonnegative costs (Strauch's negative dynamic programming, the positive-cost counterpart of Blackwell's positive model) are among the settings where the standard tools of discounted dynamic programming fail: there is no contraction, costs may be infinite, and the value-iteration algorithm started from zero may…
On Polyhedral Approximations of the Second-Order Cone I: A Compact Polyhedral Approximation of the Lorentz ConeResearch Paper
Conic quadratic programs (second-order cone programs) minimize a linear objective subject to linear constraints and constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ. They model robust linear programs with ellipsoidal uncertainty, truss topology design, contact problems with Coulomb friction, and convex quadratically constrained quadratic…
On Minimizing a Convex Function Subject to Linear Inequalities I: Beale's Simplex Method for a Convex Quadratic Function TerminatesResearch Paper
Quadratic programming, the minimization of a convex quadratic function subject to linear constraints, is the simplest nonlinear extension of linear programming. It arises in least-squares estimation with sign constraints, in portfolio selection, and as the subproblem solved at each iteration of Newton-type methods for general smooth convex programs. E. M.…
Simultaneous Analysis of Lasso and Dantzig Selector V: Estimation, Prediction and Sparsity Bounds for the LassoResearch Paper
In a linear regression with many more candidate variables than observations, least squares is not defined uniquely and does not estimate anything useful. The Lasso (Tibshirani, 1996) replaces it by an ℓ1-penalised least-squares problem, which is convex, can be solved at scale, and returns sparse coefficient vectors. The question that a statistician, a…
Simultaneous Analysis of Lasso and Dantzig Selector IV: Estimation and Prediction Error Bounds for the Dantzig SelectorResearch Paper
In high-dimensional linear regression the number of unknown coefficients M may be much larger than the number of observations n, and the coefficient vector can only be recovered because it is assumed to be sparse: few of its entries are non-zero. Two convex estimators dominate this setting: the Lasso of Tibshirani (1996), an ℓ1-penalized least-squares…
Simultaneous Analysis of Lasso and Dantzig Selector II: Approximate Equivalence of the Lasso and Dantzig Prediction LossesResearch Paper
Two estimators dominate sparse high-dimensional regression, where the number M of candidate regressors can far exceed the sample size n. The Lasso (Tibshirani, 1996) minimises a least-squares criterion plus an ℓ1 penalty. The Dantzig selector (Candès and Tao, 2007) minimises the ℓ1 norm of the coefficients subject to a bound on the correlation…
Subjectivity and Correlation in Randomized Strategies I: Subjective Mixed Equilibria of Two-Person Games Have Objective PayoffsResearch Paper
Classical non-cooperative game theory randomizes with objective, independent devices: each player spins a private wheel whose odds everyone agrees on. Aumann's 1974 paper (doi:10.1016/0304-4068(74)90037-8) asks what changes when the randomizing events are ordinary events of the world, about which players may hold different subjective probabilities and may…
On Properties of Stochastic Inventory Systems III: Bounds between the Optimal Costs of the Stochastic (Q, r) Model and the EOQ ModelResearch Paper
The continuous-review (Q,r) policy — order a fixed quantity Q whenever the inventory position falls to the reorder point r — is the textbook policy for a single item with random demand and a positive replenishment leadtime (Hadley and Whitin 1963). Its optimal parameters have no closed form, so practice routinely falls back on the deterministic economic…
Markovian Decision Processes with Uncertain Transition Probabilities I: The Max-Min Policy-Iteration Algorithm Terminates at a Max-Min Optimal Pure Stationary PolicyResearch Paper
Howard's finite Markovian decision process (MDP) models a controller who, at each instant, observes the state of a system, chooses a decision, collects a reward and moves to a random next state with known transition probabilities. Howard's policy-iteration algorithm computes an optimal policy, and the model has been applied to inventory control, equipment…
An Analysis of Several Heuristics for the Traveling Salesman Problem I: Nearest Neighbor Tours Can Be Far from OptimalResearch Paper
The traveling salesman problem with the triangle inequality asks for a shortest closed tour through n points whose distances form a metric. It is NP-hard, so in practice tours are built by fast construction heuristics, and the natural question is how far such a tour can be from optimal in the worst case. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3),…
An Exact Duality Theory for Semidefinite Programming and Its Complexity Implications: The Extended Lagrange–Slater Dual Has Zero Duality Gap and Attains Its OptimumResearch Paper
Semidefinite programming (SDP) optimizes a linear function over the intersection of the cone of positive semidefinite matrices with an affine subspace. It contains linear programming as the diagonal case and is the computational core of relaxations in combinatorial optimization, control theory and polynomial optimization. Its standard duality theory,…
A Nonsmooth Version of Newton's Method II: global convergence of the generalized-Jacobian Newton method on a ball, with an error estimateResearch Paper
Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0 with F:Rn→Rn that is continuous and locally Lipschitz but not differentiable. Complementarity problems rewritten through the min or Fischer–Burmeister functions, Karush–Kuhn–Tucker systems of nonlinear programs, and the gradients of…
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 4: First-Fit Decreasing Uses at Most 71/60 L* + 5 Bins When No Item Exceeds 1/2Research Paper
Bin packing asks how to place a list of items with sizes in (0,1] into as few unit-capacity bins as possible. It models the cutting of stock material, the packing of files onto tracks of a disc and the assignment of jobs to machines with a common deadline. Deciding the optimum is NP-hard, so in practice simple rules are used, and the question is how far…
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper
Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 2: First-Fit and Best-Fit with Bounded Item SizesResearch Paper
Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models cutting stock, memory allocation, file placement and the loading of trucks, and it is NP-hard, so in practice lists are packed by simple rules that look at one item at a time. The two most widely used rules are First-Fit and Best-Fit, and the question that…
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 1: First-Fit and Best-Fit Have Asymptotic Worst-Case Ratio 17/10Research Paper
Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It is one of the first problems studied through the worst-case analysis of approximation algorithms, and it models storage allocation, paging and file placement on tracks, as well as cutting-stock problems in operations research. Deciding the optimum exactly is NP-hard,…
Optimum Branchings: The Vertices of the Branching Polyhedron Are Exactly the BranchingsResearch Paper
A branching in a directed graph is a set of edges that contains no cycle (even ignoring directions) and in which no two edges point to the same node; a connected branching is an arborescence, a tree rooted at one node with all edges directed away from the root. The optimum branching problem asks, for real weights on the edges, for a branching of maximum…
Stochastic Linear Optimization under Bandit Feedback 1: The Regret Bound of ConfidenceBallResearch Paper
In stochastic linear optimization under bandit feedback a learner repeatedly chooses a decision xt from a fixed set D⊆Rn and observes only the noisy cost of that one decision, whose expectation is a fixed but unknown linear function μ⊤xt. The model covers online routing, ad and product selection with feature vectors, and any…