Document Open Access Logo

Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization

Authors Jimmy H. M. Lee , Allen Z. Zhong

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.31.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Author Details

Jimmy H. M. Lee
  • Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, China
Allen Z. Zhong
  • Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, China

Funding

We acknowledge the financial support of a General Research Fund (RGC Ref. No. CUHK 14206321) by the University Grants Committee, Hong Kong.

Acknowledgements

We are grateful to the anonymous referees of CP-22 for their useful comments and suggestions.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.CP.2022.31

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • Constraint Optimization Problems
  • Dominance Breaking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Tariq Aldowaisan. A new heuristic and dominance relations for no-wait flowshops with setups. Computers & Operations Research, 28(6):563-584, 2001. Google Scholar
  2. Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, 1998. Google Scholar
  3. Nicolas Beldiceanu and Helmut Simonis. ModelSeeker: Extracting global constraint models from positive examples. In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, pages 77-95. Springer International Publishing, Cham, 2016. Google Scholar
  4. Christian Bessiere, Frédéric Koriche, Nadjib Lazaar, and Barry O'Sullivan. Constraint acquisition. Artificial Intelligence, 244:315-342, 2017. Google Scholar
  5. Carlos Castro and Sebastian Manzano. Variable and value ordering when solving balanced academic curriculum problem. In Proceedings of the ERCIM Working Group on Constraints, 2001. Google Scholar
  6. TCE Cheng, JE Diamond, and Bertrand MT Lin. Optimal scheduling in film production to minimize talent hold cost. Journal of Optimization Theory and Applications, 79(3):479-492, 1993. Google Scholar
  7. Geoffrey Chu and Peter J Stuckey. A generic method for identifying and exploiting dominance relations. In International Conference on Principles and Practice of Constraint Programming, pages 6-22. Springer, 2012. Google Scholar
  8. Gérard Cornuéjols, George Nemhauser, and Laurence Wolsey. The uncapicitated facility location problem. Technical report, Cornell University Operations Research and Industrial Engineering, 1983. Google Scholar
  9. Torsten Fahle, Stefan Schamberger, and Meinolf Sellmann. Symmetry breaking. In International Conference on Principles and Practice of Constraint Programming, pages 93-107. Springer, 2001. Google Scholar
  10. Alan M Frisch, Warwick Harvey, Chris Jefferson, Bernadette Martinez-Hernandez, and Ian Miguel. Essence: A constraint language for specifying combinatorial problems. Constraints, 13(3):268-306, 2008. Google Scholar
  11. A.M. Frisch, I. Miguel, and T. Walsh. Modelling a steel mill slab design problem. In Proceedings of the IJCAI-01 Workshop on Modelling and Solving Problems with Constraints, pages 39-45, 2001. Google Scholar
  12. A.M. Frisch, I. Miguel, and T. Walsh. Symmetry and implied constraints in the steel mill slab design problem. In Proceedings of the CP'01 Workshop on Modelling and Problem Formulation, pages 8-15, 2001. Google Scholar
  13. Antoine Gargani and Philippe Refalo. An efficient model and strategy for the steel mill slab design problem. In International Conference on Principles and Practice of Constraint Programming, pages 77-89. Springer, 2007. Google Scholar
  14. Ian P Gent and Barbara M Smith. Symmetry breaking in constraint programming. In Proceedings of the 14th European Conference on Artificial Intelligence, pages 599-603, 2000. Google Scholar
  15. Ian P Gent and Toby Walsh. CSPLib: a benchmark library for constraints. In International Conference on Principles and Practice of Constraint Programming, pages 480-481. Springer, 1999. Google Scholar
  16. Lise Getoor, Greger Ottosson, Markus Fromherz, and Björn Carlson. Effective redundant constraints for online scheduling. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Conference on Innovative Applications of Artificial Intelligence, pages 302-307, 1997. Google Scholar
  17. Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap. Aggregation Functions. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  18. Toshihide Ibaraki. The power of dominance relations in branch-and-bound algorithms. Journal of the ACM (JACM), 24(2):264-279, 1977. Google Scholar
  19. Jayant R Kalagnanam, Milind W Dawande, Mark Trumbo, and Ho Soo Lee. Inventory matching problems in the steel industry. Technical report, IBM TJ Watson Research Center, 1998. Google Scholar
  20. Michael J. Kearns. Computational Complexity of Machine Learning. MIT Press, Cambridge, MA, USA, 1990. Google Scholar
  21. Samir Khuller, Anna Moss, and Joseph Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39-45, 1999. Google Scholar
  22. Richard E Korf. Optimal rectangle packing: New results. In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), pages 142-149, 2004. Google Scholar
  23. Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 134(6):516-526, 2008. Google Scholar
  24. Jimmy H. M. Lee and Allen Z. Zhong. Towards more practical and efficient automatic dominance breaking. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 3868-3876, 2021. Google Scholar
  25. Jimmy H.M. Lee and Allen Z. Zhong. Automatic generation of dominance breaking nogoods for a class of constraint optimization problems. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 1192-1200, 2020. Google Scholar
  26. Kevin Leo. Making the Most of Structure in Constraint Models. PhD thesis, Monash University, 2018. Google Scholar
  27. Jean-Noël Monette, Pierre Schaus, Stéphane Zampelli, Yves Deville, and Pierre Dupont. A CP approach to the balanced academic curriculum problem. In Symcon'07, The Seventh International Workshop on Symmetry and Constraint Satisfaction Problems, 2007. Google Scholar
  28. Nicholas Nethercote, Peter J Stuckey, Ralph Becket, Sebastian Brand, Gregory J Duck, and Guido Tack. MiniZinc: towards a standard CP modelling language. In International Conference on Principles and Practice of Constraint Programming, pages 529-543. Springer, 2007. Google Scholar
  29. Olga Ohrimenko, Peter J Stuckey, and Michael Codish. Propagation via lazy clause generation. Constraints, 14(3):357-391, 2009. Google Scholar
  30. A Oplobedu, J Marcovitch, and Y Tourbier. Charme: Un langage industriel de programmation par contraintes, illustré par une application chez renault. In Ninth International Workshop on Expert Systems and their Applications: General Conference, volume 1, pages 55-70, 1989. Google Scholar
  31. Steven Prestwich and J Christopher Beck. Exploiting dominance in three symmetric problems. In Fourth International Workshop on Symmetry and Constraint Satisfaction Problems, pages 63-70, 2004. Google Scholar
  32. Jean-Charles Régin. A filtering algorithm for constraints of difference in csps. In Proceedings of the 12th National Conference on Artificial Intelligence, pages 362-367, 1994. Google Scholar
  33. Jean-Charles Régin. Generalized arc consistency for global cardinality constraint. In Proceedings of the 13th National Conference on Artificial intelligence, volume 1, pages 209-215, 1996. Google Scholar
  34. Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of constraint programming (foundations of artificial intelligence), 2006. Google Scholar
  35. Paul Shaw. A constraint for bin packing. In International Conference on Principles and Practice of Constraint Programming, pages 648-662. Springer, 2004. Google Scholar
  36. Peter J Stuckey, Ralph Becket, and Julien Fischer. Philosophy of the MiniZinc challenge. Constraints, 15(3):307-316, 2010. Google Scholar
  37. Pascal Van Hentenryck. The OPL optimization programming language. MIT press, 1999. Google Scholar
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 About DROPS Imprint Privacy Contact