Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems

Ross J.W. JAMES; Yuji NAKAGAWA

doi:10.1093/ietisy/e88-d.10.2329

Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems

Ross J.W. JAMES, Yuji NAKAGAWA

Full Text Views

0

Share
Cite this

Summary :

In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.10 pp.2329-2340

Publication Date: 2005/10/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.10.2329

Type of Manuscript: PAPER

Category: Algorithm Theory

Cite this

Copy

Ross J.W. JAMES, Yuji NAKAGAWA, "Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 10, pp. 2329-2340, October 2005, doi: 10.1093/ietisy/e88-d.10.2329.
Abstract: In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.10.2329/_p

Copy

@ARTICLE{e88-d_10_2329,
author={Ross J.W. JAMES, Yuji NAKAGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems},
year={2005},
volume={E88-D},
number={10},
pages={2329-2340},
abstract={In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.},
keywords={},
doi={10.1093/ietisy/e88-d.10.2329},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems
T2 - IEICE TRANSACTIONS on Information
SP - 2329
EP - 2340
AU - Ross J.W. JAMES
AU - Yuji NAKAGAWA
PY - 2005
DO - 10.1093/ietisy/e88-d.10.2329
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2005
AB - In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.
ER -