  In this paper, a parametric simplex algorithm for solving linear vector
optimization problems (LVOPs) is presented. This algorithm can be seen as a
variant of the multi-objective simplex (Evans-Steuer) algorithm [12]. Different
from it, the proposed algorithm works in the parameter space and does not aim
to find the set of all efficient solutions. Instead, it finds a solution in the
sense of Loehne [16], that is, it finds a subset of efficient solutions that
allows to generate the whole frontier. In that sense, it can also be seen as a
generalization of the parametric self-dual simplex algorithm, which originally
is designed for solving single objective linear optimization problems, and is
modified to solve two objective bounded LVOPs with the positive orthant as the
ordering cone in Ruszczynski and Vanderbei [21]. The algorithm proposed here
works for any dimension, any solid pointed polyhedral ordering cone C and for
bounded as well as unbounded problems. Numerical results are provided to
compare the proposed algorithm with an objective space based LVOP algorithm
(Benson algorithm in [13]), that also provides a solution in the sense of [16],
and with Evans-Steuer algorithm [12]. The results show that for non-degenerate
problems the proposed algorithm outperforms Benson algorithm and is on par with
Evan-Steuer algorithm. For highly degenerate problems Benson's algorithm [13]
excels the simplex-type algorithms; however, the parametric simplex algorithm
is for these problems computationally much more efficient than Evans-Steuer
algorithm.
