Project "Constraint Satisfaction and Optimization"
(scroll down for publications)

Constraint satisfaction problems (CSPs) require one to satisfy a set of given constraints, while constraint optimization problems (COPs) or, equivalently, weighted CSPs require one to minimize the total cost of the unsatisfied constraints. Constraint satisfaction and optimization problems can be solved either in a centralized or decentralized way, resulting in DCSPs (or, equivalently DisCSPs) and DCOPs (or, equivalently, DisCOPs). Methods for DCOPs, for example, have emerged as key techniques for distributed reasoning in multiagent domains. They are able to model the task of scheduling meetings in large organizations, where privacy needs make COPs problematic. They are also able to model the task of allocating sensor nodes to targets in sensor networks, where the limited communication and computation power of individual sensor nodes makes COPs problematic. Finally, they are able to model the task of coordinating teams of unmanned air vehicles, where the need for rapid local responses makes COPs problematic. Unfortunately, the application of CSP, DCSP, COP and DCOP algorithms faces significant hurdles due to their inefficiency. Solving them optimally is often NP-hard, yet one typically needs to find optimal solutions quickly. We therefore study how to speed these algorithms up in order to scale them up to larger problems than can be solved today. For example, we introduced a framework of preprocessing techniques that allowed us to reduce the runtime of ADOPT, a state-of-the-art DCOP algorithm, by one-order of magnitude. Our paper on "Decision-Tree Learning-Inspired Dynamic Variable Ordering for the Weighted CSP" won a Best Paper Honorable Mention at the International Symposium on Combinatorial Search 2020.

Representative Publications on Minimum (Weighted) Vertex Covers

Representative Publications on (Weighted) CSPs

Representative Publications on DCSPs

Representative Publications on DCOPs

Representative Publications on Pseudo-Boolean Optimization

Dissertations

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig