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.
Disjunctive Programming XVI: Unions of Upper Monotone Polytopes and PolymatroidsTextbook
This mission is the sixteenth and last of the Disjunctive Programming series, and its goal
theorem is the book's own closing result. The chapter's arc closes a loop opened at the very
start of the book: Theorem 2.1 (02a-convex-hull) gave the convex hull of a union of polyhedra
in the same space via lifting; this chapter's Theorem 13.13 (not drafted in this…
Disjunctive Programming XV: Dominants of Polytopes and Upper SeparationTextbook
Many real-world disjunctive models are not unions of polyhedra in a single shared space, but
unions of polyhedra in different spaces linked by a logical implication: some action affecting
one set of entities has consequences for another. Balas's treatment of such models (§17 of the
book, following [17]) reduces to understanding a single auxiliary object…
Disjunctive Programming XIV: Disjunctive Cuts from the V-Polyhedral RepresentationTextbook
The lift-and-project cut-generating LP (CGLP) is the workhorse of the book's cutting-plane
machinery, but its number of variables grows with q, the number of terms in the disjunction —
a real computational cost for disjunctions with many terms. An alternative representation of the
same disjunctive hull, built from vertices and extreme rays rather than from…
Disjunctive Programming XIII: Monoidal Cut Strengthening and the Gomory Mixed-Integer CutTextbook
The Gomory mixed-integer (GMI) cut is the single most widely deployed cutting plane in practical
mixed-integer programming: every commercial solver generates it, from a simplex tableau row,
essentially for free. Yet the GMI cut is not the strongest cut derivable from the same row: once a
subset of the variables is known to be integer-constrained, that…
Disjunctive Programming XI: The Cut-Generating LP Under a Ray NormalizationTextbook
Lift-and-project (L&P) cuts strengthen the linear relaxation of a mixed 0-1 program by
separating a fractional point from the convex hull of a disjunction such as xk≤0∨xk≥1. Generating an optimal L&P cut means solving the cut-generating linear program
(CGLP), a linear program lifted to a space with one new pair of variables per constraint of…
Disjunctive Programming X: Solving the Cut-Generating LP on the Simplex TableauTextbook
Chapter 8 established an exact correspondence between lift-and-project cuts and simple disjunctive
cuts, but its practical payoff is what this chapter develops: the cut-generating LP (CGLP)_k
never needs to be formulated or solved on its own. Every pivot of (CGLP)_k can instead be
mimicked directly on the much smaller simplex tableau of the original LP…
Disjunctive Programming IX: The Correspondence Between Lift-and-Project Cuts and Simple Disjunctive CutsTextbook
Chapter 6 built lift-and-project (L&P) cuts from a cut-generating LP, and Chapter 7 surveyed
alternative nonlinear constructions reaching the same integer hull. This chapter asks a sharper
question: how do L&P cuts relate, coefficient for coefficient, to older, more classical cutting
planes — simple disjunctive cuts and mixed integer Gomory cuts, derived…
Chapter 2's convex-hull machinery gives an exact, finitely-generated linear description of a
disjunctive set's convex hull, but for a mixed 0-1 program with p binary variables that
description lives in a space with roughly pn auxiliary variables — one full lift per
disjunction. This chapter surveys the alternative nonlinear higher-dimensional constructions…
Disjunctive Programming VII: Lift-and-Project Cuts for Mixed 0-1 ProgramsTextbook
A mixed 0-1 program's feasible region is a disjunctive set built from the split disjunctions
xj≤0∨xj≥1, one per binary variable — a special case general enough that Chapter
2's convex-hull machinery applies directly, yet structured enough to produce closed-form cutting
planes efficiently. The resulting lift-and-project (L&P) cuts, generated…
Proximité et dualité dans un espace hilbertien II: Proximal Maps Are the Nonexpansive Subgradient Selections of Convex FunctionsResearch Paper
The proximal map of a convex function is the basic building block of proximal-point, forward–backward, Douglas–Rachford and ADMM methods, which are used throughout large-scale convex optimization, signal processing and operator splitting. All of these methods treat proxg as a nonexpansive operator and use the fact that it is a gradient. The…
Adversarially Robust Generalization Requires More Data 1: A Robust-Error Lower Bound in the Gaussian ModelResearch Paper
Classifiers trained to high standard accuracy on image benchmarks can be made to fail by perturbations of the input that are small in the ℓ∞ norm (Szegedy et al., 2014; Goodfellow et al., 2015). Adversarial training reaches high robust accuracy on the training set, but on CIFAR10 the robust accuracy on held-out data is much lower than on the…
Proximité et dualité dans un espace hilbertien I: Moreau's Decomposition into Proximal Points of a Function and Its DualResearch Paper
Proximal maps are the basic building block of first-order methods for nonsmooth convex optimization: the proximal point algorithm, forward–backward splitting (ISTA/FISTA), Douglas–Rachford splitting and ADMM all proceed by evaluating maps of the form z↦argminu[21∥u−z∥2+f(u)]. The notion and its name come from…
A Branch and Bound Algorithm for the Generalized Assignment Problem: The Knapsack Penalty Bound Equals the Lagrangean Bound at Second-Smallest CostsResearch Paper
The generalized assignment problem (GAP) asks for the cheapest way to give each of n tasks to exactly one of m agents when every agent has a limited amount of a resource and different agents consume different amounts of it for the same task. It models assigning jobs to machines or computers, software tasks to programmers, commercials to time slots, and…
Disjunctive Programming II: The Convex Hull of a Disjunctive Set via Lifting and ProjectionTextbook
Convexity is what makes optimization tractable: a linear program's feasible region is convex, and
this single fact underwrites the simplex method, LP duality, and everything built on top of them.
Integer and disjunctive programs have no such luck — their feasible regions are unions of
polyhedra, and a union of convex sets is generally not convex. If the conv…
Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms: Langevin Diffusion Limit of the First CoordinateResearch Paper
The random walk Metropolis algorithm is one of the most widely used Markov chain Monte Carlo methods for sampling from a density known up to a constant. Its one tuning parameter is the variance of the Gaussian proposal. If the variance is too small, the chain accepts almost every move but barely moves. If it is too large, it proposes long jumps that are…
Cones of Matrices and Set-Functions and 0–1 Optimization II: One Round of N on the Stable Set Polytope Gives Exactly the Odd Hole ConstraintsResearch Paper
The stable set problem (vertex packing) asks for a largest set of pairwise non-adjacent nodes of a graph. It is NP-hard, and its polyhedral study, the description of the stable set polytopeSTAB(G) by linear inequalities, is one of the most studied topics of polyhedral combinatorics. Classes of valid inequalities (clique, odd hole, odd antihole,…
Strategic Capacity Rationing to Induce Early Purchases: Rationing Is Optimal When the Valuation Bound Reaches U_c, Low-Price-Only OtherwiseResearch Paper
Retailers of seasonal goods sell at a full price first and mark down later. Customers who know this can wait for the markdown, and a firm that always has stock left for the markdown teaches them to wait. One remedy is to stock less than the low-price market would absorb, so that a customer who waits risks not getting the good at all. Liu and van Ryzin (Manag…
Advance Demand Information, Price Discrimination, and Preorder Strategies: When Preorder Profit Increases with Demand CorrelationResearch Paper
Firms that sell new products (consoles, books, films) often take preorders before release. A preorder serves two purposes at once. It lets the firm charge early adopters a different price from later buyers, a form of price discrimination, and the number of preorders is advance demand information: an early signal of how large regular-season demand will be.…
Pattern Search Algorithms for Bound Constrained Minimization: Generalized Pattern Search Drives the Projected Stationarity Measure to ZeroResearch Paper
Pattern search methods minimize a function f:Rn→R by comparing values of f at points of a structured set of trial points, without evaluating or approximating derivatives. Coordinate search and the method of Hooke and Jeeves (Hooke–Jeeves 1961) are the classical members of the family. Such methods remain in use when derivatives are…
Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 2: Closed Form of the Entropy-Constrained Worst-Case VaRResearch Paper
Value-at-Risk (VaR) is the loss level that a portfolio exceeds with probability at most ε. It is the standard risk measure of banking regulation, and its classical computation assumes Gaussian returns: for a Gaussian return vector with mean x^ and covariance Γ it equals −Φ−1(ε)w⊤Γw−x^⊤w, where …
Strong Convergence of a Proximal-Type Algorithm in a Banach Space: The Algorithm Converges Strongly to the Generalized Projection of x0 onto the Zeros of a Maximal Monotone OperatorResearch Paper
Many problems in optimization and variational analysis reduce to finding a zero of a maximal monotone operatorT: minimizers of a proper convex lower semicontinuous function are the zeros of its subdifferential, and saddle points and solutions of variational inequalities are zeros of associated monotone operators. The classical tool is Rockafellar's proximal…
Robust Solutions to Uncertain Semidefinite Programs III: Quadratic Growth and Uniqueness of the Robust SDP SolutionResearch Paper
A semidefinite program (SDP) minimizes a linear objective cTx subject to a linear matrix inequality F(x)=F0+∑ixiFi⪰0. When the data Fi are uncertain, El Ghaoui, Oustry and Lebret (SIAM J. Optim. 9(1), 1998) proposed to optimize against the worst case over a norm-bounded family of perturbations: the robust SDP. Their Theorem 3.1 shows…
Integrating Replenishment Decisions with Advance Demand Information I: The Myopic Order-Up-To Level Is Optimal When Observed Demand Beyond the Protection Period Is LargeResearch Paper
Many firms learn part of future demand before it has to be served: customers place orders days or weeks ahead of the date they need the goods, or commit to delivery dates in contracts. Advance demand information of this kind reduces the uncertainty the inventory manager has to protect against, and the question is how replenishment decisions should use it.…
Calibrated Learning and Correlated Equilibrium III: A Randomized Forecast Calibrated against Every OpponentResearch Paper
A forecaster who announces "70% chance of rain" is calibrated if, among the days on which that number was announced, it rained on about 70% of them. Dawid (The well-calibrated Bayesian, JASA 1982) proposed calibration as the minimal requirement of an honest probability forecaster. Oakes (Self-calibrating priors do not exist, JASA 1985) showed that no…
Robust Solutions to Least-Squares Problems with Uncertain Data III: Structured Robust Least Squares Is Solved Exactly by a Semidefinite ProgramResearch Paper
Least squares fits a model Ax≈b as if the data (A,b) were exact. In practice they are measured, rounded or estimated, and the least-squares solution can be very sensitive to such errors. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to treat the errors as deterministic, unknown but bounded, and to choose x minimizing the wor…