A Heuristic Algorithm for solving Integer Linear Programming Problem and Unveiling the Applications

Abstract

There is a growing need for integer solutions in industries, production units, etc. Specifically, there is an increasing demand to develop precise methods for solving integer-programming problems (IPPs). In this paper, we propose a new algorithm for solving IPPs in a general form by combining two decomposition techniques: Benders decomposition (BD) and decomposition-based pricing methods (DBP). Moreover, we generate some conditions for solving problems having either infeasible or unbounded solutions. In addition, we present an application and evaluation of a solution method for solving IPPs, while also giving a brief description of the different classical decomposition methods, namely the Dantzig-Wolfe decomposition (DWD), decomposition-based pricing (DBP), Benders decomposition (BD), and recently proposed improved decomposition (ID) methods for solving IPPs.We also discuss the use of the decomposition methods for solving IPPS to develop a heuristic algorithm, describe the limitations of the classical algorithms, and present extensions enabling its application to a broader range of problems. To illustrate the decomposition procedures, we will provide corresponding models and numerical results for two standard mathematical programs: the Fixed Charge Problem (FCP) and the Facility Location Problem (FLP). Our findings from this study suggest that our algorithm produces the most efficient computational solutions of IPPs.

Journal of Bangladesh Academy of Sciences, Vol. 44, No. 1, 13-31, 2020