Proposition 5, pp. 4–5 — a feasible mixed-integer linear system has a solution of polynomial bit-size (MIP is in NP)
DisprovedMIQPInNP.SmallSol.proposition_5computational-complexitymixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedraquadratic-programming
Let , and . There is a single polynomial , fixed before , , and the data, such that: if the mixed-integer linear system
has a real solution, then it has a rational solution with .
The paper states this as "the decision version of MIP is in NP" and justifies it by presenting a vertex of one of the polytopes of Proposition 4 as a certificate. The proof of Theorem 1 (Case 1, p. 7) uses exactly this: a point of the mixed-integer linear set of small complexity.
Formalization Note If , all coordinates are required to be integers. The polynomial is quantified before all dimensions and data.
Differences from the source:
- reading: "the decision version of MIP is in NP" → every feasible mixed-integer linear system has a rational solution of bit-size at most ; reason: Mathlib has no class NP; this is the certificate the paper presents on p. 5, and checking it is routine.
- encoding: "polynomial", "complexity" →
Polynomial ℕevaluated at Schrijver's bit-size; reason: polynomially equivalent to any standard encoding.
Preamble
import Mathlib import Definitions.Def_MIQPInNP_SmallSol_Setting
Formal statement
namespace MIQPInNP.SmallSol
/-- Proposition 5, pp. 4–5 (certificate form, p. 5) (Del Pia, Dey & Molinaro, arXiv:1407.4798v1). -/
theorem proposition_5 :
∃ g : Polynomial ℕ, ∀ (n p m : ℕ) (A : Matrix (Fin m) (Fin n) ℚ) (b : Fin m → ℚ),
(∃ x ∈ polyhedron A b, IsMixedInt p x) →
∃ xh : Fin n → ℚ, toReal xh ∈ polyhedron A b ∧ IsMixedInt p (toReal xh) ∧
vecSize xh ≤ g.eval (matSize A + vecSize b) := by sorry
end MIQPInNP.SmallSol
Source
Del Pia, Dey & Molinaro, Mixed-integer quadratic programming is in NP, arXiv:1407.4798v1, pp. 4–5, Proposition 5 and its justification
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.