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.
