§4.2, p. 1431 — a dominated triplet (b, d₂, t) can be set to zero in some optimal solution
ProvedOpenPitMIP.UltPit.dominated_tripletmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1preprocessingproduction-scheduling
Consider an instance of the PCPSP-C with either integrality condition, a block , two distinct destinations and a period . Write for the column of that multiplies . Suppose the triplet dominates :
If the PCPSP-C has an optimal solution, then it has an optimal solution with .
This justifies the dominated-triplet preprocessing: the variable can be removed from the model without changing the optimal value.
Formalization Note The comparison is between the discounted values , as on the page. The hypothesis is implicit in "dominates" (with every triplet would dominate itself, and the conclusion would be false in general).
Preamble
import Mathlib import Definitions.Def_OpenPitMIP_UltPit_Setting
Formal statement
namespace OpenPitMIP.UltPit
open PCPSPC
/-- §4.2, p. 1431: if the triplet `(b, d₁, t)` dominates `(b, d₂, t)` — the column `G_{b,d₁,t}`
is componentwise at most `G_{b,d₂,t}` and `p_{b,d₁,t} ≥ p_{b,d₂,t}` — then, whenever the
PCPSP-C has an optimal solution, it has one with `y_{b,d₂,t} = 0`. -/
theorem dominated_triplet {B D C : Type} [Fintype B] [Fintype D] [Fintype C] {T m : ℕ}
(I : PCPSPC B D C T m) (κ : Integrality) (b : B) (d₁ d₂ : D) (hd : d₁ ≠ d₂) (t : Fin T)
(hG : ∀ i, I.G i b d₁ t ≤ I.G i b d₂ t) (hp : I.value b d₁ t ≥ I.value b d₂ t)
(hopt : ∃ x y, I.Optimal κ x y) :
∃ x y, I.Optimal κ x y ∧ y b d₂ t = 0 := by sorry
end OpenPitMIP.UltPit
Source
Oper. Res. 68(5), §4.2, p. 1431
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.