Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
