IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v44y1996i2p407-415.html
   My bibliography  Save this article

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

Author

Listed:
  • Gang Yu

    (The University of Texas at Austin, Austin, Texas)

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.

Suggested Citation

  • Gang Yu, 1996. "On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications," Operations Research, INFORMS, vol. 44(2), pages 407-415, April.
    • Handle: RePEc:inm:oropre:v:44:y:1996:i:2:p:407-415
    DOI: 10.1287/opre.44.2.407
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.44.2.407
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.44.2.407?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Christina Büsing & Sebastian Goderbauer & Arie M. C. A. Koster & Manuel Kutschka, 2019. "Formulations and algorithms for the recoverable $${\varGamma }$$ Γ -robust knapsack problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 15-45, March.
    2. G. Yu, 1998. "Min-Max Optimization of Several Classical Discrete Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 98(1), pages 221-242, July.
    3. S Das & D Ghosh, 2003. "Binary knapsack problems with random budgets," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(9), pages 970-983, September.
    4. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    5. Nikulin, Yury, 2006. "Robustness in combinatorial optimization and scheduling theory: An extended annotated bibliography," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 606, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Fabrice Talla Nobibon & Roel Leus, 2014. "Complexity Results and Exact Algorithms for Robust Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 533-552, May.
    7. Fabio Furini & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2015. "Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 392-405, May.
    8. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    9. Adam Kasperski & Paweł Zieliński, 2009. "A randomized algorithm for the min-max selecting items problem with uncertain weights," Annals of Operations Research, Springer, vol. 172(1), pages 221-230, November.
    10. Alexandre Belloni & Mitchell J. Lovett & William Boulding & Richard Staelin, 2012. "Optimal Admission and Scholarship Decisions: Choosing Customized Marketing Offers to Attract a Desirable Mix of Customers," Marketing Science, INFORMS, vol. 31(4), pages 621-636, July.
    11. Iida, Hiroshi, 2007. "Comments on knapsack problems with a penalty," ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) 10252/910, Otaru University of Commerce.
    12. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    13. Hanan Luss, 1999. "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach," Operations Research, INFORMS, vol. 47(3), pages 361-378, June.
    14. Thekra Al-douri & Mhand Hifi & Vassilis Zissimopoulos, 2021. "An iterative algorithm for the Max-Min knapsack problem with multiple scenarios," Operational Research, Springer, vol. 21(2), pages 1355-1392, June.
    15. Florian Biermann & Victor Naroditskiy & Maria Polukarov & Alex Rogers & Nicholas Jennings, 2011. "Task Assignment with Autonomous and Controlled Agents," Working Papers 004-11, International School of Economics at TSU, Tbilisi, Republic of Georgia.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:44:y:1996:i:2:p:407-415. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.