(29), A.3 Case 2, p. 46 — if ẑ_i(ϵ) has no fractional component, 2ŷ_i ≥ (v_i0+ϵ)^γ_i [K_i(ϵ)/(v_i0+ϵ) − 2x̂]
ProvedNestedLogitVariants.PartialCompetitive.ineq_29assortment-optimizationknapsacknested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a nested logit instance with for every nest and at least one product per nest, and let be an optimal solution of the linear program (4) over the candidate collections . Fix a nest and a capacity , and suppose that no component of the greedy solution of (11) lies strictly between and . Then
This is Case 2 of the proof of Theorem 10: here the constraint of (4) for alone dominates the knapsack value.
Formalization Note As for (28), the page states (29) at a maximizer ; the statement here holds for every capacity , and the page's form equals the bracket form for . The hypothesis is the paper's nonempty .
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
Formal statement
namespace NestedLogitVariants.PartialCompetitive
/-- Inequality (29), A.3 Case 2, p. 46: if `ẑ_i(ε)` has no fractional component, then
`2 ŷ_i ≥ (v_{i0} + ε)^{γ_i} [K_i(ε)/(v_{i0} + ε) − 2 x̂]`. Stated for every `ε ≥ 0`. -/
theorem ineq_29 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (hn : 0 < n)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (candidates I) xh yh)
(i : ι) (ε : ℝ) (hε : 0 ≤ ε) (hnf : ∀ k, zhat I i ε k ∉ Set.Ioo (0 : ℝ) 1) :
(I.vnp i + ε) ^ I.γ i * (Kval I i ε / (I.vnp i + ε) - 2 * xh) ≤ 2 * yh i := 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. 46, Appendix A.3, Case 2, display (29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.