Proof of Theorem 10, A.3, p. 45 — an optimal solution of (4) over the candidate collection has x̂ ≥ 0
ProvedNestedLogitVariants.PartialCompetitive.xh_nonnegassortment-optimizationlinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a nested logit instance with for every nest and at least one product per nest. Let be an optimal solution of the linear program (4) in which the candidate collection of nest is . Then
This sign is what lets the proof of Theorem 10 compare the right sides of (4) at different capacities.
Formalization Note The hypothesis (the paper's is nonempty) is the setting of the page's argument, which uses nonempty singleton assortments.
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
Formal statement
namespace NestedLogitVariants.PartialCompetitive
/-- Proof of Theorem 10 (A.3, p. 45): an optimal solution `(x̂, ŷ)` of (4) over the candidate
collections `{Ŝ_i(ε) : ε ∈ [0, ∞]} ∪ {{j} : j ∈ N}` has `x̂ ≥ 0`. -/
theorem xh_nonneg {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (hn : 0 < n)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (candidates I) xh yh) :
0 ≤ xh := 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), p. 45, Appendix A.3 (proof of Theorem 10), first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.