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

Journal of Industrial Engineering International

مقاله 5، دوره 4، شماره 6، شهریور 2008، صفحه 39-50   

نویسندگان

M.S Sabbagh¹؛ M Roshanjooy²

¹Assistant Professor, Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

²M.Sc., Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

چکیده

Presented here is a generalization of the implicit enumeration algorithm that can be applied when the objec-tive 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 effec-tive in dealing with many integer programming problems, including knapsack problems, reliability optimiza-tion, 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-and-bound 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 algo-rithm to find a global or near global optimal solutions for those problems, in less than 100 seconds. The algo-rithm is based on function values only; it does not require continuity or differentiability of the problem func-tions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The re-liability and efficiency of the proposed algorithm has been demonstrated on some integer optimization prob-lems taken from the literature.

کلیدواژه‌ها

Algebraic form؛ Function values؛ Generalized implicit enumeration؛ Integer programming؛ Linear speedup