Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Online Supplement A, p. 33 — every feasible solution of (13) has ŷ_i ≥ 0

Proved
ConstrNestedLogit.UpperBound.y_nonneg

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

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

Consider the nested logit model with preference weights vij>0v_{ij} > 0vij​>0, arbitrary revenues rijr_{ij}rij​, dissimilarity parameters γi>0\gamma_i > 0γi​>0 and no within-nest no-purchase weight. Let wij>0w_{ij} > 0wij​>0 be space requirements and cic_ici​ capacities with wij≤ciw_{ij} \le c_iwij​≤ci​ for every product (the paper's standing assumption, p. 8), and 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. If (z,y)(z, y)(z,y) is a feasible solution of the linear program (13) built on these sets, then

yi≥0for all i∈M.y_i \ge 0 \qquad \text{for all } i \in M.yi​≥0for all i∈M.

This is the first step of the proof of Proposition 7: it settles the claim yi≥Vi(Si∗)γi(Ri(Si∗)−z)y_i \ge V_i(S_i^*)^{\gamma_i}(R_i(S_i^*) - z)yi​≥Vi​(Si∗​)γi​(Ri​(Si∗​)−z) whenever the right side is nonpositive.

Formalization Note The fact that the zero vector belongs to XiX_iXi​ is not assumed; it follows from the two properties of the family. The statement is for every feasible (z,y)(z, y)(z,y); the paper applies it to an optimal one. The positivity vij>0v_{ij} > 0vij​>0 is added (the paper's weights are exponentials of utilities, p. 10, but positivity is not restated), and so is vi0=0v_{i0} = 0vi0​=0, which is the paper's model. The paper's assumption wij≤ciw_{ij} \le c_iwij​≤ci​ (p. 8) is kept, and wij>0w_{ij} > 0wij​>0 is added; together they make the zero vector feasible for every relaxation (without them, e.g. wij<0w_{ij} < 0wij​<0 and ci<0c_i < 0ci​<0, the conclusion fails).

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. 33): if the vectors `X 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`, then every feasible solution `(z, y)` of the linear program
(13) has `y_i ≥ 0` for every nest `i`. -/
theorem y_nonneg {ι : Type*} [Fintype ι] {n : ℕ} (I : Instance ι n)
    (hvnp : ∀ i, I.vnp i = 0) (hv : ∀ i j, 0 < I.v i j) (hγ : ∀ i, 0 < I.γ i)
    (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) (z : ℝ) (y : ι → ℝ) (hzy : LP13Feasible I X z y) :
    ∀ i, 0 ≤ y i := 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, proof of 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