caa a22 4500 465774350 CHVBK 20180323111937.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02283686 doi (NATIONALLICENCE)springer-10.1007/BF02283686 Computational experience with an interior point algorithm on the satisfiability problem [Elektronische Daten] [A. Kamath, N. Karmarkar, K. Ramakrishnan, M. Resende] 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. J.C. Baltzer A.G. Scientific Publishing Company, 1990 Integer programming nationallicence interior point method nationallicence logic nationallicence satisfiability nationallicence Kamath A. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Karmarkar N. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Ramakrishnan K. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Resende M. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 25/1(1990-12-01), 43-58 0254-5330 25:1<43 1990 25 10479 https://doi.org/10.1007/BF02283686 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02283686 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kamath A. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Karmarkar N. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Ramakrishnan K. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Resende M. Mathematical Sciences Research Center, AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 25/1(1990-12-01), 43-58 0254-5330 25:1<43 1990 25 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer