Lemma 9, p. 23 — with γ_i ≤ 1, problems (3) and (10) have the same optimal solutions
ProvedNestedLogitVariants.PartialCompetitive.lemma_9assortment-optimizationknapsacklinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a nested logit instance in which every dissimilarity parameter satisfies (the no-purchase weights are arbitrary), with at least one product per nest. Let (3) be the linear program
and (10) the program in which the second family of constraints is replaced by . Then for every and ,
Lemma 9 is what lets §5 work with knapsack problems in place of the assortment problem.
Formalization Note An optimal solution is a feasible pair whose is no larger than that of any feasible pair. The hypothesis (the paper's is nonempty) is added: with no products, all and , problem (3) has no optimal solution while is optimal for (10).
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
Formal statement
namespace NestedLogitVariants.PartialCompetitive
/-- Lemma 9, p. 23: with dissimilarity parameters at most one, problems (3) and (10) have the same
optimal solutions. -/
theorem lemma_9 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (hn : 0 < n) (x : ℝ) (y : ι → ℝ) :
LP3Optimal I x y ↔ LP10Optimal I x y := 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. 23, Lemma 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.