Application of The Interior Point and NSGA-II to Multi-Objective Linear Programming

Abstract

Multi-Objective Linear Programming (MOLP) provides a systematic framework for solving decision problems involving multiple, often conflicting, linear objectives. This study compares the performance of Arbel’s Affine Scaling Interior Multi-Objective Linear Programming (ASIMOLP) algorithm and the Nondominated Sorting Genetic Algorithm II (NSGA-II) for solving MOLP problems. The comparison focuses on the quality of the nondominated solutions generated by the two approaches. ASIMOLP was implemented in MATLAB based on the affine scaling interior-point procedure, while an existing MATLAB implementation of NSGA-II was employed for the evolutionary optimization process. Both algorithms were tested on ten MOLP instances ranging from small to medium-sized problems, comprising benchmark and randomly generated instances with varying numbers of variables, constraints, and objectives. The computational results indicate that ASIMOLP generally produced nondominated solutions with better objective-function values than NSGA-II across most of the test problems. Although NSGA-II was capable of generating good approximations of the nondominated set, the solutions obtained were generally inferior to those produced by ASIMOLP for the instances considered. The findings demonstrate the effectiveness of the interior-point approach for obtaining high-quality nondominated solutions in MOLP and provide useful evidence for selecting solution methods according to the characteristics of the optimization problem. The study also highlights the potential of combining exact interior-point techniques with evolutionary approaches to improve the solution of larger and more complex multi-objective optimization problems..