Premium
Solving partial constraint satisfaction problems with tree decomposition
Author(s) -
Koster Arie M. C. A.,
van Hoesel Stan P. M.,
Kolen Antoon W. J.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10046
Subject(s) - bounding overwatch , constraint satisfaction problem , mathematical optimization , decomposition method (queueing theory) , constraint satisfaction , constraint programming , mathematics , tree decomposition , decomposition , computer science , constraint (computer aided design) , graph , theoretical computer science , discrete mathematics , stochastic programming , artificial intelligence , probabilistic logic , ecology , pathwidth , line graph , biology , geometry
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. © 2002 Wiley Periodicals, Inc.