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.
Reset Sequences for Monotonic Automata: Breadth-First Search over Cyclic Intervals Finds a Minimum-Length Reset Sequence in O(kn²) TimeResearch Paper
A parts orienter takes a mechanical part in an unknown orientation and delivers it in a known one. In the pan handler studied by Natarajan, the part slides on a tray; each tilt of the tray moves it to a new resting orientation, determined by the tilt and the current orientation. Choosing a sequence of tilts that brings the part to the same final orientation…
The Minimum Latency Problem: A Polynomial-Time 144-Approximation Algorithm for the Minimum Latency Tour in Metric SpacesResearch Paper
A repairman, a delivery vehicle or a disk head starts at a depot and must visit n locations. The traveling salesman problem (TSP) minimizes the time at which the last visit ends. In many service settings what matters is instead the time each customer waits: the minimum latency problem (MLT), also called the traveling repairman or deliveryman problem,…
On the Inherent Intractability of Certain Coding Problems: COSET WEIGHTS (Decoding a Binary Linear Code) and SUBSPACE WEIGHTS (a Codeword of Given Weight) Are NP-CompleteResearch Paper
A binary linear code is used on a noisy channel by transmitting codewords and correcting the errors at the receiver. If H is a parity-check matrix of the code and y is the received word, the receiver computes the syndromes=yH and must find a minimum-weight error pattern z with zH=s. A second basic question is whether a code has a codeword of a given…
Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework: Elevated-Flow-Relaxation Prices Earn an m/(m+n−1) Fraction of the Optimal State-Dependent ObjectiveResearch Paper
Bike-sharing and car-sharing systems, and ride-hailing platforms, all move a fixed fleet of units between stations. Every ride takes a unit away from its origin and leaves it at its destination, so demand that is unbalanced across stations drains some stations and floods others. Pricing is the main lever an operator has: raising the price of rides out of a…
M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System: Steepest Descent from the Center Is Optimal at Every L1 RadiusResearch Paper
Bike-sharing operators periodically move docks between stations: a station that often runs out of bikes or of open docks frustrates users, but every moved dock costs money. Freund, Henderson and Shmoys modelled this dock re-allocation problem as a separable nonlinear integer program with a budget on the number of moved docks (Freund–Henderson–Shmoys, IPCO…
Hamilton-Jacobi Equations with Semilinear Costs and State Constraints, with Applications to Large Deviations in Games: Verification Theorem for the State-Constrained Target ProblemResearch Paper
Stochastic evolutionary game dynamics model a population of N agents who occasionally revise their actions by a noisy best-response rule with noise level η>0. As η→0, the population spends long periods near Nash equilibria and occasionally transits between them; the exponential rates of these transitions, and hence which equilibrium is stochastically…
Fluctuation Theory of Continuous-Time, Skip-Free Downward Markov Chains with Applications to Branching Processes with Immigration: Fluctuation Identities for Branching Processes with ImmigrationResearch Paper
A Markov branching process with immigration (MBI) models a population in continuous time: each individual independently dies, splits or is removed at affine rates, and batches of immigrants arrive at a constant rate. Such processes appear in population biology, queueing (infinite-server systems with batch arrivals), epidemics and the analysis of branching…
Large Independent Sets in Recursive Markov Random Graphs: For Every r < 1 and ε > 0, With High Probability α(G^r_{n,p}) ≥ ((1 − r)/(2 + ε))·n/log nResearch Paper
The stability numberα(G) of a graph, the largest number of pairwise non-adjacent vertices, is one of the basic parameters of combinatorial optimization: computing it is NP-hard, and random graphs are the standard test bed for what typical instances look like. For the Erdős–Rényi–Gilbert graph Gn,p, in which every edge is present independently, the…
Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems: Dispatching to One Remembered Server, Updated by Queue-Length Messages, Is Stable for Every Vector of Server RatesResearch Paper
A central dispatcher that routes jobs to parallel servers is the basic model behind web server farms, cloud schedulers and call centers. When the servers have different speeds, and the speeds are not known to the dispatcher, two classical policies behave very differently. Random routing is cheap but unstable as soon as some server is slower than the average…
The Secretary Problem with Predictions: Learned Dynkin Is max{0.215, (1−ε)/(1+ε)}-CompetitiveResearch Paper
The secretary problem asks how to hire the best of n candidates who are interviewed one at a time in random order, when every hiring decision must be made irrevocably at the interview. It is the standard model of online selection under uncertainty, and its answer, Dynkin's rule, hires the maximum with probability 1/e (Dynkin 1963; see the survey of Ferguson…
SYN-DIGITS: A Synthetic Control Framework for Calibrated Digital Twin Simulation: Error Bound for Ridge Fit-and-Transfer on a New QuestionResearch Paper
Large language models are increasingly used as digital twins of survey respondents: a model is prompted with a persona and asked to answer the same questionnaire a human would. The appeal is cost and speed, since a new question can be "fielded" to thousands of simulated respondents in minutes. The obstacle is fidelity. Large language models exhibit…
The Fragility of Optimized Bandit Algorithms: Optimized Bandit Algorithms Have Truncated Cauchy Regret TailsResearch Paper
The stochastic multi-armed bandit is the basic model of sequential decision-making under uncertainty: in each round an algorithm chooses one of K arms, observes a random reward from that arm's distribution, and tries to play the best arm as often as possible. Since Lai and Robbins (1985) the standard of quality has been the expected regret, and an algorithm…
Improved Guarantees for the A Priori TSP: Random Sampling with Probability 1 − (1 − p)^0.663 and a 3/2-Approximate Master Tour Has Approximation Guarantee Below 3.1 on Instances with a DepotResearch Paper
In the a priori traveling salesman problem with independent activation, a tour through all customers must be fixed before it is known which customers need a visit; each customer is active independently with a known probability, and the fixed tour is afterwards cut short to the active ones. The model, introduced by Jaillet and by Bertsimas as the…
Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity: Under Geometric Mixing the Empirical Estimator Is ε-Accurate After Order dT/ε² Samples, and This Rate Is MinimaxResearch Paper
Offline reinforcement learning and off-policy evaluation start from a single logged trajectory of a controlled system. The policy that generated the log is often unknown, history-dependent and not stationary. Model-based methods first estimate the transition probabilities of the system from this log, then plan or evaluate policies in the estimated model (Aga…
Revenue Management with Repeated Customer Interactions: the myopic policy earns at least a (1 − γ) fraction of the optimal revenue under bang-per-buck heterogeneity γResearch Paper
Network revenue management studies how a platform with limited supply should allocate products to customers at given prices. Most of the literature treats each interaction as one-shot: a request arrives, is served or rejected, and leaves. Examples are the fluid models of Gallego and van Ryzin (1997) and the bid-price controls of Talluri and van Ryzin (1998).…
Distribution-Free Pricing: Knowing Only the Mean and Variance, the Price μ − k*σ Is Maximin-Optimal and Earns a Fraction ρ of the Optimal ProfitResearch Paper
A seller who posts a single price p for a product with marginal cost c earns (p−c) from every customer whose valuation is at least p. Choosing p well requires the distribution of valuations, which in practice is rarely known: a new product, a new market, or a short sales history typically yields an estimate of the mean and the spread of willingness to pay,…
Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization: The Optimal Independent Block Randomization Experiment Is Asymptotically Optimal at Rate O(√(w₁²/Σwᵢ²))Research Paper
Online platforms run randomized experiments on users who interact with each other. When the treatment of one user affects the outcome of another, comparing treated and control users is biased. A standard remedy is cluster-based randomization: users are grouped into clusters with few edges between them, and whole clusters are assigned to treatment or control…
Pricing with Samples: Posting 0.76 Times a Single Sample Earns at Least 64% of the Optimal Revenue Against Every Monotone Hazard Rate DistributionResearch Paper
A seller who knows the distribution F of a buyer's value can post the revenue-maximizing price. In practice the seller rarely knows F; often it has only a handful of past observations. Pricing with samples asks how much revenue such data can guarantee: the seller sees N independent draws from F, posts a price that depends on them, and is judged by the…
Optimal Monopoly Mechanisms with Demand Uncertainty: When All Consumers Find the Low-Demand State More Likely, State-by-State Monopoly Pricing Is an Optimal BIC and EIR MechanismResearch Paper
A monopolist selling to a large market of unit-demand consumers with a known demand curve cannot do better than posting a single price (Myerson 1981; Bulow and Roberts 1989). When the demand curve itself is uncertain, consumers' valuations are correlated through the aggregate state, and the picture changes. Crémer and McLean (1985,1988) showed that with…
Information Nudges and Self-Control: An Optimal Incentive-Compatible Information Nudge Is a Cutoff MechanismResearch Paper
Warnings about health, financial or environmental risks are among the most common policy instruments: cigarette packs carry risk statements, doctors tell patients which risk group they belong to, and retirement planners report survival probabilities. Standard decision theory says that more accurate information can only help a decision maker. That conclusion…
The Cost of Nonconvexity in Deterministic Nonsmooth Optimization: Deterministic Bisection Finds a Small Goldstein Subgradient Within an Oracle-Call Budget Set by the Nonconvexity ModulusResearch Paper
Minimizing a nonsmooth, nonconvex Lipschitz function is intractable in general, so nonsmooth optimization asks for a weaker certificate: a point near which a small convex combination of nearby subgradients exists. Such a vector is a Goldstein subgradient, a notion going back to Goldstein in the 1970s. Zhang, Lin, Jegelka, Sra and Jadbabaie (2020) gave the…
Lagrangian Inference for Ranking Problems: Asymptotic Normality of the Lagrangian Debiased EstimatorResearch Paper
Ranking from pairwise comparisons is used in sports ratings, recommendation systems, crowdsourcing and web search. The most widely used parametric model is the Bradley–Terry–Luce (BTL) model (Bradley and Terry 1952; Luce 1959), in which item k carries a score θk and item i beats item j with probability eθi/(eθi+eθj). The…
Monte Carlo Estimation of CoVaR: Asymptotic Normality and the n^(-1/3) Rate of the Batching EstimatorResearch Paper
CoVaR is the measure of systemic risk proposed by Adrian and Brunnermeier (AER 2016): the β-quantile of one institution's loss Y given that another loss X (a bank, a market index) sits exactly at its own α-quantile, its value-at-risk. Regulators and risk managers compute it from simulation models of portfolios, where the joint law of (X,Y) is available…
A Discrete Convex Min-Max Formula for Box-TDI Polyhedra: Min-Max Theorem for Separable Discrete Convex Functions over Integral Points of a Box-TDI PolyhedronResearch Paper
Minimizing a separable convex function over the integral points of a polyhedron is a recurring problem in combinatorial optimization: resource allocation, minimum-cost flows with convex costs, and the "fair" or "decreasingly minimal" integral elements studied by Frank and Murota all have this form. When the polyhedron is described by a totally unimodular…
New Constructions of Obviously Strategyproof Mechanisms: No OSP Mechanism for Scheduling Identical Jobs on Related Machines with Three-Value Domains Is Better Than √n-ApproximateResearch Paper
A mechanism is strategyproof when truth-telling is a dominant strategy for every agent. Experimental and theoretical work has found that this guarantee is fragile in practice: agents faced with a sealed-bid second-price auction often misreport, while the same agents bid truthfully in the strategically equivalent ascending clock auction. Li (Obviously…