Solving partial constraint satisfaction problems with tree decomposition

被引:39
作者
Koster, AMCA
van Hoesel, SPM
Kolen, AWJ
机构
[1] Konrad Zuse Zentrum Informat Tech Berlin, D-14195 Berlin, Germany
[2] Maastricht Univ, Dept Quantitat Econ, NL-6200 MD Maastricht, Netherlands
关键词
tree decomposition; partial constraint satisfaction; frequency assignment; MAX-SAT; dynamic programming;
D O I
10.1002/net.10046
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we describe a computational study to solve hard partial constraint satisfaction problems (PCSPs) to optimality. The PCSP is a general class of problems that contains a diversity of problems, such as generalized subgraph problems, MAX-SAT, Boolean quadratic programs, and assignment problems like coloring and frequency planning. We present a dynamic programming algorithm that solves PCSPs based on the structure (tree decomposition) of the underlying constraint graph. With the use of dominance and bounding techniques, we are able to solve small and medium-size instances of the problem to optimality and to obtain good lower bounds for large-size instances within reasonable time and memory limits. (C) 2002 Wiley Periodicals, Inc.
引用
收藏
页码:170 / 180
页数:11
相关论文
共 17 条
[1]  
Aardal K., 1996, 96011 MAASTR U
[2]  
Aardal K., 2001, Tech Report 01-40, ZIB
[3]  
AARDAL KI, IN PRESS OPER RES
[4]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[5]   COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].
ARNBORG, S ;
CORNEIL, DG ;
PROSKUROWSKI, A .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284
[6]  
Bodlaender H. L., 1993, Acta Cybernetica, V11, P1
[7]   A linear-time ie algorithm for finding three-decompositions of small treewidth [J].
Bodlaender, HL .
SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1305-1317
[8]  
Eisenblatter A., 2000, FAP WEB WEBSITE DEVO
[9]  
FEREMANS C, 2001, THESIS U LIBRE BRUXE
[10]  
HURKENS CAJ, 1995, 9534 COSOR EINDH U T