Proof of Theorem 8, p. 1435 — predecessors S, the blocks of c̄ and b(R) share the capacity U_s^d of destination d
ProvedOpenPitMIP.Hourglass.capacity_splitknapsackmixed-integer-programmingopen-pit-miningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1production-scheduling
Consider an instance of the PCPSP-C satisfying the standing assumptions. Fix a destination , a cluster , a set of blocks of strict predecessors of , and let . If satisfies the destination capacity rows (9), , then for every period
This is the capacity inequality from which the proof of Theorem 8 starts, before summing over .
Formalization Note The page writes ""; the inequality holds for every period and is stated so. Only nonnegativity of and the rows (9) are assumed about .
Preamble
import Mathlib import Definitions.Def_OpenPitMIP_Hourglass_Setting
Formal statement
namespace OpenPitMIP.Hourglass
/-- Proof of Theorem 8, p. 1435: for a cluster `c̄`, a set `S` of blocks of strict predecessors of
`c̄` and `R = rcl(c̄) \ {c̄}`, every nonnegative `y` satisfying the destination capacity rows (9)
satisfies, for every period `s`,
`∑_{b∈S} q_b y_{b,d,s} + ∑_{b∈c̄} q_b y_{b,d,s} + ∑_{b∈b(R)} q_b y_{b,d,s} ≤ U_s^d`. -/
theorem capacity_split {B D C : Type} [Fintype B] [Fintype D] [Fintype C]
[DecidableEq B] [DecidableEq C] {T m : ℕ}
(I : PCPSPC B D C T m) (hI : I.Standing) (d : D) (cbar : C) (S : Finset B)
(hS : S ⊆ I.blocksOf (I.cl cbar \ {cbar}))
(y : B → D → Fin T → ℝ) (hy0 : ∀ b d t, 0 ≤ y b d t) (hcap : I.DestCap y) :
∀ s : Fin T,
∑ b ∈ S, I.q b * y b d s + ∑ b ∈ I.blocksOf {cbar}, I.q b * y b d s
+ ∑ b ∈ I.blocksOf (I.rcl cbar \ {cbar}), I.q b * y b d s ≤ I.Ud d s := by sorry
end OpenPitMIP.Hourglass
Source
Oper. Res. 68(5), proof of Theorem 8, p. 1435
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.