Proof of Theorem 4, p. 13 — the IFP answer is yes iff x⋆ = n, and no iff x⋆ < n − ϵ′
ProvedSPHardness.IntFeas.xStar_dichotomygapinteger-feasibilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Let be an instance of the Integer Feasibility Problem with a nonempty polytope , let , and let satisfy the hypotheses of Lemma 4: and for every row . Then
The optimal decision of (11) therefore has a gap of width between yes-instances and no-instances, which an approximately optimal decision can detect.
Formalization Note. is cast to . The condition on is encoded as in Lemma 4 (zero rows impose nothing).
Preamble
import Mathlib import Definitions.Def_SPHardness_IntFeas_Model open MeasureTheory
Formal statement
namespace SPHardness.IntFeas
theorem xStar_dichotomy {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ)
(hinst : IsIFPInstance A b) (hne : ∃ ξ : Fin n → ℝ, InPolytope A b ξ)
(ε' : ℝ) (hε'0 : 0 ≤ ε') (hε'half : ε' < 1 / 2)
(hε'row : ∀ i, ε' * ∑ j, |(A i j : ℝ)| < 1) :
(IFPAnswer A b ↔ xStar A b = n) ∧ (¬ IFPAnswer A b ↔ xStar A b < n - ε') := by sorry
end SPHardness.IntFeas
Source
Hanasusanto, Kuhn & Wiesemann, A comment on "computational complexity of stochastic programming problems", Optimization Online preprint 2015/03/4825 (version of October 6, 2015), §3, proof of Theorem 4, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.