Title: Solution of an integer linear programming problem via a primal dual method combined with a heuristic

Authors: Mohand Ouamer Bibi; Houria Boussouira; Abdelhek Laouar

Addresses: Research Unit LaMOS, Department of Operations Research, Faculty of the Exact Sciences, University of Bejaia, 06000 Bejaia, Algeria ' Research Unit LaMOS, Department of Operations Research, Faculty of the Exact Sciences, University of Bejaia, 06000 Bejaia, Algeria ' Research Unit LaMOS, Department of Operations Research, Faculty of the Exact Sciences, University of Bejaia, 06000 Bejaia, Algeria

Abstract: In this paper, we propose an algorithm for solving integer linear programming (ILP) problem with upper and lower bounded variables where we combined a cutting plane method with a heuristic. At each iteration, a relaxed problem is solved by the adaptive method and its optimal solution is submitted to a judicious rounding procedure. The concept of β-optimality is used to indicate the quality of the approximate solution obtained by this heuristic. In order to compare our method with the intlinprog method of the MATLAB optimisation toolbox, numerical experiments on randomly generated test problems are presented.

Keywords: integer linear programming; ILP; cutting planes; adaptive method; heuristic method; approximate solution; β-optimality.

DOI: 10.1504/IJMMNO.2022.119781

International Journal of Mathematical Modelling and Numerical Optimisation, 2022 Vol.12 No.1, pp.69 - 87

Received: 20 Nov 2020
Accepted: 11 Apr 2021
Published online: 20 Dec 2021 *