Computer Science – Logic in Computer Science
Scientific paper
2009-04-22
Computer Science
Logic in Computer Science
Scientific paper
We consider the decision problem for quantifier-free formulas whose atoms are linear inequalities interpreted over the reals or rationals. This problem may be decided using satisfiability modulo theory (SMT), using a mixture of a SAT solver and a simplex-based decision procedure for conjunctions. State-of-the-art SMT solvers use simplex implementations over rational numbers, which perform well for typical problems arising from model-checking and program analysis (sparse inequalities, small coefficients) but are slow for other applications (denser problems, larger coefficients). We propose a simple preprocessing phase that can be adapted on existing SMT solvers and that may be optionally triggered. Despite using floating-point computations, our method is sound and complete - it merely affects efficiency. We implemented the method and provide benchmarks showing that this change brings a naive and slow decision procedure ("textbook simplex" with rational numbers) up to the efficiency of recent SMT solvers, over test cases arising from model-checking, and makes it definitely faster than state-of-the-art SMT solvers on dense examples.
No associations
LandOfFree
On using floating-point computations to help an exact linear arithmetic decision procedure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On using floating-point computations to help an exact linear arithmetic decision procedure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On using floating-point computations to help an exact linear arithmetic decision procedure will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275550