(38), p. 1436 — the block set S* = {b : c(b) ≺ c̄, w*_{c̄,t} > w*_{c(b),t} − ∑ y*_{b,d,s}} maximizes the violation of (37)
ProvedOpenPitMIP.Hourglass.most_violated_setConsider an instance of the PCPSP-C satisfying the standing assumptions, arbitrary values and (for instance a solution of the LP relaxation), a cluster , a destination and periods . For a set of blocks let
be the violation of the hourglass inequality (37), with and the blocks of together with those of . Then the set
satisfies , and for every .
This makes the separation of the most violated hourglass cut, for fixed , a simple pass over the blocks.
Formalization Note The page says "maximizes the violation"; with ties the maximizer is not unique, so the statement is that attains the maximum. The maximum is over all , as on the page; the side condition of Theorem 8 is not imposed, and need not satisfy it. No feasibility is assumed of .
import Mathlib import Definitions.Def_OpenPitMIP_Hourglass_Setting
namespace OpenPitMIP.Hourglass
open Classical in
/-- Display (38), p. 1436: the most violated hourglass cut. For arbitrary values `w*` and `y*`
(for instance a solution of the LP relaxation), a cluster `c̄`, a destination `d` and periods
`t₁ ≤ t`, let `viol S` be the left-hand side minus the right-hand side of (37) at `(w*, y*)`.
The block set `S* = {b : c(b) ≺ c̄, w*_{c̄,t} > w*_{c(b),t} − ∑_{s=t₁}^{t} y*_{b,d,s}}` is admissible,
`S* ⊆ b(cl(c̄) \ {c̄})`, and attains the maximum of `viol` over all `S ⊆ b(cl(c̄) \ {c̄})`. -/
theorem most_violated_set {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)
(w : C → Fin T → ℝ) (y : B → D → Fin T → ℝ) (cbar : C) (d : D)
(t₁ t : Fin T) (ht : t₁ ≤ t) :
let viol : Finset B → ℝ := fun S =>
(I.qBlocks (S ∪ I.blocksOf {cbar}) - I.Ucum d t₁ t) * w cbar t
+ ∑ b ∈ I.blocksOf (I.rcl cbar \ {cbar}), I.q b * PCPSPC.ySum y b d t₁ t
- ∑ b ∈ S ∪ I.blocksOf {cbar}, I.q b * (w (I.clu b) t - PCPSPC.ySum y b d t₁ t)
let Sstar : Finset B := Finset.univ.filter
(fun b => I.cprec (I.clu b) cbar ∧ w (I.clu b) t - PCPSPC.ySum y b d t₁ t < w cbar t)
Sstar ⊆ I.blocksOf (I.cl cbar \ {cbar}) ∧
∀ S ⊆ I.blocksOf (I.cl cbar \ {cbar}), viol S ≤ viol Sstar := by sorry
end OpenPitMIP.Hourglass
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.