Global optimization and multi knapsack: A percolation algorithm |
| |
Affiliation: | 1. Department of Construction Management, Tsinghua University, Beijing 100084, China;2. Sonny Astani Department of Civil and Environmental Engineering, University of Southern California, Los Angeles, CA 90089, United States;3. Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, United States |
| |
Abstract: | Since the standard multi knapsack problem, may be rewritten as a reverse convex problem, we present a global optimization approach. It is known from solving high dimensional nonconvex problems that pure cutting plane methods may fail and branch-and-bound is impractical, due to a large duality gap. On the other hand, a strategy based on some sufficient optimality condition does not help much because it requires generating all level set points, an intractable problem. Therefore, we propose to combine both a cutting plane method and a sufficient optimality condition together with a random generation of level set points where the number of points is limited by a tabu list to prevent re-examination of the same level set area. Experiments show that we end up with a small duality gap allowing a subsequent branch-and-bound approach to prove optimality. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|