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 Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 2: FOREST's Forests E_i Preserve Local Node-Connectivity up to i in a Simple GraphResearch Paper
Given a k-connected graph, many connectivity algorithms run in time that grows with the number of edges ∣E∣. A sparse certificate is a spanning subgraph with only O(k∣V∣) edges that is still k-connected; computing one first and running the expensive algorithm on it replaces ∣E∣ by k∣V∣ in the bound. Finding a k-connected spanning subgraph with the minimum…
A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 1: The FOREST Decomposition Preserves Local Edge-ConnectivityResearch Paper
Many graph algorithms for connectivity questions run in time proportional to the number of edges. When the question is only whether a graph is k-edge-connected, or what its local edge-connectivities are up to a threshold k, most edges are irrelevant: a spanning subgraph with O(k∣V∣) edges already carries the answer. Such a subgraph is called a sparse…
Disjunctive Programming VI: Extended Formulations for Perfectly Matchable Subgraph PolytopesTextbook
Many polytopes that arise from combinatorial optimization problems have no small facet
description in their natural variable space, yet become describable by a compact linear system
once lifted to a higher-dimensional space of auxiliary variables and projected back down —
Chapter 2's own extended formulation of the convex hull of a disjunctive set is one…
The Relaxation Method for Linear Inequalities II: For a Lower-Dimensional Solution Polytope Infinite Reflexions Settle on a Sphere with Axis L_rResearch Paper
Adversarially Robust Generalization Requires More Data 4: Robust Learning from One Thresholded Sample in the Bernoulli ModelResearch Paper
Classifiers trained to high standard accuracy can be fooled by small, deliberately chosen perturbations of their inputs, so-called adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015). Training methods that aim at robustness against perturbations bounded in the ℓ∞ norm reach high robust accuracy on the training set while robust test…
The Relaxation Method for Linear Inequalities I: For a Full-Dimensional Solution Polytope the Relaxation Converges and the Reflexion Method TerminatesResearch Paper
Finding a point that satisfies a finite system of linear inequalities is the feasibility problem underlying linear programming, and it is also the basic step of many methods in signal and image reconstruction, where the system is too large to be solved by elimination. The relaxation method attacks it one inequality at a time: from the current point, move…
Adversarially Robust Generalization Requires More Data 2: A Robust-Error Lower Bound for Linear Classifiers in the Bernoulli ModelResearch Paper
Classifiers trained by standard methods reach high accuracy on image benchmarks and yet change their prediction under perturbations of each pixel that are invisible to a human. Training against such perturbations (adversarial training) improves robustness, but on CIFAR10 and SVHN the robust test accuracy stays far below the robust training accuracy: robust…
On Controllability of Delayed Boolean Control Networks: Trajectory Controllability Avoiding Forbidden Trajectories Iff the Reduced Transition-Count Matrix Is IrreducibleResearch Paper
Boolean networks model gene regulatory networks by giving each gene an on/off value and updating all values synchronously by logical rules (Kauffman, 1969). Adding external Boolean inputs gives Boolean control networks (BCNs), in which a designer (a drug, an intervention) chooses the inputs over time. The basic control-theoretic question is controllability:…
Cones of Matrices and Set-Functions and 0–1 Optimization III: The Defect of a Stable Set Inequality Bounds Its N-IndexResearch Paper
Many 0–1 optimization problems can be written as linear programs over the convex hull of the 0–1 points of a polytope, but that hull usually has no manageable description by inequalities. Lift-and-project methods approximate it by a sequence of convex sets. Each set comes from a linear or semidefinite system in more variables, followed by a projection.…
Cones of Matrices and Set-Functions and 0–1 Optimization I: n Rounds of the Lovász–Schrijver N Operator Give the 0–1 HullResearch Paper
A 0–1 integer program asks for the best 0–1 vector satisfying a system of linear inequalities. Its linear relaxation is easy to optimize over, but the relaxation is usually much larger than the convex hull of the 0–1 solutions. Lift-and-project methods close this gap systematically: they lift the relaxation to a higher-dimensional space, add constraints…
Supervisory Control of a Class of Discrete Event Processes I: Minimally Restrictive Supervisors Exist iff the Supremal Controllable Legal Sublanguage Contains the Minimal Acceptable LanguageResearch Paper
Manufacturing cells, communication protocols, traffic systems and database transaction managers are naturally described not by differential equations but by sequences of discrete events: a machine starts, a part arrives, a message is lost. Ramadge and Wonham's 1987 paper (SIAM J. Control Optim. 25(1)) set up a control theory for such systems in which the…
Approximating Clique-Width and Branch-Width: Well-Linked Sets Certify Clique-WidthResearch Paper
Clique-width is a graph parameter introduced by Courcelle and Olariu (Discrete Appl. Math. 101 (2000)) that measures how far a graph is from being built by a few labelled operations. Every problem expressible in monadic second-order logic with quantification over vertices and vertex sets (MSO1) can be solved in linear time on graphs given together with a…
Approximation Algorithms for Combinatorial Problems V: The Overlap-Ratio Greedy C2 Is Within 1 + ln k of the Least-Overlap Cover on EC(k)Research Paper
David S. Johnson's 1974 paper Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9 (1974) 256–278) was one of the first systematic worst-case analyses of polynomial-time heuristics for NP-complete optimization problems. Its Section 5 proves the harmonic bound ∑j=1k1/j for the greedy algorithm on minimum-cardinality set…
Sparse Approximate Solutions to Linear Systems 2: An Exact Cover by 3-Sets Exists iff Its Incidence System Has a 1/2-Approximate Solution with at Most m/3 NonzerosResearch Paper
Many problems in signal processing, statistics and function interpolation ask for a solution of a linear system Ax≈b that uses as few columns of A as possible: a sparse approximate solution. Natarajan's 1995 paper Sparse Approximate Solutions to Linear Systems (SIAM J. Comput. 24(2):227–234) was motivated by radial basis interpolation, where each…
Jobshop-Like Queueing Systems: The Equilibrium Distribution with State-Dependent Arrival and Service RatesResearch Paper
A jobshop is a factory in which each job visits a sequence of machine groups, the sequence differing from job to job. J. R. Jackson's 1963 paper Jobshop-Like Queueing Systems (Management Science 10(1), 131–142) models such a shop as a network of queues and computes its long-run distribution of queue lengths in closed form. It generalizes his 1957 paper Netwo…
Scenario Reduction Algorithms in Stochastic Programming III: The Minimal Reduction Distance of a Regular Ternary Scenario TreeResearch Paper
Multistage stochastic programs are solved on a finite scenario tree: a discrete probability distribution whose support points are paths of a random process. Realistic trees have far too many scenarios for the resulting optimization problem, so practitioners reduce the tree, keeping n of its N scenarios and redistributing the probability of the deleted ones.…
Scenario Reduction Algorithms in Stochastic Programming II: The Minimal Reduction Distance of a Regular Binary Scenario TreeResearch Paper
Multistage stochastic programs are solved on a finite scenario tree, a discrete probability measure whose atoms are paths of a stochastic process. The size of the deterministic equivalent grows with the number of scenarios, so practitioners replace the original measure P=∑i=1Npiδωi by a measure supported on n<N of its scenarios.…
Scenario Reduction Algorithms in Stochastic Programming I: Fast Forward Selection Realizes the Forward Selection PrincipleResearch Paper
Multistage and two-stage stochastic programs are solved numerically on a discrete probability distribution: a finite set of scenariosω1,…,ωN with probabilities p1,…,pN. The size of the resulting optimization problem grows with N, and scenario sets produced by sampling or by historical data are often far too large to be solved…
Golden Ratio Algorithms for Variational Inequalities I: The Golden Ratio Algorithm with a Fixed Step Converges to a Solution of a Monotone Variational InequalityResearch Paper
A monotone variational inequality asks for a point at which a monotone operator and a convex function are in equilibrium. It unifies convex minimization (where F is a gradient), convex–concave saddle-point problems (where F is the skew gradient of a Lagrangian), Nash equilibria of monotone games, and complementarity problems in economics and traffic…
Fast Algorithms for Finding Nearest Common Ancestors II: Nearest Common Ancestors in a Complete Binary Tree by Symmetric-Order ArithmeticResearch Paper
The nearest common ancestor (nca) problem asks, for a fixed rooted tree and a sequence of vertex pairs (v,w), for the deepest vertex that is an ancestor of both. It is a basic step in suffix-tree string algorithms and is equivalent to range-minimum queries (Bender, Farach-Colton, 2000). Harel and Tarjan, Fast Algorithms for Finding Nearest Common Ancestors,…
Fast Algorithms for Finding Nearest Common Ancestors I: A Lower Bound for Pointer MachinesResearch Paper
The nearest common ancestor problem asks, for a rooted tree and two of its vertices x and y, for the deepest vertex that is an ancestor of both, written nca(x,y). It appears as a subroutine in string algorithms (suffix trees), in graph algorithms (path queries, dominators) and in the analysis of set-union structures. Aho, Hopcroft and Ullman (…
Proximal Newton-Type Methods for Minimizing Composite Functions II: Local Linear and Superlinear Convergence of the Inexact Proximal Newton MethodResearch Paper
Many estimation problems in statistics, signal processing and bioinformatics minimize a composite functionf=g+h: a smooth convex loss g plus a convex but nonsmooth penalty or constraint h, such as the lasso's ℓ1 norm or the indicator of a convex set. Proximal Newton-type methods handle such problems by minimizing, at each iterate xk, a model …
A New Approach to the Maximum-Flow Problem 2: The Nonsaturating-Push Bound for FIFO Push-RelabelResearch Paper
The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges carry capacities. It is a basic model of operations research. Transportation, scheduling, bipartite matching and image segmentation reduce to it, and it is the inner step of many combinatorial algorithms.
Proximal Newton-Type Methods for Minimizing Composite Functions I: Proximal Quasi-Newton Methods Converge Q-Superlinearly under the Dennis–Moré CriterionResearch Paper
Many estimation problems in statistics, machine learning and signal processing minimize a composite function, the sum of a smooth loss and a convex but nonsmooth regularizer or constraint: the lasso and ℓ1-regularized logistic regression, the graphical lasso for sparse inverse covariance estimation, and constrained least squares, where the nonsmooth…
A New Approach to the Maximum-Flow Problem 1: The Generic Push-Relabel Algorithm and Its Operation BoundResearch Paper
The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges have capacities. It is a basic model in operations research (transportation, scheduling, bipartite matching) and a standard subroutine in combinatorial optimization.