§2, p. 12 — (4) relaxes (3), so its optimal value satisfies x̂ ≤ Z*
ProvedNestedLogitVariants.LP.lp4_le_optimalassortment-optimizationlinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be candidate collections, let be an optimal solution of the linear program (4), and let be an optimal assortment of problem (2). Then
- every feasible solution of (3) is feasible for (4), and
Problem (4) imposes only a subset of the constraints of (3), so its optimal value cannot exceed that of (3), which is .
Formalization Note The standing assumptions are those of §1: , , revenues ordered , together with the disclosed pins (the page allows zero-weight padding products, under which Proposition 2 of the paper fails), (revenues are prices) and (the page has ; its convention when fails at ).
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model
Formal statement
namespace NestedLogitVariants.LP
/-- §2, p. 12: problem (4) is a relaxation of problem (3) (every feasible point of (3) is feasible for
(4)), so the optimal value `x̂` of (4) satisfies `Z* = x* ≥ x̂`. -/
theorem lp4_le_optimal {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(A : ι → Set (Finset (Fin n))) (xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I A xh yh)
(Sstar : ι → Finset (Fin n)) (hSopt : IsOptimal I Sstar) :
(∀ x y, LP3Feasible I x y → LP4Feasible I A x y) ∧ xh ≤ revenue I Sstar := by sorry
end NestedLogitVariants.LP
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. 12, §2, paragraph "We observe that problem (4) includes only a subset of the constraints in problem (3) …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.