Theorem 4, p. 13 — for ϵ < ϵ′/4n, any ϵ-optimal decision x of (11) decides the Integer Feasibility Problem by x > n − ϵ′/2
ProvedSPHardness.IntFeas.theorem_4This is the correctness of the reduction behind Theorem 4: comparing any -optimal decision of the random-recourse program (11) with the threshold answers the Integer Feasibility Problem exactly.
Let and form an instance of the Integer Feasibility Problem, that is, , with and with a nonempty polytope . Let be as in Lemma 4: and for every row . Let and let be an -optimal decision of problem (11),
with uniform on and the optimal value of the second-stage problem . Then
The paper concludes that determining an -optimal decision of a linear two-stage stochastic program with random recourse is strongly NP-hard for , and hence that no FPTAS exists unless the problems in NP admit an efficient solution scheme. The statement here is the mathematical core of that conclusion.
Formalization Note. Strong NP-hardness, the absence of an FPTAS, polynomial-time computability of the reduction and bit lengths are not formalized; the theorem states only that the decision procedure "" is correct. Feasibility in (11) is robust (the second stage feasible for every ); the page's "infeasible with positive probability" would, read almost surely, break the proof's formula for on instances with a Lebesgue-null polytope. The constraint block of the second stage is indexed by (the page prints and says ); stays arbitrary. Lemma 4's is encoded as for all rows. Added hypotheses, all disclosed: the polytope is nonempty (the proof's own assumption; otherwise the answer is trivially negative), (used in ), and (implicit). The uniform law is Lebesgue measure on the unit cube, which has volume .
import Mathlib import Definitions.Def_SPHardness_IntFeas_Model open MeasureTheory
namespace SPHardness.IntFeas
theorem theorem_4 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ)
(hinst : IsIFPInstance A b) (hne : ∃ ξ : Fin n → ℝ, InPolytope A b ξ) (hn : 1 ≤ n)
(ε' : ℝ) (hε'0 : 0 ≤ ε') (hε'half : ε' < 1 / 2)
(hε'row : ∀ i, ε' * ∑ j, |(A i j : ℝ)| < 1)
(ε : ℝ) (hε0 : 0 ≤ ε) (hε : ε < ε' / (4 * n))
(x : ℝ) (hx : IsEpsOptimal A b ε x) :
IFPAnswer A b ↔ (n : ℝ) - ε' / 2 < x := by sorry
end SPHardness.IntFeas
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.