Online Supplement A, p. 34 — at û the zero vector is not optimal for the relaxation of (10)
ProvedConstrNestedLogit.UpperBound.relax_opt_ne_zeroassortment-optimizationknapsacknested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the nested logit model with preference weights , arbitrary revenues and no within-nest no-purchase weight, and fix a nest with . Let be a nonempty assortment satisfying the space constraint and let be a real number with . Then the zero vector is not an optimal solution of the linear programming relaxation of the knapsack problem (10) of nest at
In the proof of Proposition 7 this rules out the case , so the chain of inequalities for a nonzero relaxation optimum always applies.
Formalization Note The positivity is an added hypothesis. The paper's argument passes through " for all "; the statement records the conclusion of that argument, that is not optimal.
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_General_Model import Definitions.Def_NestedLogitVariants_General_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_LP13 open NestedLogitVariants.General
Formal statement
namespace ConstrNestedLogit.UpperBound
/-- Online Supplement A, proof of Proposition 7 (p. 34): let `S` be a nonempty assortment
satisfying the space constraint of nest `i` with `R_i(S) > z`, and put
`û = γ_i z + (1 − γ_i) R_i(S)` with `γ_i > 0`. Then the zero vector is not an optimal solution of
the linear programming relaxation of the knapsack problem (10) at `u = û`. -/
theorem relax_opt_ne_zero {ι : Type*} {n : ℕ} (I : Instance ι n)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ i j, 0 < I.v i j)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (i : ι) (hγ : 0 < I.γ i)
(S : Finset (Fin n)) (hS : SpaceFeasible w c i S) (hSne : S.Nonempty)
(z : ℝ) (hRz : z < R I i S) :
¬ RelaxOptimal I w c i (I.γ i * z + (1 - I.γ i) * R I i S) 0 := by sorry
end ConstrNestedLogit.UpperBound
Source
Gallego & Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science (2014), DOI 10.1287/mnsc.2014.1931; authors' manuscript of Sept. 11, 2013, p. 34, Online Supplement A, proof of Proposition 7 (case x_i^g = 0̄)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.