Allen Z. Zhong‘s paper, “Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization“, won the Best Student Paper Award at the 28th International Conference on Principles and Practice of Constraint Programming (CP 2022).
Mr. Zhong is supervised by Prof. Jimmy Lee. His research focuses on constraint optimization and satisfaction.
Abstract:
Dominance breaking is an effective technique to reduce the time for solving constraint optimization problems. Lee and Zhong propose an automated 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 to discover new dominance relations on problems with ineffective or no known dominance breaking constraints in the literature.
