Bucket elimination for multiobjective optimization problems

被引:1
作者
Emma Rollón
Javier Larrosa
机构
[1] Universitat Politecnica de Catalunya,
来源
Journal of Heuristics | 2006年 / 12卷
关键词
Multiobjective optimization; Dynamic programming; Decomposition methods; Global constraints;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:307 / 328
页数:21
相关论文
共 24 条
  • [1] Bensana E.(1999)Earth Observation Satellite Management Constraints 4 293-299
  • [2] Lemaitre M.(1999)Semiring-Based CSPs and Valued CSPs: Frameworks, Properties and Comparison Constraints 4 199-240
  • [3] Verfaillie G.(1997)Semiring-Based Constraint Satisfaction and Optimization Journal of the ACM 44 201-236
  • [4] Bistarelli S.(1999)Bucket Elimination: A Unifying Framework for Reasoning Artificial Intelligence 113 41-85
  • [5] Fargier H.(2003)Mini-Buckets: A General Scheme for Bounded Inference Journal of the ACM 50 107-153
  • [6] Montanari U.(2001)Bounds and Bound Sets for Biobjective Combinatorial Optimization Problems Lecture Notes in Economics and Mathematical Systems 507 241-253
  • [7] Rossi F.(1992)Partial Constraint Satisfaction Artificial Intelligence 58 21-70
  • [8] Schiex T.(1985)Depth-First Iterative-Deepening: An Optimal Admissable Tree search Artificial Intelligence 27 97-109
  • [9] Verfaillie G.(2003)A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints Annals of Operations Research 118 73-84
  • [10] Bistarelli S.(1992)Constraint Satisfaction Using Constraint Logic Programming Artificial Intelligence 58 113-159