Exploiting functional constraints in automatic dominance breaking for constraint optimization

Jimmy H.M. Lee, Allen Z. Zhong

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publication28th International Conference on Principles and Practice of Constraint Programming
EditorsChristine Solnon
Place of PublicationSaarbrücken/Wadern Germany
PublisherSchloss Dagstuhl
Number of pages17
ISBN (Electronic)9783959772402
DOIs
Publication statusPublished - 2022
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2022 - Haifa, Israel
Duration: 31 Jul 20228 Aug 2022
Conference number: 28th
https://cp2022.a4cp.org/ (Website)
http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://drops.dagstuhl.de/opus/volltexte/2022/16629/pdf/LIPIcs-CP-2022-0.pdf (Proceedings)

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl
Volume235
ISSN (Print)1868-8969

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2022
Abbreviated titleCP 2022
Country/TerritoryIsrael
CityHaifa
Period31/07/228/08/22
Internet address

Keywords

  • Constraint Optimization Problems
  • Dominance Breaking

Cite this