A generalized implicit enumeration algorithm for a class of integer nonlinear programming problems

Presented here is a generalization of the implicit enumeration algorithm that can be applied when the objective function is being maximized and can be rewritten as the difference of two non-decreasing functions. Also developed is a computational algorithm, named linear speedup, to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. To see some application of the generalized algorithm, we notice that the branch-and-bound is the popular method to solve integer linear programming problems. But branch-andbound cannot efficiently solve all integer linear programming problems. For example, De Loera et al. in their 2005 paper discuss some knapsack problems that CPLEX cannot solve in hours. We use our generalized algorithm to find a global or near global optimal solutions for those problems, in less than 100 seconds. The algorithm is based on function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm has been demonstrated on some integer optimization problems taken from the literature.