pp. 23–24 — the greedy fill ẑ_i(ϵ_i) is optimal for the continuous knapsack (11) and has at most one fractional component
ProvedNestedLogitVariants.PartialCompetitive.zhat_optimalgreedyknapsacklinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a nest of a nested logit instance (revenues ordered , weights ) and a capacity . Let be the greedy solution of the continuous knapsack problem (11): fill the capacity with the eligible products () in revenue order, each fully while it fits and the next one fractionally. Then:
- is feasible for (11): and ;
- it is optimal for (11): for every feasible ,
- at most one component lies strictly between and .
Optimality of the greedy fill identifies , and the single fractional component is what makes the case analysis of the proof of Theorem 10 possible.
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
Formal statement
namespace NestedLogitVariants.PartialCompetitive
/-- pp. 23–24: the greedy fill `ẑ_i(ε)` is feasible for (11), optimal for (11), and has at most
one fractional component. -/
theorem zhat_optimal {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(i : ι) (ε : ℝ) (hε : 0 ≤ ε) :
feas11 I i ε (zhat I i ε) ∧
(∀ z : Fin n → ℝ, feas11 I i ε z →
∑ j, I.r i j * I.v i j * z j ≤ ∑ j, I.r i j * I.v i j * zhat I i ε j) ∧
(∀ j k : Fin n, zhat I i ε j ∈ Set.Ioo (0 : ℝ) 1 → zhat I i ε k ∈ Set.Ioo (0 : ℝ) 1 →
j = k) := by sorry
end NestedLogitVariants.PartialCompetitive
Source
Davis, Gallego, Topaloglu, Assortment optimization under variants of the nested logit model, revised manuscript of June 18, 2013 (published Oper. Res. 62(2), 2014, DOI 10.1287/opre.2014.1256), pp. 23–24, the paragraph after display (11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.