Multi-Objective Combinatorial Optimization (MOCO) explores a finite search space of feasible solutions and finds the optimal ones that balance multiple (often conflicting) objectives simultaneously. MOCO is a fundamental challenge in many problems in software engineering (e.g., architecture design, test data generation, and project planning) and other domains (e.g., hybrid vehicle powertrain design, electric vehicle battery design, and civil infrastructure repair planning).

Most MOCO problems are NP-hard. To address them, approximate approaches that depend mainly on meta-heuristics have been advocated for years. In most cases, they solve MOCO problems in an acceptable time, but they find only near-optimal solutions, and often suffer from parameter sensitivity (i.e., the accuracy of the found solutions varies widely with the parameter settings of these approaches). In contrast, exact methods that scan all candidate solutions one by one often take too long for large-scale problems, but they are accurate in finding all, exact optimal solutions, which is desirable for those stakeholders who never want to miss any optimal opportunity.

We aim at exact, parallel approaches that solve MOCO problems accurately and efficiently. We propose five novel parallel MOCO algorithms that search for exact optimal solutions using off-the-shelf solvers, and that parallelize the search via collaborative communication, divide-and-conquer, or both. A key finding is that one algorithm, which we call FS-GIA, achieves substantial (even super-linear) speedups that scales well up to 64 cores. Our work opens a new direction in scaling exact MOCO methods. We hope that our work encourages other researchers to reconsider the feasibility of exact MOCO methods and to try different ways to scale them. Appropriate parallelization, especially given the increasing availability of multi-core systems, is definitely a promising approach.

More details, implementation code, and experimental data are available on an open-source project website: http://epoal.googlecode.com.

Team Members

• Jianmei Guo (郭健美) (University of Waterloo, Canada)
• Ed Zulkoski (University of Waterloo, Canada)
• Rafael Olaechea (University of Waterloo, Canada)
• Derek Rayside (University of Waterloo, Canada)
• Krzysztof Czarnecki (University of Waterloo, Canada)
• Sven Apel (University of Passau, Germany)
• Jo(anne) M. Atlee (University of Waterloo, Canada)

News

Tools

Publications