Proposition 6.4 — equivalent formulation bounds (printed convention)
DisprovedPochetWolsey.Decomposition.formulation_boundsLet have rational data, let , and let . All dimensions are finite; and the linking data are real. Let and be tight descriptions: . For a finite family of cuts valid on , put .
An exact separator returns no cut precisely at points of ; every returned cut is valid for and strictly violated by the query point. Assume the cutting-plane run has terminated at a minimizer over where that separator returns no cut. Write , , and . With the preceding paragraph's literal convention , the printed assertion is
All three suprema and the minimum are asserted to be attained. This records the source's comparison of direct formulations, projections, and completed cutting-plane relaxations.
Formalization Note This faithful item is false: the page defines each by maximization but equates it to a minimum. Finding F1 gives , all three sets , and . Values use extended reals to avoid default real infima; the finite minimum is explicitly witnessed. Exact separation is encoded by its oracle specification and terminal-state conditions, without assuming that the finite cut region equals the hull.
import Mathlib
namespace PochetWolsey.Decomposition
theorem formulation_bounds {n m q t p a s : ℕ}
(A : Matrix (Fin m) (Fin n) ℚ) (b : Fin m → ℚ)
(D : Matrix (Fin q) (Fin n) ℝ) (d : Fin q → ℝ)
(c : Fin n → ℝ)
(B : Matrix (Fin t) (Fin n) ℝ) (e : Fin t → ℝ)
(F : Matrix (Fin a) (Fin n) ℝ) (G : Matrix (Fin a) (Fin p) ℝ)
(g : Fin a → ℝ)
(cuts : Matrix (Fin s) (Fin n) ℝ) (rhs : Fin s → ℝ)
(sep : (Fin n → ℝ) → Option ((Fin n → ℝ) × ℝ)) :
let PY : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
∀ i, (b i : ℝ) ≤ ∑ j, (A i j : ℝ) * x j}
let Y : Set (Fin n → ℝ) := {x | x ∈ PY ∧ ∀ j, ∃ z : ℤ, x j = (z : ℝ)}
let PZ : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
∀ i, d i ≤ ∑ j, D i j * x j}
let direct : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
∀ i, e i ≤ ∑ j, B i j * x j}
-- The auxiliary sum over Fin p remains even when the original dimension n is zero.
let Q : Set ((Fin n → ℝ) × (Fin p → ℝ)) := {xv |
(∀ j, 0 ≤ xv.1 j) ∧
∀ i, g i ≤ (∑ j, F i j * xv.1 j) + ∑ j, G i j * xv.2 j}
let projection : Set (Fin n → ℝ) := {x | ∃ v : Fin p → ℝ, (x, v) ∈ Q}
let cutting : Set (Fin n → ℝ) := {x | x ∈ PY ∩ PZ ∧
∀ i, rhs i ≤ ∑ j, cuts i j * x j}
let cost : (Fin n → ℝ) → ℝ := fun x => ∑ j, c j * x j
let value : Set (Fin n → ℝ) → EReal := fun S =>
sSup ((fun x => (cost x : EReal)) '' S)
direct = convexHull ℝ Y → projection = convexHull ℝ Y →
(∀ i, ∀ y ∈ Y, rhs i ≤ ∑ j, cuts i j * y j) →
(∀ x, sep x = none ↔ x ∈ convexHull ℝ Y) →
(∀ x α β, sep x = some (α, β) →
(∀ y ∈ Y, β ≤ ∑ j, α j * y j) ∧ (∑ j, α j * x j) < β) →
(∃ xbar ∈ cutting, (∀ x ∈ cutting, cost xbar ≤ cost x) ∧ sep xbar = none) →
value (direct ∩ PZ) = value (projection ∩ PZ) ∧
value (projection ∩ PZ) = value cutting ∧
value cutting = sInf ((fun x => (cost x : EReal)) '' (convexHull ℝ Y ∩ PZ)) ∧
(∀ S ∈ [direct ∩ PZ, projection ∩ PZ, cutting],
∃ xmax ∈ S, (∀ x ∈ S, cost x ≤ cost xmax) ∧ value S = (cost xmax : EReal)) ∧
∃ xstar ∈ convexHull ℝ Y ∩ PZ,
(∀ x ∈ convexHull ℝ Y ∩ PZ, cost xstar ≤ cost x) ∧
sInf ((fun x => (cost x : EReal)) '' (convexHull ℝ Y ∩ PZ)) =
(cost xstar : EReal) := by sorry
end PochetWolsey.Decomposition
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. Fix natural numbers , any of which may be . Vectors are indexed by . The theorem takes:
- a rational matrix and a rational vector , both used only after conversion to reals;
- a real matrix and ;
- a cost vector ;
- a real matrix and ;
- real matrices () and (), and ;
- a real matrix (named
cuts) and (namedrhs); - an arbitrary function (named
sep). For each , either returns "none" or returns a pair with and .
Sets defined. All inequalities between vectors below are componentwise.
In the auxiliary vector has no sign constraint.
The cost is . For a set , define
This is a supremum taken in the extended reals.
Hypotheses. Write for the real convex hull of .
- .
- .
- Every satisfies .
- For every : is "none" if and only if .
- Whenever , two things hold:
- for all ;
- .
- There exists such that:
- for all , so is a cost minimizer over Cut;
- is "none".
Conclusions. All five hold together.
- .
- .
- The supremum of cost over Cut equals the infimum of cost over :
- Each of the three sets contains a point such that:
- for all , so is a cost maximizer on ;
- .
- There exists such that:
- for all ;
- .
No boundedness assumption on the cost over any of these sets appears among the hypotheses.
Degenerate cases. Hypothesis 6 makes Cut nonempty. By hypothesis 4 the point lies in , so and are nonempty. If were empty, hypothesis 4 would force "none", and the hypotheses could not all hold. Whenever the hypotheses cannot hold simultaneously, the statement is vacuously true. The defaults that would otherwise apply are: the supremum of the empty set is and the infimum of the empty set is .
The zero-size cases are as follows:
- . is a single point and every sum over is , so the cost is identically . is that point exactly when ; similarly requires and Direct requires . Cut requires , and Proj requires some with . Integrality is vacuous, so .
- . is the nonnegative orthant and is the set of all nonnegative integer vectors.
- . is the nonnegative orthant.
- . Direct is the nonnegative orthant.
- . Proj is the nonnegative orthant.
- . Proj is .
- . Hypothesis 3 is vacuous and .
Since cost takes only real values, for a nonempty is either a real number or . Conclusion 4 nevertheless asserts that a maximizer exists on each of the three sets.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.