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.
- ~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 Scholar
- ~BEV, GE, C. 1972. Balanced matrices. Math. Prog. 2, 19-31.Google Scholar
- ~CItANDRU, V., HOOKER, J.N. 1991. Extended Horn sets in propositional logic. J. ACM 38, 1 ~(Jan.), 205-22t. Google Scholar
- ~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 Scholar
- ~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 Scholar
- ~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 Scholar
- ~DANTZIG, G.B. 1963. Linear Programming and Extensions. Princeton University Press, Prince- ~ton, N.J.Google Scholar
- ~FULKERSON, D. R., HOFFMAN, A., AND HOPPENHE1M, R. 1974. On balanced matrices. Math. ~Prog. Study 1, 120-132.Google Scholar
- ~HOOKER, J. N. 1988. A quantitative approach to logical inference. Dectsion Sttpp. Syst. 4, ~45-69. Google Scholar
- ~SCHRIJVER, A. 1986. Theory of Linear and I~teger Programming. Wiley, New York. Google Scholar
- ~TRUEMPER, K. 1982. Alpha-balanced graphs and matrices and GF(3)-representability of ma- ~troids. J Combitz. Theory B 32, 112-139.Google Scholar
- ~TRUEMPER, K. 1990. Polynomial theorem proving I. Central matrices. Tech. Rep. UTDCS ~34-90. Univ. Texas at Dallas, Dallas, Tex.Google Scholar
Index Terms
A class of logic problems solvable by linear programming
Recommendations
A class of logic problems solvable by linear programming
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer ScienceSeveral problems of propositional logic, such as satisfiability, MAXSAT and logical inference, can be formulated as integer programs. The authors consider sets of clauses for which these integer programs can be solved as linear programs. They prove that ...
Transformation of a multi-choice linear programming problem
The aim of this paper is to transform a multi-choice linear programming problem to a standard mathematical programming problem where the right hand side goals of some constraints are 'multi-choice' in nature. For each of the constraint there may exist ...
Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices
We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate ...
Comments