Capacity consumed by a positive fractional product
ProvedConstrNestedLogit.Space.capacity_consumedassortment-optimizationknapsacknested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose an optimal LP solution of (10) has exactly one fractional product and this product has positive utility. The rounded assortment then satisfies
This expresses the paper's capacity-consumption step without assuming it for a zero-utility fractional product, which an optimal but non-greedy LP solution may contain.
Formalization Note The positive-utility condition is explicit because it is needed for the stated capacity conclusion.
Preamble
import Mathlib import Definitions.Def_ConstrNestedLogit_Space_Model
Formal statement
namespace ConstrNestedLogit.Space
/-- A positive-utility fractional product can occur only when the LP fills the capacity. -/
theorem capacity_consumed {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(I : NestedLogitVariants.LP.Instance ι n)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (i : ι)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ k, 0 < I.v i k)
(hw : ∀ k, 0 < w i k) (hwc : ∀ k, w i k ≤ c i)
(u : ℝ) (hu : 0 ≤ u) (x : Fin n → ℝ)
(hx : spaceLPOptimal I w c i u x) (j : Fin n)
(hj : oneFractional x j) (hpositive : 0 < utility I i u j) :
c i ≤ (∑ k ∈ rounded x, w i k) + w i j := by sorry
end ConstrNestedLogit.Space
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. 21, §5.2 paragraph before the ratio inequality
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.