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.
Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies IV: Sufficient Conditions for Logarithmic Regret with a Known Incumbent PriceResearch Paper
A seller who does not know how demand responds to price must learn the demand curve from its own sales while also earning revenue. This is the learn-and-earn problem of dynamic pricing. Every price it charges both earns and informs, and a policy that only earns can stop learning. Keskin and Zeevi (Operations Research 62(5), 2014) study the problem for a…
Project Scheduling with Time Windows and Scarce Resources I: A Time-Feasible Schedule Exists iff the Project Network Has No Cycle of Positive LengthTextbook
Project scheduling assigns start times to the activities of a project subject to constraints between them. The classical critical path method (CPM) of Kelley and Walker (1959) and the program evaluation and review technique (PERT) allow only minimum time lags: activity j may start no earlier than a given time after activity i starts. Practice also needs maxi…
An Analysis of Bid-Price Controls for Network Revenue Management II: Bid-Price Controls Are Not Optimal in GeneralResearch Paper
Airlines, hotels and other capacity-constrained sellers decide, request by request, whether to sell a unit of a perishable resource now or hold it for a more valuable request later. In an airline network an itinerary uses seats on several flight legs at once, so the decision couples the legs. Bid-price controls are a widely used practical answer: each leg…
Understanding and Using Linear Programming V: The Primal–Dual Central Path and the Self-Dual EmbeddingTextbook
Interior point methods solve linear programs in a number of iterations polynomial in the input size, and in practice they compete with the simplex method on large instances. Their modern form goes back to Karmarkar's projective algorithm (Karmarkar 1984); the primal–dual path-following variant analysed in textbooks follows a curve, the central path, defined…
An Analysis of Bid-Price Controls for Network Revenue Management I: The Fixed-Bid-Price Heuristic Is Asymptotically OptimalResearch Paper
Airlines, hotels and rental-car firms sell a fixed, perishable capacity to customers who arrive over time and pay different prices. In an airline network, one ticket for an origin–destination itinerary consumes seats on several flight legs at once, so accepting a cheap connecting passenger today can displace a more valuable request tomorrow on any of those…
Understanding and Using Linear Programming I: Integral Bipartite Matchings, Total Unimodularity and König's TheoremTextbook
Many combinatorial optimization problems are integer programs: linear objectives and linear constraints, with the extra requirement that the variables be integers. Dropping that requirement gives the LP relaxation, which is solvable efficiently but in general only bounds the integer optimum. For a small but important class of problems the relaxation loses…
Fundamentals of Queueing Theory VII: The Geometric Arrival-Point Law of the G/M/1 QueueTextbook
Most queueing models with a closed-form answer assume Poisson arrivals. In practice the times between arrivals are often far from exponential: scheduled appointments, batch releases from an upstream process, or arrivals timed by a machine cycle. The G/M/1 queue keeps the service side exponential and makes no assumption about the arrival stream beyond…
Fundamentals of Queueing Theory VI: The Pollaczek–Khintchine Transform for the M/G/1 QueueTextbook
The M/G/1 queue is the single-server queue with Poisson arrivals and an arbitrary service-time distribution. It is the first queueing model beyond the birth–death family in which exact formulas survive. It is also the model a practitioner reaches for when service times are measured and visibly not exponential: repair times, transmission times of…
Fundamentals of Queueing Theory V: Closed Jackson Networks and the Mean-Value RecursionTextbook
Networks of queues model systems in which a job visits several service stations in turn: jobs in a computer system alternating between CPU and disks, machines cycling between operation and repair, parts routed through a job shop. In a closed network no job enters or leaves; a fixed population of N customers circulates among k nodes. Closed networks are the…
Fundamentals of Queueing Theory IV: The Stationary Distribution of the M/M/1 Retrial QueueTextbook
In many service systems a customer who finds every server busy does not join a queue. A caller who hears a busy signal hangs up and redials later; a request rejected by a saturated server is resent after a timeout; an aircraft that cannot land circles and tries again. These retrial queues are the subject of a substantial literature in telephone traffic…
Fundamentals of Queueing Theory III: The Transient M/M/1 Queue via Modified Bessel FunctionsTextbook
Steady-state formulas describe a queue that has been running forever. Many practical questions are about a queue that has not: a call centre just after opening, a server just after a reset, a system under a burst of load. For these, the relevant quantity is the transient distributionpn(t)=Pr{N(t)=n} of the number N(t) in the system at a finite time …
On the Choice-Based Linear Programming Model for Network Revenue Management III: Under MNL, Offering the Top-Ranked Products Solves the Offer-Set ProblemResearch Paper
Airlines, hotels and rail operators sell many products (itinerary–fare combinations) that share scarce capacity. When customers choose among whatever is on offer, the seller's lever is the offer set: the subset of products made available at each moment. Choice-based network revenue management, as set up by Liu and van Ryzin (2008), optimizes over offer sets…
Fundamentals of Queueing Theory II: Erlang's Formulas and the Halfin–Whitt Square-Root Staffing LawTextbook
Every call center, hospital ward, cloud server pool and telephone exchange that is sized by formula is sized by one of a handful of explicit expressions from Markovian queueing theory. The two oldest are A. K. Erlang's: the Erlang-B (loss) formula of 1917, which gives the fraction of calls lost when c trunks carry an offered load of r erlangs, and the Erlang…
Fundamentals of Queueing Theory I: Foster's Criterion for Positive RecurrenceTextbook
Almost every model in queueing theory is analysed through a Markov chain. The number of customers in an M/M/c queue is a continuous-time birth–death chain; the number left behind by departing customers of an M/G/1 queue is a discrete-parameter chain on {0,1,2,…} (the imbedded Markov chain); networks of queues are chains on vectors of queue lengths.…
An Introduction to the Theory of Mechanism Design XI: Optimal Sequential Screening by Option ContractsTextbook
Many sales are contracted before the buyer knows what the good is worth to her. An airline sells a ticket months before the trip, a hotel sells a refundable or non-refundable room before the traveller's plans are settled, and a supplier signs a capacity contract before demand is realised. At the time of contracting the buyer holds some private information…
An Introduction to the Theory of Mechanism Design X: Robust Mechanism Design — Belief Revelation on Finite Type SpacesTextbook
Classical Bayesian mechanism design assumes that the designer knows the agents' beliefs about each other: typically a commonly known prior over independent private values. Wilson's critique (1987) observed that mechanisms tuned to such a prior can depend on details that no designer knows, and a literature on robust mechanism design replaced the fixed prior…
An Introduction to the Theory of Mechanism Design IX: Monotone Direct Mechanisms Are Dictatorial (Gibbard–Satterthwaite)Textbook
Voting rules, committee procedures and any other method that turns individual rankings into one collective choice face the same question: can the rule be designed so that no participant ever gains by misreporting their ranking? The Gibbard–Satterthwaite theorem (Gibbard, 1973; Satterthwaite, 1975) answers no. When at least three alternatives can be chosen…
An Introduction to the Theory of Mechanism Design VII: Crémer–McLean Full Surplus Extraction with Correlated TypesTextbook
Bayesian mechanism design asks which collective decisions and payments a designer can implement when every agent holds private information, the type, drawn from a commonly known prior. Most of the classical theory (Myerson's optimal auction, the Myerson–Satterthwaite impossibility, the public goods results) assumes that types are independent. Once types are…
Toward Robust Revenue Management: Competitive Analysis of Online Booking III: Bid-Price Controls Are Optimally 1/(1 − ln r)-CompetitiveResearch Paper
Revenue management decides how much of a fixed, perishable capacity (airline seats, hotel rooms) to sell, and at what price. Classical single-leg models assume a known demand distribution for each fare class and maximise expected revenue. Many carriers instead use bid-price controls: a request is accepted when its fare is at least a threshold ("bid price")…
Toward Robust Revenue Management: Competitive Analysis of Online Booking II: Nested Protection Levels Are Optimally 1/Δ-Competitive for m FaresResearch Paper
Airlines, hotels and rental firms sell a fixed stock of capacity to customers who arrive over time and pay different prices for the same unit. Classical revenue management, from Littlewood's two-fare rule (1972) to the dynamic programs of Brumelle and McGill (1993), decides how much capacity to hold back for high-fare customers from a demand forecast. When…
Toward Robust Revenue Management: Competitive Analysis of Online Booking I: The Nested Two-Fare Protection Level Is Optimally b(r)-CompetitiveResearch Paper
Revenue management decides how much of a fixed, perishable capacity (airline seats, hotel rooms) to sell at each price. The classical single-leg models, starting with Littlewood's two-fare rule (1972) and continued by Belobaba, Brumelle–McGill and Lee–Hersh, assume that demand for each fare class follows a known probability distribution and maximise…
Bellman's Dynamic Programming VIII: Multi-Stage Games, Games of Survival and the Extended Min-Max TheoremTextbook
Chapter X of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) carries the functional-equation method of the earlier chapters from one-player decision processes to two-player zero-sum games that are played over many stages. At each stage the two players make simultaneous…
Bellman's Dynamic Programming VII: Convergence of Discrete Approximations in the Calculus of VariationsTextbook
Chapter IX of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) recasts problems of the calculus of variations with constraints as dynamic programming processes. A variational problem with an inequality constraint on the control, such as 0≤y≤x, is awkward for the…
Linear Programming: Foundations and Extensions VI: The Homogeneous Self-Dual Predictor–Corrector MethodTextbook
Interior-point methods are the standard polynomial-time algorithms for linear programming, and the path-following method that practitioners implement (Chapter 18 of Vanderbei's Linear Programming: Foundations and Extensions) comes without a complete convergence proof. Chapter 22 of the same book presents a closely related algorithm for which a complete…
Minimization Methods for Non-Differentiable Functions IV: Linear Convergence of the Subgradient Method under Level-Set Shape ConditionsTextbook
The subgradient method minimizes a convex function f on Rn that need not be differentiable, by stepping against an arbitrary subgradient. With stepsizes hk→0, ∑hk=∞ it converges (Shor, Theorem 2.2), but in general only slowly: no stepsize rule that ignores the structure of f gives a geometric rate. Section 2.3 of N. Z. Shor's Minim…