Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls

被引：88

作者：

Akbar, MM ^{[1
]}

Rahman, MS

Kaykobad, M

Manning, EG

Shoja, GC

机构：

[1] BUET, Dept CSE, Dhaka, Bangladesh

[2] Univ Victoria, Dept CSC, Victoria, BC, Canada

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 05期

关键词：

algorithms; convex hull; heuristics; MMKP; multimedia systems;

D O I：

10.1016/j.cor.2004.09.016

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper presents a heuristic to solve the Multidimensional Multiple-choice Knapsack Problem (MMKP), a variant of the classical 0-1 Knapsack Problem. We apply a transformation technique to map the multidimensional resource consumption to single dimension. Convex hulls are constructed to reduce the search space to find the near-optimal solution of the MMKP. We present the computational complexity of solving the MMKP using this approach. A comparative analysis of different heuristics for solving the MMKP has been presented based on the experimental results. (c) 2004 Elsevier Ltd. All rights reserved.

引用

页码：1259 / 1273

页数：15

共 20 条

[1]

AKBAR MM, 2002, THESIS U VICTORIA, V6

[2]

[Anonymous], STUDIA INFORM

[3]

Cormen T., 1990, INTRO ALGORITHM

[4] A SIMULATED ANNEALING APPROACH TO THE MULTICONSTRAINT ZERO-ONE KNAPSACK-PROBLEM [J].