An improved partial enumeration algorithm for integer programming problems |
| |
Authors: | Mohammad S Sabbagh Richard M Soland |
| |
Institution: | (1) Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, 84156-83111, Iran;(2) Department of Engineering Management and Systems Engineering, The George Washington University, Washington, DC 20052, USA |
| |
Abstract: | In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special
algorithm, named PE_SPEEDUP (partial enumeration 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. The algorithm
is based on monotonicity properties of the problem functions, and uses 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 PE_SPEEDUP algorithm has been demonstrated on some integer
optimization problems taken from the literature. |
| |
Keywords: | Integer programming Partial enumeration speedup |
本文献已被 SpringerLink 等数据库收录! |
|