IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v58y2014i1p161-185.html
   My bibliography  Save this article

Strategic oscillation for the quadratic multiple knapsack problem

Author

Listed:
  • Carlos García-Martínez
  • Fred Glover
  • Francisco Rodriguez
  • Manuel Lozano
  • Rafael Martí

Abstract

The quadratic multiple knapsack problem (QMKP) consists in assigning a set of objects, which interact through paired profit values, exclusively to different capacity-constrained knapsacks with the aim of maximising total profit. Its many applications include the assignment of workmen to different tasks when their ability to cooperate may affect the results. Strategic oscillation (SO) is a search strategy that operates in relation to a critical boundary associated with important solution features (such as feasibility). Originally proposed in the context of tabu search, it has become widely applied as an efficient memory-based methodology. We apply strategic oscillation to the quadratic multiple knapsack problem, disclosing that SO effectively exploits domain-specific knowledge, and obtains solutions of particularly high quality compared to those obtained by current state-of-the-art algorithms. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Carlos García-Martínez & Fred Glover & Francisco Rodriguez & Manuel Lozano & Rafael Martí, 2014. "Strategic oscillation for the quadratic multiple knapsack problem," Computational Optimization and Applications, Springer, vol. 58(1), pages 161-185, May.
    • Handle: RePEc:spr:coopap:v:58:y:2014:i:1:p:161-185
    DOI: 10.1007/s10589-013-9623-y
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-013-9623-y
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-013-9623-y?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. Duarte, Abraham & Martí, Rafael & Álvarez, Ada & Ángel-Bello, Francisco, 2012. "Metaheuristics for the linear ordering problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 216(2), pages 270-277.
    2. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    3. M Gallego & M Laguna & R Martí & A Duarte, 2013. "Tabu search with strategic oscillation for the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(5), pages 724-734, May.
    4. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    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. Yuning Chen & Jin-Kao Hao, 2015. "Iterated responsive threshold search for the quadratic multiple knapsack problem," Annals of Operations Research, Springer, vol. 226(1), pages 101-131, March.
    2. Wei, Zequn & Hao, Jin-Kao & Ren, Jintong & Glover, Fred, 2023. "Responsive strategic oscillation for solving the disjunctively constrained knapsack problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 993-1009.
    3. Zheng Wang & Wei Xu & Xiangpei Hu & Yong Wang, 2022. "Inventory allocation to robotic mobile-rack and picker-to-part warehouses at minimum order-splitting and replenishment costs," Annals of Operations Research, Springer, vol. 316(1), pages 467-491, September.

    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. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    2. Arne Schulz, 2024. "Efficient neighborhood evaluation for the maximally diverse grouping problem," Annals of Operations Research, Springer, vol. 341(2), pages 1247-1265, October.
    3. Tao Pham Dinh & Nam Nguyen Canh & Hoai Le Thi, 2010. "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs," Journal of Global Optimization, Springer, vol. 48(4), pages 595-632, December.
    4. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    5. Yuning Chen & Jin-Kao Hao, 2015. "Iterated responsive threshold search for the quadratic multiple knapsack problem," Annals of Operations Research, Springer, vol. 226(1), pages 101-131, March.
    6. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    7. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    8. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    9. Fred Glover & Gary Kochenberger & Weihong Xie & Jianbin Luo, 2019. "Diversification methods for zero-one optimization," Journal of Heuristics, Springer, vol. 25(4), pages 643-671, October.
    10. Mauri, Geraldo Regis & Lorena, Luiz Antonio Nogueira, 2012. "A column generation approach for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 69-74.
    11. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    12. Glover, Fred & Alidaee, Bahram & Rego, Cesar & Kochenberger, Gary, 2002. "One-pass heuristics for large-scale unconstrained binary quadratic problems," European Journal of Operational Research, Elsevier, vol. 137(2), pages 272-287, March.
    13. Yang, Xiao & Cai, Zonghui & Jin, Ting & Tang, Zheng & Gao, Shangce, 2022. "A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 925-953.
    14. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    15. Goldengorin, Boris & Vink, Marius de, 1999. "Solving large instances of the quadratic cost of partition problem on dense graphs by data correcting algorithms," Research Report 99A50, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    16. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    17. Lai, Xiangjing & Hao, Jin-Kao & Fu, Zhang-Hua & Yue, Dong, 2021. "Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1067-1086.
    18. Alidaee, Bahram & Glover, Fred & Kochenberger, Gary & Wang, Haibo, 2007. "Solving the maximum edge weight clique problem via unconstrained quadratic programming," European Journal of Operational Research, Elsevier, vol. 181(2), pages 592-597, September.
    19. Anna Martínez-Gavara & Vicente Campos & Micael Gallego & Manuel Laguna & Rafael Martí, 2015. "Tabu search and GRASP for the capacitated clustering problem," Computational Optimization and Applications, Springer, vol. 62(2), pages 589-607, November.
    20. Mohan Gopalakrishnan & Ke Ding & Jean-Marie Bourjolly & Srimathy Mohan, 2001. "A Tabu-Search Heuristic for the Capacitated Lot-Sizing Problem with Set-up Carryover," Management Science, INFORMS, vol. 47(6), pages 851-863, June.

    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:spr:coopap:v:58:y:2014:i:1:p:161-185. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.