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

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.