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 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales: The Dual-Balancing Policy Costs at Most Twice Any Nonanticipatory Policy under Independent DemandsResearch Paper
Inventory systems in which unmet demand is lost, not backlogged, are the norm in retail: a customer who finds an empty shelf buys elsewhere. With a positive lead timeL between ordering and delivery, the optimal policy for such a system depends on the entire pipeline of outstanding orders, so dynamic programming is intractable beyond small L. Optimal…
Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization: The Matrix Shrinkage Fixed Point Iteration Converges to an Optimal Solution of the Nuclear Norm Regularized ProblemResearch Paper
Many estimation problems ask for a matrix of low rank that is consistent with a small number of linear measurements: completing a partially observed ratings matrix, identifying a low-order linear system, or embedding points from a few pairwise distances. Rank minimization under linear constraints is NP-hard, and the standard convex surrogate replaces the…
Stochastic Convex Programming: Basic Duality 2: With a Bounded Second-Stage Set the Intrinsic First-Stage Problem Coincides with the One Induced by P and Recourse Is AttainedResearch Paper
Two-stage stochastic programming with recourse models a decision taken in two steps: a first-stage decision x1 is fixed before a random outcome s is observed, and a recourse decision x2(s) is taken afterwards, once s is known. The model goes back to Dantzig (1955) and Beale (1955) and is the basic template of stochastic optimization in operations…
Quality Control under Markovian Deterioration 3: Sufficient Conditions for a Three-Region Optimal Policy and for an Optimal Policy That Never InspectsResearch Paper
Inspection and revision cost money, but continued production can allow a deteriorating process to remain in a costly state. A controller therefore needs a rule that converts incomplete information about the process into an action. Ross's two-state model makes that decision precise: the process can be good or bad, the bad state persists until revision, and…
Quality Control under Markovian Deterioration 2: Never Inspecting or Revising Is Optimal Exactly When R ≥ C/(1 − β(1 − π))Research Paper
A production process can deteriorate without an operator seeing its current condition. Producing a unit, inspecting the process, and revising the process have different immediate costs and different effects on what can be known or controlled next period. The operator therefore needs a rule based on a belief about deterioration, rather than on the hidden…
Approximation Algorithms for Scheduling Unrelated Parallel Machines 2: Enumerating Long Assignments and Rounding the LP Gives a (1 + ε)-Approximation for MakespanResearch Paper
Scheduling independent jobs on unrelated parallel machines to minimize the makespan is one of the basic NP-hard problems of scheduling theory: each job has its own processing time on each machine, with no relation between machines, and the goal is to finish all jobs as early as possible. When the number of machines is part of the input, Lenstra, Shmoys and…
The Geometry of Graphs and Some of Its Algorithmic Applications 4: The m-Cube Has Isometric Dimension mResearch Paper
A finite graph has distances defined by the lengths of its shortest paths. Representing those distances inside a normed vector space lets geometric language describe a combinatorial object, but the number of coordinates required can depend sharply on the graph. The isometric dimension asks for the smallest dimension of any real normed space that preserves…
Strongly Regular Generalized Equations IV: Strong Second-Order Sufficiency and Linearly Independent Binding Gradients Make the KKT Generalized Equation Strongly RegularResearch Paper
A nonlinear program is rarely solved once. Its data are estimated, rounded, or varied on purpose in a parametric study, and an algorithm such as sequential quadratic programming replaces it at every iteration by a nearby linearised problem. Both uses need the same fact: near a solution, the Karush–Kuhn–Tucker (KKT) system should have exactly one solution…
The Four-Colour Theorem: Birkhoff's Lemma (6.4) — Every Non-Empty Consistent Set of Edge-Colourings of a Ring of Length 5 Meeting ℰ Includes One of 𝒞ᵢ, 𝒟ᵢ, ℰResearch Paper
The Four-Colour Theorem was proved by Appel and Haken (1976–77) and re-proved by Robertson, Sanders, Seymour and Thomas (RSST, 1997) with a simpler, fully computer-checkable argument. Both proofs rest on reducibility: a configuration is reducible when every 4-colouring of the ring around it can be modified, by Kempe-chain recolouring, into one that extends…
Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations II: A Semismooth, Strongly BD-Regular Zero That Is a Limit Point of the Damped Newton Method Attracts It with Unit StepsResearch Paper
Many problems of optimization and equilibrium reduce to a system of nonsmooth equationsF(x)=0 with F:Rn→Rn locally Lipschitz but not differentiable: nonlinear complementarity problems written as min{h(x),f(x)}=0, variational inequalities through the normal map, and Karush–Kuhn–Tucker systems of constrained programs. Newton's method…
Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations I: At a Semismooth, Strongly BD-Regular Zero the ∂_B Newton Method Converges Superlinearly and ‖F‖ Decreases SuperlinearlyResearch Paper
Many problems of operations research reduce to a system of nonsmooth equationsF(x)=0 with F:Rn→Rn locally Lipschitz but not differentiable: the nonlinear complementarity problem h(x)≥0, f(x)≥0, h(x)Tf(x)=0 becomes F(x)=min{h(x),f(x)}=0 componentwise, and variational inequalities, KKT systems and max-type equations admit similar…
Job Matching, Coalition Formation, and Gross Substitutes 3: A Coalition Technology Satisfying Gross Substitutes for m + 1 Identical Firms Has a Strict Core AllocationResearch Paper
Workers can form groups and produce an output that they divide through salaries. A group may object to a proposed allocation when it can pay all of its members at least as much and one member more. The central question is whether any allocation survives every such objection. Kelso and Crawford's 1982 paper gives a sufficient condition based on how an…
Job Matching, Coalition Formation, and Gross Substitutes 4: Without Ties the Salary-Adjustment Process Reaches the Firm-Optimal Discrete Strict Core AllocationResearch Paper
Labor markets match heterogeneous workers to heterogeneous firms, and the terms of each match — the salary — are negotiated. Kelso and Crawford (Econometrica 50 (1982)) studied such a market in which a firm may hire many workers, its output depends on the whole set it hires, and salaries are set worker by worker. Their model contains the marriage problem of…
Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 3: Shifting and Scaling the Processing Times Changes Neither the Optimal Sequence nor the Branch-and-Bound PathResearch Paper
Branch and bound was introduced for integer programming by Land and Doig (1960) and for the travelling salesman problem by Little, Murty, Sweeney and Karel (1963). Ignall and Schrage (1965) were among the first to apply it to machine scheduling. They give lower bounds for two permutation flow-shop problems: the makespan on three machines, and the mean…
Job Matching, Coalition Formation, and Gross Substitutes 2: Under Gross Substitutes Every Job-Matching Market with Continuous Salaries Has a Strict Core AllocationResearch Paper
Labour markets match workers to firms that hire teams: a firm's output depends on the whole set of workers it employs, while each worker holds one job. A salary agreement is stable when no firm and group of workers can renegotiate among themselves to the benefit of all of them. Shapley and Shubik (1971) showed that such stable outcomes exist when each firm…
Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 2: Stable and Unstable Modes Coexist Under Clearing on a Two-Part-Type SystemResearch Paper
Flexible manufacturing systems are often scheduled by simple distributed rules: each machine looks only at its own buffers and decides, in real time, which part type to work on next. Switching from one part type to another costs a set-up time during which the machine produces nothing, so a natural rule is to work on a buffer until it is empty and only then…
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem 2: For g = 0 ≤ f, the Tour ψ′ Minimizes the Largest Changeover CostResearch Paper
A machine whose condition is described by one real number — the temperature of a furnace, the setting of a cutting knife — must process N jobs in some order. Job i must be started in state Ai and leaves the machine in state Bi; moving the state between jobs costs money. Ordering the jobs so that the machine returns to its starting job after the last one…
Contact Interactions on a Lattice II: If λₖ/μ < k/(2d − 1), the Expected Size of a Contact Process Is Integrable in TimeResearch Paper
The contact process is the basic model of an infection spreading on a graph: infected sites recover at a constant rate, and healthy sites are infected at a rate that depends on how many of their neighbours are infected. T. E. Harris introduced it in Contact Interactions on a Lattice (Ann. Probab. 2, 1974, doi:10.1214/aop/1176996493), and it became one of…
Global Convergence Properties of Conjugate Gradient Methods for Optimization II: Conjugate Gradient Methods with β_k ≥ 0 and Property (*) Are Globally Convergent under Sufficient DescentResearch Paper
Nonlinear conjugate gradient methods minimize a smooth function f of n variables using only function values, gradients and a few vectors of storage. They are the standard choice when n is too large for quasi-Newton matrices, and they remain building blocks of large-scale solvers in optimization, scientific computing and machine learning. The method of Polak…
Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints 2: Near the Optimal Ratio, a Maximum-Weight Initial Set Is ρ-MaximalResearch Paper
The single-machine sequencing problem with precedence constraints, written 1∣prec∣∑wjCj, asks for an order of n jobs on one machine that respects a given acyclic digraph of precedences and minimizes the weighted sum of completion times. It is NP-hard in general (Lawler 1978; Lenstra and Rinnooy Kan 1978), and much of its structural…
Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 3: Clear-a-Fraction Policies Are Stable From Every Initial State When ρ′ₘ < 1Research Paper
A flexible manufacturing system processes several part types on shared machines, and a machine that switches from one part type to another pays a set-up time. Real-time, distributed scheduling rules for such systems decide locally, at each machine, when to switch and to which buffer. The simplest such rules are clearing policies: a machine keeps working on…
Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms III: Every Directed Uniform Multicommodity Flow Problem Has Ω(𝒮/log n) ≤ f ≤ 𝒮Research Paper
Many graph problems in routing, VLSI layout and scheduling ask for a cut that separates a lot of demand while cutting little capacity. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest flow equals the smallest cut. For several commodities sharing one network this equality fails, and the question becomes how far…
A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 2: Internal Approximations Under (4.1)–(4.3) Have Solutions v_h Converging Strongly to vResearch Paper
An infinite dimensional variational problem can be described by continuous linear operators and convex functionals, yet numerical work needs finite dimensional spaces. The question is whether a solution computed in a finite dimensional approximation still approaches the solution of the original problem when the approximation is refined. Gabay and Mercier's I…
Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms II: Every Product Multicommodity Flow Problem with k Commodities Has Ω(𝒮/log k) ≤ f ≤ 𝒮Research Paper
For a single commodity, the Ford–Fulkerson theorem says that the maximum flow between two nodes equals the minimum capacity of a cut separating them. Many routing and partitioning problems involve many source–sink pairs at once, and for those the equality fails: the largest fraction of every demand that can be routed simultaneously can be strictly smaller…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 4: Nonquadratic Multiplier Methods for Inequality Constraints Find an Optimal MultiplierResearch Paper
Convex programs with inequality constraints arise when a decision must meet capacity, resource, or performance limits. Their Lagrange multipliers assign a price to each constraint. Finding an optimal multiplier gives a dual certificate and can guide a primal optimization method. Classical quadratic multiplier methods update these prices through a particular…