以調適記憶投射法求解附有一般上限限制式之多維袋裝問題

The Adaptive Memory Projection Method for Multidimensional Knapsack problems with generalized Upper Bound Constraints

張桓輔(Huan-Fu Chang)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

https://doi.org/10.6838/YZU.2009.00265

摘要

本研究提出調適記憶投射法(Adaptive Memory Projection, AMP)求解附有一般上限限制式的多維背包問題(Multidimensional Knapsack Problem with Generalized Upper Bound Constraints, GUBMKP)。此問題中，所有變數被分派至數個一般上限集合中，且每一個一般上限集合中，最多有一個變數被選擇。GUBMKP可被應用在資本預算、資源分派、貨運裝載與專案分配等實際問題上，且GUBMKP是多維背包問題的一個特殊類型，而多維背包問題則隸屬於NP-hard的範疇。因此，當求解問題規模較大例子時，使用萬用啟發式演算法在計算上是較有優勢的。
調適記憶法(Adaptive Memory)紀錄演算法搜尋到的較好解，並根據這些解產生新的解。投射法即固定所選擇子集合中的變數，並最佳化其所對應之子問題；投射法在萬用啟發式演算法中是非常有用的法則，特別是在大規模問題的最佳化上。此調適記憶投射法使用關鍵事件禁忌搜尋法(Critical Event Tabu Search)與精確演算法，並利用假切面不等式(Pseudo-cut Inequality)與長期記憶來增加多樣化。
本研究根據調適記憶投射法中所使用的參數及策略進行詳盡之敏感度分析，並以大小不等之九組測試例題加以測試。運算結果具體呈現本方法之優勢。

關鍵字

調適記憶法、關鍵事件禁忌搜尋法、附有一般上限限制式之多維裝袋問題、切割平面法、限制搜尋解空間

並列摘要

An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems with generalized upper bound constraints (referred as the GUBMKP). All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each GUB set. The GUBMKP can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, project selection, just to name a few. The GUBMKP is a special case of multidimensional knapsack problems (referred as MKP), a well-known NP-hard problem. Therefore, it is justified to use metaheuristics to approximate the optimal solution for large problem instances.
The adaptive memory procedure keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which fixes the selected variables while varying the others, is very useful for metaheuristics, especially in large scale optimization. In this study, the AMP method is implemented by incorporating critical event tabu search and the branch and bound method built in a commercial optimization solver. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.
This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP algorithm. The performance of the algorithm is verified using a set of nine instances that consists of small- to large-scale instances. Therefore, this study has provided a fundamental basis for applying the AMP method to solve the GUBMKP.

並列關鍵字

Adaptive Memory, Critical Event Tabu Search, GUBMKP, Cutting Planes, Restricted Search Space

參考文獻

Ahmadi, S. and Osman, I. (2005) Greedy random adaptive memory programming search for the capacitated clustering problem. European Journal of Operational Research, 162: 30-44.

Ahuja, R. K., Ergun, O., Orlin, J. B., and Punnen A. P. (2002) Survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123: 75-102.

Bertsimas, D. and Demir, R. (2002) An approximate dynamic programming approach to multidimensional knapsack problems. Management Science, 48: 550-565.

Bozkaya, B., Erkut, E., and Laporte, G.. (2003) A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research, 144: 12–26.

Chardaire, P., McKeown, G. P., and Maki, J. A. (2001) Application of GRASP to the multiconstraint knapsack problem. Applications of Evolutionary Computing, LNCS 2037: 30-39.