§2.2, p. 1428 — feasible PCPSP-C solutions correspond to a nested sequence of pits
ProvedOpenPitMIP.UltPit.feasible_nested_pitsnested-pitsopen-pit-miningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1precedence-constraints
Consider an instance of the PCPSP-C (formulation (1)–(7)) under the standing assumptions of §2.1, and let be a feasible solution under either integrality condition (10) or (11). For each period define
Then:
- for every , the set is a pit: if and then ;
- the sets are nested: implies .
This is the observation that links PCPSP-C schedules with the phase design problem: a schedule extracts, period by period, an increasing family of pits.
Formalization Note The precedence constraints (4) are imposed only along the arcs of the transitive reduction, as in the paper. Periods are Fin T (index is period ).
Preamble
import Mathlib import Definitions.Def_OpenPitMIP_UltPit_Setting
Formal statement
namespace OpenPitMIP.UltPit
open PCPSPC
/-- §2.2, p. 1428: for every feasible solution of the PCPSP-C and every period `t`, the set
`𝓑(x; t) = {b ∈ 𝓑 : ∑_{t'=1}^{t} x_{c(b),t'} > 0}` is a pit, and these sets are nested in `t`. -/
theorem feasible_nested_pits {B D C : Type} [Fintype B] [Fintype D] [Fintype C] {T m : ℕ}
(I : PCPSPC B D C T m) (hI : I.Standing) (κ : Integrality)
(x : C → Fin T → ℝ) (y : B → D → Fin T → ℝ) (hxy : I.Feasible κ x y) :
(∀ t, I.IsPit {b | 0 < cum x (I.clu b) t}) ∧
∀ t t', t ≤ t' → {b | 0 < cum x (I.clu b) t} ⊆ {b | 0 < cum x (I.clu b) t'} := by sorry
end OpenPitMIP.UltPit
Source
Oper. Res. 68(5), §2.2, p. 1428
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.