Lemma A.1 — partition and none contains a pair together with its reverse
ProvedSingleMachinePrec.ConvexBipartite.lemma_A_1convex-bipartite-orderp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1posetsrealizer
Let be a convex bipartite order and let be the sets of incomparable pairs defined in the Appendix. Then:
- the sets form a partition of : a pair is incomparable if and only if it lies in , and the three sets are pairwise disjoint;
- for every and every ,
Part 2 ensures that no forces both orders of an incomparable pair, and part 1 that every incomparable pair is placed in some in the direction it will be reversed.
Formalization Note "Partition" is read as covering plus pairwise disjointness; some of the may be empty (for instance when there are no plus jobs). No numbering assumption on the plus jobs is used.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_ConvexBipartite_IncPartition
Formal statement
namespace SingleMachinePrec.ConvexBipartite
open ConvexBipartiteOrder
/-- Lemma A.1 (Ambühl et al. 2011, p. 668). For a convex bipartite order:
(i) `E₁, E₂, E₃` form a partition of `inc(P)` — every incomparable pair lies in one of them,
each of them consists of incomparable pairs, and they are pairwise disjoint;
(ii) for every incomparable pair `(x, y)` and every `m ∈ {1, 2, 3}`, if `(x, y) ∈ E_m` then
`(y, x) ∉ E_m`. -/
theorem lemma_A_1 {a b : ℕ} (C : ConvexBipartiteOrder a b) :
((∀ x y : Job a b, SingleMachinePrec.Framework.Incomparable C.prec x y ↔ (C.E1 x y ∨ C.E2 x y ∨ C.E3 x y)) ∧
(∀ x y : Job a b, ¬ (C.E1 x y ∧ C.E2 x y)) ∧
(∀ x y : Job a b, ¬ (C.E1 x y ∧ C.E3 x y)) ∧
(∀ x y : Job a b, ¬ (C.E2 x y ∧ C.E3 x y))) ∧
(∀ x y : Job a b, SingleMachinePrec.Framework.Incomparable C.prec x y →
(C.E1 x y → ¬ C.E1 y x) ∧ (C.E2 x y → ¬ C.E2 y x) ∧ (C.E3 x y → ¬ C.E3 y x)) := by sorry
end SingleMachinePrec.ConvexBipartite
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 668, Lemma A.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.