Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7 — under space constraints, the optimal value of LP (13) is at least Z*

Proved
ConstrNestedLogit.UpperBound.proposition_7

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

assortment-optimizationlinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1upper-bound

Consider the nested logit model with nests MMM, products N={1,…,n}N = \{1, \dots, n\}N={1,…,n} in each nest, no-purchase weight v0>0v_0 > 0v0​>0, preference weights vij>0v_{ij} > 0vij​>0, arbitrary revenues rijr_{ij}rij​ and dissimilarity parameters γi∈(0,1]\gamma_i \in (0, 1]γi​∈(0,1]. For an assortment (S1,…,Sm)(S_1, \dots, S_m)(S1​,…,Sm​) with Vi(Si)=∑j∈SivijV_i(S_i) = \sum_{j \in S_i} v_{ij}Vi​(Si​)=∑j∈Si​​vij​ and Ri(Si)=∑j∈Sivijrij/Vi(Si)R_i(S_i) = \sum_{j\in S_i} v_{ij} r_{ij} / V_i(S_i)Ri​(Si​)=∑j∈Si​​vij​rij​/Vi​(Si​) (with Ri(0ˉ)=0R_i(\bar 0) = 0Ri​(0ˉ)=0), the expected revenue is

Π(S1,…,Sm)=∑i∈MVi(Si)γiRi(Si)v0+∑i∈MVi(Si)γi.\Pi(S_1, \dots, S_m) = \frac{\sum_{i \in M} V_i(S_i)^{\gamma_i} R_i(S_i)}{v_0 + \sum_{i \in M} V_i(S_i)^{\gamma_i}}.Π(S1​,…,Sm​)=v0​+∑i∈M​Vi​(Si​)γi​∑i∈M​Vi​(Si​)γi​Ri​(Si​)​.

Under space constraints product jjj of nest iii needs wij>0w_{ij} > 0wij​>0 units of space, nest iii has capacity cic_ici​ with wij≤ciw_{ij} \le c_iwij​≤ci​ (p. 8), the feasible assortments of nest iii are Ci={Si:∑j∈Siwij≤ci}\mathcal C_i = \{S_i : \sum_{j \in S_i} w_{ij} \le c_i\}Ci​={Si​:∑j∈Si​​wij​≤ci​}, and Z∗=Π(S1∗,…,Sm∗)Z^* = \Pi(S_1^*, \dots, S_m^*)Z∗=Π(S1∗​,…,Sm∗​) is the optimal value of problem (1), max⁡{Π(S1,…,Sm):Si∈Ci ∀i}\max\{\Pi(S_1,\dots,S_m) : S_i \in \mathcal C_i\ \forall i\}max{Π(S1​,…,Sm​):Si​∈Ci​ ∀i}.

Let {Xi:i∈M}\{X_i : i \in M\}{Xi​:i∈M} be finite sets of vectors such that every vector of XiX_iXi​ is feasible for the linear programming relaxation of the knapsack problem (10) of nest iii, and for every u≥0u \ge 0u≥0 some vector of XiX_iXi​ is optimal for that relaxation at uuu (the paper's {xig:g∈Gi}\{x_i^g : g \in \mathcal G_i\}{xig​:g∈Gi​}). If (z^,y^)(\hat z, \hat y)(z^,y^​) is an optimal solution of the linear program (13) built on these sets, then

z^  ≥  Z∗.\hat z \;\ge\; Z^*.z^≥Z∗.

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 XiX_iXi​ is any finite family with the two properties above, a generalization of the paper's interval solutions xigx_i^gxig​ that uses exactly what the proof needs. Z∗Z^*Z∗ is the revenue of a hypothesised optimal assortment Sstar of problem (1). The positivity of v0v_0v0​ and of the vijv_{ij}vij​ is added; the within-nest no-purchase weights are 000, as in the paper's model. The paper's standing assumption wij≤ciw_{ij} \le c_iwij​≤ci​ (p. 8) is kept and the positivity wij>0w_{ij} > 0wij​>0 is added; the proof needs them to make the zero vector feasible for each relaxation.

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

/-- 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
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. 33, Online Supplement A, Proposition 7
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me