Multi-objective constraint optimization with tradeoffs

Loading...
Thumbnail Image
Files
cp2013-moopt.pdf(370.09 KB)
Accepted Version
Date
2013-09
Authors
Marinescu, Radu
Razak, Abdul
Wilson, Nic
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Research Projects
Organizational Units
Journal Issue
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.
Description
Keywords
Multi-objective Constraint Optimization (MOCOP) , Discrete mathematics in computer science , Logics and meanings of programs , Algorithm analysis and problem complexity , Numeric computing , Mathematical logic and formal languages , Programming languages, compilers, interpreters
Citation
MARINESCU, R., RAZAK, A. & WILSON, N. 2013. Multi-Objective Constraint Optimization with Tradeoffs. In: SCHULTE, C. (ed.) Principles and Practice of Constraint Programming. Uppsala, Sweden, 16-20 Sep. Berlin Heidelberg: Springer, pp. 497-512
Copyright
©Springer-Verlag Berlin Heidelberg 2013. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40627-0_38