Computational experience with an interior point algorithm on the satisfiability problem

DOI10.1007/BF02283686zbMath0716.90083OpenAlexW1571307015MaRDI QIDQ753688

K. G. Ramakrishnan, Mauricio G. C. Resende, Narendra K. Karmarkar, Anil P. Kamath

Publication date: 1990

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02283686

zbMATH Keywords

satisfiability probleminterior point algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Linear programming (90C05) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach, The state of SAT, Matrix representation and gradient flows for NP-hard problems, An approach to guided learning of Boolean functions, Potential reduction algorithms for structured combinatorial optimization problems, A potential reduction approach to the frequency assignment problem, On the minimum number of logical clauses inferred from examples, Differential approximation of MIN SAT, MAX SAT and related problems, A BDD SAT solver for satisfiability testing: An industrial case study, Some pitfalls for experimenters with random SAT, The \(Multi\)-SAT algorithm, Experimental complexity analysis of continuous constraint satisfaction problems., A continuous approach to inductive inference, An intelligent algorithm for mixed-integer programming models, Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid, Solving satisfiability problems using elliptic approximations -- effective branching rules, New methods for computing inferences in first order logic, Interior-point algorithms for global optimization, Generating logical expressions from positive and negative examples via a branch-and-bound approach, Differential approximation for optimal satisfiability and related problems

Uses Software

• MINOS

Cites Work

• Unnamed Item
• Modeling and integer programming techniques applied to propositional calculus
• Resolution vs. cutting plane solution of inference problems: Some computational experience
• Some results and experiments in programming techniques for propositional logic
• An interior point algorithm to solve computationally difficult set covering problems
• Branch-and-cut solution of inference problems in propositional logic
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• A mathematical programming approach to inference with the capability of implementing default rules
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures
• A method for the solution of certain non-linear problems in least squares