IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v20y2022i2d10.1007_s10288-022-00510-8.html
   My bibliography  Save this article

Matheuristics: using mathematics for heuristic design

Author

Listed:
  • Marco Antonio Boschetti

    (University of Bologna)

  • Vittorio Maniezzo

    (University of Bologna)

Abstract

Matheuristics are heuristic algorithms based on mathematical tools such as the ones provided by mathematical programming, that are structurally general enough to be applied to different problems with little adaptations to their abstract structure. The result can be metaheuristic hybrids having components derived from the mathematical model of the problems of interest, but the mathematical techniques themselves can define general heuristic solution frameworks. In this paper, we focus our attention on mathematical programming and its contributions to developing effective heuristics. We briefly describe the mathematical tools available and then some matheuristic approaches, reporting some representative examples from the literature. We also take the opportunity to provide some ideas for possible future development.

Suggested Citation

  • Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    • Handle: RePEc:spr:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-022-00510-8
    DOI: 10.1007/s10288-022-00510-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-022-00510-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-022-00510-8?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. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    2. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    3. Borisovsky, P. & Dolgui, A. & Eremeev, A., 2009. "Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder," European Journal of Operational Research, Elsevier, vol. 195(3), pages 770-779, June.
    4. Paul M. Thompson & Harilaos N. Psaraftis, 1993. "Cyclic Transfer Algorithm for Multivehicle Routing and Scheduling Problems," Operations Research, INFORMS, vol. 41(5), pages 935-946, October.
    5. Raidl, Günther R., 2015. "Decomposition based hybrid metaheuristics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 66-76.
    6. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    7. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    8. Marshall L. Fisher & R. Jaikumar & Luk N. Van Wassenhove, 1986. "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, INFORMS, vol. 32(9), pages 1095-1103, September.
    9. Boschetti, Marco A. & Golfarelli, Matteo & Graziani, Simone, 2020. "An exact method for shrinking pivot tables," Omega, Elsevier, vol. 93(C).
    10. Prandtstetter, Matthias & Raidl, Günther R., 2008. "An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 1004-1022, December.
    11. Tatsushi Nishi & Tatsuya Okura & Eduardo Lalla-Ruiz & Stefan Voß, 2020. "A dynamic programming-based matheuristic for the dynamic berth allocation problem," Annals of Operations Research, Springer, vol. 286(1), pages 391-410, March.
    12. Holmberg, Kaj & Ling, Jonas, 1997. "A Lagrangean heuristic for the facility location problem with staircase costs," European Journal of Operational Research, Elsevier, vol. 97(1), pages 63-74, February.
    13. Christian Blum, 2008. "Beam-ACO for Simple Assembly Line Balancing," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 618-627, November.
    14. Fred Glover, 1975. "Surrogate Constraint Duality in Mathematical Programming," Operations Research, INFORMS, vol. 23(3), pages 434-451, June.
    15. Lorena, Luiz Antonio N. & Belo Lopes, Fabio, 1994. "A surrogate heuristic for set covering problems," European Journal of Operational Research, Elsevier, vol. 79(1), pages 138-150, November.
    16. Harvey J. Greenberg & William P. Pierskalla, 1970. "Surrogate Mathematical Programming," Operations Research, INFORMS, vol. 18(5), pages 924-939, October.
    17. M.A. Boschetti & A. Mingozzi & S. Ricciardelli, 2004. "An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem," Annals of Operations Research, Springer, vol. 127(1), pages 177-201, March.
    18. Richard K. Congram & Chris N. Potts & Steef L. van de Velde, 2002. "An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 52-67, February.
    19. Umetani, Shunji & Yagiura, Mutsunori & Ibaraki, Toshihide, 2003. "One-dimensional cutting stock problem to minimize the number of different patterns," European Journal of Operational Research, Elsevier, vol. 146(2), pages 388-402, April.
    20. Fred Glover, 1965. "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Research, INFORMS, vol. 13(6), pages 879-919, December.
    21. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    22. Fred Glover, 1968. "Surrogate Constraints," Operations Research, INFORMS, vol. 16(4), pages 741-749, August.
    23. 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.
    24. Barcelo, J. & Casanovas, J., 1984. "A heuristic lagrangean algorithm for the capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 15(2), pages 212-226, February.
    25. A. Mingozzi & M. A. Boschetti & S. Ricciardelli & L. Bianco, 1999. "A Set Partitioning Approach to the Crew Scheduling Problem," Operations Research, INFORMS, vol. 47(6), pages 873-888, December.
    26. Yagiura, Mutsunori & Ibaraki, Toshihide, 1996. "The use of dynamic programming in genetic algorithms for permutation problems," European Journal of Operational Research, Elsevier, vol. 92(2), pages 387-401, July.
    27. Mike Hewitt & George L. Nemhauser & Martin W. P. Savelsbergh, 2010. "Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 314-325, May.
    28. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    29. Yipei Zhang & Feng Chu & Ada Che & Yugang Yu & Xin Feng, 2019. "Novel model and kernel search heuristic for multi-period closed-loop food supply chain planning with returnable transport items," International Journal of Production Research, Taylor & Francis Journals, vol. 57(23), pages 7439-7456, December.
    30. Narciso, Marcelo G. & Lorena, Luiz Antonio N., 1999. "Lagrangean/surrogate relaxation for generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 114(1), pages 165-177, April.
    31. Fred Glover, 1990. "Tabu Search—Part II," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 4-32, February.
    32. Guastaroba, G. & Speranza, M.G., 2012. "Kernel Search: An application to the index tracking problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 54-68.
    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. Raka Jovanovic & Stefan Voß, 2024. "Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(4), pages 1329-1365, December.
    2. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Tao, Siyu & Zhang, Bojian & Peng, Qiyuan, 2024. "A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).

    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. Andaryan, Abdullah Zareh & Mousighichi, Kasra & Ghaffarinasab, Nader, 2024. "A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands," European Journal of Operational Research, Elsevier, vol. 312(3), pages 954-968.
    2. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    3. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar & Mohammad Hassan Sharifitabar, 2015. "A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 48-58, February.
    4. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    5. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    6. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    7. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    8. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    9. Abdmouleh, Zeineb & Gastli, Adel & Ben-Brahim, Lazhar & Haouari, Mohamed & Al-Emadi, Nasser Ahmed, 2017. "Review of optimization techniques applied for the integration of distributed generation from renewable energy sources," Renewable Energy, Elsevier, vol. 113(C), pages 266-280.
    10. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    11. Chris S. K. Leung & Henry Y. K. Lau, 2018. "Multiobjective Simulation-Based Optimization Based on Artificial Immune Systems for a Distribution Center," Journal of Optimization, Hindawi, vol. 2018, pages 1-15, May.
    12. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.
    13. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    14. Panta Lučić & Dušan Teodorović, 2007. "Metaheuristics approach to the aircrew rostering problem," Annals of Operations Research, Springer, vol. 155(1), pages 311-338, November.
    15. Daniel O’Malley & Velimir V Vesselinov & Boian S Alexandrov & Ludmil B Alexandrov, 2018. "Nonnegative/Binary matrix factorization with a D-Wave quantum annealer," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-12, December.
    16. C-H Lan & C-C Chen, 2007. "Optimal purchase of two-itemized drugs for a disease," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 309-316, March.
    17. G Lulli & U Pietropaoli & N Ricciardi, 2011. "Service network design for freight railway transportation: the Italian case," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2107-2119, December.
    18. Alidaee, Bahram, 2014. "Zero duality gap in surrogate constraint optimization: A concise review of models," European Journal of Operational Research, Elsevier, vol. 232(2), pages 241-248.
    19. Sadan Kulturel-Konak & Bryan A. Norman & David W. Coit & Alice E. Smith, 2004. "Exploiting Tabu Search Memory in Constrained Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 241-254, August.
    20. Ouzineb, Mohamed & Nourelfath, Mustapha & Gendreau, Michel, 2008. "Tabu search for the redundancy allocation problem of homogenous series–parallel multi-state systems," Reliability Engineering and System Safety, Elsevier, vol. 93(8), pages 1257-1272.

    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:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-022-00510-8. 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.