  In this paper, we develop a new decomposition technique for solving
bi-objective linear programming problems. The proposed methodology combines the
bi-objective simplex algorithm with Benders decomposition and can be used to
obtain a complete set of extreme efficient solutions, and the corresponding set
of extreme non-dominated points, for a bi-objective linear program. Using a
Benders-like reformulation, the decomposition approach decouples the problem
into a bi-objective master problem and a bi-objective subproblem, each of which
is solved using the bi-objective parametric simplex algorithm. The master
problem provides candidate extreme efficient solutions that the subproblem
assesses for feasibility and optimality. As in standard Benders decomposition,
optimality and feasibility cuts are generated by the subproblem and guide the
master problem solve. This paper discusses bi-objective Benders decomposition
from a theoretical perspective, proves the correctness of the proposed
reformulation and addresses the need for so-called weighted optimality cuts.
Furthermore, we present an algorithm to solve the reformulation and discuss its
performance for three types of bi-objective optimisation problems.
