Name
Title | ||
|---|---|---|
Computational experience with an interior point algorithm on the satisfiability problem |
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. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1007/BF02283686 | Annals of Operations Research |
Keywords | Field | DocType |
Integer programming,interior point method,logic,satisfiability | Discrete mathematics,Mathematical optimization,Boolean satisfiability problem,Satisfiability,Algorithm,Integer programming,Karmarkar's algorithm,Linear programming relaxation,Interior point method,MINOS,Mathematics | Conference |
Volume | Issue | Citations |
25 | 1-4 | 31 |
PageRank | References | Authors |
10.12 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anil P. Kamath | 1 | 31 | 10.12 |
| Narendra Karmarkar | 2 | 1670 | 490.93 |
| K. G. Ramakrishnan | 3 | 587 | 98.53 |
| Mauricio G. C. Resende | 4 | 3729 | 336.98 |