×

Linear programs for constraint satisfaction problems. (English) Zbl 0920.90106

Summary: A novel representation is described that models some important NP-hard problems, such as the propositional satisfiability problem (SAT), the Traveling Salesperson Problem (TSP), the Quadratic Assignment Problem (QAP), and the Minimal Set Covering Problem (MSCP) by means of only two types of constraints: ‘choice constraints’ and ‘exclusion constraints’. In its main section the paper presents an approach for solving an \(m\)-CNF-SAT problem (Conjunctive Normal Form Satisfaction: \(n\) variables, \(p\) clauses, clause length \(m\)) by integer programming. The approach is unconventional, because \(2n\) distinct 0-1 variables are used for each clause of the \(m\)-CNF-SAT problem. The constraint matrix \(A\) forces that for every clause exactly one 0-1 variable is set equal to 1 (choice constraint), and no two 0-1 variables, representing a literal and its complement, are both set equal to 1 (exclusion constraints). The particular \(m\)-CNF-SAT instance is coded in a cost vector, which serves for maximization of the number of satisfied clauses. The paper presents a modification of the simplex for solving the obtained integer program. A main theorem of the paper is that this algorithm always finds a 0-1 integer solution. A solution of the integer program corresponds to a solution of the \(m\)-CNF-SAT and vice versa. The results of significant experimental tests are reported, and the procedure is compared to other approaches. The same modelling technique is then used for the traveling salesperson problem, for the minimal set covering, and for the quadratic assignment problem: it is shown that a uniform approach is thus useful.

MSC:

90C10 Integer programming
90C27 Combinatorial optimization
90C09 Boolean programming
90C05 Linear programming

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphs (1985), North-Holland: North-Holland Amsterdam · Zbl 0334.05117
[2] Berge, C., Hypergraphs (1989), North-Holland: North-Holland Amsterdam · Zbl 0334.05117
[3] Bixby, R. E., Matroids and operations research, (Greenberg, H.; Murphy, F.; Show, S., Advanced Techniques in Operations Research (1982), North Holland: North Holland Amsterdam) · Zbl 0314.05106
[4] Cook, S. A., The complexity of theorem proving procedures, (Proceedings 3rd annual ACM Symposium on the Theory of Computing (1971)) · Zbl 0363.68125
[5] Davis, M.; Putnam, H., A computing procedure for quantification theory, Journal of the ACM, 8, 201-215 (1960) · Zbl 0212.34203
[6] Franco, J.; Paull, M., Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem, Discrete Applied Mathematics, 5, 77-87 (1983) · Zbl 0497.68021
[7] Garey, M. R.; Johnson, D. S., Computer and Intractability (1979), Freeman: Freeman San Francisco
[8] Gent, I. P.; Walsh, T., Easy problems are sometimes hard, Artificial Intelligence, 70, 1-2, 335-345 (1994) · Zbl 0824.68107
[9] Hoffman, A. J.; Kruskam, J. B., Integral boundary points of convex polyhedra, (Kuhn, H. W.; Tucker, A. W., Linear Inequalities and Related Systems (1956), Princeton University Press: Princeton University Press Princeton, NJ)
[10] Hopcroft; Karp, R., The matching problem for bipartite graphs, SIAM Journal of Computing (1973)
[11] Jeroslow, R. G.; Wang, J., Solving propositional satisfiability problems, (Golumbic, M. C., Annals of Mathematics and Artificial Intelligence (1990), Baltzer, Scientific Basel: Baltzer, Scientific Basel Switzerland) · Zbl 0878.68107
[12] Karmarkar, N., A new polynomial time algorithm for linear programming, (Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984)) · Zbl 0557.90065
[13] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatches, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York) · Zbl 0366.68041
[14] Khachian, L. G., A polynomial algorithm for linear programming, Soviet Mathematics Dklady (1979)
[15] Laporte, G., Recent algorithmic developments for the traveling salesman problem and the vehicle routing problem, Ricerca Operativa, 68, 5-28 (1993)
[16] Loveland, D. W., Automated Theorem Proving: a Logical Basis (1978), North-Holland: North-Holland Amsterdam · Zbl 0364.68082
[17] Mackworth, A. K., The logic of constraint satisfaction, Artificial Intelligence, 58, 1-3, 3-20 (1992) · Zbl 0782.68104
[18] Mackworth, A. K.; Freuder, E. C., Special volume on “Constraint-based reasoning”, Artificial Intelligence, 58, 1-3 (1992)
[19] Mitchell, D.; Selman, B.; Levesque, H., Hard and easy distributions for SAT problems, (Proceedings of the 10th National Conference on Artificial Intelligence (1992), AAAI), 459-465
[20] Monfroglio, A., Integer programs for logic constraint satisfaction, Theoretical Computer Science, 100 (1992) · Zbl 0764.90063
[21] Monfroglio, A., Hybrid genetic algorithms for constraint satisfaction, (Proceedings A.ICA. Conference. Proceedings A.ICA. Conference, Turin, Italy (1992)), 803-820
[22] Monfroglio, A., Logic decisions under constraints, Decision Support Systems, 11 (1993)
[23] Nevins, A. J., A human oriented logic for automatic theoremproving, Journal of the ACM, 21, 606-621 (1974) · Zbl 0332.68061
[24] Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), (Proceedings of the 14th Annual ACM Symposium on Theory of Computing. Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco (1982)) · Zbl 0571.68028
[25] Parker, R. G.; Rardin, R. L., Discrete Optimization (1988), Academic Press: Academic Press San Diego, CA · Zbl 0652.90068
[26] Reinelt, G., The Traveling Salesman (1994), Springer-Verlag: Springer-Verlag Berlin · Zbl 0825.90720
[27] Salkin, H. M.; Mathur, K., Foundations of Integer Programming (1989), North-Holland: North-Holland New York · Zbl 0683.90042
[28] Seymour, P. D., Decomposition of regular matroids, Journal of Combinatorial Theory (1980) · Zbl 0443.05027
[29] Simonis, D., Propositional calculus problems in CHIP, (Proceedings of the 2nd International Conference on Algebraic and Logic Programming (1990), LNCS, Springer-Verlag: LNCS, Springer-Verlag Nancy) · Zbl 1493.68077
[30] Van Hentenryck, P., Constraint Satisfaction in Logic Programming (1989), MIT Press: MIT Press Cambridge, MA
[31] Veinott, A. F.; Dantzig, G. B., Integral extreme points, SIAM Review, 10 (1968) · Zbl 0162.33401
[32] Welsh, D., Matroid Theory (1976), Academic Press: Academic Press New York · Zbl 0343.05002
[33] Ye, Y., A build-down scheme for linear programming, Mathematical Programming, 46, 61-72 (1990) · Zbl 0698.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.