The partial constraint satisfaction problem : facets and lifting theorems

In this paper the partial constraint satisfaction problem (PCSP) is introduced and formulated as a {0,1}-programming problem. We define the partial constraint satisfaction polytope as the convex hull of feasible solutions for this programming problem. As examples of the class of problems studied we mention the frequency assignment problem and the maximum satisfiability problem. Lifting theorems are presented and some classes of facet-defining valid inequalities for PCSP are given. Computational results show that these valid inequalities reduce the gap between LP-value and IP-value substantially.