skip to main content
article
Free Access

A class of logic problems solvable by linear programming

Published:01 September 1995Publication History
Skip Abstract Section

Abstract

In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property.

References

  1. ~BERGE, C. 1970. Sur certains hypergraphes gdndralisant les graphes bipartltes. In Combinato- ~rial Theory and its Applications I, P. Erd6s, A. R~nyi and V. S6s eds. Colloq. Math. Soc. Jcinos ~Bolyat vol. 4. North-Holland, Amsterdam, The Netherlands, 119-133.Google ScholarGoogle Scholar
  2. ~BEV, GE, C. 1972. Balanced matrices. Math. Prog. 2, 19-31.Google ScholarGoogle Scholar
  3. ~CItANDRU, V., HOOKER, J.N. 1991. Extended Horn sets in propositional logic. J. ACM 38, 1 ~(Jan.), 205-22t. Google ScholarGoogle Scholar
  4. ~CONFOr, TI, M., COr~4U~JOLS, AND RAO, M.R. 1991. Decomposition of balanced matrices, Parts ~I-VII, preprints. MSRR 569-575, GSIA, Carnegie-Mellon Univ. Pittsburgh, Pa.Google ScholarGoogle Scholar
  5. ~CONFORTI, M., CORNUEJOLS, G., KAPOOR, A., AND VUSKOVIC, K. 1994a. Balanced 0, _+ 1 ~matrices, Parts I, II, preprints. GSIA, Carnegie-Mellon Univ. Pittsburgh, Pa.Google ScholarGoogle Scholar
  6. ~CONFORTI, M., CORNUEJOLS, G., KAPOOR, A., RAO, M. R., VUSKOVIC, K. 1994b. Balanced ~matrices. In Mathematical Pt'ogrammztzg: State of the Art 1994, J. R. Birge and K. G. Murty eds. ~Univ. Michigan, pp, 1-33.Google ScholarGoogle Scholar
  7. ~DANTZIG, G.B. 1963. Linear Programming and Extensions. Princeton University Press, Prince- ~ton, N.J.Google ScholarGoogle Scholar
  8. ~FULKERSON, D. R., HOFFMAN, A., AND HOPPENHE1M, R. 1974. On balanced matrices. Math. ~Prog. Study 1, 120-132.Google ScholarGoogle Scholar
  9. ~HOOKER, J. N. 1988. A quantitative approach to logical inference. Dectsion Sttpp. Syst. 4, ~45-69. Google ScholarGoogle Scholar
  10. ~SCHRIJVER, A. 1986. Theory of Linear and I~teger Programming. Wiley, New York. Google ScholarGoogle Scholar
  11. ~TRUEMPER, K. 1982. Alpha-balanced graphs and matrices and GF(3)-representability of ma- ~troids. J Combitz. Theory B 32, 112-139.Google ScholarGoogle Scholar
  12. ~TRUEMPER, K. 1990. Polynomial theorem proving I. Central matrices. Tech. Rep. UTDCS ~34-90. Univ. Texas at Dallas, Dallas, Tex.Google ScholarGoogle Scholar

Index Terms

  1. A class of logic problems solvable by linear programming

                Recommendations

                Reviews

                Joseph M. Lambert

                The logic problems considered in this paper are the classical satisfiability problem, the weighted maximum satisfiability problem<__?__Pub Caret>, the weighted exact satisfiability problem, and the logical inference problem. In their complete generality, these problems are known to be NP-hard. NP-hard problems are at least as hard as any problem in NP, the problems whose solutions can be checked in polynomial time, but whose solutions have not yet been found in polynomial time. Each of the problems listed above can be reformulated as an integer program of the form min cx: Ax?w , where the elements of the matrix A come from the set -1,0,1 . A , a matrix of the above form, is said to be balanced if, for every submatrix of A with exactly two nonzero elements per row and per column, the sum of the elements is a multiple of four. When A is balanced, each of the above problems is solvable as a linear program. In other words, the authors have expanded the collection of cases for which the problems listed above can be solved in polynomial time. This paper may interest those interested in computational complexity. Those interested in balanced matrices may see additional applications. This is a theoretical paper and will not be of direct value to a practitioner attempting to gain new insights into integer or linear programming. There are about ten references, with those later than 1990 being previous works of the authors and their colleagues.

                Access critical reviews of Computing literature here

                Become a reviewer for Computing Reviews.

                Comments

                Login options

                Check if you have access through your login credentials or your institution to get full access on this article.

                Sign in

                Full Access

                PDF Format

                View or Download as a PDF file.

                PDF

                eReader

                View online with eReader.

                eReader