Computational experience with an interior point algorithm on the satisfiability problem |
| |
Authors: | A. P. Kamath N. K. Karmarkar K. G. Ramakrishnan M. G. C. Resende |
| |
Affiliation: | (1) Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| |
Abstract: | We apply the zero-one integer programming algorithm described in Karmarkar [12] and Karmarkar, Resende and Ramakrishnan [13] to solve randomly generated instances of the satisfiability problem (SAT). The interior point algorithm is briefly reviewed and shown to be easily adapted to solve large instances of SAT. Hundreds of instances of SAT (having from 100 to 1000 variables and 100 to 32,000 clauses) are randomly generated and solved. For comparison, we attempt to solve the problems via linear programming relaxation with MINOS. |
| |
Keywords: | Integer programming interior point method logic satisfiability |
本文献已被 SpringerLink 等数据库收录! |