A generalized implicit enumeration algorithm for a class of integer nonlinear programming problems
محورهای موضوعی : Mathematical OptimizationM.S Sabbagh 1 , M Roshanjooy 2
1 - Assistant Professor, Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
2 - M.Sc., Dep. of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
کلید واژه: Integer programming, Algebraic form, Function values, Generalized implicit enumeration, Linear speedup,
چکیده مقاله :
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.
