Appendix A.1, p. 41 — an optimal solution of (4) over the nested-by-revenue assortments has ŷ ≥ 0 and x̂ ≥ 0
ProvedNestedLogitVariants.Synergistic.xh_yh_nonnegassortment-optimizationnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management
Let be an optimal solution of the linear program (4) in which the candidate collections are the nested-by-revenue assortments , , , for an instance with fully-captured nests. Then
These sign conditions are used throughout the proof of Theorem 7 to enlarge the coefficients of and .
Formalization Note The standing assumptions are those of the model (see the Model definition) and of §4: every nest is fully captured, , and for some nest (p. 16). An optimal solution of (4) is a feasible pair whose is no larger than that of any feasible pair. The page argues from the first constraint of (4), which needs ; no hypothesis on is added, because when optimality forces .
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_Synergistic_Model
Formal statement
namespace NestedLogitVariants.Synergistic
/-- Appendix A.1, p. 41: an optimal solution `(x̂, ŷ)` of (4) over the nested-by-revenue assortments
`{N_{ij} : j ∈ N_+}` has `ŷ_i ≥ 0` for every nest and `x̂ ≥ 0`. -/
theorem xh_yh_nonneg {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing) (hfc : ∀ i, I.vnp i = 0) (hsyn : ∃ i, 1 < I.γ i)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (fun _ => {S | ∃ j ≤ n, S = nbr n j}) xh yh) :
(∀ i, 0 ≤ yh i) ∧ 0 ≤ xh := by sorry
end NestedLogitVariants.Synergistic
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. 41, Appendix A.1 (first paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.