论文标题
弯曲器分解双线性线性程序
Benders Decomposition for Bi-objective Linear Programs
论文作者
论文摘要
在本文中，我们开发了一种新的分解技术，用于解决双目标线性编程问题。所提出的方法将双目标单纯形算法与弯曲器分解结合在一起，可用于获得一组完整的极有效的解决方案，以及相应的极端非主导点，用于双向目标线性计划。使用类似弯曲的重新印象，分解方法将问题分解为双目标主问题和双目标子问题，每种问题都使用Bi-Objective参数单纯形算法解决。主问题提供了候选的极有效解决方案，子问题评估了可行性和最佳性。与标准弯曲器分解一样，子问题也会产生最佳性和可行性削减，并指导主问题解决。本文从理论的角度讨论了双向弯曲器的分解，证明了拟议的重新印象的正确性，并解决了对所谓加权最佳削减的需求。此外，我们提出了一种算法来解决重新制定并讨论其针对三种双向目标优化问题的性能。
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.
