We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the max-min 0-1 knapsack problem with robust...
- Authors
Yu, Gang
- Abstract
Given a set of items, a set of scenarios, and a knapsack of fixed capacity, a nonnegative weight is associated with each item; and a value is associated with each item under each scenario. The max-mm Knapsack (MNK) problem is defined as filling the knapsack with a selected set of items so that the minimum total value gained under all scenarios is maximized. The MNK problem is a generalization of the conventional knapsack problem to situations with multiple scenarios. This extension significantly enlarges its scope of applications, especially in the application of recent robust optimization developments. In this paper, the MNK problem is shown to be strongly NP-hard for an unbounded number of scenarios and pseudopolynomially solvable for a bounded number of scenarios. Effective lower and upper bounds are generated by surrogate relaxation. The ratio of these two bounds is shown to be bounded by a constant for situations where the data range is limited to be within a fixed percentage from its mean. This result leads to an approximation algorithm for MNK in the special case. A branch-and-bound algorithm has been implemented to efficiently solve the MNK problem to optimality. Extensive computational results are presented.
- Subjects
ALGORITHMS; OPERATIONS research; INTEGER programming; POTENTIAL theory (Physics); VALUE (Economics); MATHEMATICAL optimization; RESEARCH; METHODOLOGY
- Publication
Operations Research, 1996, Vol 44, Issue 2, p407
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.44.2.407