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.
A Nonsmooth Version of Newton's Method I: local superlinear convergence of the generalized-Jacobian Newton method at a semismooth regular rootResearch Paper
Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0 whose map F:Rn→Rn is Lipschitz but not differentiable: reformulations of nonlinear complementarity problems through the componentwise minimum or the Fischer–Burmeister function, Karush–Kuhn–Tucker systems of constrained programs, and…
Shortest Connection Networks And Some Generalizations: Construction Principles P1 and P2 Yield a Shortest Spanning Subtree of Every Connected Labelled GraphResearch Paper
Connecting a set of terminals by a network of direct links of least total length is one of the oldest problems of combinatorial optimization. R. C. Prim's 1957 paper in the Bell System Technical Journal (DOI) was motivated by the rate structure for Bell System leased-line services, in which the charge for connecting a set of terminals depends on the length…
Updating Quasi-Newton Matrices with Limited Storage: The Limited-Storage BFGS Method Reaches the Minimizer of a Strictly Convex Quadratic in at Most n StepsResearch Paper
Quasi-Newton methods minimize a smooth function f on Rn by moving along dk=−Hkgk, where gk is the gradient and Hk is an approximation of the inverse Hessian built from observed gradient differences. The BFGS update is the most widely used way of building Hk, but it stores a dense n×n matrix, which is prohibitive for large n.
Cubic Regularization of Newton Method and Its Global Performance I: Global Rate of Convergence to Second-Order Stationary PointsResearch Paper
Newton's method is the standard second-order algorithm for unconstrained minimization, but without safeguards it has no global guarantee: far from a minimizer the Newton step can increase the objective, and at a point where the Hessian is indefinite the step can head for a saddle point or a maximum. The usual repairs (line search, trust regions,…
A Simple Parallel Algorithm for the Maximal Independent Set Problem II: The Round Bound of the Derandomized AlgorithmResearch Paper
A maximal independent set (MIS) of a graph is a set of pairwise non-adjacent vertices to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be computed by a fast parallel algorithm was a central question of parallel complexity in the early 1980s: Karp and…
A Simple Parallel Algorithm for the Maximal Independent Set Problem I: One Round of Monte Carlo Algorithm A or B Removes an Expected Eighth of the EdgesResearch Paper
A maximal independent set (MIS) of a graph is a set of vertices, no two adjacent, to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be found fast in parallel was a central question of parallel complexity in the early 1980s: an MIS algorithm is a…
Critical-Path Planning and Scheduling I: Critical Jobs Occur Only When the Completion Time Is the Earliest, and Then Form a Path from Origin to TerminusResearch Paper
The Critical-Path Method (CPM) was introduced by J. E. Kelley, Jr. (Remington Rand) and M. R. Walker (du Pont) in Critical-Path Planning and Scheduling (Proc. Eastern Joint Computer Conference, 1959, pp. 160–173, doi:10.1145/1460299.1460318). Together with PERT, developed at the same time for the Polaris programme, it became the standard way to plan and…
Markov-Renewal Programming. I: Formulation, Finite Return Models: Policy Iteration Finds an Optimal Stationary Policy for the Discounted Infinite-Horizon Markov-Renewal ProgramResearch Paper
Many operational systems move between a finite number of states at random times: a machine alternates between working and repair, a queue between occupancy levels, an inventory between stock positions. When the time spent in a state is not exponential and not a fixed period, neither discrete-time Markov decision processes nor continuous-time Markov chains…
Methods of Conjugate Gradients for Solving Linear Systems II: Each Conjugate Gradient Step Shortens the Error VectorResearch Paper
The conjugate gradient method (cg-method) of Hestenes and Stiefel is the standard iterative solver for linear systems Ax=k with a symmetric positive definite matrix A. It is used for the large sparse systems of finite-element and finite-difference discretizations, as the inner solver of Newton-type and interior-point methods in optimization, and as the…
Methods of Conjugate Gradients for Solving Linear Systems I: Finite Termination of the Conjugate Gradient MethodResearch Paper
Solving a linear system Ax=k with a large symmetric positive definite matrix A is a basic task of scientific computing: it arises from discretized elliptic equations, least-squares problems and the Newton steps of optimization methods. In 1952 Magnus Hestenes and Eduard Stiefel published the conjugate gradient method (cg-method) (J. Res. Natl. Bur. Stand.…
Logarithmic Regret Algorithms for Online Convex Optimization 4: Logarithmic Regret of Exponentially Weighted Online OptimizationResearch Paper
In online convex optimization a player repeatedly chooses a point xt from a convex set P⊆Rn, after which an adversary reveals a convex cost function ft and the player pays ft(xt). The player's regret after T rounds is its total cost minus the cost of the best fixed point in hindsight. The model covers online portfolio selection,…
Logarithmic Regret Algorithms for Online Convex Optimization 3: Logarithmic Regret of Follow the Approximate LeaderResearch Paper
Online convex optimization models repeated decision making against an adversary: in each round a player chooses a point of a convex set, and only then learns the convex cost of that round. It covers online portfolio selection, online regression and routing, and it is the standard lens for analysing learning algorithms that must commit before seeing data.…
The Optimal Sample Complexity of PAC Learning: The Optimal Realizable Sample Complexity BoundResearch Paper
The sample complexity of a learning problem is the number of labelled examples needed to learn to a prescribed accuracy with a prescribed confidence. In Valiant's probably approximately correct (PAC) model it is the basic quantity of statistical learning theory: it says how much data is necessary and sufficient, as a function of the complexity of the…
Optimizing Strategic Safety Stock Placement in Supply Chains: Binding Base Stocks Are Optimal in a Serial System without Guaranteed Internal ServiceResearch Paper
Where to hold safety stock in a multi-stage supply chain is a basic question of inventory planning. Graves and Willems (MSOM 2(1), 2000) optimize safety-stock placement under the guaranteed-service assumption: each stage quotes a service time to its customers and always meets it. That assumption makes the placement problem tractable, and it is the basis of…
Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper
Many combinatorial optimization problems ask for a subset of a finite ground set that maximizes a set function with diminishing returns: Max Cut and Max Directed Cut in graphs, facility location, maximum entropy sampling, and welfare problems in combinatorial auctions all fit this pattern. The common abstraction is the maximization of a submodular function,…
Scenario Reduction in Stochastic Programming: The Optimal Redistribution Rule and the Explicit Kantorovich Distance of a Reduced MeasureResearch Paper
Stochastic programs are solved in practice on a finite set of scenarios: a discrete probability distribution P=∑i=1Npiδωi that approximates the true distribution of the uncertain data. The size of the resulting deterministic problem grows with N, and for multistage models it grows very fast, so N is often reduced before solving. The…
A Social Equilibrium Existence Theorem: Equilibrium Points Exist When Actions Are Contractible Polyhedra and Constrained Best Responses Are ContractibleResearch Paper
Nash's equilibrium existence theorem assumes that each player's set of available strategies is fixed. Many social and economic systems do not work that way: a consumer's budget set depends on prices, which are the choices of another agent, and a firm's feasible production may depend on what other firms do. Gerard Debreu's A Social Equilibrium Existence…
Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper
Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…
Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper
Minimizing the sum of weighted completion times∑jwjCj is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on m identical parallel machines it is harder still, so the…
Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper
Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written P∣rj∣∑Cj), the problem is strongly NP-hard already on one machine. Research has therefore looked for…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 3: Advance-Purchase Discounts Pareto-Improve Pull Contracts under At-Once Shipping CostsResearch Paper
A supplier and a retailer who trade a seasonal product must decide who carries the inventory risk: the stock left unsold, or the demand left unserved, when the season ends. With a push contract the retailer orders everything before the season and bears the risk; with a pull contract he orders during the season from the supplier's stock at a single wholesale…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 2: Advance-Purchase Discounts Coordinate the Supply ChainResearch Paper
A supplier who must produce before a selling season, and a retailer who sells into uncertain demand, have to decide who holds the inventory that may go unsold. Cachon (Management Science 50(2), 2004) studies this allocation of inventory risk using nothing but wholesale prices. With a push contract the retailer orders everything before production and bears…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 1: The Pareto Set of Push and Pull ContractsResearch Paper
A supplier and a retailer trade a product with a single selling season and uncertain demand. Someone has to decide, before demand is known, how many units exist, and someone has to be left holding the units that do not sell. With a push contract the retailer orders (prebooks) before the season and bears all of this risk; with a pull contract the supplier…
Generalization Bounds in the Predict-then-Optimize Framework III: Strongly Convex Sets Satisfy the Strength PropertyResearch Paper
In the predict-then-optimize framework, a machine-learning model predicts the cost vector c^ of a linear optimization problem minw∈Sc^⊤w, and a decision is made by solving that problem with the prediction. Elmachtoub and Grigas (Smart "Predict, then Optimize", Management Science 2022) proposed judging predictions by the SPO loss, the…
Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper
Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…