IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v26y2020i4d10.1007_s10732-019-09434-9.html
   My bibliography  Save this article

On combining variable ordering heuristics for constraint satisfaction problems

Author

Listed:
  • Hongbo Li

    (Northeast Normal University)

  • Guozhong Feng

    (Northeast Normal University)

  • Minghao Yin

    (Northeast Normal University)

Abstract

Variable ordering heuristics play a central role in solving constraint satisfaction problems. Combining two variable ordering heuristics may generate a more efficient heuristic, such as dom/deg. In this paper, we propose a novel method for combining two variable ordering heuristics, namely Pearson-Correlation-Coefficient-based Combination (PCCC). While the existing combination strategies always combine participant heuristics, PCCC checks whether the participant heuristics are suitable for combination before combining them in the context of search. If they should be combined, it combines the heuristic scores to select a variable to branch on, otherwise, it randomly selects one of the participant heuristics to make the decision. The experiments on various benchmark problems show that PCCC can be used to combine different pairs of heuristics, and it is more robust than the participant heuristics and some classical combining strategies.

Suggested Citation

  • Hongbo Li & Guozhong Feng & Minghao Yin, 2020. "On combining variable ordering heuristics for constraint satisfaction problems," Journal of Heuristics, Springer, vol. 26(4), pages 453-474, August.
    • Handle: RePEc:spr:joheur:v:26:y:2020:i:4:d:10.1007_s10732-019-09434-9
    DOI: 10.1007/s10732-019-09434-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-019-09434-9
    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/s10732-019-09434-9?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. Hongbo Li & Yanchun Liang & Ning Zhang & Jinsong Guo & Dong Xu & Zhanshan Li, 2016. "Improving degree-based variable ordering heuristics for solving constraint satisfaction problems," Journal of Heuristics, Springer, vol. 22(2), pages 125-145, April.
    2. Edmund K Burke & Michel Gendreau & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & Rong Qu, 2013. "Hyper-heuristics: a survey of the state of the art," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1695-1724, December.
    Full references (including those not matched with items on IDEAS)

    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. Ahmed Kheiri & Alina G. Dragomir & David Mueller & Joaquim Gromicho & Caroline Jagtenberg & Jelke J. Hoorn, 2019. "Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 561-595, December.
    2. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    3. W. B. Yates & E. C. Keedwell, 2019. "An analysis of heuristic subsequences for offline hyper-heuristic learning," Journal of Heuristics, Springer, vol. 25(3), pages 399-430, June.
    4. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.
    5. Surafel Luleseged Tilahun & Mohamed A. Tawhid, 2019. "Swarm hyperheuristic framework," Journal of Heuristics, Springer, vol. 25(4), pages 809-836, October.
    6. Venkatesh Pandiri & Alok Singh, 2020. "Two multi-start heuristics for the k-traveling salesman problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(4), pages 1164-1204, December.
    7. Li, Wenwen & Özcan, Ender & John, Robert, 2017. "Multi-objective evolutionary algorithms and hyper-heuristics for wind farm layout optimisation," Renewable Energy, Elsevier, vol. 105(C), pages 473-482.
    8. Jari Kyngäs & Kimmo Nurmi & Nico Kyngäs & George Lilley & Thea Salter & Dries Goossens, 2017. "Scheduling the Australian Football League," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 973-982, August.
    9. Sara Ceschia & Rosita Guido & Andrea Schaerf, 2020. "Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods," Annals of Operations Research, Springer, vol. 288(1), pages 95-113, May.
    10. Aleksandra Swiercz & Wojciech Frohmberg & Michal Kierzynka & Pawel Wojciechowski & Piotr Zurkowski & Jan Badura & Artur Laskowski & Marta Kasprzak & Jacek Blazewicz, 2018. "GRASShopPER—An algorithm for de novo assembly based on GPU alignments," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-23, August.
    11. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    12. Alberto Santini & Stefan Ropke & Lars Magnus Hvattum, 2018. "A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic," Journal of Heuristics, Springer, vol. 24(5), pages 783-815, October.
    13. Sabir, Zulqurnain & Saoud, Sahar & Raja, Muhammad Asif Zahoor & Wahab, Hafiz Abdul & Arbi, Adnène, 2020. "Heuristic computing technique for numerical solutions of nonlinear fourth order Emden–Fowler equation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 178(C), pages 534-548.
    14. Mallol-Poyato, R. & Salcedo-Sanz, S. & Jiménez-Fernández, S. & Díaz-Villar, P., 2015. "Optimal discharge scheduling of energy storage systems in MicroGrids based on hyper-heuristics," Renewable Energy, Elsevier, vol. 83(C), pages 13-24.
    15. Longlong Leng & Yanwei Zhao & Zheng Wang & Jingling Zhang & Wanliang Wang & Chunmiao Zhang, 2019. "A Novel Hyper-Heuristic for the Biobjective Regional Low-Carbon Location-Routing Problem with Multiple Constraints," Sustainability, MDPI, vol. 11(6), pages 1-31, March.
    16. Helga Ingimundardottir & Thomas Philip Runarsson, 2018. "Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem," Journal of Scheduling, Springer, vol. 21(4), pages 413-428, August.
    17. Nelishia Pillay & Ender Özcan, 2019. "Automated generation of constructive ordering heuristics for educational timetabling," Annals of Operations Research, Springer, vol. 275(1), pages 181-208, April.
    18. Issam AlHadid & Khalid Kaabneh & Hassan Tarawneh, 2018. "Hybrid Simulated Annealing with Meta-Heuristic Methods to Solve UCT Problem," Modern Applied Science, Canadian Center of Science and Education, vol. 12(11), pages 385-385, November.
    19. Belinda Spratt & Erhan Kozan, 2021. "An integrated rolling horizon approach to increase operating theatre efficiency," Journal of Scheduling, Springer, vol. 24(1), pages 3-25, February.
    20. Lenin Kanagasabai, 2022. "Real power loss reduction by Q-learning and hyper-heuristic method," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 13(4), pages 1607-1622, August.

    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:joheur:v:26:y:2020:i:4:d:10.1007_s10732-019-09434-9. 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.