A.4, p. 46 — the optimal x̂ of the restricted LP (4) with the collection {N^k_ij} ∪ {{j}} is nonnegative
ProvedNestedLogitVariants.General.xh_nonnegassortment-optimizationlinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a nested logit instance satisfying the standing assumptions, with (the standing assumption of §6). Let be an optimal solution of the linear program (4) in which the candidate collection of every nest is . Then
This is the first step of the proof of Theorem 11; the cases of that proof multiply constraints by and use its sign.
Formalization Note The page states this for the optimal solution of (4) and gives no further hypotheses; none is added here (in particular no : for an optimal solution of (4) does not exist when there is a nest).
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_General_Model import Definitions.Def_NestedLogitVariants_General_NestedPR
Formal statement
namespace NestedLogitVariants.General
/-- Appendix A.4 (p. 46): an optimal solution `(x̂, ŷ)` of (4) with the candidate collections
`{N^k_ij} ∪ {{j}}` has `x̂ ≥ 0`. -/
theorem xh_nonneg {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hsyn : ∃ i, 1 < I.γ i)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (candidatesPR I) xh yh) :
0 ≤ xh := by sorry
end NestedLogitVariants.General
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. 46, Appendix A.4, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.