IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v54y2007i6p656-666.html
   My bibliography  Save this article

The minmax multidimensional knapsack problem with application to a chance‐constrained problem

Author

Listed:
  • Moshe Kress
  • Michal Penn
  • Maria Polukarov

Abstract

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007

Suggested Citation

  • Moshe Kress & Michal Penn & Maria Polukarov, 2007. "The minmax multidimensional knapsack problem with application to a chance‐constrained problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 656-666, September.
    • Handle: RePEc:wly:navres:v:54:y:2007:i:6:p:656-666
    DOI: 10.1002/nav.20237
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20237
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20237?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
    ---><---

    References listed on IDEAS

    as
    1. M A H Dempster & N Hicks Pedrón & E A Medova & J E Scott & A Sembos, 2000. "Planning logistics operations in the oil industry," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(11), pages 1271-1288, November.
    2. Raymond K. Cheung & Warren B. Powell, 1996. "An Algorithm for Multistage Dynamic Networks with Random Arc Capacities, with an Application to Dynamic Fleet Management," Operations Research, INFORMS, vol. 44(6), pages 951-963, December.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Raymond K. Cheung & Chuen-Yih Chen, 1998. "A Two-Stage Stochastic Network Model and Solution Methods for the Dynamic Empty Container Allocation Problem," Transportation Science, INFORMS, vol. 32(2), pages 142-162, May.
    2. Chen, Ruoran & Deng, Tianhu & Huang, Simin & Qin, Ruwen, 2015. "Optimal crude oil procurement under fluctuating price in an oil refinery," European Journal of Operational Research, Elsevier, vol. 245(2), pages 438-445.
    3. Kochel, Peter & Kunze, Sophie & Nielander, Ulf, 2003. "Optimal control of a distributed service system with moving resources: Application to the fleet sizing and allocation problem," International Journal of Production Economics, Elsevier, vol. 81(1), pages 443-459, January.
    4. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2005. "Decision Support for Consumer Direct Grocery Initiatives," Transportation Science, INFORMS, vol. 39(3), pages 313-327, August.
    5. Thapalia, Biju K. & Crainic, Teodor Gabriel & Kaut, Michal & Wallace, Stein W., 2012. "Single-commodity network design with random edge capacities," European Journal of Operational Research, Elsevier, vol. 220(2), pages 394-403.
    6. Nguyet Thi Tran & Dirk Weichgrebe, 2020. "Regional material flow behaviors of agro‐food processing craft villages in Red River Delta, Vietnam," Journal of Industrial Ecology, Yale University, vol. 24(3), pages 707-725, June.
    7. D-P Song, 2007. "Characterizing optimal empty container reposition policy in periodic-review shuttle service systems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 122-133, January.
    8. Raymond K.-M. Cheung & Warren B. Powell, 2000. "Shape -- A Stochastic Hybrid Approximation Procedure for Two-Stage Stochastic Programs," Operations Research, INFORMS, vol. 48(1), pages 73-79, February.
    9. Apoorva Ghosh & Pranabesh Ray, 2012. "A Contemporary Model for Industrial Relations," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 37(1), pages 17-30, February.
    10. Klosterhalfen, S.T. & Kallrath, J. & Fischer, G., 2014. "Rail car fleet design: Optimization of structure and size," International Journal of Production Economics, Elsevier, vol. 157(C), pages 112-119.
    11. Jeremy Bulow & Paul Klemperer, 1998. "The Tobacco Deal," Brookings Papers on Economic Activity, Economic Studies Program, The Brookings Institution, vol. 29(1998 Micr), pages 323-394.
    12. Sumit Kunnumkal & Huseyin Topaloglu, 2008. "A duality‐based relaxation and decomposition approach for inventory distribution systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 612-631, October.
    13. Kallrath, J. & Klosterhalfen, S.T. & Walter, M. & Fischer, G. & Blackburn, R., 2017. "Payload-based fleet optimization for rail cars in the chemical industry," European Journal of Operational Research, Elsevier, vol. 259(1), pages 113-129.
    14. Zhou, Shaorui & Zhang, Hui & Shi, Ning & Xu, Zhou & Wang, Fan, 2020. "A new convergent hybrid learning algorithm for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 283(1), pages 33-46.
    15. Golmohamadi, Hessam, 2022. "Demand-side management in industrial sector: A review of heavy industries," Renewable and Sustainable Energy Reviews, Elsevier, vol. 156(C).
    16. Hezarkhani, Behzad & Kubiak, Wieslaw, 2010. "A coordinating contract for transshipment in a two-company supply chain," European Journal of Operational Research, Elsevier, vol. 207(1), pages 232-237, November.
    17. Chang, Tsung-Sheng, 2009. "Decision support for truckload carriers in one-shot combinatorial auctions," Transportation Research Part B: Methodological, Elsevier, vol. 43(5), pages 522-541, June.
    18. Gregory D. Glockner & George L. Nemhauser, 2000. "A Dynamic Network Flow Problem with Uncertain arc Capacities: Formulation and Problem Structure," Operations Research, INFORMS, vol. 48(2), pages 233-242, April.
    19. Alexander S. Estes & Michael O. Ball, 2021. "Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 785-807, May.
    20. Moradi Nasab, N. & Amin-Naseri, M.R., 2016. "Designing an integrated model for a multi-period, multi-echelon and multi-product petroleum supply chain," Energy, Elsevier, vol. 114(C), pages 708-733.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:54:y:2007:i:6:p:656-666. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.