Home > Research > Publications & Outputs > Approximating the nondominated set of an MOLP b...
View graph of relations

Approximating the nondominated set of an MOLP by approximately solving its dual problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>12/2008
<mark>Journal</mark>Mathematical Methods of Operational Research
Issue number3
Volume68
Number of pages24
Pages (from-to)469-492
Publication StatusPublished
<mark>Original language</mark>English

Abstract

The geometric duality theory of Heyde and Lohne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson, 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al., 2007). Duality theory then assures that it is possible to find the nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the nondominated set of the primal. We show that this set is an ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.