Heuristic Ceiling Point Algorithm for General Integer Linear Programming

Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. Our heuristic approach is based upon the idea that a feasible 1-ceiling point found relatively near the optimal solution for the LP-relaxation is apt to have a high (possibly even optimal) objective function value. Having applied this Heuristic Ceiling Point Algorithm to 48 test problems taken from literature, it appears that searching for such 1-ceiling points usually does provide a very good solution with a moderate amount of computational effort."