Lemma 2, p. 87 — V₀(z, c) is jointly concave in z₁, …, zₙ and in c₁, …, cₘ
ProvedSubstOverbooking.Structure.lemma2_V0_concaveconcavityoverbookingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1transportation-problem
Fix net benefits .
- For capacities with (), the map is concave on .
- For , the map is concave on .
That is, is jointly concave in the demand block and jointly concave in the capacity block . Together with Lemma 1 this is the structure of the service-period value that the expected net revenue inherits.
Formalization Note. The virtual class is uncapacitated, so does not affect and is left free in part 2; the paper's statement is about .
Preamble
import Mathlib import Definitions.Def_SubstOverbooking_Structure_Setting
Formal statement
namespace SubstOverbooking.Structure
theorem lemma2_V0_concave {n m : ℕ} (a : Fin n → Fin (m + 1) → ℝ) :
(∀ c : Fin (m + 1) → ℝ, (∀ j, j ≠ 0 → 0 ≤ c j) →
ConcaveOn ℝ {z : Fin n → ℝ | ∀ i, 0 ≤ z i} (fun z => V0 a c z)) ∧
(∀ z : Fin n → ℝ, (∀ i, 0 ≤ z i) →
ConcaveOn ℝ {c : Fin (m + 1) → ℝ | ∀ j, j ≠ 0 → 0 ≤ c j} (fun c => V0 a c z)) := by sorry
end SubstOverbooking.Structure
Source
Karaesmen & van Ryzin, Overbooking with Substitutable Inventory Classes, Operations Research 52(1):83–104 (2004), p. 87, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.