The Linear Multiple Choice Knapsack Problem.

reportActive / Technical Report | Accession Number: ADA069129 | Open PDF

Abstract:

We discuss a fast algorithm for the linear programming relaxation of the Multiple Choice Knapsack Problem. Let N be the total number of variables in this problem and let J and J sub max denote the total number of multiple choice variables and the cardinality of the largest multiple choice set, respectively. The running time of the algorithm is then bounded by 0J log J sub max 0N. Under certain conditions it is possible to reduce this bound to 0N steps on the average. Possible further improvements are also discussed.

Author(s):
Zemel, Eitan
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Descriptive Note:
Technical rept.,
Supplementary Note:
Revision of report dated Oct 78.
Pagination:
0017

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
MSRR-434
Contract/Grant Number(s):
N00014-76-C-0621, NSF-MCS76-12026
 Subject Terms
Joint Capability Areas:
JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating; JCA_5_Command and Control
Modernization Areas:
Fully Networked C3
Communities of Interest:
Air Platforms
Descriptor(s):
*INTEGER PROGRAMMING, *COMBINATORIAL ANALYSIS, LINEAR PROGRAMMING, TRANSFORMATIONS(MATHEMATICS)
Field(s)/Group(s):
Numerical Mathematics
Keyword(s):
Knapsack problem
Report Date:
1979 Apr 01