General
This site provides supporting material for the paper Verifying a Solver for Linear Mixed Integer Arithmetic in Isabelle/HOL by Ralph Bottesch, Max W. Haslbeck, Alban Reynaud and René Thiemann.Generated Haskell code
Archive fileThe .tar.gz archive contains the generated Haskell code. The generated code doesn't have any dependencies and is compilable with an up to date Haskell environment. The archive also contains the Isabelle .thy files which were used to generate the Haskell code.
Links to Lemmas, Definitions, etc. in the Isabelle Source Code
- lemma small_mixed_integer_solution
- lemma fundamental_theorem_of_linear_inequalities
- lemma Caratheodory_theorem
- lemma farkas_minkowsky_weyl_theorem
- lemma decomposition_theorem_polyhedra
- lemma decomposition_theorem_polyhedra_1
- lemma farkas_minkowsky_weyl_theorem_1
- lemma small_integer_solution_nonstrict_via_decomp
- lemma expand_to_basis
- lemma Farkas_Lemma
- lemma Farkas_Lemma'
- function bnb
- lemma brach_and_bound_sat
- lemma banch_and_bound_unsat
- definition branch_and_bound
- lemma compute_bound
- lemma branch_and_bound
Experimental Results
The experiments have been conducted as follows.
- Testing was done on a subset of the non-incremental QF_LIA (quantifier-free linear integer arithmetic) benchmark set from SMT-LIB.
- 1192 benchmarks, comprising 18% of 6489 benchmarks in QF_LIA, were converted to a format that is readable by our solver. Specifically, the sub-folders 20180326-Bromberger, miplib2003, pb2010, pidgeons, prime-cone, and slacks from QF_LIA were fully converted. All solvers were tested on this set of benchmarks.
- Each solver was given 60s per test on the same hardware.
- Z3 version 4.4.0pre-2, CVC4 version 1.5-4, and the 2019-05-09 release of SMT-LIB were used.
Both tables display the execution times in seconds of our experiments. Satisfiable answers of the verified solvers have been converted back so that variable names of the original SMT-LIB benchmarks are used.
The first table is a selection of only those experiments where one of our verified solvers was successful, but at least one of Z3 or CVC4 failed.
The second table contains all our experiments.