Comparison of Benders decomposition algorithms to solve bi-objective linear programmes

We present four Benders decomposition algorithms to solve bi-objective linear programmes (BLPs) and compare their performance for the bi-objective fixed charge transportation problem. In three of the algorithms, Benders decomposition is incorporated within the biobjective simplex algorithm by decomposing the problem into a bi-objective master problem (BM) and a bi-objective sub-problem (BS). Like the bi-objective simplex algorithm, the biobjective Benders simplex algorithm (BBSA) aims to find a set of extreme efficient solutions by proceeding iteratively from the optimiser of one objective to that of the other. In this algorithm, iteratively, an efficient solution of BM is chosen to be solved with BS - this is called exploring an efficient solution in BS. If BS is infeasible, a feasibility cut is added to BM; otherwise, an optimality cut is generated for each efficient solution of BS and added to BM. The BBSA stops when there is no new non-dominated point in BM that needs to be explored. Since solving BS is a time-consuming step in BBSA, we propose a variant of BBSA where at most two weighted optimality cuts are generated from BS. Another variant of the BBSA proceeds in a bidirectional fashion, where the problem is solved by simultaneously starting from the minimisers of the first and second objectives. The algorithm proceeds similarly to the second algorithm in two directions until the same non-dominated point is found from each direction. We also present a Benders algorithm to solve a BLP, where a sequence of weighted-sum single-objective problems is solved with Benders decomposition to find a complete set of extreme non-dominated points. We present a new procedure to calculate the value of the next weight using information from the decomposed problem.