A Safe Computational Framework for Integer Programming applied to Chv\'atal's Conjecture
From MaRDI portal
Publication:6306293
DOI10.1145/3485630arXiv1809.01572WikidataQ113309852 ScholiaQ113309852MaRDI QIDQ6306293FDOQ6306293
Authors: Leon Eifler, Ambros M. Gleixner, Jonad Pulaj 
Publication date: 5 September 2018
Abstract: We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chv'atal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result, we are able to provide a first machine-assisted proof that Chv'atal's conjecture holds for all downsets whose union of sets contains seven elements or less.
This page was built for publication: A Safe Computational Framework for Integer Programming applied to Chv\'atal's Conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6306293)
