p. 16 — filling the knapsack with the largest positive utilities solves the unit-weight knapsack problem (9)
ProvedConstrNestedLogit.Card.greedy_solves_9assortment-optimizationgreedyknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a nest , a cardinality limit and , and write for the utility of product . Let satisfy
- ;
- for every ;
- for every and every ;
- if , then for every .
These are the sets produced by ordering the products by utility and filling the knapsack from the largest utility as long as the utility is positive. Then is an optimal solution of problem (9):
The result shows that an optimal solution of (9) is read off from the ordering and the signs of the utilities.
Formalization Note The 0/1 vector is the indicator of a Finset (Fin n). Ties among utilities are allowed; any tie-breaking of the greedy order gives an optimal set.
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model import Definitions.Def_ConstrNestedLogit_Card_Knapsack open NestedLogitVariants.LP
Formal statement
namespace ConstrNestedLogit.Card
/-- Greedy solves the knapsack problem (9) (p. 16): a set `S` with `|S| ≤ c_i` whose products all
have positive utility `f_ij(u) > 0`, such that no product outside `S` has larger utility than a
product in `S`, and such that, if `|S| < c_i`, every product outside `S` has utility `≤ 0`,
is an optimal solution of (9) at `u`. -/
theorem greedy_solves_9 {ι : Type*} {n : ℕ} (I : Instance ι n) (c : ι → ℕ) (i : ι) (u : ℝ)
(S : Finset (Fin n)) (hcard : S.card ≤ c i)
(hpos : ∀ j ∈ S, 0 < utility I i j u)
(horder : ∀ j ∈ S, ∀ k ∉ S, utility I i k u ≤ utility I i j u)
(hrest : S.card < c i → ∀ k ∉ S, utility I i k u ≤ 0) :
IsKnapsackOptimal I c i u S := by sorry
end ConstrNestedLogit.Card
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. 16, discussion of problem (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.