Bucket elimination for multiobjective optimization problems

Multi-objective 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 multi-objective optimization. We show that...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2006-09, Vol.12 (4-5), p.307-328
Main Authors: Rollón, Emma, Larrosa, Javier
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Dynamic programming
Heuristic
Optimization
Studies
Traveling salesman problem
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multi-objective 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 multi-objective 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 multi-objective 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 bi-objective weighted minimum vertex cover problems. [PUBLICATION ABSTRACT]
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-006-6726-y