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.
Adversarial Robustness for Latent Models: Revisiting the Robust-Standard Accuracies Tradeoff: The Bayes-Optimal Classifier's Boundary Risk Vanishes in the Latent Gaussian Mixture ModelResearch Paper
Classifiers that reach high accuracy on test data can often be fooled by perturbations of the input that are small in some norm. Training a classifier to resist such perturbations (adversarial training) typically lowers its accuracy on unperturbed data, and part of the literature argues that this robust–standard accuracy tradeoff is unavoidable: for some…
Greedy Algorithm for Multiway Matching with Bounded Regret: The Sum-of-Squares Algorithm Has Any-Time Regret O(1/δ), and O(logt) When Configurations Mix Queueable and Nonqueueable ResourcesResearch Paper
Many allocation systems combine units of several resource types into bundles: kidney exchanges, ride-sharing pools, network revenue management (a flight itinerary uses seats on several legs), assemble-to-order production, and online bin packing. Units arrive over time; some can wait in a queue, some must be used on arrival or lost, and some are an inventory…
Indefinite Linear-Quadratic Partially Observed Mean-Field Game: With a Relaxed Compensator, the Decentralized Strategies Form an O(1/√N)-Nash EquilibriumResearch Paper
Mean-field games model a large population of agents in which each agent's dynamics and cost depend on the others only through population averages. In the linear-quadratic (LQ) case the agents' states follow linear stochastic differential equations and costs are quadratic, so the equilibrium can be computed from Riccati equations. A standard way to use the…
Strategy-Proof Multidimensional Mechanism Design: A Strategy-Proof, Agent-Sovereign Mechanism That Sells Every Object Is Anonymous If and Only If It Is EfficientResearch Paper
When a seller has several different indivisible objects and buyers value bundles additively, the simplest selling procedure is to run one sealed-bid second-price auction per object. The New Zealand government sold cellular management rights tenders this way in 1990 (Remark 3 of Basu–Mukherjee, citing Mueller). Basu and Mukherjee ask which normative axioms…
Dynamic Pricing with Point Redemption: the optimal price lies strictly between the one-period blackout price and the reimbursement rateResearch Paper
Hotels, airlines and retailers increasingly let customers pay with loyalty points from a third-party program: a consumer either pays the cash price p or redeems a fixed number q of points, and for every reward sale the seller receives a reimbursementR from the point issuer. A seller with limited inventory and a finite selling season must then set its cash…
A 0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming: SNSCO Takes Full Newton Steps and Converges Locally Superlinearly or QuadraticallyResearch Paper
A chance constrained program minimizes a cost while requiring a random constraint to hold with high probability. It models decisions under uncertainty in energy systems, finance, and process and water-quality engineering. Replacing the probability by an empirical frequency over N samples gives the sample average approximation, whose constraint counts the…
Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems: Under Dual Quadratic Growth, the Expected Dual Gap of RCD Contracts at Rate 1 − σ/(m(σ+1))Research Paper
Many problems in signal processing, machine learning and computational geometry ask for a point that minimizes a simple objective over an intersection of convex sets, where projecting onto each single set is easy and projecting onto the intersection is not. The classical instance is the best approximation problem: project a point onto X1∩⋯∩Xm.…
A Test Score-Based Approach to Stochastic Submodular Optimization: Selecting the Top k Items by Replication Test Score Gives a (1 − 1/e)/(5 − 1/e)-Approximation Under Extended Diminishing ReturnsResearch Paper
Many selection problems ask for a team of k items out of n candidates whose individual performances are random and whose joint value is not additive: a team of contributors where only the best submission counts, a slate of content topics where a user clicks if at least one topic appeals, a portfolio of research projects where the strongest result dominates.…
Mean-Variance Portfolio Selection with Dynamic Targets for Expected Terminal Wealth: Closed-Form Equilibrium Strategies for the Three Targets, Each Unique in Its ClassResearch Paper
Mean-variance analysis is the standard model of portfolio choice: an investor fixes a target for expected wealth and minimizes the variance of wealth. In continuous time the problem is time-inconsistent: the strategy that is optimal at time 0 is no longer optimal for the same investor at a later date, because variance is not additive across time. Dynamic…
Quantile Markov Decision Processes: Backward Dynamic Programming over State and Quantile Level Computes the Optimal Quantile of the Cumulative RewardResearch Paper
A classical Markov decision process (MDP) chooses a policy that maximizes the expected cumulative reward. In many applications the expectation is the wrong summary: a clinician choosing when to start a treatment, or an investor facing ruin, cares about the bad outcomes, and two policies with equal means can have very different lower tails. A natural…
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps: The de Klerk–Sotirov SDP Has Integrality Gap at Least z for Every z ∈ ℕResearch Paper
The metric traveling salesman problem (TSP) asks for a shortest tour through n cities whose pairwise costs are symmetric and satisfy the triangle inequality. The best-known guarantees for it come from relaxations: Christofides' 3/2-approximation is analysed against the subtour-elimination linear program (Held–Karp), and the integrality gap of that LP is…
Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems: Discrete Gradient Descent Finds the Best Dock Allocation at Every Dock-Move DistanceResearch Paper
Bike-sharing systems such as New York's Citi Bike place bikes in docks at fixed stations. Over a day, demand pushes bikes away from some stations and toward others, and customers who find no bike, or no empty dock to return one, leave dissatisfied. Operators rebalance bikes by truck overnight, but the number of docks at each station is a strategic decision…
Assigning and Scheduling Generalized Malleable Jobs Under Subadditive or Submodular Processing Speeds: Fractionally Subadditive Speeds Make Any Assignment Well-Structured Within Load Factor 2e/(e−1)Research Paper
In malleable scheduling a job may be processed on several machines at once, the machines of its set working on it in unison. Parallel computing, project scheduling with teams, and data-centre workloads all have this shape. The classical model gives every job a processing time that depends only on the number of machines it receives, and assumes the monotone…
State-Dependent Estimation of Delay Distributions in Fork-Join Networks: An Exact Recursion for the Joint Laplace–Stieltjes Transform of the Tagged Customer's Sojourn TimesResearch Paper
Service systems increasingly tell arriving customers how long they will wait. Emergency departments, call centres and repair shops publish delay announcements, and an announcement is only useful if it reflects the state of the system at the moment the customer arrives. For a single queue the state-dependent delay distribution is classical. Many real…
Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation: Under i.i.d. Noise the p-th Moment Error Is ≲ √(p Tr Σε/n) + ‖ε‖∞(p/n^{3/4} + p²/n)Research Paper
Linear stochastic approximation (LSA) solves a linear system Aˉθ=bˉ when only noisy observations of the matrix and of the right-hand side are available. It is the linear core of temporal-difference learning with linear function approximation, of stochastic gradient descent on least squares, and of many online estimation…
Persuasion in Networks: Public Signals and Cores: Algorithm 1 applied to an optimal solution of the convex program (OPT) yields an optimal double-interval public signaling mechanismResearch Paper
An information designer who knows a payoff-relevant state, and who cannot pay or coerce anyone, can still shape behavior by committing in advance to what is disclosed. This is Bayesian persuasion (Kamenica and Gentzkow, 2011). Candogan studies the case of many receivers in a social network, who act on a common public signal and whose actions are strategic…
The Competition Complexity of Dynamic Pricing: For ε > 0, m ≥ ϕ(ε)n Buyers Give (1 + ε)Aₘ(F) ≥ Mₙ(F) for Every F, Asymptotically Tight, with ϕ(ε) = Θ(log log 1/ε)Research Paper
A seller with one item faces buyers whose values are drawn i.i.d. from a distribution F. The welfare-optimal mechanism is an auction: it allocates to the highest bidder and achieves Mn(F), the expected maximum of n values. Dynamic pricing, which offers the item to the buyers one at a time at prices that may depend on the remaining number of buyers, is…
Labelling algorithms for paired-domination problems in block and interval graphs: Linear-time minimum paired domination in interval graphsResearch Paper
A dominating set chooses locations that collectively cover a network: every location outside the chosen set must be adjacent to a chosen location. Paired domination adds a backup requirement. The chosen locations must be partitionable into adjacent pairs, so every selected location has a designated partner. Minimizing the number of selected locations…
Many combinatorial optimization problems ask for a maximum-weight set that is "independent" in two different senses at once: a bipartite matching is a set of edges that uses each left node at most once and each right node at most once; a branching in a digraph is a forest that enters each node at most once. Each of these is a common independent set of two…
Stochastic Linear Programming: Models, Theory, and Computation XII: aggregating a stagewise independent multistage program gives a lower bound that refining never decreasesTextbook
A multi-stage stochastic linear program chooses decisions over T stages while a random process unfolds, each decision depending only on what has been observed so far. Such problems arise in planning under uncertainty, from production and energy systems to asset-liability management. With a non-discrete distribution the unknowns are functions, and the…
Stochastic Linear Programming: Models, Theory, and Computation XIII: Boole–Bonferroni bounds on the probability of a union from two binomial momentsTextbook
The joint distribution function of a random vector is the quantity that a joint probability constraint P(ξ≤x)≥α asks for. In dimension r it is an r-dimensional integral, and for most distributions no exact formula is available. The one- and two-dimensional marginals are usually much easier to compute, so stochastic programming algorithms…
Combinatorial Optimization (Cook et al.) XI: The Subtour Bound Equals the Optimal Held–Karp Bound (corrected: loopless)Textbook
The traveling salesman problem (TSP) asks for a cheapest circuit through every node of a graph with edge costs. No polynomial-time algorithm is known, and exact codes for large instances depend on strong lower bounds to prune their search. Two lower bounds dominate the classical literature. The first is the subtour bound, the optimal value of the linear…
Stochastic Linear Programming: Models, Theory, and Computation X: multiple simple recourse reduces to simple recourse with a mixed distributionTextbook
In a two-stage stochastic linear program, a simple recourse constraint penalizes the gap between a first-stage quantity z (for example a production level tTx) and a random demand ξ~ at constant unit costs: a surplus z>ξ~ costs β per unit and a shortage z<ξ~ costs α per unit. Its expected cost has a closed form in the…
Stochastic Linear Programming: Models, Theory, and Computation III: separate chance constraints under a multivariate normal distribution are convex for levels at least one halfTextbook
A linear constraint ηTx≥ξ whose coefficients η and right-hand side ξ are random cannot be required to hold for every realization without becoming either infeasible or very conservative. The chance-constrained (probabilistic) approach of Charnes and Cooper asks instead that it hold with a prescribed probability α. Whether the…
Stochastic Linear Programming: Models, Theory, and Computation V: integrated chance constraints with a finite discrete distribution define polyhedraTextbook
A probability constraint in a stochastic linear program asks that a random linear inequality hold with high probability. It counts every violation the same, however large, and the feasible set it defines is in general not convex, as Klein Haneveld's examples show (Klein Haneveld 1986). Integrated chance constraints replace the probability of a shortfall…