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.
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…
Convergence Properties of the Nelder–Mead Simplex Method in Low Dimensions I: In Dimension 1, Both Endpoints Converge to the Minimizer of a Strictly Convex Function When ρχ ≥ 1Research Paper
The Nelder–Mead simplex method (Nelder and Mead, 1965) is one of the most widely used methods for minimizing a function without derivatives. It is the default unconstrained derivative-free minimizer in several numerical libraries (fminsearch in MATLAB, method="Nelder-Mead" in SciPy) and is used routinely in chemistry, engineering and statistics, where the…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 3: The Nonquadratic Method of Multipliers for Linear Equality Constraints ConvergesResearch Paper
The method of multipliers (augmented Lagrangian method) of Hestenes and Powell is one of the standard algorithms for constrained convex optimization. Each iteration minimizes the Lagrangian plus a quadratic penalty on the constraint residual, then updates the multiplier estimate. Rockafellar showed in 1976 that this method is the proximal point algorithm…
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 2: Bregman Proximal Point Sequences Exist When im ∇h Is ℝⁿ, or Is Open and 0 ∈ im TResearch Paper
The proximal point method seeks a zero of an operator by repeatedly solving an implicit equation. For a maximal monotone operator, the ordinary quadratic proximal step is available throughout a Hilbert space. Eckstein's 1993 paper replaces the quadratic penalty with a Bregman function, allowing a step to reflect the geometry of a constrained problem. Before…
Dynamic Pricing and Inventory Control of Substitute Products 3: Optimal Dynamic Prices When the Other Variates Keep Fixed PricesResearch Paper
A retailer that sells a line of substitutable products — sizes, colours or models of one item — over a short season without replenishment must decide how to price each variate as inventory runs down. Customers substitute: when one variate is expensive or sold out, part of its demand moves to the others. Dong, Kouvelis and Tian (M&SOM 2009) model this with a …