Bucket elimination for multiobjective optimization problems |
| |
Authors: | Emma Rollón Javier Larrosa |
| |
Affiliation: | (1) Universitat Politecnica de Catalunya, Barcelona, Spain |
| |
Abstract: | Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems. |
| |
Keywords: | Multiobjective optimization Dynamic programming Decomposition methods Global constraints |
本文献已被 SpringerLink 等数据库收录! |
|