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.

Representative Publications on Minimum (Weighted) Vertex Covers

- H. Xu, K. Sun, S. Koenig and S. Kumar. A Warning Propagation-Based Linear-Time-and-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs. In
*Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR),*567-584, 2018.**[downloadable]** - M. Nakajima, H. Xu, S. Koenig and S. Kumar. Towards Understanding the Min-Sum Message Passing Algorithm for the Minimum Weighted Vertex Cover Problem: An Analytical Approach. In
*Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM),*2018.**[downloadable]** - H. Xu, X.-Z. Wu, C. Cheng, S. Koenig and S. Kumar. The Buss Reduction for the k-Weighted Vertex Cover Problem. In
*Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM),*2018.**[downloadable]** - H. Xu, S. Kumar and S. Koenig. A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs [Short Paper]. In
*Proceedings of the Symposium on Combinatorial Search (SoCS),*173-175, 2017.**[downloadable]** - H. Xu, S. Kumar and S. Koenig. A New Solver for the Minimum Weighted Vertex Cover Problem. In
*Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR),*392-405, 2016.**[downloadable]**

Representative Publications on (Weighted) CSPs

- H. Xu, S. Koenig and S. Kumar. Towards Effective Deep Learning for Constraint Satisfaction Problems. In
*Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP),*588-597, 2018.**[downloadable]** - H. Xu, C. Cheng, S. Koenig and S. Kumar. Message Passing Algorithms for Semiring-Based and Valued Constraint Satisfaction Problems. In
*Proceedings of the Symposium on Combinatorial Search (SoCS),*115-123, 2018.**[downloadable]** - H. Xu, S. Koenig and S. Kumar. A Constraint Composite Graph-Based ILP Encoding of the Boolean Weighted CSP. In
*Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP),*630-638, 2017.**[downloadable]** - H. Xu, S. Kumar and S. Koenig. The Nemhauser-Trotter Reduction and Lifted Message Passing for the Weighted CSP. In
*Proceedings of the International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR),*387-402, 2017.**[downloadable]** - H. Xu, S. Kumar and S. Koenig. Min-Max Message Passing and Local Consistency in Constraint Networks. In
*Proceedings of the Australasian Joint Conference on Artificial Intelligence (AI),*340-352, 2017.**[downloadable]** - S. Kumar, L. Cohen and S. Koenig. Submodular Constraints and Planar Constraint Networks: New Results. In
*Proceedings of the Symposium on Abstraction, Reformulation, and Approximation (SARA),*2013.**[downloadable]**

Representative Publications on DCSPs

- S. Kumar, D. Nguyen, W. Yeoh and S. Koenig. A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints. In
*Proceedings of the AAAI Conference on Artificial Intelligence (AAAI),*2308-2314, 2014.**[downloadable]**

Representative Publications on DCOPs

- F. Fioretto, H. Xu, S. Koenig and S. Kumar. Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph. In
*Proceedings of the International Conference on Principles and Practice of Multi-Agent Systems (PRIMA),*106-122, 2018.**[downloadable]** - W. Yeoh, P. Varakantham, X. Sun and S. Koenig. Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems. In
*Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT),*257-264, 2015.**[downloadable]** - W. Yeoh, A. Felner and S. Koenig. BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm.
*Journal of Artificial Intelligence Research,*38, 85-133, 2010.**[downloadable]** - W. Yeoh, X. Sun and S. Koenig. Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms. In
*Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI),*354-360, 2009.**[downloadable]** - W. Yeoh, P. Varakantham and S. Koenig. Caching Schemes for DCOP Search Algorithms. In
*Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS),*609-616, 2009.**[downloadable]** - W. Yeoh, R. Zivan and S. Koenig. Discrepancy-Based Approach for Solving Distributed Constraint Optimization Problems. In
*Proceedings of the International Workshop on Distributed Constraint Reasoning (DCR),*132-144, 2009.**[downloadable]** - W. Yeoh, A. Felner and S. Koenig. BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm. In
*Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS),*591-598, 2008.**[downloadable]** - W. Yeoh, S. Koenig and A. Felner. IDB-ADOPT: A Depth-First Search DCOP Algorithm. In
*Proceedings of the International Workshop on Distributed Constraint Reasoning (DCR),*60-70, 2007.**[downloadable]** - S. Ali, S. Koenig and M. Tambe. Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT. In
*Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS),*1041-1048, 2005.**[downloadable]**

Representative Publications on Pseudo-Boolean Optimization

- K. Yip, H. Xu, S. Koenig and S. Kumar. Quadratic Reformulation of Nonlinear Pseudo-Boolean Functions via the Constraint Composite Graph. In
*Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR),*(in print), 2019.**[downloadable]**

Dissertations

- W. Yeoh. Speeding up Distributed Constraint Optimization Search Algorithms. PhD thesis, Department of Computer Science, University of Southern California, Los Angeles (California), 2010.
**[downloadable]**

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.