Clause-probe B&B MILP and ERM language
DefinitionAggCG_Supplement_clauseProbeMILPalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
The clause-probe program is the MILP (8)–(12) with selector, parity, trap, and auxiliary variables. Block sizes encode absent, positive, and negative literals, and a final odd block supplies the probe trap. The fixed dyadic node-selection policy makes the generated tree size read the encoded clause.
The associated threshold language asks whether one parameter makes the sum of training tree sizes at most .
Definition code
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_QAlgorithms_ClassicalRationalEncoding
import Definitions.Def_AggCG_Supplement_MILP
namespace AggCG.Supplement
/-- The variables of the frontier gadget (8)–(12) with `n = T + 1` stages and block sizes `k`
(Sharma, *Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and
Learning Algorithms*, STOC 2027 submission (manuscript sha256 f7ea0248…), §H.1, p.45, PDF p.46):
selectors `x_j`, parity blocks `y_{j,a}` (`a < k_j`), `t_j`, and `z_i` for `i < T` (the paper's `z_{i+1}`).
Indices are `0`-based. -/
abbrev HVar (T : ℕ) (k : Fin (T + 1) → ℕ) :=
Fin (T + 1) ⊕ (Σ j : Fin (T + 1), Fin (k j)) ⊕ Fin (T + 1) ⊕ Fin T
namespace HVar
variable {T : ℕ} {k : Fin (T + 1) → ℕ}
/-- Selector `x_j`. -/
def x (j : Fin (T + 1)) : HVar T k := Sum.inl j
/-- Parity variable `y_{j,a}`. -/
def y (j : Fin (T + 1)) (a : Fin (k j)) : HVar T k := Sum.inr (Sum.inl ⟨j, a⟩)
/-- `t_j`. -/
def t (j : Fin (T + 1)) : HVar T k := Sum.inr (Sum.inr (Sum.inl j))
/-- `z_i` (the paper's `z_{i+1}`). -/
def z (i : Fin T) : HVar T k := Sum.inr (Sum.inr (Sum.inr i))
/-- Being a parity variable. -/
def IsY (v : HVar T k) : Prop := ∃ j a, v = y j a
end HVar
open HVar in
/-- The MILP (8)–(12) of §H.1 (p.45): `max Σ_j t_j` subject to `t_j ≤ 2x_j`, `t_j ≤ 2(1 − x_j)`,
`2 Σ_a y_{j,a} = k_j x_j`, `y_{j,a} ≤ x_j`, `z_j ≥ x_j`, `x_{j+1} + z_j ≤ 1`, `z_j ≥ z_{j−1}`, with
`x, y` binary and `0 ≤ t, z ≤ 1`. -/
noncomputable def clauseProbeMILP (T : ℕ) (k : Fin (T + 1) → ℕ) : MILP (HVar T k) where
obj := fun v => match v with | Sum.inr (Sum.inr (Sum.inl _)) => 1 | _ => 0
rows :=
((List.finRange (T + 1)).map fun j =>
((fun v => if v = t j then 1 else if v = x j then -2 else 0), false, (0 : ℝ))) ++
((List.finRange (T + 1)).map fun j =>
((fun v => if v = t j then 1 else if v = x j then 2 else 0), false, (2 : ℝ))) ++
((List.finRange (T + 1)).map fun j =>
((fun v => if (∃ a, v = y j a) then 2 else if v = x j then -(k j : ℝ) else 0), true, (0 : ℝ))) ++
((List.finRange (T + 1)).flatMap fun j => (List.finRange (k j)).map fun a =>
((fun v => if v = y j a then 1 else if v = x j then -1 else 0), false, (0 : ℝ))) ++
((List.finRange T).map fun i =>
((fun v => if v = x i.castSucc then 1 else if v = z i then -1 else 0), false, (0 : ℝ))) ++
((List.finRange T).map fun i =>
((fun v => if v = x i.succ then 1 else if v = z i then 1 else 0), false, (1 : ℝ))) ++
((List.finRange T).filterMap fun i =>
if h : 0 < i.val then
some ((fun v => if v = z ⟨i.val - 1, by omega⟩ then 1 else if v = z i then -1 else 0),
false, (0 : ℝ))
else none)
lo := fun _ => 0
hi := fun _ => 1
isBin := fun v => match v with | Sum.inl _ => true | Sum.inr (Sum.inl _) => true | _ => false
open Classical in
/-- The block sizes (15) of a clause (p.46): `k_j = 3` if the positive literal `b_j` occurs, `5` if the
negative literal `¬b_j` occurs, `1` otherwise, for `j < T`; the last block has size `k∗`. -/
noncomputable def clauseSizes (T : ℕ) (C : CookLevin.Clause) (kstar : ℕ) : Fin (T + 1) → ℕ :=
fun j => if j.val < T then
(if CookLevin.Literal.Pos j.val ∈ C then 3 else if CookLevin.Literal.Neg j.val ∈ C then 5 else 1)
else kstar
/-- The final rule's test (p.46–47): the clause read from the block sizes (`k_j = 3` a positive literal,
`k_j = 5` a negative one) is false on the recorded word `b`. -/
def sizesClauseFalse (T : ℕ) (k : Fin (T + 1) → ℕ) (b : ℕ → Bool) : Prop :=
∀ j : Fin (T + 1), j.val < T → (k j = 3 → b j.val = false) ∧ (k j = 5 → b j.val = true)
/-- `TreeSize_θ(Q)` of the fixed B&B policy family of §H.2 on the program (8)–(12) with block sizes `k`. -/
noncomputable def probeTreeSize (T : ℕ) (k : Fin (T + 1) → ℕ) (θ : ℝ) : ℕ :=
bbTreeSize (clauseProbeMILP T k)
(ctrlSel HVar.x HVar.IsY (sizesClauseFalse T k) θ) (ctrlBranch HVar.x HVar.IsY)
/-- A clause of the restricted family of arity at most `w` over `b_0, …, b_{T−1}`: at most `w` literals,
on distinct variables, all below `T`. -/
def ProbeClause (w T : ℕ) (C : CookLevin.Clause) : Prop :=
C.length ≤ w ∧ (C.map CookLevin.Literal.var).Nodup ∧ ∀ l ∈ C, l.var < T
/-- The code of a training set of clause-probe programs: `T` and `k∗` in unary, the clauses, then the
threshold `K` in binary. -/
def encodeProbeSet (T kstar : ℕ) (Φ : CookLevin.Formula) (K : ℕ) : List Bool :=
CookLevin.encodeNat T ++ CookLevin.encodeNat kstar ++ CookLevin.encodeFormula Φ ++
QAlgorithms.LocalHamiltonian.encBin K
/-- The code of a training set without a threshold (the input of an approximation algorithm). -/
def encodeProbeSet' (T kstar : ℕ) (Φ : CookLevin.Formula) : List Bool :=
CookLevin.encodeNat T ++ CookLevin.encodeNat kstar ++ CookLevin.encodeFormula Φ
/-- The ERM threshold decision of Theorem H.5 (p.47) for clauses of arity at most `w`: odd `k∗`, clauses of
the restricted family and `K`; is there `θ ∈ [0, 1]` with `Σ_a TreeSize_θ(Q_{C_a}) ≤ K`? -/
def ProbeTreeLang (w : ℕ) : CookLevin.Language := fun x =>
∃ (T kstar : ℕ) (Φ : CookLevin.Formula) (K : ℕ), x = encodeProbeSet T kstar Φ K ∧ Odd kstar ∧
(∀ C ∈ Φ, ProbeClause w T C) ∧
∃ θ ∈ Set.Icc (0 : ℝ) 1, (Φ.map fun C => probeTreeSize T (clauseSizes T C kstar) θ).sum ≤ K
/-- The normalized average tree size of Theorem H.6 (p.48): `(1/m) Σ_a TreeSize_θ(Q_{C_a}) / M` with
`M = H + 2T + 3 + 38T` and `H = h(k∗)`. -/
noncomputable def avgNormTree (T kstar : ℕ) (Φ : CookLevin.Formula) (θ : ℝ) : ℝ :=
(1 / (Φ.length : ℝ)) * (Φ.map fun C =>
(probeTreeSize T (clauseSizes T C kstar) θ : ℝ) / ((trapCount kstar + 2 * T + 3 + 38 * T : ℕ) : ℝ)).sum
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), §H.1–H.4, pp.45–48, PDF pp.46–49