§7, p. 15 — a minimum capacity (s,t) cutset of G* yields a maximum weight initial set
ProvedLawlerWCT.RhoMax.min_cut_max_weightclosure-probleminitial-setsminimum-cutnetwork-flowsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a digraph on a finite job set with real weights of either sign, and let be the network of §7 (capacities , , on the arcs of ). If is an cutset of minimum capacity among all cutsets of , then is an initial set of and
This turns the search for an initial set of maximum total weight, with weights of either sign, into a minimum-cut computation; it is the subroutine every trial value of the ratio uses.
Formalization Note. The maximum ranges over all initial sets, the empty one included (weight ); this is what a minimum cut delivers, because the cutset with is finite.
Preamble
import Mathlib import Definitions.Def_LawlerWCT_RhoMax_Model
Formal statement
namespace LawlerWCT.RhoMax
theorem min_cut_max_weight {ι : Type*} [DecidableEq ι] (N : Finset ι)
(G : ι → ι → Prop) (hGN : ∀ i j, G i j → i ∈ N ∧ j ∈ N) (w : ι → ℝ)
(T : Finset (Node ι)) (hT : T ⊆ nodes N) (ht : Node.t ∈ T) (hs : Node.s ∉ T)
(hmin : ∀ T' : Finset (Node ι), T' ⊆ nodes N → Node.t ∈ T' → Node.s ∉ T' →
cutCapacity N G w T ≤ cutCapacity N G w T') :
LawlerWCT.SeriesPar.IsInitialSet G N (jobsOf N T) ∧
∀ I, LawlerWCT.SeriesPar.IsInitialSet G N I → ∑ j ∈ I, w j ≤ ∑ j ∈ jobsOf N T, w j := by sorry
end LawlerWCT.RhoMax
Source
Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints, IRIA-LABORIA Rapport de Recherche No. 205 (Dec. 1976), HAL hal-04716371v1, p. 15, §7, sentence "It follows that a minimum capacity (s,t) cutset yields a maximum weight initial set I."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.