Proposition 7 — under space constraints, the optimal value of LP (13) is at least Z*
ProvedConstrNestedLogit.UpperBound.proposition_7Consider the nested logit model with nests , products in each nest, no-purchase weight , preference weights , arbitrary revenues and dissimilarity parameters . For an assortment with and (with ), the expected revenue is
Under space constraints product of nest needs units of space, nest has capacity with (p. 8), the feasible assortments of nest are , and is the optimal value of problem (1), .
Let be finite sets of vectors such that every vector of is feasible for the linear programming relaxation of the knapsack problem (10) of nest , and for every some vector of is optimal for that relaxation at (the paper's ). If is an optimal solution of the linear program (13) built on these sets, then
The linear program (13) thus gives a computable upper bound on the optimal expected revenue, against which the expected revenue of any heuristic assortment can be compared instance by instance.
Formalization Note The family is any finite family with the two properties above, a generalization of the paper's interval solutions that uses exactly what the proof needs. is the revenue of a hypothesised optimal assortment Sstar of problem (1). The positivity of and of the is added; the within-nest no-purchase weights are , as in the paper's model. The paper's standing assumption (p. 8) is kept and the positivity is added; the proof needs them to make the zero vector feasible for each relaxation.
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
namespace ConstrNestedLogit.UpperBound
/-- Proposition 7 (Online Supplement A, p. 33): under space constraints, if the vectors `X i`
(the paper's `{x_i^g : g ∈ G_i}`) are feasible for the linear programming relaxation of the
knapsack problem (10) and include an optimal solution of that relaxation for every `u ≥ 0`, and
`(ẑ, ŷ)` is an optimal solution of the linear program (13), then `ẑ ≥ Z*`, where
`Z* = Π(S*_1, …, S*_m)` is the optimal expected revenue of problem (1). -/
theorem proposition_7 {ι : Type*} [Fintype ι] {n : ℕ} (I : Instance ι n)
(hvnp : ∀ i, I.vnp i = 0) (hv0 : 0 < I.v0) (hv : ∀ i j, 0 < I.v i j)
(hγ : ∀ i, 0 < I.γ i ∧ I.γ i ≤ 1)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (X : ι → Finset (Fin n → ℝ))
(hw : ∀ i j, 0 < w i j) (hwc : ∀ i j, w i j ≤ c i)
(hX : IsRelaxSolutionFamily I w c X)
(Sstar : ι → Finset (Fin n)) (hfeas : ∀ i, SpaceFeasible w c i (Sstar i))
(hopt : ∀ S : ι → Finset (Fin n), (∀ i, SpaceFeasible w c i (S i)) →
revenue I S ≤ revenue I Sstar)
(zhat : ℝ) (yhat : ι → ℝ) (hzy : LP13Optimal I X zhat yhat) :
revenue I Sstar ≤ zhat := by sorry
end ConstrNestedLogit.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.