Solving partial constraint satisfaction problems with tree decomposition.

*(English)*Zbl 1027.90072Summary: 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.

##### MSC:

90C27 | Combinatorial optimization |

90C35 | Programming involving graphs or networks |

90C39 | Dynamic programming |

90B80 | Discrete location and assignment |

##### Keywords:

tree decomposition; partial constraint; satisfaction; frequency assignment; MAX-SAT; dynamic programming
PDF
BibTeX
XML
Cite

\textit{A. M. C. A. Koster} et al., Networks 40, No. 3, 170--180 (2002; Zbl 1027.90072)

Full Text:
DOI

##### References:

[1] | and A branch-and-cut algorithm for the frequency assignment problem, Research Memorandum 96/011, Maastricht University, 1996. Available at http://www-edocs.unimaas.nl/abs/rm96011.htm. |

[2] | Aardal, Oper Res |

[3] | and Models and solution techniques for the frequency assignment problem, ZIB-report 01-40, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2001. Available at http://www.zib.de/PaperWeb/abstracts/ZR-01-40/. |

[4] | Arnborg, SIAM J Alg Discr Methods 8 pp 277– (1987) |

[5] | Bodlaender, Acta Cybernet 11 pp 1– (1993) |

[6] | Bodlaender, SIAM J Comput 25 pp 1305– (1996) |

[7] | The second DIMACS implementation challenge: ??-hard problems: Maximum clique, graph coloring, and satisfiability; see http://dimacs.rutgers.edu/Challenges/ or http://mat.gsia.cmu.edu/challenge.html, 1992- 1993. |

[8] | and FAP web?A website devoted to frequency assignment. URL: http://fap.zib.de, 2000. |

[9] | Generalized spanning trees and extensions, Ph.D. Thesis, Université Libre de Bruxelles, 2001. Available at http://smg.ulb.ac.be/Theses/Theses.html. |

[10] | and Computers and intractability: A guide to the theory of ??-completeness, Freeman, New York, 1979. · Zbl 0411.68039 |

[11] | and Upper and lower bounding techniques for frequency assignment problems, Technical Report COSOR 95-34, Eindhoven University of Technology, 1995. Available at ftp://ftp.win.tue.nl/pub/techreports/cosor/. |

[12] | A genetic algorithm for frequency assignment, Technical report, Maastricht University, 1999. |

[13] | Frequency assignment?Models and algorithms, Ph.D. Thesis, Maastricht University, 1999. Available at http://www.zib.de/koster/. |

[14] | Koster, Oper Res Lett 23 pp 89– (1998) |

[15] | and Solving frequency assignment problems via tree-decomposition, Technical Report RM 99/011, Maastricht University, 1999. Available at http://www.zib.de/koster/. · Zbl 1038.90086 |

[16] | Padberg, Math Program 45 pp 139– (1989) |

[17] | Robertson, J Alg 7 pp 309– (1986) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.