Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Ski-rental fractional LP: primal covering and dual packing programs

Definition
PrimalDualOnline_SkiRentalLP

by moutei · Sep 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysislinear-programmingonline-algorithmsprimal-dualski-rental

This bundle sets up the linear-programming model of the ski-rental problem used throughout Chapter 3 of the source.

An instance is a pair (B,k)(B, k)(B,k): the purchase price BBB and the number k≥0k \ge 0k≥0 of ski days. Renting costs 111 per day. The primal program is a covering program with one buy variable xxx and one rent variable zjz_jzj​ per day, and objective

primalCost(B,x,z)  =  Bx+∑j=0k−1zj,\mathrm{primalCost}(B, x, z) \;=\; B x + \sum_{j=0}^{k-1} z_j ,primalCost(B,x,z)=Bx+j=0∑k−1​zj​,

subject to covering constraints x+zj≥1x + z_j \ge 1x+zj​≥1, which say each day is either rented or covered by the purchase. The dual is a packing program with one variable yjy_jyj​ per day, objective dualValue(y)=∑j<kyj\mathrm{dualValue}(y) = \sum_{j<k} y_jdualValue(y)=∑j<k​yj​, and constraints 0≤yj≤10 \le y_j \le 10≤yj​≤1 together with the single budget constraint ∑jyj≤B\sum_j y_j \le B∑j​yj​≤B.

Two primal feasible regions are recorded, because the source states two. The prose relaxation lets xxx and every zjz_jzj​ range over the unit interval,

PrimalFeasibleBox:0≤x≤1,0≤zj≤1,x+zj≥1,\mathrm{PrimalFeasibleBox}: \qquad 0 \le x \le 1, \qquad 0 \le z_j \le 1, \qquad x + z_j \ge 1 ,PrimalFeasibleBox:0≤x≤1,0≤zj​≤1,x+zj​≥1,

whereas the printed figure imposes nonnegativity only,

PrimalFeasible:0≤x,0≤zj,x+zj≥1.\mathrm{PrimalFeasible}: \qquad 0 \le x, \qquad 0 \le z_j, \qquad x + z_j \ge 1 .PrimalFeasible:0≤x,0≤zj​,x+zj​≥1.

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 x=5x = 5x=5, z≡0z \equiv 0z≡0 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 primalValues\mathrm{primalValues}primalValues and primalValuesNonneg\mathrm{primalValuesNonneg}primalValuesNonneg respectively, and what the mission's two lp_optimum_* theorems establish about them is narrower than equivalence: each has least attained value min⁡(B,k)\min(B,k)min(B,k).

Finally offlineOpt(B,k)=min⁡(B,k)\mathrm{offlineOpt}(B,k) = \min(B, k)offlineOpt(B,k)=min(B,k) 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 j+1j+1j+1 of the source is index jjj. offlineOpt\mathrm{offlineOpt}offlineOpt is a bare definition and asserts no optimality property of its own — that min⁡(B,k)\min(B,k)min(B,k) really is the least attained objective value is the content of two separate theorems, one per region.

Definition code
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
Source
Niv Buchbinder, "Designing Competitive Online Algorithms via a Primal-Dual Approach", PhD thesis, Tel Aviv University, 2008, https://www.tau.ac.il/~nivb/download/phd-thsis.pdf, Chapter 3, pp. 17-18 (PDF pp. 33-34): Figure 3.1 (the fractional ski problem and its dual), together with the relaxation described in the paragraph preceding it on p. 17.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

All nine declarations live in the namespace PrimalDualOnline.SkiRental. Throughout, Fin k\mathrm{Fin}\,kFink denotes the finite index type {0,1,…,k−1}\{0,1,\dots,k-1\}{0,1,…,k−1}, which is empty when k=0k = 0k=0, and every sum ranges over all of Fin k\mathrm{Fin}\,kFink and equals 000 when k=0k = 0k=0.

1. PrimalFeasibleBox — a definition of a proposition (nothing is proved about it), taking three explicit arguments: a natural number kkk, a real xxx, and a family z:Fin k→Rz : \mathrm{Fin}\,k \to \mathbb{R}z:Fink→R. It asserts

(0≤x∧x≤1)∧(∀j, 0≤zj∧zj≤1)∧(∀j, 1≤x+zj).(0 \le x \wedge x \le 1) \wedge \bigl(\forall j,\ 0 \le z_j \wedge z_j \le 1\bigr) \wedge \bigl(\forall j,\ 1 \le x + z_j\bigr).(0≤x∧x≤1)∧(∀j, 0≤zj​∧zj​≤1)∧(∀j, 1≤x+zj​).

All inequalities are non-strict. No parameter BBB appears, so the predicate is independent of any cost coefficient, and there is no constraint tying different indices to one another. For k=0k = 0k=0 both quantified clauses are vacuous and the predicate reduces to 0≤x≤10 \le x \le 10≤x≤1; it is satisfiable for every kkk (e.g. x=1x = 1x=1, z≡0z \equiv 0z≡0, or x=0x = 0x=0, z≡1z \equiv 1z≡1).

2. PrimalFeasible — a second proposition with the same three explicit arguments, asserting

0≤x∧(∀j, 0≤zj)∧(∀j, 1≤x+zj).0 \le x \wedge \bigl(\forall j,\ 0 \le z_j\bigr) \wedge \bigl(\forall j,\ 1 \le x + z_j\bigr).0≤x∧(∀j, 0≤zj​)∧(∀j, 1≤x+zj​).

This differs from the previous in exactly two respects: it omits x≤1x \le 1x≤1 and omits every zj≤1z_j \le 1zj​≤1. 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 x=5x = 5x=5, zj=0z_j = 0zj​=0 satisfy this one and not the box predicate. For k=0k = 0k=0 it reduces to 0≤x0 \le x0≤x.

3. PrimalFeasible_of_box — a theorem with three implicit arguments k,x,zk, x, zk,x,z (inferred from the hypothesis) and one explicit hypothesis hhh 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 ⇒\Rightarrow⇒ plain; the converse is not asserted anywhere in this bundle, and no equivalence is claimed. The hypothesis is satisfiable for every kkk, so the statement is never vacuous; for k=0k = 0k=0 it reduces to "0≤x≤10 \le x \le 10≤x≤1 implies 0≤x0 \le x0≤x".

4. primalCost — a real-valued definition with an explicit real BBB, an implicit natural kkk, an explicit real xxx, and an explicit family zzz (from which kkk is inferred). Its value is B⋅x+∑jzjB \cdot x + \sum_{j} z_jB⋅x+∑j​zj​. No feasibility hypothesis is imposed: it is defined for arbitrary reals including negative values, and may therefore be negative. When k=0k = 0k=0 the sum is empty and the value is exactly B⋅xB \cdot xB⋅x. The coefficient BBB multiplies xxx only; each zjz_jzj​ enters with coefficient 111.

5. DualFeasible — a proposition with three explicit arguments, a real BBB, a natural kkk, and a family yyy. It asserts

(∀j, 0≤yj∧yj≤1)∧∑jyj≤B.\bigl(\forall j,\ 0 \le y_j \wedge y_j \le 1\bigr) \wedge \sum_{j} y_j \le B .(∀j, 0≤yj​∧yj​≤1)∧j∑​yj​≤B.

All inequalities are non-strict and the sum is bounded above by BBB. Here kkk is explicit, unlike in primalCost and dualValue. When k=0k = 0k=0 the per-index clause is vacuous and the condition collapses to 0≤B0 \le B0≤B, so for k=0k = 0k=0 and B<0B < 0B<0 no yyy is dual feasible. More generally, since each yj≥0y_j \ge 0yj​≥0 forces ∑jyj≥0\sum_j y_j \ge 0∑j​yj​≥0, the predicate is unsatisfiable for every negative BBB, at every kkk; for B≥0B \ge 0B≥0 it is satisfied at least by the all-zero family.

6. dualValue — a real-valued definition with one implicit kkk and one explicit yyy, given by ∑jyj\sum_{j} y_j∑j​yj​. It takes no parameter BBB and imposes no hypothesis: yyy need not be dual feasible, its entries may be negative or exceed 111, and the value may be any real. It is the same expression that DualFeasible bounds above by BBB, but stated here as a free-standing quantity. For k=0k = 0k=0 the value is 000.

7. primalValues — a set of reals with two explicit arguments BBB and kkk:

{ v  ∣  ∃ x, ∃ z, PrimalFeasibleBox(k,x,z)∧Bx+∑jzj=v }.\Bigl\{\, v \;\Bigm|\; \exists\, x,\ \exists\, z,\ \mathrm{PrimalFeasibleBox}(k,x,z) \wedge B x + \textstyle\sum_{j} z_j = v \,\Bigr\}.{v​∃x, ∃z, PrimalFeasibleBox(k,x,z)∧Bx+∑j​zj​=v}.

The existentials are plain ∃\exists∃, not ∃!\exists!∃!; there is no minimality, no infimum, and no claim that this set has a least element. Because the box predicate is satisfiable for every kkk and every BBB, the set is never empty, including for k=0k = 0k=0 and negative BBB. When k=0k = 0k=0 it is exactly {Bx:0≤x≤1}\{B x : 0 \le x \le 1\}{Bx:0≤x≤1}, the closed segment between 000 and BBB.

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 ⊆\subseteq⊆ 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 k=0k = 0k=0 it is {Bx:x≥0}\{B x : x \ge 0\}{Bx:x≥0} — the nonnegative reals if B>0B > 0B>0, {0}\{0\}{0} if B=0B = 0B=0, the nonpositive reals if B<0B < 0B<0; for B<0B < 0B<0 and any kkk the unbounded xxx makes the set contain arbitrarily negative values. Despite the name, the nonnegativity restricted here is that of the variables, not of the values vvv.

9. offlineOpt — a noncomputable real-valued definition with explicit BBB and kkk: min⁡(B,k)\min(B, k)min(B,k), with kkk coerced into R\mathbb{R}R. 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 BBB whenever B≤kB \le kB≤k — in particular for every negative BBB, where the result is negative — and kkk otherwise. When k=0k = 0k=0 it is min⁡(B,0)\min(B,0)min(B,0), which is 000 for B≥0B \ge 0B≥0 and BBB for B<0B < 0B<0.

Human review
  • Endorsed by Shuze Chen · Sep 16, 2026

  • Endorsed by moutei · Sep 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me