Multi-objective constraint optimization with tradeoffs

Abstract

In this paper, we consider the extension of multi-objective constraint optimization algorithms to the case where there are additional tradeoffs, reducing the number of optimal solutions. We focus especially on branch-and-bound algorithms which use a mini-buckets algorithm for generating the upper bound at each node (in the context of maximizing values of objectives). Since the main bottleneck of these algorithms is the very large size of the guiding upper bound sets we introduce efficient methods for reducing these sets, yet still maintaining the upper bound property. We also propose much faster dominance checks with respect to the preference relation induced by the tradeoffs. Furthermore, we show that our tradeoffs approach which is based on a preference inference technique can also be given an alternative semantics based on the well known Multi-Attribute Utility Theory. Our comprehensive experimental results on common multi-objective constraint optimization benchmarks demonstrate that the proposed enhancements allow the algorithms to scale up to much larger problems than before.