IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v297y2022i1p53-65.html
   My bibliography  Save this article

A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem

Author

Listed:
  • Lamanna, Leonardo
  • Mansini, Renata
  • Zanotti, Roberto

Abstract

The Multidimensional Multiple-choice Knapsack Problem (MMKP) is a complex combinatorial optimization problem for which finding high quality feasible solutions is very challenging. Recently, several heuristic approaches and a few exact algorithms have been proposed for its solution. These methods have been able to provide new best-known values for benchmark instances although many of them still remain unclosed to optimality. In this paper, we provide a new variant of the heuristic framework Kernel Search and apply it to the MMKP. The proposed variant keeps the method’s main idea of solving a sequence of restricted mixed-integer subproblems but innovates by partitioning the solution process into two different phases with complementary goals. The first phase strives for feasibility and collects important information to dynamically adapt subproblems’ dimension and solution time in the second phase that is focused on getting high quality solutions. This makes the global approach more scalable and efficient.

Suggested Citation

  • Lamanna, Leonardo & Mansini, Renata & Zanotti, Roberto, 2022. "A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 53-65.
    • Handle: RePEc:eee:ejores:v:297:y:2022:i:1:p:53-65
    DOI: 10.1016/j.ejor.2021.05.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721004197
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.05.007?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. P. C. Gilmore & R. E. Gomory, 1966. "The Theory and Computation of Knapsack Functions," Operations Research, INFORMS, vol. 14(6), pages 1045-1074, December.
    2. Yoshiaki Toyoda, 1975. "A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems," Management Science, INFORMS, vol. 21(12), pages 1417-1427, August.
    3. Renata Mansini & Roberto Zanotti, 2020. "A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1061-1079, October.
    4. N. Cherfi & M. Hifi, 2010. "A column generation method for the multiple-choice multi-dimensional knapsack problem," Computational Optimization and Applications, Springer, vol. 46(1), pages 51-73, May.
    5. Gao, Chao & Lu, Guanzhou & Yao, Xin & Li, Jinlong, 2017. "An iterative pseudo-gap enumeration approach for the Multidimensional Multiple-choice Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 260(1), pages 1-11.
    6. Guastaroba, G. & Savelsbergh, M. & Speranza, M.G., 2017. "Adaptive Kernel Search: A heuristic for solving Mixed Integer linear Programs," European Journal of Operational Research, Elsevier, vol. 263(3), pages 789-804.
    7. Voudouris, Christos & Tsang, Edward, 1999. "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 469-499, March.
    8. Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
    9. Enrico Angelelli & Renata Mansini & M. Speranza, 2012. "Kernel Search: a new heuristic framework for portfolio selection," Computational Optimization and Applications, Springer, vol. 51(1), pages 345-361, January.
    10. R Mansini & M G Speranza, 2002. "A multidimensional knapsack model for asset-backed securitization," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(8), pages 822-832, August.
    11. Chen, Yuning & Hao, Jin-Kao, 2014. "A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 313-322.
    12. M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
    13. Caserta, Marco & Voß, Stefan, 2019. "The robust multiple-choice multidimensional knapsack problem," Omega, Elsevier, vol. 86(C), pages 16-27.
    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. Mansini, Renata & Zanella, Marina & Zanotti, Roberto, 2023. "Optimizing a complex multi-objective personnel scheduling problem jointly complying with requests from customers and staff," Omega, Elsevier, vol. 114(C).
    2. Kinene, Alan & Birolini, Sebastian & Cattaneo, Mattia & Granberg, Tobias Andersson, 2023. "Electric aircraft charging network design for regional routes: A novel mathematical formulation and kernel search heuristic," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1300-1315.
    3. Jaeyoung Yang & Yong-Hyuk Kim & Yourim Yoon, 2022. "A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 10(4), pages 1-15, February.

    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. Jaeyoung Yang & Yong-Hyuk Kim & Yourim Yoon, 2022. "A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 10(4), pages 1-15, February.
    2. Renata Mansini & Roberto Zanotti, 2020. "A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1061-1079, October.
    3. Caserta, Marco & Voß, Stefan, 2019. "The robust multiple-choice multidimensional knapsack problem," Omega, Elsevier, vol. 86(C), pages 16-27.
    4. Mancini, Simona & Triki, Chefi & Piya, Sujan, 2022. "Optimal selection of touristic packages based on user preferences during sports mega-events," European Journal of Operational Research, Elsevier, vol. 302(3), pages 819-830.
    5. Ewa M. Bednarczuk & Janusz Miroforidis & Przemysław Pyzel, 2018. "A multi-criteria approach to approximate solution of multiple-choice knapsack problem," Computational Optimization and Applications, Springer, vol. 70(3), pages 889-910, July.
    6. Gao, Chao & Lu, Guanzhou & Yao, Xin & Li, Jinlong, 2017. "An iterative pseudo-gap enumeration approach for the Multidimensional Multiple-choice Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 260(1), pages 1-11.
    7. Setzer, Thomas & Blanc, Sebastian M., 2020. "Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems," European Journal of Operational Research, Elsevier, vol. 282(1), pages 58-70.
    8. M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.
    9. N. Cherfi & M. Hifi, 2010. "A column generation method for the multiple-choice multi-dimensional knapsack problem," Computational Optimization and Applications, Springer, vol. 46(1), pages 51-73, May.
    10. Diallo, Claver & Venkatadri, Uday & Khatab, Abdelhakim & Liu, Zhuojun, 2018. "Optimal selective maintenance decisions for large serial k-out-of-n: G systems under imperfect maintenance," Reliability Engineering and System Safety, Elsevier, vol. 175(C), pages 234-245.
    11. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    12. Yanhong Feng & Hongmei Wang & Zhaoquan Cai & Mingliang Li & Xi Li, 2023. "Hybrid Learning Moth Search Algorithm for Solving Multidimensional Knapsack Problems," Mathematics, MDPI, vol. 11(8), pages 1-28, April.
    13. M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
    14. Kirschstein, Thomas & Meisel, Frank, 2019. "A multi-period multi-commodity lot-sizing problem with supplier selection, storage selection and discounts for the process industry," European Journal of Operational Research, Elsevier, vol. 279(2), pages 393-406.
    15. Oliver Bastert & Benjamin Hummel & Sven de Vries, 2010. "A Generalized Wedelin Heuristic for Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 93-107, February.
    16. Navratil, Robert & Taylor, Stephen & Vecer, Jan, 2022. "On the utility maximization of the discrepancy between a perceived and market implied risk neutral distribution," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1215-1229.
    17. Al-Shihabi, Sameh, 2021. "A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem," Operations Research Perspectives, Elsevier, vol. 8(C).
    18. Ivan Derpich & Carlos Herrera & Felipe Sepúlveda & Hugo Ubilla, 2021. "Complexity indices for the multidimensional knapsack problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(2), pages 589-609, June.
    19. Dimitris Bertsimas & Ramazan Demir, 2002. "An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems," Management Science, INFORMS, vol. 48(4), pages 550-565, April.
    20. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.

    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:eee:ejores:v:297:y:2022:i:1:p:53-65. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.