1 Search Results for "Lee, Jimmy H. M."

Document
DOI: 10.4230/LIPIcs.CP.2022.31
Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization

Authors: Jimmy H. M. Lee and Allen Z. Zhong

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Dominance breaking is an effective technique to reduce the time for solving constraint optimization problems. Lee and Zhong propose an automatic dominance breaking framework for a class of constraint optimization problems based on specific forms of objectives and constraints. In this paper, we propose to enhance the framework for problems with nested function calls which can be flattened to functional constraints. In particular, we focus on aggregation functions and exploit such properties as monotonicity, commutativity and associativity to give an efficient procedure for generating effective dominance breaking nogoods. Experimentation also shows orders-of-magnitude runtime speedup using the generated dominance breaking nogoods and demonstrates the ability of our proposal to reveal dominance relations in the literature and discover new dominance relations on problems with ineffective or no known dominance breaking constraints.
Cite as

Jimmy H. M. Lee and Allen Z. Zhong. Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.CP.2022.31,
  author =	{Lee, Jimmy H. M. and Zhong, Allen Z.},
  title =	{{Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.31},
  URN =		{urn:nbn:de:0030-drops-166607},
  doi =		{10.4230/LIPIcs.CP.2022.31},
  annote =	{Keywords: Constraint Optimization Problems, Dominance Breaking}
}
  • Refine by Author
  • 1 Lee, Jimmy H. M.
  • 1 Zhong, Allen Z.

  • Refine by Classification
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Constraint Optimization Problems
  • 1 Dominance Breaking

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact