[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A matheuristic for the 0–1 generalized quadratic multiple knapsack problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this study, we address the 0–1 generalized quadratic multiple Knapsack problem. We use a linearization technique of the existing mathematical model and we propose a new matheuristic that we called Matheuristic Variable Neighborhood Search combining variable neighborhood search with integer programing to solve the large sized instances. The matheuristic considers a local search technique with an adaptive perturbation mechanism to assign the classes to different knapsacks, and then once the assignment is identified, applies the IP to select the items to allocate to each knapsack. Experimental results obtained on a wide set of benchmark instances clearly show the competitiveness of the proposed approach compared to the best state-of-the-art solving techniques.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Chajakis, E., Guignard, M.: Exact algorithms for the setup knapsack problem. IN-FOR. 32, 124–142 (1994)

    MATH  Google Scholar 

  2. Avci, M., Topaloglu, S.: A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem. Comput. Oper. Res. 83, 54–65 (2017)

    Article  MathSciNet  Google Scholar 

  3. Saraç, T., Sipahioglu, A.: Generalized quadratic multiple knapsack problem and two solution approaches. Comput. Oper. Res. 43, 78–89 (2014)

    Article  MathSciNet  Google Scholar 

  4. Pisinger, D.: The quadratic knapsack problem—a survey. Discret. Appl. Math. 155, 623–48 (2007)

    Article  MathSciNet  Google Scholar 

  5. Johnson, E., Mehrotra, A., Nemhauser, G.: Min-cut clustering. Math. Program. 62, 133–152 (1993)

    Article  MathSciNet  Google Scholar 

  6. Chaillou, P., Hansen, P., Mahieu, Y.: Best network flow bounds for the quadratic knapsack problem. Combinatorial Optimization, pp. 225–235. Springer, Berlin (1989)

    Chapter  Google Scholar 

  7. Billionnet, A., Soutif, É.: Using a mixed integer programming tool for solving the 0–1 quadratic knapsack problem. INFORMS J. Comput. 16, 188–197 (2004)

    Article  MathSciNet  Google Scholar 

  8. Sundar, S., Singh, A.: A swarm intelligence approach to the quadratic multiple knapsack problem. Neural Information Processing. Theory and Algorithms, pp. 626–633. Springer, Berlin (2010)

    Google Scholar 

  9. García-Martínez, C., Rodriguez, F.J., Lozano, M.: Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem. Eur. J. Oper. Res. 232, 454–463 (2014)

    Article  MathSciNet  Google Scholar 

  10. Qin, J., Xu, X., Wu, Q., Cheng, T.C.E.: Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem. Comput. Oper. Res. 66, 199–214 (2016)

    Article  MathSciNet  Google Scholar 

  11. Peng, B., Liu, M., Lü, Z., Kochengber, G., Wang, H.: An ejection chain approach for the quadratic multiple knapsack problem. Eur. J. Oper. Res. 253, 328–336 (2016)

    Article  MathSciNet  Google Scholar 

  12. Chen, Y., Hao, J.K.: Memetic search for the generalized quadratic multiple knapsack problem. IEEE Trans. Evolut. Comput. 20, 908–923 (2016)

    Article  Google Scholar 

  13. Jourdan, L., Basseur, M., Talbi, E.G.: Hybridizing exact methods and metaheuristics. Eur. J. Oper. Res. 199, 620–629 (2009)

    Article  MathSciNet  Google Scholar 

  14. Dumitrescu, I., Stutzle, T.: Combinations of local search and exact algorithms. Appl. Evolut. Comput. 2611, 211–223 (2003)

    Article  Google Scholar 

  15. Puchinger, J., Raidl, G.R.: Combining meta-heuristics and exact algorithms in combinatorial optimization. Artif. Intell. Knowl. Eng. Appl. 3562, 41–53 (2005)

    Google Scholar 

  16. Hanafi, S., Lazić, J., Mladenović, N., Wilbaut, C.: New hybrid matheuristics for solving the multidimensional knapsack problem. In: International Workshop on Hybrid Metaheuristics, pp. 118–132. vol. 6373, Springer, Berlin (2010)

  17. Fernandes, S., Lourenco, H.: Hybrid combining local search heuristics with exact algorithms. In: Algoritmos Evolutivos y Bioinspirados, pp. 269–274. Spain (2007)

  18. Burke, E.K., Li, J., Qu, R.: A hybrid model of integer programming and variable neighborhood search for highly-constrained nurse rostering problems. Eur. J. Oper. Res. 2003, 484–493 (2010)

    Article  Google Scholar 

  19. Prandtstetter, M., Raidl, G.R.: An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. Eur. J. Oper. Res. 191, 1004–1022 (2008)

    Article  MathSciNet  Google Scholar 

  20. Lamghari, A., Dimitrakopoulos, R., Ferland, J.A.: A hybrid method based on linear programming and variable neighborhood descent for scheduling production in open-pit mines. J. Glob. Optim. 63, 555–582 (2015)

    Article  MathSciNet  Google Scholar 

  21. Vasquez, M., Hao, J.K.: A hybrid approach for the 0–1 multidimensional knapsack problem. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 328-333. Washington (2001)

  22. Billionnet, A., Calmels, F.: Linear programming for the 0–1 quadratic knapsack problem. Eur. J. Oper. Res. 92, 310–325 (1996)

    Article  Google Scholar 

  23. Martello, S., Pisinger, D., Toth, P.: New trends in exact algorithms for the 0–1 knapsack problems. Eur. J. Oper. Res. 123, 325–332 (2000)

    Article  MathSciNet  Google Scholar 

  24. Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997)

    Article  MathSciNet  Google Scholar 

  25. Hansen, P., Mladenovic, N., Todosijevic, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5, 423–454 (2017)

    Article  MathSciNet  Google Scholar 

  26. Jarboui, B., Derbel, H., Hanafi, S., Maldenovic, N.: Variable neighborhood search for location routing. Comput. Oper. Res. 40, 47–57 (2013)

    Article  MathSciNet  Google Scholar 

  27. Soyster, A.L., Lev, B., Slivka, W.: Zero-one programming with many variables and few constraints. Eur. J. Oper. Res. 2, 195–201 (1978)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Faculty of Economics and Management Sciences of Sfax, University of Sfax, Sfax, Tunisia

    Yassine Adouani

  2. Higher Colleges of Technology, Abu Dhabi, United Arab Emirates

    Bassem Jarboui

  3. Faculty of Sciences and Techniques, University of Lyon, University Jean Monnet Saint-Etienne, 42000, Saint-Etienne, France

    Malek Masmoudi

Authors
  1. Yassine Adouani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bassem Jarboui
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Malek Masmoudi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yassine Adouani.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 140 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Adouani, Y., Jarboui, B. & Masmoudi, M. A matheuristic for the 0–1 generalized quadratic multiple knapsack problem. Optim Lett 16, 37–58 (2022). https://doi.org/10.1007/s11590-019-01503-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-019-01503-z

Keywords

Search

Navigation