Exact-count witness optimization on a supplied tree decomposition
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.factor_optimizer_on_given_layoutalgorithmsclusteringdynamic-programming
Given polynomial bit programs for the variables, finite domain, factors, costs, and a width-t tree decomposition of their explicit primal graph, return an actual minimum-cost represented pack for each attainable number of blocks.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_FactorLayouts import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.factor_optimizer_on_given_layout {α : Type} [Coding α] [Inhabited α] (t : ℕ)
(vars terms : α→Block) (dom : α→List Value) (scope : α×ℕ→Block)
(emit : (α×ℕ)×Plan→Pack) (cost : α×Block→ℚ)
(layout : α→FactorLayout) (pl : Poly layout)
(p1 : Poly vars) (p2 : Poly terms) (p3 : Poly dom) (p4 : Poly scope)
(p5 : Poly emit) (p6 : Poly cost) :
∃ F : α→Table, Poly F ∧ ∀ a,
(∀ i∈terms a, ∀ v∈scope (a,i),v∈vars a) →
GoodLayout (vars a) ((terms a).map (fun i => scope (a,i))) t (layout a) →
(∀ i∈terms a, DependsOn (vars a) (scope (a,i)) (fun s => emit ((a,i),s))) →
FactorRow (vars a) (dom a) (renderFactors (terms a) (fun i s => emit ((a,i),s)))
(fun w => cost (a,w)) (F a) := by
sorry
Source
Executable counterpart of StableMSR.Recovery.TreeDP.bounded_treewidth_dp, with rational costs and witness recovery.