Ski-rental online algorithms: deterministic cost and fractional primal-dual variables
DefinitionPrimalDualOnline_SkiRentalAlgThis bundle defines the two online algorithms of Chapter 3 for the ski-rental problem with purchase price and ski days.
Day-index convention. The source numbers ski days ; Lean indices start at . The translation this development commits to is: is the state after updates, so is the state before any ski day. On source day (for ) the algorithm observes the state current before that day's update, sets , updates to , and sets on an active day. Lean index therefore corresponds to source day : algZ B c j is the source's and algY B c j is the source's , both computed from the pre-update state algX B c j. Consequently algZ B c j is exactly the source's — one rental variable per ski day — and the source's identity reads here as algZ B c j algX B c j on an active day.
The deterministic algorithm rents on each of the first days and buys on day , at the cost the source displays:
The fractional primal-dual algorithm maintains , initially . On each new day, while it sets the rent variable to the shortfall, raises , and sets that day's dual variable to ; once has reached it does nothing further:
The rate parameter is . Finally is the primal objective after days, and the dual objective. Note the deliberate index asymmetry: the buy term is read at index , while the sums run over .
The guard is part of the algorithm, not an informal aside: without it the cost would keep growing after day .
Source correspondence.
- What the thesis states: the deterministic algorithm in prose (p. 18) with its accounting, and the fractional algorithm as numbered steps 1 and 2(a)–2(c) (p. 18).
- What this bundle defines: those two algorithms as total functions, with the day-index translation above made explicit.
- Introduced by the formalization: the names
algCost,algDualValue,cOpt; the decision to carry the guard in the definition rather than as a side condition; and the choice of .
Formalization Note. The purchase price is a natural number, because the source uses as a price, a day index, and the exponent in ; it is coerced into inside cost expressions. Real division is total, so every reciprocal degenerates to when or , and the constant is itself ; every theorem mentioning these definitions therefore carries the hypothesis .
import Definitions.Def_PrimalDualOnline_SkiRentalLP
import Mathlib.Tactic
namespace PrimalDualOnline.SkiRental
/-!
The two online algorithms of Chapter 3.
## Day-index convention (stated once, used everywhere)
The source numbers ski days `1, …, k`; Lean indices start at `0`. The translation this
development commits to is:
* `algX B c j` is the state **after `j` updates**. So `algX B c 0 = 0` is the state before any
ski day has been processed, and `algX B c k` is the state after exactly `k` days.
* On source day `j` (for `1 ≤ j ≤ k`) the algorithm observes the state `x_{j-1}` that is
current *before* that day's update, sets `z_j := 1 - x_{j-1}`, then updates `x_{j-1}` to
`x_j`, and sets `y_j := 1` if the day is active.
* Therefore **Lean index `j` corresponds to source day `j+1`**: `algZ B c j` is the source's
`z_{j+1}` and `algY B c j` is the source's `y_{j+1}`, both computed from the pre-update
state `algX B c j`.
* Consequently `∑ j : Fin k, algZ B c j` is exactly the source's `z_1 + ⋯ + z_k`: `k` daily
rental variables, one per ski day, and the source's `z_j = 1 - x_{j-1}` reads here as
`algZ B c j = 1 - algX B c j` on an active day.
`detCost` is the cost of the deterministic algorithm, under the accounting the source
displays. `algX`, `algZ`, `algY` are the primal and dual variables maintained by the
fractional primal-dual algorithm.
-/
/-- The cost of the deterministic algorithm of Chapter 3 on an instance with purchase
price `B` and `k` ski days, under the `2 * B` accounting the source displays for `k ≥ B`.
See the mission notes on the wording ambiguity in the source's description of this
algorithm. -/
def detCost (B k : ℕ) : ℝ := if k < B then (k : ℝ) else 2 * (B : ℝ)
/-- The value of the primal buy-variable `x` maintained by the fractional primal-dual
algorithm after `j` updates, for purchase price `B` and parameter `c`. The update
`x ← x * (1 + 1/B) + 1/(c*B)` is applied only while the current value satisfies `x < 1`. -/
noncomputable def algX (B : ℕ) (c : ℝ) : ℕ → ℝ
| 0 => 0
| j + 1 =>
let x := algX B c j
if x < 1 then x * (1 + 1 / (B : ℝ)) + 1 / (c * (B : ℝ)) else x
/-- The primal rent-variable the fractional algorithm sets on source day `j + 1`, computed
from the pre-update state `algX B c j`: it is `1 - algX B c j` while that state is below `1`,
and `0` afterwards. -/
noncomputable def algZ (B : ℕ) (c : ℝ) (j : ℕ) : ℝ :=
if algX B c j < 1 then 1 - algX B c j else 0
/-- The dual variable the fractional algorithm sets on source day `j + 1`, computed from the
same pre-update state `algX B c j`: it is `1` while that state is below `1`, and `0`
afterwards. -/
noncomputable def algY (B : ℕ) (c : ℝ) (j : ℕ) : ℝ :=
if algX B c j < 1 then 1 else 0
/-- The parameter `c = (1 + 1/B)^B - 1` chosen in Chapter 3, for which the fractional
algorithm's buy-variable equals `1` after `B` updates. -/
noncomputable def cOpt (B : ℕ) : ℝ := (1 + 1 / (B : ℝ)) ^ B - 1
/-- The primal cost of the fractional algorithm's solution after `k` ski days: the buy
variable in its state after `k` updates, together with the `k` daily rent variables of
source days `1, …, k`. -/
noncomputable def algCost (B : ℕ) (c : ℝ) (k : ℕ) : ℝ :=
primalCost (B : ℝ) (algX B c k) (fun j : Fin k => algZ B c (j : ℕ))
/-- The dual objective value the fractional algorithm has accumulated after `k` ski days,
summing the dual variables of source days `1, …, k`. -/
noncomputable def algDualValue (B : ℕ) (c : ℝ) (k : ℕ) : ℝ :=
dualValue (fun j : Fin k => algY B c (j : ℕ))
end PrimalDualOnline.SkiRental
Read-back
What the Lean code literally says, in plain math · claude-opus-5
detCost is a function of two natural-number arguments and , both explicit, returning a real number, defined by the case split
where the test is a comparison of natural numbers and both branch values are real images of the naturals and . The definition mentions none of the other declarations in this bundle, and there is no reference to any algorithm, cost model, or parameter . Degenerate cases: when the guard is false for every , so the value is for all ; when and the guard holds and the value is ; for the value is regardless of how much larger is.
algX takes a natural and a real and defines a sequence by primitive recursion:
The guard tests the previous value — it does not test , nor the index, nor any quantity derived from or alone. Both occurrences of are the real cast. The sequence is frozen from the first index at which the value is . Division is total, with , which produces the following degenerate behaviour. If , the recursion reads whenever , giving for all . If (any ), the recursion reads on that branch, again giving for all , so the sequence never leaves the branch . If and , the additive term is negative, so from the terms are strictly decreasing, remain forever, and the second branch is never taken. At index the value is unconditionally, with no case split.
algZ takes , , and a natural index , and returns
where . Both the guard and the subtracted quantity consult algX at exactly the same index as algZ's own argument — not at and not at . In particular is determined by , hence for every and . If is negative (as happens when and ) the first branch gives . If or then for all and hence for all .
algY takes , , , and returns if and if . As with algZ, the guard consults algX at the same index , not at . The only possible values are and ; the value does not depend on how far below the quantity lies. Since , for every and . If , or , or with , then for all and hence for all .
cOpt takes a natural and returns , where inside the parentheses is the real cast and the exponent is the same natural . This is a closed-form expression in alone: it is not defined in terms of algX, algZ, algY, or detCost, no property relating it to them is asserted here, and the name carries no claim of optimality. Degenerate case: with total division, gives .
algCost takes , , and applies the previously defined primal cost functional with budget parameter (cast to ), its "" slot filled by and its vector slot by the family over the indices . Unfolding:
There are therefore exactly summands, running over indices through inclusive (index itself does not contribute a summand), while algX in the first term is evaluated at index — one past the largest index occurring in the sum. Degenerate cases: for the sum is empty and the whole expression reduces to ; for the first term is and, since for all , the total is ; for likewise the total is ; for with every summand is and the first term is negative.
algDualValue takes , , and applies the dual value functional — the sum of the entries — to the family over the same indices. Unfolding:
There are exactly summands, over indices through inclusive; the parameter appears only through its role inside algY (hence inside algX) and not as an outside coefficient, and algX is evaluated only at indices — the index does not occur anywhere in this expression, in contrast to algCost. For the value is ; if , or , or with , every summand is and the value is . In general the value is a natural number between and viewed in .
Confirmed by the mission captain (proposal self-audit).