§7, p. 15 — a finite cutset of G* has capacity Σ_{j∈N} max(0, w_j) − Σ_{j∈I} w_j
ProvedLawlerWCT.RhoMax.cutCapacity_eqinitial-setsminimum-cutnetwork-flowsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In the setting of the network (source , sink , capacities , , and on the arcs of ), let be an cutset of finite capacity and let . Then
The first sum does not depend on the cutset, so minimizing the capacity of a finite cutset is the same as maximizing the weight of the corresponding initial set.
Formalization Note. The capacity lives in WithTop ℝ; the identity is stated as the coercion of a real number, so no subtraction takes place in WithTop ℝ. The "constant" of the paper's display is , read off its third line. The first line of the printed display writes where the arcs from into are meant, , as the second line shows; the statement uses the corrected reading.
Preamble
import Mathlib import Definitions.Def_LawlerWCT_RhoMax_Model
Formal statement
namespace LawlerWCT.RhoMax
theorem cutCapacity_eq {ι : 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)
(hfin : cutCapacity N G w T < ⊤) :
cutCapacity N G w T =
((∑ j ∈ N, max 0 (w j) - ∑ j ∈ jobsOf N T, w j : ℝ) : WithTop ℝ) := 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, display beginning "Let (S,T) be a cutset with c(S,T) finite"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.