Ski-rental fractional LP: primal covering and dual packing programs
DefinitionPrimalDualOnline_SkiRentalLPThis bundle sets up the linear-programming model of the ski-rental problem used throughout Chapter 3 of the source.
An instance is a pair : the purchase price and the number of ski days. Renting costs per day. The primal program is a covering program with one buy variable and one rent variable per day, and objective
subject to covering constraints , which say each day is either rented or covered by the purchase. The dual is a packing program with one variable per day, objective , and constraints together with the single budget constraint .
Two primal feasible regions are recorded, because the source states two. The prose relaxation lets and every range over the unit interval,
whereas the printed figure imposes nonnegativity only,
The first is taken as the canonical fractional program of this mission; the second is retained exactly as printed. These are different regions: the second admits points such as , that the first excludes. PrimalFeasible_of_box records the inclusion, which runs in one direction only; the converse is false and is not asserted. The two attained-value sets are named and respectively, and what the mission's two lp_optimum_* theorems establish about them is narrower than equivalence: each has least attained value .
Finally names the cost of the better of the two offline strategies — buy at once, or rent on every day.
These declarations are the vocabulary in which every other statement of the mission is phrased, and the covering/packing pair is the smallest instance of the general framework later missions in this series will build.
Source correspondence.
- What the thesis states: Figure 3.1 (p. 18) with its printed constraints, and the prose relaxation on p. 17.
- What this bundle defines: both regions, the two objectives, the two value sets, and the offline optimum, as total definitions.
- Introduced by the formalization: the decision to carry both regions rather than silently pick one; the names; and the structural lemma recording the inclusion.
Formalization Note. Costs are real numbers; the day index runs over Fin k, so day of the source is index . is a bare definition and asserts no optimality property of its own — that really is the least attained objective value is the content of two separate theorems, one per region.
import Mathlib.Tactic
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
namespace PrimalDualOnline.SkiRental
/-!
The ski-rental linear program of Chapter 3.
A ski-rental instance is given by the purchase price `B` (renting costs `1` per day)
and the number `k` of ski days. The primal (covering) program has one variable `x`
for the buy decision and one variable `z j` for renting on day `j`; the dual (packing)
program has one variable `y j` per day.
Two primal feasible regions are recorded, because the source states two. The prose
(p. 17) relaxes the integer program by letting `x` and each `z j` range over `[0,1]`;
Figure 3.1 (p. 18) prints only the nonnegativity constraints `x ≥ 0`, `z j ≥ 0`.
`PrimalFeasibleBox` is the canonical fractional program of the prose, and
`PrimalFeasible` is the region exactly as printed in the figure. The two regions are
**not** the same: dropping the upper bounds admits points such as `x = 5`, `z = 0` that the
bounded region excludes, and `PrimalFeasible_of_box` records that the inclusion runs one way
only. What the mission's two `lp_optimum_*` theorems establish is narrower: each region has
least attained objective value `min B k`.
-/
/-- Canonical fractional primal (covering) feasibility, following the relaxation
described on p. 17: `x` and every `z j` lie in `[0,1]`, and `x + z j ≥ 1` for each
day `j`, so every day is either rented or covered by the purchase. -/
def PrimalFeasibleBox (k : ℕ) (x : ℝ) (z : Fin k → ℝ) : Prop :=
(0 ≤ x ∧ x ≤ 1) ∧ (∀ j : Fin k, 0 ≤ z j ∧ z j ≤ 1) ∧ ∀ j : Fin k, 1 ≤ x + z j
/-- Primal (covering) feasibility exactly as printed in Figure 3.1, p. 18: the
covering constraints together with nonnegativity only, and no upper bounds. -/
def PrimalFeasible (k : ℕ) (x : ℝ) (z : Fin k → ℝ) : Prop :=
0 ≤ x ∧ (∀ j : Fin k, 0 ≤ z j) ∧ ∀ j : Fin k, 1 ≤ x + z j
/-- Every solution of the canonical `[0,1]`-bounded program is a solution of the
program as printed in Figure 3.1: dropping the upper bounds enlarges the region. -/
theorem PrimalFeasible_of_box {k : ℕ} {x : ℝ} {z : Fin k → ℝ}
(h : PrimalFeasibleBox k x z) : PrimalFeasible k x z :=
⟨h.1.1, fun j => (h.2.1 j).1, h.2.2⟩
/-- The primal (covering) objective of Figure 3.1: `B * x + ∑ j, z j`. -/
def primalCost (B : ℝ) {k : ℕ} (x : ℝ) (z : Fin k → ℝ) : ℝ :=
B * x + ∑ j : Fin k, z j
/-- Feasibility for the dual (packing) program of Figure 3.1: `0 ≤ y j ≤ 1` for every
day `j`, and `∑ j, y j ≤ B`. -/
def DualFeasible (B : ℝ) (k : ℕ) (y : Fin k → ℝ) : Prop :=
(∀ j : Fin k, 0 ≤ y j ∧ y j ≤ 1) ∧ (∑ j : Fin k, y j) ≤ B
/-- The dual (packing) objective of Figure 3.1: `∑ j, y j`. -/
def dualValue {k : ℕ} (y : Fin k → ℝ) : ℝ :=
∑ j : Fin k, y j
/-- The set of objective values attained by the canonical fractional primal program. -/
def primalValues (B : ℝ) (k : ℕ) : Set ℝ :=
{v : ℝ | ∃ (x : ℝ) (z : Fin k → ℝ), PrimalFeasibleBox k x z ∧ primalCost B x z = v}
/-- The set of objective values attained by the primal program as printed in
Figure 3.1, with nonnegativity constraints only. -/
def primalValuesNonneg (B : ℝ) (k : ℕ) : Set ℝ :=
{v : ℝ | ∃ (x : ℝ) (z : Fin k → ℝ), PrimalFeasible k x z ∧ primalCost B x z = v}
/-- The offline optimum of a ski-rental instance with purchase price `B` and `k` ski
days: either buy on the first day, at cost `B`, or rent on all `k` days, at cost `k`. -/
noncomputable def offlineOpt (B : ℝ) (k : ℕ) : ℝ := min B (k : ℝ)
end PrimalDualOnline.SkiRental
Read-back
What the Lean code literally says, in plain math · claude-opus-5
All nine declarations live in the namespace PrimalDualOnline.SkiRental. Throughout, denotes the finite index type , which is empty when , and every sum ranges over all of and equals when .
1. PrimalFeasibleBox — a definition of a proposition (nothing is proved about it), taking three explicit arguments: a natural number , a real , and a family . It asserts
All inequalities are non-strict. No parameter appears, so the predicate is independent of any cost coefficient, and there is no constraint tying different indices to one another. For both quantified clauses are vacuous and the predicate reduces to ; it is satisfiable for every (e.g. , , or , ).
2. PrimalFeasible — a second proposition with the same three explicit arguments, asserting
This differs from the previous in exactly two respects: it omits and omits every . The lower bounds and covering inequalities are literally the same in both. Hence PrimalFeasibleBox is the strictly more restrictive of the two: every pair satisfying the box predicate satisfies this one, while pairs such as , satisfy this one and not the box predicate. For it reduces to .
3. PrimalFeasible_of_box — a theorem with three implicit arguments (inferred from the hypothesis) and one explicit hypothesis asserting the box predicate; its conclusion is the plain predicate. The proof is the direct term that forgets the two upper-bound components. The implication runs only in the direction box plain; the converse is not asserted anywhere in this bundle, and no equivalence is claimed. The hypothesis is satisfiable for every , so the statement is never vacuous; for it reduces to " implies ".
4. primalCost — a real-valued definition with an explicit real , an implicit natural , an explicit real , and an explicit family (from which is inferred). Its value is . No feasibility hypothesis is imposed: it is defined for arbitrary reals including negative values, and may therefore be negative. When the sum is empty and the value is exactly . The coefficient multiplies only; each enters with coefficient .
5. DualFeasible — a proposition with three explicit arguments, a real , a natural , and a family . It asserts
All inequalities are non-strict and the sum is bounded above by . Here is explicit, unlike in primalCost and dualValue. When the per-index clause is vacuous and the condition collapses to , so for and no is dual feasible. More generally, since each forces , the predicate is unsatisfiable for every negative , at every ; for it is satisfied at least by the all-zero family.
6. dualValue — a real-valued definition with one implicit and one explicit , given by . It takes no parameter and imposes no hypothesis: need not be dual feasible, its entries may be negative or exceed , and the value may be any real. It is the same expression that DualFeasible bounds above by , but stated here as a free-standing quantity. For the value is .
7. primalValues — a set of reals with two explicit arguments and :
The existentials are plain , not ; there is no minimality, no infimum, and no claim that this set has a least element. Because the box predicate is satisfiable for every and every , the set is never empty, including for and negative . When it is exactly , the closed segment between and .
8. primalValuesNonneg — a set of reals differing from the previous only in which feasibility predicate it uses. Since box-feasibility implies the weaker predicate (declaration 3), every witness for primalValues is also a witness here, so primalValues primalValuesNonneg; the reverse containment is not stated, and no relation between the two sets is asserted anywhere in this bundle. The set is never empty. When it is — the nonnegative reals if , if , the nonpositive reals if ; for and any the unbounded makes the set contain arbitrarily negative values. Despite the name, the nonnegativity restricted here is that of the variables, not of the values .
9. offlineOpt — a noncomputable real-valued definition with explicit and : , with coerced into . This is a bare minimum of two numbers; it is not defined as an infimum or minimum over either value set, and no theorem in this bundle connects it to any of them. Its value is whenever — in particular for every negative , where the result is negative — and otherwise. When it is , which is for and for .
Confirmed by the mission captain (proposal self-audit).