1 Search Results for "Zheng, Kexin"


Document
FastMapSVM for Predicting CSP Satisfiability

Authors: Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)


Abstract
Recognizing the satisfiability of Constraint Satisfaction Problems (CSPs) is NP-hard. Although several Machine Learning (ML) approaches have attempted this task by casting it as a binary classification problem, they have had only limited success for a variety of challenging reasons. First, the NP-hardness of the task does not make it amenable to straightforward approaches. Second, CSPs come in various forms and sizes while many ML algorithms impose the same form and size on their training and test instances. Third, the representation of a CSP instance is not unique since the variables and their domain values are unordered. In this paper, we propose FastMapSVM, a recently developed ML framework that leverages a distance function between pairs of objects. We define a novel distance function between two CSP instances using maxflow computations. This distance function is well defined for CSPs of different sizes. It is also invariant to the ordering on the variables and their domain values. Therefore, our framework has broader applicability compared to other approaches. We discuss various representational and combinatorial advantages of FastMapSVM. Through experiments, we also show that it outperforms other state-of-the-art ML approaches.

Cite as

Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar. FastMapSVM for Predicting CSP Satisfiability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.CP.2023.40,
  author =	{Zheng, Kexin and Li, Ang and Zhang, Han and Kumar, T. K. Satish},
  title =	{{FastMapSVM for Predicting CSP Satisfiability}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.40},
  URN =		{urn:nbn:de:0030-drops-190775},
  doi =		{10.4230/LIPIcs.CP.2023.40},
  annote =	{Keywords: Constraint Satisfaction Problems, Machine Learning, FastMapSVM}
}
  • Refine by Author
  • 1 Kumar, T. K. Satish
  • 1 Li, Ang
  • 1 Zhang, Han
  • 1 Zheng, Kexin

  • Refine by Classification
  • 1 Computing methodologies → Machine learning

  • Refine by Keyword
  • 1 Constraint Satisfaction Problems
  • 1 FastMapSVM
  • 1 Machine Learning

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail