[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Iterative Relaxation-Based Heuristics for the Multiple-choice Multidimensional Knapsack Problem

  • Conference paper
Hybrid Metaheuristics (HM 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5818))

Included in the following conference series:

Abstract

The development of efficient hybrid methods for solving hard optimization problems is not new in the operational research community. Some of these methods are based on the complete exploration of small neighbourhoods. In this paper, we apply iterative relaxation-based heuristics that solves a series of small sub-problems generated by exploiting information obtained from a series of relaxations to the multiple–choice multidimensional knapsack problem. We also apply local search methods to improve the solutions generated by these algorithms. The method is evaluated on a set of problem instances from the literature, and compared to the results reached by both Cplex solver and an efficient column generation–based algorithm. The results of the method are encouraging with 9 new best lower bounds among 33 problem instances.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Akbar, M.M., Rahman, M.S., Kaykobad, M., Manning, E.G., Shoja, G.C.: Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls. Computers & Operations Research 33, 1259–1273 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chen, L., Khan, S., Li, K.F., Manning, E.G.: Building an adaptive multimedia system using the utility model. In: Rolim, J.D.P. (ed.) IPPS-WS 1999 and SPDP-WS 1999. LNCS, vol. 1586, pp. 289–298. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  3. Cherfi, N., Hifi, M.: A column generation method for the multiple–choice multi–dimensional knapsack problem. Computational Optimization and Applications (2008), doi:10.1007/s10589-008-9184-7

    Google Scholar 

  4. Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxations induced neighborhoods to improve MIP solutions. Mathematical Programming 102, 71–90 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dyer, M.E., Riha, W.O., Walker, J.: A hybrid dynamic programming/branch and bound algorithm for the multiple–choice knapsack problem. European Journal of Operational Research 58, 43–54 (1995)

    MathSciNet  MATH  Google Scholar 

  6. Fischetti, M., Lodi, A.: Local Branching. Mathematical Programming 98, 23–47 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hansen, P., Mladenovic, N., Urosevic, D.: Variable neighbourhood search and local branching. Computers & Operations Research 33, 3034–3045 (2006)

    Article  MATH  Google Scholar 

  8. Hanafi, S., Wilbaut, C.: Improved convergent heuristics for the 0–1 multidimensional knapsack problem. Annals of Operations Research (2009), doi:10.1007/s10479-009-0546-z

    Google Scholar 

  9. Hifi, M., Michrafy, M., Sbihi, A.: Heuristic algorithms for the multiple–choice multidimensional knapsack problem. Journal of the Operational Research Society 55, 1323–1332 (2004)

    Article  MATH  Google Scholar 

  10. Khan, S., Li, K.F., Manning, E.G., Akbar, M.M.: Solving the knapsack problem for adaptive multimedia systems. Studia Informatica Universalis 2, 157–178 (2002)

    Google Scholar 

  11. Li, V.C., Curry, G.L., Boyd, E.A.: Towards the real time solution of strike force asset allocation problems. Computers & Operations Research 31, 273–291 (2004)

    Article  MATH  Google Scholar 

  12. Moser, M., Jokanovic, D.P., Shiratori, N.: An algorithm for the multidimensional multiple–choice knapsack problem. IEICE Transactions A(E80), 582–589 (1997)

    Google Scholar 

  13. Parra-Hernandez, R., Dimopoulos, N.: A new heuristic for solving the multi-choice multidimensional knapsack problem. Technical Report, Department of Electrical and Computer Engineering, University of Victoria (2002)

    Google Scholar 

  14. Pirkul, H.: A heuristic solution procedure for the multiconstraint zero–one knapsack problem. Naval Research Logistics 34, 161–172 (1987)

    Article  MATH  Google Scholar 

  15. Pisinger, D.: A minimal algorithm for the multiple–choice knapsack problem. European Journal of Operational Research 83, 394–410 (1995)

    Article  MATH  Google Scholar 

  16. Pisinger, D.: Budgeting with bounded multiple-choice constraints. European Journal of Operational Research 129, 471–480 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  17. Sinha, A., Zoltners, A.: The multiple–choice knapsack problem. Operations Research 27, 503–515 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  18. Toyoda, Y.: A simplified algorithm for obtaining approximate solution to zero–one programming problems. Management Sciences 21, 1417–1427 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  19. Watson, R.K.: Packet Networks and optimal admission and upgrade of service level agreements: applying the utility model. M.A.Sc. Thesis, Department of ECE, University of Victoria (2001)

    Google Scholar 

  20. Wilbaut, C., Hanafi, S.: New convergent heuristics for 0–1 mixed integer programming. European Journal of Operational Research 195, 62–74 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Wilbaut, C., Hanafi, S., Fréville, A., Balev, S.: Tabu Search: Global Intensification using Dynamic Programming. Control and Cybernetics 35, 579–598 (2006)

    MathSciNet  MATH  Google Scholar 

  22. Wilbaut, C., Hanafi, S., Salhi, S.: A survey of effective heuristics and their application to a variety of knapsack problems. IMA Journal of Management Mathematics 19, 227–244 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Univ Lille Nord de France, F-59000, Lille, France

    Saïd Hanafi, Raïd Mansi & Christophe Wilbaut

  2. UVHC, LAMIH, F-59313, Valenciennes, France

    Saïd Hanafi, Raïd Mansi & Christophe Wilbaut

  3. CNRS, UMR 8530, F-59313, Valenciennes, France

    Saïd Hanafi, Raïd Mansi & Christophe Wilbaut

Authors
  1. Saïd Hanafi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raïd Mansi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christophe Wilbaut
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universitat Politècnica de Catalunya, Omega 213 Campus Nord, Jordi Girona 1-3, 08034, Barcelona, Spain

    María J. Blesa

  2. Universitat Politècnica de Catalunya, Omega 112 Campus Nord, Jordi Girona 1-3, 08034, Barcelona, Spain

    Christian Blum

  3. DIEGM, Università di Udine, via delle Scienze 208, 33100, Udine, Italy

    Luca Di Gaspero

  4. DEIS, Università di Bologna, Sede di Cesena, Via Venezia 52, 47521, Cesena, Italy

    Andrea Roli

  5. IRIDIA CP 194/6, Université Libre de Bruxelles, Avenue Franklin D. Roosevelt 50, 1050, Bruxelles, Belgium

    Michael Sampels

  6. DIEGM, University of Udine, via delle Scienze 208, 33100, Udine, Italy

    Andrea Schaerf

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hanafi, S., Mansi, R., Wilbaut, C. (2009). Iterative Relaxation-Based Heuristics for the Multiple-choice Multidimensional Knapsack Problem. In: Blesa, M.J., Blum, C., Di Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds) Hybrid Metaheuristics. HM 2009. Lecture Notes in Computer Science, vol 5818. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04918-7_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-04918-7_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-04917-0

  • Online ISBN: 978-3-642-04918-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation