Template-type: ReDif-Paper 1.0
Author-Name: Koster Arie M.C.A.
Author-Name: Hoesel Stan P.M. van
Author-Name: Kolen Antoon W.J.
Author-workplace-name: METEOR
Title: The partial constraint satisfaction problem : facets and lifting theorems
Abstract: 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.
Keywords: mathematical applications; 
Series: Research Memoranda
Creation-Date: 1997
Number: 004
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:ba994447-9350-400f-bbe0-9d6557aadee8/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 267473
Handle: RePEc:unm:umamet:1997004