在文獻中，Sbihi提出一個使用最佳優先分支限界法(branch and bound with best-first solution )，求解多維度多重選擇背包問題(Multidimensional Multiple-Choice Knapsack Problem ,MMKP)的最佳化演算法。本論文主要是使用Sbihi的最佳優先分支限界法，討論如何改進上界(upper bound)，提高最佳化演算法的績效，求解多維度多重選擇背包問題。本論文提出EMKP-1演算法與EMKP-2演算法與Sbihi演算法作比較，發現EMKP-1與EMKP-2演算法均能縮短Sbihi演算法的求解時間，且在中小型的問題下，EMKP-1演算法與EMKP-2演算法的執行效率，也比CPLEX高。

Sbihi develops an exact algorithm using branch and bound with best-first solution for solving the Multidimensional Multiple-Choice Knapsack Problem(MMKP). This thesis aims at analyzing and modifying Sbihi’s exact algorithm for MMKP. It tries to improve the upper bound for the branch and bound strategy to solve MMKP. This thesis proposes our two exact algorithm, EMKP-1 algorithm and EMKP-2 algorithm and compare with Sbihi algorithm. The experimental results show that our two algorithms use shorter solving time than Sbihi’s algorithm. Our two algorithm is also better than Cplex with instances of small and medium sizes.

參考文獻
1. A. Sbihi. A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem. J Comb Optim, 13:337-351, 2007
2. M. Hifi, M. Michrafy, and A. Sbihi. A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem. Computational Optimization and Applications, 33, 271-285, 2006.
3. M. Hifi, M. Michrafy, and A. Sbihi. Heuristic algorithms for the multiple-choice multidimensional knapsack problem. Journal of the Operational Research Society, 55, 1323-1332, 2004
4. S. Martello, D. Pisinger, and P. Toth. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research, 123, 325-332, 2000.
5. M. M. Akbar, E. G. Manning, G. C. Shoja, and S. Khan. Heuristic searchs for the multiple-choice multi-dimension knapsack problem. Proceeding of International Conference on Computational Science, May 28-30, 2001.
6. Y. Toyoda. A simplified algorithm for obtaining approximate search to zero-one programming problems. Management Science, 21: 1417-1427, 1975
7. M. Moser, D. P. Jokanovic, and N. Shiratori. An algorithm for the multidimensional multiple-choice knapsack problem. IEICE Trans Fundamentals Electron, 80(3):582-589, 1997.
8. S. Martello, D. Pisinger , and P. Toth. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45:414-424, 1999.
9. S. Khan, K. F. Li, E. G. Manning, and MD M.Akbar. Solving the knapsack problem for adaptive multimedia system. Studia Information Universalis, 2(1):157-178, 2002.

10. S. Khan. Quality adaptation in a multi-session adaptive multimedia system: model and architecture. PhD thesis, Department of Electrical and Computer Engineering, University of Victoria, 1998.
11. P. J. Kolesar. A branch and bound algorithm for knapsack problem. Management Science, 13:723-735, 1967.
12. S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester, England, 1990.
13. 陳珮綺，「多維度多重選擇背包問題啟發式演算法之研究」，國立台灣科技大學資訊管理學系碩士論文，2007。
14. A. E. Lawabni and A. H. Tewfik. Resource management and quality adaptation in distributed multimedia networks. In Proceedings of the 10th IEEE Symposium on Computers and Communications(ISCC), 2005.
15. D. Pisinger. Where are the hard knapsack problems ? Computer and Operational Research, 2271-2284, 2005.
16. W. Shih. A branch and bound method for multiconstraint knapsack problem. Journal of the Operational Research Society, 30:336-378, 1979.
17. T. Yu and K.J. Lin. Service selection algorithms for web services with end-to-end qos constraints. Information systems and e-Business Management, 3(2):103-126, 2005.
18. S.Khan, Kin F. Li, Eric G. Manning, Robert Watson, and G. C. Shoja. Optimal Quality of Service routing and admission control using the utility model. Future Generation Computer System, 19:1063-1073, 2003.