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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Joel A. Shapiro & Warren B. Powell, 2006. "A Metastrategy for Large-Scale Resource Management Based on Informational Decomposition," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 43-60, February.
    8. Guajardo, Mario & Kylinger, Martin & Rönnqvist, Mikael, 2013. "Speciality oils supply chain optimization: From a decoupled to an integrated planning approach," European Journal of Operational Research, Elsevier, vol. 229(2), pages 540-551.
    9. Chen, Lichun & Miller-Hooks, Elise, 2012. "Optimal team deployment in urban search and rescue," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 984-999.
    10. Song, Dong-Ping & Dong, Jing-Xin, 2011. "Effectiveness of an empty container repositioning policy with flexible destination ports," Transport Policy, Elsevier, vol. 18(1), pages 92-101, January.
    11. Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2009. "Robust Optimization for Empty Repositioning Problems," Operations Research, INFORMS, vol. 57(2), pages 468-483, April.
    12. Al-Othman, Wafa B.E. & Lababidi, Haitham M.S. & Alatiqi, Imad M. & Al-Shayji, Khawla, 2008. "Supply chain optimization of petroleum organization under uncertainty in market demands and prices," European Journal of Operational Research, Elsevier, vol. 189(3), pages 822-840, September.
    13. Crainic, Teodor Gabriel & Laporte, Gilbert, 1997. "Planning models for freight transportation," European Journal of Operational Research, Elsevier, vol. 97(3), pages 409-438, March.
    14. Topaloglu, Huseyin, 2009. "A tighter variant of Jensen's lower bound for stochastic programs and separable approximations to recourse functions," European Journal of Operational Research, Elsevier, vol. 199(2), pages 315-322, December.
    15. Alexander S. Estes & Michael O. Ball, 2020. "Equity and Strength in Stochastic Integer Programming Models for the Dynamic Single Airport Ground-Holding Problem," Transportation Science, INFORMS, vol. 54(4), pages 944-955, July.
    16. Jia Shu & Miao Song, 2014. "Dynamic Container Deployment: Two-Stage Robust Model, Complexity, and Computational Results," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 135-149, February.
    17. Charles I. Nkeki, 2013. "Dynamic Optimization Technique for Distribution of Goods with Stochastic Shortages," Journal of Optimization, Hindawi, vol. 2013, pages 1-12, December.
    18. Sumit Kunnumkal & Huseyin Topaloglu, 2010. "Computing Time-Dependent Bid Prices in Network Revenue Management Problems," Transportation Science, INFORMS, vol. 44(1), pages 38-62, February.
    19. Warren B. Powell, 2016. "Perspectives of approximate dynamic programming," Annals of Operations Research, Springer, vol. 241(1), pages 319-356, June.
    20. 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.

    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.