Title: A constructive method for solving a multi-objective linear program with bounded variables

Authors: Noureddine Khimoum; Taous Mernache; Mohand Ouamer Bibi

Addresses: LaMOS Research Unit, Operational Research Department, University of Bejaia, 06000 Bejaia, Algeria ' Department of Technical Sciences, Ferhat Abbas University, 19000 Setif, Algeria ' LaMOS Research Unit, Operational Research Department, University of Bejaia, 06000 Bejaia, Algeria

Abstract: The search for an optimal solution remains a central objective in optimisation, but in many situations the optimal solution cannot be obtained in polynomial time. For this, it would sometimes be necessary to find a good solution close to the optimum that can be obtained in a reasonable time. The aim of this paper is to find an ε-efficient or efficient solution for a multi-objective linear programming problem with polyhedral constraints and bounded decision variables. For this, we define an ε-efficient solution for which a characterisation theorem is proved, and where the ε-optimality criterion is formulated simultaneously for all the objectives of the problem. By using this concept of ε-efficiency, we develop an algorithm that combines the well known Benson's procedure in multi-objective linear programming and the adaptive method elaborated for finding ε-optimal solutions in mono-objective linear programming, based on the diminution of the suboptimality estimate. The proposed algorithm is illustrated by a numerical example and finally, it is implemented in MATLAB to solve a set of generated test problems. The efficient solutions found are located on the Pareto fronts of the same test problems treated by using the well-known Gamultiobj algorithm of MATLAB optimisation tool.

Keywords: multi-objective linear programming; MOLP; subefficient solutions; Benson's procedure; adaptive method.

DOI: 10.1504/IJMCDM.2022.128904

International Journal of Multicriteria Decision Making, 2022 Vol.9 No.2, pp.154 - 173

Accepted: 25 Oct 2022
Published online: 09 Feb 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article