An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane (Q870164)

Previous algorithms for solving the general integer linear programming problem often involve the solution of linear programs and have significant memory requirement in the heuristic search process. This paper considers practical algorithms for solving the integer programming problem. The value ranges of the variables in the convex polyhedron of the feasible region of the linear programming relaxation problem intercepted by the objective function hyperplane are established. An efficient heuristic algorithm is presented for finding an optimal solution or showing that there is no feasible solution to the integer programming problem on the objective function hyperplane. The algorithm does not need to solve any linear programming subproblems. The memory requirements of the algorithm change linearly with the size of the problem. Computational results on some numerical problems show that the proposed algorithm is more efficient than the stopped simplex method of Thompson and the all-integer method of Gomory.