A dual variant of Benson%26apos;s %26quot;outer approximation algorithm%26quot; for multiple objective linear programming

作者：Ehrgott Matthias; Loehne Andreas; Shao Lizhen^*

来源：Journal of Global Optimization, 2012, 52(4): 757-778.

DOI：10.1007/s10898-011-9709-y

• Multiobjective optimization
• Vector optimization
• Linear programming
• Duality
• Objective space
• Outer approximation

Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson%26apos;s %26quot;outer approximation algorithm%26quot; to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.

• 出版日期2012-4