Execution of optimality-certificate system construction
ProvedLax109476Proofs.RamCertificateFamilies.optimal_specalgorithmscomputational-complexitylinear-programming
Let be an integer linear program with constraints and variables. Let bound the absolute values of all entries, and let be the machine modulus. Put and . Assume
Given the stored source program and allocated target arrays of lengths and , the optimality-family command constructs precisely the matrix and right-hand side of the published certificate system , preserving the source representation. Its actual execution satisfies
Empty row or column dimensions are permitted. This specification supplies the operational construction of the certificate family used by the exact LP solver.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
Formal statement
theorem Lax109476Proofs.RamCertificateFamilies.optimal_spec : ∀ (B M m n : ℕ) (P : Lax109476.LinearProgram.Program ℤ m n),
1 ≤ M →
M < B →
m * n + 2 * m + 2 * n + 8 < B →
(m + (n + 2)) * (n + m) + (m + (n + 2)) + (n + m) + 4 < B →
(∀ (i : Fin m) (j : Fin n), (P.A i j).natAbs ≤ M) →
(∀ (i : Fin m), (P.b i).natAbs ≤ M) →
(∀ (j : Fin n), (P.c j).natAbs ≤ M) →
Lax808846Proofs.Reasoning.Spec B (Lax109476Proofs.RamCertificateFamilies.Input P (m + (n + 2)) (n + m))
Lax109476Proofs.RamCertificateFamilies.optimal
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamCertificateSource.Data P τ ∧
Lax109476Proofs.RamEquationData.Data (Lax109476Proofs.CertificateFamilyPrograms.optimal P) τ)
(142 * ((m + (n + 2)) * (n + m)) + 98 * (m + (n + 2)) + 72) := by sorrySource