On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications

Gang Yu
Additional contact information
Gang Yu: The University of Texas at Austin, Austin, Texas

Operations Research, 1996, vol. 44, issue 2, 407-415

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-min 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.

Keywords: analysis of algorithms: strong/weak NP-hardness of a max-min problem; programming; integer: surrogate relaxation upper/lower bounds; programming; integer: heuristics and worst-case performance (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.2.407 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:2:p:407-415

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().