A polyhedral approach to maximum 2-satisfiability
William H. Cunningham, Joseph Cheriyan, Levent Tunçel, Y. Wang · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
The maximum 2-satisfiability problem is: Given Boolean variables and a list of clauses of length one or two, to find values for the variables so as to maximize the number (or weight) of satisfied clauses. We will describe some linear programming bounds, in particular some classes of inequalities for which the separation problem can be solved efficiently, and some other polyhedral results for this problem.