2026-07-22T18:37:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23888 2025-11-12T13:11:01Z ddc:004 open_access

Understanding the Impact of Value Selection Heuristics in Scheduling Problems Luchterhand, Tim Hebrard, Emmanuel Thiébaux, Sylvie Scheduling Branching Heuristics Constraint Programming It has been observed that value selection heuristics have less impact than other heuristic choices when solving hard combinatorial optimization (CO) problems. It is often thought that this is because more time is spent on unsatisfiable sub-problems where the value ordering is irrelevant. In this paper we investigate this belief in the scheduling domain and come up with a more detailed explanation. We find that, even though there are less relevant choices to be made on hard instances, each mistake tends to have a bigger impact, to a point where the potential gain from a value heuristic predominates. Moreover, we observe two interesting and relatively surprising phenomena when solving scheduling problems. First, the accuracy of a given value selection heuristic decreases with the optimality gap. Second, the computational penalty of a mistake increases with the accuracy of the heuristic. For the first observation, we argue that on hard problems, constraint propagation removes a large portion of choices that align with the intuition behind the heuristic. This means that the heuristic faces mostly difficult choices. For the second observation, we argue that simple heuristics tend to make more mistakes on intuitive choice points, and the computational cost for refuting these mistakes is smaller than for those made by a more accurate heuristic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tim Luchterhand and Emmanuel Hebrard and Sylvie Thiébaux 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.27 urn:nbn:de:0030-drops-238885 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode