2022/12/15 by Andrea Raith, Raith, Andrea, Richard Martin Lusby +3 · 1 citation
Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Process Optimization and Integration
paper · pdf · doi:10.48550/arxiv.2212.08178
openalex publication_date 2022/12/15 · openalex created_date 2023/01/03 · openalex updated_date 2026/07/28
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.