MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability

Artificial Intelligence - Tập 164 - Trang 47-80 - 2005
Zhao Xing1, Weixiong Zhang1
1Department of Computer Science and Engineering, Washington University in Saint Louis, Saint Louis, MO 63130, USA

Tài liệu tham khảo

Aloul, 2002, Generic ILP versus specialized 0-1 ILP: an update

Alsinet, 2003, Improved branch and bound algorithms for Max-SAT

Blair, 1986, Some results and experiments in programming techniques for prepositional logic, Comput. Oper. Res., 13, 633, 10.1016/0305-0548(86)90056-0

Borchchers, 1999, A two-phase exact algorithm for Max-SAT and weighted Max-SAT problems, J. Combin. Optim., 2, 299, 10.1023/A:1009725216438

Cook, 1971, The complexity of theorem-proving procedures, 151

Coppersmith, 2003, Random MAX SAT, random MAX CUT, and their phase transitions, 364

Crawford, 1993, Experimental results on the crossover point in satisfiability problems, 21

Dantzig, 1997

Davis, 1962, A machine program for theorem proving, C. ACM, 5, 394, 10.1145/368273.368557

Davis, 1960, A computing procedure for quantification theory, J. ACM, 7, 201, 10.1145/321033.321034

Dixon, 2002, Inference methods for a pseudo-boolean satisfiability solver, 635

J.W. Freeman, Improvements to propositional satisfiability search algorithms, PhD thesis, Univ. of Pennsylvania, 1995

Freuder, 1992, Partial constraint satisfaction, Artificial Intelligence, 58, 21, 10.1016/0004-3702(92)90004-H

Garey, 1979

Gill, 1986, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Programming, 26, 183, 10.1007/BF02592025

Givry, 2003, Solving Max-SAT as weighted CSP, 363

Hammer, 1984, Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. Programming, 28, 121, 10.1007/BF02612354

Hammer, 1968

Hansen, 1990, Algorithm for the maximum satisfiability problem, Computing, 44, 279, 10.1007/BF02241270

Hillier, 2001

Hooker, 1989, Input proofs and rank one cutting-planes, ORSA J. Comput, 1, 137, 10.1287/ijoc.1.3.137

Hooker, 1990, Branch-and-cut solution of inference problems in prepositional logic, Ann. Math. Artificial Intelligence, 1, 123, 10.1007/BF01531074

Hooker, 1995, Branching rules for satisfiability, J. Automated Reasoning, 15, 359, 10.1007/BF00881805

Hoos

Johnson, 1974, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256, 10.1016/S0022-0000(74)80044-9

Joy, 1997, A branch and cut algorithm for Max-SAT and weighted Max-SAT, 519

Karp, 1992, Reducibility among combinatorial problems, 85

Li, 1997, Heuristics based on unit propagation for satisfiability problems, 366

Liu, 1968

McAllester, 1997, Evidence for invariants in local search, 321

Mitchell, 1993, Hare and easy distributions of SAT problems, 459

Moskewics, 2001, Chaff: engineering an efficient SAT solver

Niedermeier, 2000, New upper bounds for maximum satisfiability, J. Algorithm, 36, 63, 10.1006/jagm.2000.1075

Park, 2002, Using weighted MAX-SAT engines to solve MPE, 682

B. Selman, Mwff: Program for generating random max k-SAT instances, Available from DIMACS

Selman, 1994, Noise strategies for local search, 337

Shen, 2002, Study of lower bound functions for Max-2-SAT, 185

Shen, 2003, An empirical study of Max-2-SAT phase transitions

Spielman, 2004, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM, 51, 385, 10.1145/990308.990310

Wallace, 1996, Enhancing maximum satisfiability algorithms with pure literal strategies

Wallace, 1996, Comparative study of constraint satisfaction and Davis–Putnam algorithms for maximum satisfiability problems, 587

Walser, 1999

Xing, 2004, Efficient strategies for (weighted) maximum satisfiability, 690

Zhang, 2003, Exact algorithms for Max-SAT

Zhang, 2001, Phase transitions and backbones of 3-SAT and maximum 3-SAT, 155

Thông tin
Thông tin xuất bản

Artificial Intelligence

Tập 164

47-80

Thông tin tác giả