A CLASS OF LOGIC PROBLEMS SOLVABLE BY LINEAR-PROGRAMMING

Authors
CONFORTI M CORNUEJOLS G
Citation
M. Conforti et G. Cornuejols, A CLASS OF LOGIC PROBLEMS SOLVABLE BY LINEAR-PROGRAMMING, Journal of the Association for Computing Machinery, 42(5), 1995, pp. 1107-1113
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
42
Issue
5
Year of publication
1995
Pages
1107 - 1113
Database
ISI
SICI code
Abstract
In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In t his paper, we consider sets of clauses for which the corresponding int eger programs can be solved as linear programs. We prove that balanced sets of clauses have this property.