TY - JOUR
ID - 511073
TI - A generalized implicit enumeration algorithm for a class of integer nonlinear programming problems
JO - Journal of Industrial Engineering, International
JA - JIEI
LA - en
SN - 1735-5702
AU - Sabbagh, M.S
AU - Roshanjooy, M
AD - Assistant Professor, Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
AD - M.Sc., Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
Y1 - 2008
PY - 2008
VL - 4
IS - 6
SP - 39
EP - 50
KW - Algebraic form
KW - Function values
KW - Generalized implicit enumeration
KW - Integer programming
KW - Linear speedup
DO -
N2 - 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.
UR - http://jiei.azad.ac.ir/article_511073.html
L1 - http://jiei.azad.ac.ir/article_511073_e31ca6284dea1119a2d5cda925fd2c30.pdf
ER -