Pith. sign in

REVIEW 3 major objections 4 minor 71 references

Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Treating FDS's branch choice as a multi-armed bandit makes complete search faster and improves hundreds of published bounds.

desk verdict Solid empirical paper: real speedups from hybrid exploration and choice rollback in FDS, but the 'implicitly minimizes' claim is heuristic and the abstract overstates the lower-bound comparison. read the letter →

arxiv 2508.20056 v1 pith:G6KUH6Q7 submitted 2025-08-27 cs.LG

Vilém Heinz , Petr Vilím , Zdeněk Hanzálek This is my paper
classification cs.LG MSC 90-0890B3590C5990C9968T2090C27
keywords Failure-DirectedSearchMulti-armedbanditConstraintProgrammingReinforcementLearningJobShopSchedulingRCPSPtreeminimizationLowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Failure-Directed Search (FDS) is a complete constraint-programming search method that proves optimality by exploring a search tree, and this paper argues that its branch-choice scoring is, in essence, a multi-armed bandit problem: each possible domain-splitting decision is an arm whose reward is how quickly the branch fails. On that reading, the original FDS was pure exploitation, so the paper adds bandit-style exploration—epsilon-greedy, Boltzmann, UCB-1, and Thompson sampling—combined with a greedy fallback, plus a 'choice rollback' mechanism that tests exploratory choices without permanently growing the tree. After tuning 24 parameters on job-shop (JSSP) and resource-constrained project scheduling (RCPSP) instances, the enhanced FDS is about 1.7 times faster on JSSP and 2.5 times faster on RCPSP than the original OptalCP implementation, and 3.5 times and 2.1 times faster than IBM CP Optimizer's FDS, respectively. Within a 900-second per-instance limit it reports improved state-of-the-art lower bounds on 78 of 84 open JSSP and 226 of 393 open RCPSP instances, closing a handful. The practical stake is that a generic complete search engine can get large speedups from a simple learning mechanism, directly tightening known optimality proofs on hard scheduling benchmarks.

What carries the argument

The load-bearing object is Failure-Directed Search (FDS), a complete constraint-programming search algorithm that branches by splitting a variable's domain into two intervals and, at each node, assigns a local rating of 0 when propagation detects infeasibility and 1+R otherwise, with branch ratings updated as exponential moving averages. The paper's theoretical move is to map those ratings onto Q-values of a multi-armed bandit and define reward as the negation of local rating, so minimizing accumulated penalty is proportional to the search tree's internal node count. Carrying the argument are the hybrid choice-selection strategies—especially B-greedy, which picks Boltzmann-exploration choice

What would settle it

Rerun the enhanced FDS on the 84 open JSSP instances after incorporating the seven newer lower bounds from the follow-up paper cited in Section 6.3 and compare the counts; if fewer than 78 instances improve, the state-of-the-art claim is weakened. Alternatively, give CP Optimizer's FDS the same 900-second single-core limit on the same machine and check whether it reaches the same or better lower bounds.

Watch

Extended reading notes

Core claim

The paper's central claim is that the branch-selection rule inside Failure-Directed Search—which choice to split on next, and which side to try first—is structurally the same as arm selection in a multi-armed bandit, with reward defined as a negative local rating that penalizes feasible branches and rewards infeasibility. Maximizing the sum of these rewards is proportional to minimizing the number of internal nodes in the search tree, so the search-tree-size minimization problem is an instance of reward maximization. From this equivalence the authors derive that the original FDS's greedy rating rule is an epsilon-greedy bandit with epsilon equal to zero, i.e., pure exploitation, and they rep

Load-bearing premise

The headline lower-bound results assume the published 'old' values are still the true best known bounds and are comparable to a single 900-second, single-core run; if any are stale or produced under more favorable conditions, the count of improved bounds overstates the advance.

Editorial extensions

If this is right

  • Complete search in OptalCP's FDS becomes roughly 1.7 times faster on JSSP and 2.5 times faster on RCPSP than the same solver's original FDS, with the gains coming mostly from fewer branches rather than faster propagation.
  • Against IBM CP Optimizer's FDS under single-worker settings, the enhanced FDS is 3.5 times faster on JSSP and 2.1 times faster on RCPSP on the tested instances.
  • Using 900 seconds per instance, the algorithm raises reported best lower bounds for 78 of 84 open JSSP and 226 of 393 open RCPSP benchmark instances, and fully closes several instances by matching the known upper bound.
  • Exploration is not wasted: a 10 percent exploration rate with choice rollback outperforms lower or zero exploration, and freezing learned ratings makes runs slower, so continuous rating updates are load-bearing.
  • Because the mechanism is problem-independent, the same enhanced complete search could be applied to other constraint problems where FDS proves infeasibility against a bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the MAB mapping should transfer to any complete search whose node rating is an exponential average of a fail/success signal, including branch-and-bound for integer programming, so the speedups may not be specific to scheduling.
  • Editorial inference: the 1.7x/2.5x and lower-bound gains are measured against a particular baseline and literature values that can go stale; a fairer comparison would rerun the same 900-second protocol against the latest published bounds after the seven newer bounds the paper acknowledges.
  • Editorial inference: choice rollback's roughly 70 percent rollback rate suggests an upper bound on exploration cost; one could test whether dynamically adapting epsilon from this rate produces further gains.
  • Editorial inference: since the paper used infeasible instances (upper bound set below optimum) to test FDS, the practical gain inside a full solver depends on how much of total runtime is spent on optimality proofs; the paper's own figure suggests it is often the majority.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies Failure-Directed Search (FDS) for Constraint Programming scheduling, argues that FDS branch selection is closely related to the Multi-armed Bandit (MAB) problem, and uses this analogy to introduce exploration strategies (epsilon-greedy, B-greedy, U-greedy, T-greedy) with a problem-specific choice-rollback mechanism and parameter tuning. The enhanced FDS is evaluated on held-out JSSP and RCPSP instance sets, reporting speedups over the original OptalCP FDS and over IBM CP Optimizer 22.1's FDS, and on all open benchmark instances, claiming 78/84 JSSP and 226/393 RCPSP improved state-of-the-art lower bounds within 900 seconds.

Significance. If the empirical claims hold, this is a practically valuable contribution to complete search in CP-based scheduling. The experimental protocol has notable strengths: held-out evaluation sets, 7-seed averages, paired Wilcoxon and t-tests, and branch-count comparisons that partly control for implementation efficiency. The MAB connection is more of an analogy than a formal derivation, and the authors themselves disclaim regret guarantees; the weight of the paper therefore rests on the empirical results and on the lower-bound comparison. The reproducible data and solver availability are additional strengths. The main risk is the fairness and currency of the state-of-the-art lower-bound baselines, as discussed below.

major comments (3)
  1. [§6.3, Tables D.15–D.16] The headline claim of 78/84 JSSP and 226/393 RCPSP improved state-of-the-art lower bounds is computed against Old LB values taken from web aggregators [52]–[54]. These are not peer-reviewed sources, they are accessed at specific dates, and [56] already reports seven JSSP bounds not reflected in the comparison. The disclaimer in §6.3 is honest, but the abstract and conclusion present the counts without that caveat. In addition, Appendix D lists one time per instance, so no seed-variance information is available for the 900 s protocol. Please re-derive the Better/Equal/Worse counts after incorporating [56] and any updates to [52]–[54], report access dates/versions, and provide at least a sensitivity analysis over a few seeds on the open instances.
  2. [Appendix C.1 and C.2] Tables C.7 and C.9 are numerically identical, as are C.8/C.10, C.11/C.13, and C.12/C.14, even though the captions state that one is a paired t-test and the other a Wilcoxon signed-rank test. As printed, the Wilcoxon results are actually missing, so the strong statistical-significance claims in §6.1–§6.2 cannot be verified. Please replace the duplicated tables with the correct statistics and report p-values.
  3. [§6.1, Table 2] Entries marked 'timeout' are not defined: no time limit is stated, no aggregation rule is given, and it is unclear whether timeouts are included in the reported sums/means. This matters because the conclusion that choice rollback is efficient for all strategies and the ranking of U-greedy/T-greedy rest on this table. Please provide the cutoff, the number of timeouts per row, and the imputation/aggregation method used for the 7-run averages.
minor comments (4)
  1. [§3.2] Equations (4)–(6) make the MAB correspondence definitional by setting reward = -localRatings, and the statement that sFDS 'implicitly minimizes the search tree' is only informally justified through penalty-sum proportionality. Since the authors explicitly disclaim regret guarantees, it would be clearer to present this as an analogy and to give a short formal statement of the penalty/tree-size proportionality.
  2. [Table 1] The 'Importance' column is not defined. Optuna supports several importance measures; please state which one is used and how it is normalized.
  3. [Appendix B.4] The histograms in Figure B.7 use bins labeled '0 1 2 4 8 ∞' without explaining the bin edges. A short caption describing the binning would improve readability.
  4. [Conclusions] Minor typos remain, e.g. 'implemention' in §7, 'scarse' in §2.3, and 'T able D.15' with a stray space. These do not affect the technical content.

Circularity Check

1 steps flagged · score 3.0 of 10

MAB equivalence is definitional, but the headline speedups and lower-bound improvements are externally benchmarked and not circular.

  1. self definitional [Section 3.2, Equations (1)-(6)]
    "So, we define localReward (reward for one branch) as a negation of obtained localRating s: localReward = −localRatings, (4) ... This makes Equation (2) equivalent to the standard Q-learning equation: Q(c) := Q(c) + α · (reward − Q(c)), (6)"

    The correspondence between FDS branching and MAB is manufactured by defining the MAB reward as the negative of the FDS localRating. Substituting (4) into the rating update (2) yields exactly the Q-learning update (6). Thus the claimed theoretical result that FDS is closely related to MAB is true by definition, not by independent derivation. The subsequent statement that MAB algorithms are suitable candidates inherits this definitional character. However, this step does not fit the measured speedups; those come from empirical comparisons against the OptalCP baseline, IBM CP Optimizer, and literature lower bounds, so the circularity is partial and not load-bearing for the headline numbers.

full rationale

The paper's central empirical claims are externally grounded. The enhanced FDS is compared against its own OptalCP baseline, against IBM CP Optimizer 22.1, and against literature lower bounds for open JSSP and RCPSP instances; these are independent reference points. Parameter tuning is separated from evaluation: development instances are used for tuning, and evaluation instances are used for reporting (Section 5), so the speedup figures are not fitted predictions on the same data used to choose the parameters. The self-citation of the original FDS paper [9] is appropriate and not load-bearing: FDS is a published external algorithm, and the improvements are new. The only notable definitional step is the MAB analogy in Section 3.2, where reward is defined as the negative of the FDS rating, making the Q-learning update identical to the FDS rating update by construction. This is a genuine self-definitional element, but the paper does not use it to compute the reported runtime or lower-bound results; those are measured empirically. Therefore the circularity is minor and confined to the theoretical framing, not to the paper's key experimental contributions.

Assumptions & free parameters 12 free parameters · 5 assumptions · 0 invented entities

The reported performance depends on the OptalCP FDS implementation, the correctness and comparability of reference lower bounds, and the identified parameter values. These are external inputs the paper does not derive, plus a constructed reward mapping used to motivate the bandit connection.

free parameters (12)
  • LengthStepRatio (LSR) = JSSP: 0.6-0.85, RCPSP: 0.3-0.55
    Controls pivot spacing when generating branching choices; authors call it extremely sensitive and problem-dependent (Section 4.2).
  • UniformChoiceStep (UCS) = true (uniform)
    Boolean deciding whether step is computed from average interval length or per-variable length; tuned to uniform.
  • RatingAverageComparison (RAC) = off
    Removing avgRating[d] and compensating with InitialRating is part of the tuned configuration (Appendix B.2).
  • RatingAverageLength (RAL) = 30
    L in the hybrid alpha calculation; tuned between 5 and 100 (Section 4.2).
  • InitialRating (IR) = JSSP: 0.38, RCPSP: 0.76
    Initial Q-value for unexplored branches; tuned based on the optimistic initial values idea (Table 1).
  • Epsilon = JSSP: 0.09, RCPSP: 0.12
    Exploration probability in the hybrid greedy bandit strategies; tuned (Table 1).
  • BothFailRewardFactor (BFRF) = JSSP: 0.95, RCPSP: 0.98
    Reward multiplier when both branches of a choice fail; tuned (Table 1).
  • StrongBranchingCriterion (SBC) = Left
    Strong branching evaluates only left-branch localRating; tuned (Table 1).
  • StrongBranchingSize (SBS) = JSSP: 12, RCPSP: 8
    Number of choices probed by strong branching; tuned (Table 1).
  • MaxInitialChoicesPerVariable (MIC) = JSSP: 80, RCPSP: 68
    Limit on initial choices per variable; tuned (Table 1).
  • PenaltyNotFailed (PNF) = JSSP: 0.8, RCPSP: 0.92
    Penalty for a non-failing branch; tuned (Table 1).
  • Boltzmann temperature tau = 1
    Fixed temperature for softmax exploration in B-greedy; a parameter of the choice-selection strategy (Section 4.1).
assumptions (5)
  • domain assumption OptalCP's FDS is a faithful implementation of the original FDS [9].
    Row 1 of Table 3 is the baseline; if the implementation diverges, the speedup attribution to MAB and tuning is compromised (Appendix A).
  • domain assumption The source lower bounds in [52], [53], [54] are the current state-of-the-art values for each open instance.
    The better/equal/closed counts in Table 4 assume the Old LB column is correct and up to date; the paper itself notes [56] appeared after submission.
  • ad hoc to paper Defining reward as -localRating makes rating minimization equivalent to Q-learning reward maximization, and the penalty sum monotonically tracks search tree size.
    Section 3.2, Equations (4) and (5). The equivalence is by construction; the search-tree-minimization claim is asserted rather than proven.
  • domain assumption MAB algorithms remain effective when arms change over time and rewards are non-stationary.
    Section 3.2 invokes [39] and [40] for arm-acquiring and non-stationary MAB; the FDS setting violates classical MAB assumptions.
  • domain assumption Constraint propagation algorithms used in OptalCP are sound, including timetable filtering, edge finding, and related propagators.
    Correctness of infeasibility proofs and lower-bound results depends on sound propagation (Appendix A).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks." pith.science (2026). https://pith.science/paper/G6KUH6Q7

@misc{pith2026250820056,
  author       = {Pith},
  title        = {Pith review of: Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G6KUH6Q7}},
  note         = {Machine review of arXiv:2508.20056}
}
read the original abstract

Failure-Directed Search (FDS) is a significant complete generic search algorithm used in Constraint Programming (CP) to efficiently explore the search space, proven particularly effective on scheduling problems. This paper analyzes FDS's properties, showing that minimizing the size of its search tree guided by ranked branching decisions is closely related to the Multi-armed bandit (MAB) problem. Building on this insight, MAB reinforcement learning algorithms are applied to FDS, extended with problem-specific refinements and parameter tuning, and evaluated on the two most fundamental scheduling problems, the Job Shop Scheduling Problem (JSSP) and Resource-Constrained Project Scheduling Problem (RCPSP). The resulting enhanced FDS, using the best extended MAB algorithm and configuration, performs 1.7 times faster on the JSSP and 2.1 times faster on the RCPSP benchmarks compared to the original implementation in a new solver called OptalCP, while also being 3.5 times faster on the JSSP and 2.1 times faster on the RCPSP benchmarks than the current state-of-the-art FDS algorithm in IBM CP Optimizer 22.1. Furthermore, using only a 900-second time limit per instance, the enhanced FDS improved the existing state-of-the-art lower bounds of 78 of 84 JSSP and 226 of 393 RCPSP standard open benchmark instances while also completely closing a few of them.

Figures

Figures reproduced from arXiv: 2508.20056 by the authors.

Figure 1
Figure 1. Bar charts showing gradual reduction of explored branches needed to prove instance [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Scatter plots showing the ratio between explored branches in the 1st run and the 10th [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Graph demonstrating the cooperation of LNS and FDS in solving process on (formerly) [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

71 extracted references · 62 canonical work pages

  1. [52]

    URL https://optimizizer.com/jobshop.php

    Optimizizer, Job shop scheduling problem solver, Online, accessed: April 14, 2023 (n.d.). URL https://optimizizer.com/jobshop.php

    work page 2023

  2. [54]

    of Ghent, Resource-constrained project scheduling, Online, accessed: Mar 2, 2023 (n.d.)

    U. of Ghent, Resource-constrained project scheduling, Online, accessed: Mar 2, 2023 (n.d.). URL https://www.projectmanagement.ugent.be/research/project_ scheduling/rcpsp/

    work page 2023

  3. [56]

    Yuraszeck, G

    F. Yuraszeck, G. Mej ´ ıa, D. A. Rossit, A. L¨ uer-Villagra, A constraint programming-based lower bounding procedure for the job shop schedul- ing problem, Computers & Operations Research 177 (2025) 106964. doi:https://doi.org/10.1016/j.cor.2024.106964. URL https://www.sciencedirect.com/science/article/pii/ S0305054824004362 58

    work page arXiv 2025

  4. [1]

    Liess, P

    O. Liess, P. Michelon, A constraint programming approach for the resource- constrained project scheduling problem, Annals of Operations Research 157 (2008). doi:https://doi.org/10.1007/s10479-007-0188-y . URL https://link.springer.com/article/10.1007/s10479-007-0188-y

    work page doi:10.1007/s10479-007-0188-y 2008

  5. [2]

    F. He, R. Qu, A constraint programming based column generation approach to nurse rostering problems, Computers & Operations Research 39 (12) (2012) 3331–3343. doi:https://doi.org/10.1016/j.cor.2012.04.018. URL https://www.sciencedirect.com/science/article/pii/ S0305054812000986

    work page doi:10.1016/j.cor.2012.04.018 2012

  6. [3]

    Nedb´ alek, A

    L. Nedb´ alek, A. Nov´ ak, Bottleneck identification in resource-constrained project scheduling via constraint relaxation, in: Proceedings of the 14th International Conference on Operations Research and Enterprise Systems - ICORES, INSTICC, SciTePress, 2025, pp. 340–347. doi:10.5220/ 0013253700003893

    work page 2025

  7. [4]

    L. R. Abreu, M. S. Nagano, A new hybridization of adaptive large neigh- borhood search with constraint programming for open shop scheduling with sequence-dependent setup times, Computers & Industrial Engineering 168 (2022) 108128. doi:https://doi.org/10.1016/j.cie.2022.108128. URL https://www.sciencedirect.com/science/article/pii/ S036083522200198X

    work page arXiv 2022

  8. [5]

    Rohaninejad, Z

    M. Rohaninejad, Z. Hanz´ alek, Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches, International Journal of Production Economics 263 (2023) 108958. doi:https://doi.org/10.1016/j.ijpe.2023.108958. URL https://www.sciencedirect.com/science/article/pii/ S0925527323001901

    work page arXiv 2023

Show all 71 references
  1. [6]

    Heinz, A

    V. Heinz, A. Nov´ ak, M. Vlk, Z. Hanz´ alek, Constraint programming and con- structive heuristics for parallel machine scheduling with sequence-dependent setups and common servers, Computers & Industrial Engineering 172 (2022) 108586. doi:https://doi.org/10.1016/j.cie.2022.108...

    2022

  2. [7]

    W. T. Lunardi, E. G. Birgin, P. Laborie, D. P. Ronconi, H. Voos, Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem, Computers & Operations Research 123 (2020) 105020. doi:https://doi.org/10.1016/j.cor.2020.105020...

    2020

  3. [8]

    Fatemi-Anaraki, R

    S. Fatemi-Anaraki, R. Tavakkoli-Moghaddam, M. Foumani, B. Vahedi-Nouri, Scheduling of multi-robot job shop systems in dynamic environments: Mixed- integer linear programming and constraint programming approaches, Omega 53 115 (2023) 102770. doi:https://doi.org/10.1016/j.omega....

    2023

  4. [9]

    Vil ´ ım, P

    P. Vil ´ ım, P. Laborie, P. Shaw, Failure-directed search for constraint-based scheduling, in: International Conference on Integration of Constraint Pro- gramming, Artificial Intelligence, and Operations Research, Springer, 2015, pp. 437–453

    2015

  5. [10]

    IBM, CP Optimizer, https://www.ibm.com/analytics/ cplex-cp-optimizer, accessed: April 17, 2023 (2023)

    2023

  6. [11]

    Naderia, R

    B. Naderia, R. Ruizb, V. Roshanaeic, Mixed-integer programming versus con- straint programming for shop scheduling problems: New results and outlook, INFORMS Journal on Computing (2023)

    2023

  7. [12]

    V. A. Hauder, A. Beham, S. Raggl, S. N. Parragh, M. Affenzeller, Resource- constrained multi-project scheduling with activity and time flexibility, Com- puters & Industrial Engineering 150 (2020) 106857

    2020

  8. [13]

    S. C. Brailsford, C. N. Potts, B. M. Smith, Constraint satisfaction problems: Algorithms and applications, European Journal of Operational Research 119 (3) (1999) 557–581. doi:https://doi.org/10.1016/S0377-2217(98) 00364-6. URL https://www.sciencedirect.com/science/article/pii...

    1999 doi

  9. [14]

    Robbins, Some aspects of the sequential design of experiments, Bulletin of the American Mathematical Society 58 (5) (1952) 527 – 535

    H. Robbins, Some aspects of the sequential design of experiments, Bulletin of the American Mathematical Society 58 (5) (1952) 527 – 535

    1952

  10. [15]

    Kazikova, M

    A. Kazikova, M. Pluhacek, R. Senkerik, Why tuning the control parameters of metaheuristic algorithms is so important for fair comparison?, MENDEL 26 (2) (2020) 9–16. doi:10.13164/mendel.2020.2.009. URL https://mendel-journal.org/index.php/mendel/article/view/120

    2020 doi

  11. [16]

    C. H. A. Koster, J. G. Beney, On the importance of parameter tuning in text categorization, in: I. Virbitskaite, A. Voronkov (Eds.), Perspectives of Systems Informatics, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 270–283

    2007

  12. [17]

    Refalo, Impact-based search strategies for constraint programming, in: In- ternational Conference on Principles and Practice of Constraint Programming, Springer, 2004, pp

    P. Refalo, Impact-based search strategies for constraint programming, in: In- ternational Conference on Principles and Practice of Constraint Programming, Springer, 2004, pp. 557–571

    2004

  13. [18]

    Michel, P

    L. Michel, P. V. Hentenryck, Activity-based search for black-box constraint programming solvers, in: International Conference on Integration of Artifi- cial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Springer, 2012, pp. 228–243. 54

    2012

  14. [19]

    Lecoutre, L

    C. Lecoutre, L. Sa ¨ ıs, S. Tabary, V. Vidal, Reasoning from last conflict(s) in constraint programming, Artificial Intelligence 173 (18) (2009) 1592–1614. doi:https://doi.org/10.1016/j.artint.2009.09.002. URL https://www.sciencedirect.com/science/article/pii/ S0004370209001040

    2009 doi

  15. [20]

    Boussemart, F

    F. Boussemart, F. Hemery, C. Lecoutre, L. Sais, Boosting systematic search by weighting constraints, in: ECAI, Vol. 16, 2004, p. 146

    2004

  16. [21]

    Wattez, C

    H. Wattez, C. Lecoutre, A. Paparrizou, S. Tabary, Refining constraint weight- ing, in: 2019 IEEE 31st International Conference on Tools with Artificial In- telligence (ICTAI), 2019, pp. 71–77. doi:10.1109/ICTAI.2019.00019

    2019

  17. [22]

    Habet, C

    D. Habet, C. Terrioux, Conflict History Based Branching Heuristic for CSP Solving, in: Proceedings of the 8th International Workshop on Combinations of Intelligent Methods and Applications (CIMA), Volos, Greece, 2018, pp. 1– 10. URL https://hal-amu.archives-ouvertes.fr/hal-02090610

    2018

  18. [23]

    Doolaard, N

    F. Doolaard, N. Yorke-Smith, Online learning of variable ordering heuristics for constraint optimisation problems, Annals of Mathematics and Artificial Intelligence (Oct 2022). doi:10.1007/s10472-022-09816-z . URL https://doi.org/10.1007/s10472-022-09816-z

    2022 doi

  19. [24]

    J. Xu, Y. Wu, H. Li, M. Yin, Prediction-based adaptive variable ordering heuristics for constraint satisfaction problems, Proceedings of the AAAI Con- ference on Artificial Intelligence 39 (11) (2025) 11390–11398. doi:10.1609/ aaai.v39i11.33239. URL https://ojs.aaai.org/index....

    2025

  20. [25]

    Zarpellon, J

    G. Zarpellon, J. Jo, A. Lodi, Y. Bengio, Parameterizing branch-and-bound search trees to learn branching policies, Proceedings of the AAAI Conference on Artificial Intelligence 35 (5) (2021) 3931–3939. doi:10.1609/aaai.v35i5. 16512. URL https://ojs.aaai.org/index.php/AAAI/arti...

    2021 doi

  21. [26]

    Khalil, P

    E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, B. Dilkina, Learning to branch in mixed integer programming, Proceedings of the AAAI Conference on Arti- ficial Intelligence 30 (1) (Feb. 2016). doi:10.1609/aaai.v30i1.10080. URL https://ojs.aaai.org/index.php/AAAI/article/view/10080

    2016 doi

  22. [27]

    Bouˇ ska, P.ˇS ˚ ucha, A

    M. Bouˇ ska, P.ˇS ˚ ucha, A. Nov´ ak, Z. Hanz´ alek, Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness, European Journal of Operational Research 308 (3) (2023) 990–1006. doi:https://doi.org/10.1016/j.ejor.2022.11.034. URL htt...

    2023 doi

  23. [28]

    Bonfietti, M

    A. Bonfietti, M. Lombardi, M. Milano, Embedding decision trees and random forests in constraint programming, in: L. Michel (Ed.), Integration of AI and OR Techniques in Constraint Programming, Springer International Publishing, Cham, 2015, pp. 74–90

    2015

  24. [29]

    Chalumeau, I

    F. Chalumeau, I. Coulon, Q. Cappart, L.-M. Rousseau, Seapearl: A constraint programming solver guided by reinforcement learning, in: P. J. Stuckey (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer International Publishing,...

    2021

  25. [30]

    Cappart, T

    Q. Cappart, T. Moisan, L.-M. Rousseau, I. Pr´ emont-Schwarz, A. Cire, Com- bining reinforcement learning and constraint programming for combinatorial optimization (2020). arXiv:2006.01610

    2020 arXiv

  26. [31]

    J. H. Liang, V. Ganesh, P. Poupart, K. Czarnecki, Learning rate based branch- ing heuristic for SAT solvers, in: N. Creignou, D. Le Berre (Eds.), Theory and Applications of Satisfiability Testing – SAT 2016, Springer International Pub- lishing, Cham, 2016, pp. 123–140

    2016

  27. [32]

    Popescu, S

    A. Popescu, S. Polat-Erdeniz, A. Felfernig, M. Uta, M. Atas, V.-M. Le, K. Pilsl, M. Enzelsberger, T. N. T. Tran, An overview of machine learning techniques in constraint solving, Journal of Intelligent Information Systems 58 (1) (2022) 91–118. doi:10.1007/s10844-021-00666-5 . ...

    2022 doi

  28. [33]

    W. Xia, R. Yap, Learning robust search strategies using a bandit-based ap- proach, Proceedings of the AAAI Conference on Artificial Intelligence 32 (1) (Apr. 2018). doi:10.1609/aaai.v32i1.12211. URL https://ojs.aaai.org/index.php/AAAI/article/view/12211

    2018 doi

  29. [34]

    Koriche, C

    F. Koriche, C. Lecoutre, A. Paparrizou, H. Wattez, Best heuristic identification for constraint satisfaction, in: 31st International Joint Conference on Artificial Intelligence (IJCAI’22), 2022, pp. 1859–1865

    2022

  30. [35]

    Kletzander, N

    L. Kletzander, N. Musliu, Large-state reinforcement learning for hyper- heuristics, Proceedings of the AAAI Conference on Artificial Intelligence 37 (10) (2023) 12444–12452. doi:10.1609/aaai.v37i10.26466. URL https://ojs.aaai.org/index.php/AAAI/article/view/26466

    2023 doi

  31. [36]

    Wattez, F

    H. Wattez, F. Koriche, C. Lecoutre, A. Paparrizou, S. Tabary, Learning vari- able ordering heuristics with multi-armed bandits and restarts, in: G. Got- tlob, T. Soininen, C. Vieira, M. Virkki (Eds.), ECAI 2020 - 24th Euro- pean Conference on Artificial Intelligence, Vol. 325 ...

    2020 doi

  32. [37]

    Balafrej, C

    A. Balafrej, C. Bessiere, A. Paparrizou, Multi-armed bandits for adaptive con- straint propagation, in: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press, Buenos Aires, Argentina, 2015, pp. 290–296. URL https://hal.archives-o...

    2015

  33. [38]

    M. Loth, M. Sebag, Y. Hamadi, M. Schoenauer, Bandit-based search for con- straint programming, in: International Conference on Principles and Practice of Constraint Programming, Springer, 2013, pp. 464–480

    2013

  34. [39]

    Mahajan, D

    A. Mahajan, D. Teneketzis, Multi-Armed Bandit Problems, Springer US, Boston, MA, 2008, Ch. 6, pp. 121–151.doi:10.1007/978-0-387-49819-5\_6 . URL https://doi.org/10.1007/978-0-387-49819-5_6

    2008 doi

  35. [40]

    R. S. Sutton, A. G. Barto, Reinforcement learning: An introduction, MIT press, 2018

    2018

  36. [41]

    Kuleshov, D

    V. Kuleshov, D. Precup, Algorithms for multi-armed bandit problems, CoRR abs/1402.6028 (2014). arXiv:1402.6028. URL http://arxiv.org/abs/1402.6028

    2014 arXiv

  37. [42]

    Chapelle, L

    O. Chapelle, L. Li, An empirical evaluation of thompson sampling, in: J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, K. Weinberger (Eds.), Ad- vances in Neural Information Processing Systems, Vol. 24, Curran Associates, Inc., 2011, pp. 2249–2257. URL https://proceedings.n...

    2011

  38. [43]

    Akiba, S

    T. Akiba, S. Sano, T. Yanase, T. Ohta, M. Koyama, Optuna: A next- generation hyperparameter optimization framework, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019, pp. 1–10

    2019

  39. [44]

    Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research 64 (2) (1993) 278–285, project Management anf Scheduling

    E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research 64 (2) (1993) 278–285, project Management anf Scheduling. doi:https://doi.org/10.1016/0377-2217(93)90182-M . URL https://www.sciencedirect.com/science/article/pii/ 037722179390182M

    1993 doi

  40. [45]

    Demirkol, S

    E. Demirkol, S. Mehta, R. Uzsoy, Benchmarks for shop scheduling prob- lems, European Journal of Operational Research 109 (1) (1998) 137–141. doi:https://doi.org/10.1016/S0377-2217(97)00019-2 . URL https://www.sciencedirect.com/science/article/pii/ S0377221797000192

    1998 doi

  41. [46]

    Adams, E

    J. Adams, E. Balas, D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science 34 (3) (1988) 391–401. URL http://www.jstor.org/stable/2632051 57

    1988

  42. [47]

    R. H. Storer, S. D. Wu, R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science 38 (10) (1992) 1495–1509. URL http://www.jstor.org/stable/2632676

    1992

  43. [48]

    Yamada, R

    T. Yamada, R. Nakano, A genetic algorithm applicable to large-scale job-shop problems., in: Parallel Problem Solving from Nature 2, Vol. 2, 1992, pp. 283– 292

    1992

  44. [49]

    Kolisch, A

    R. Kolisch, A. Sprecher, Psplib - a project scheduling problem li- brary: Or software - orsep operations research software exchange pro- gram, European Journal of Operational Research 96 (1) (1997) 205–216. doi:https://doi.org/10.1016/S0377-2217(96)00170-1 . URL https://www.sc...

    1997 doi

  45. [50]

    URL https://scheduleopt.com/

    ScheduleOpt, Optalcp, Online, optalCP’s solver landing page (2023). URL https://scheduleopt.com/

    2023

  46. [51]

    URL https://gitlab.com/optal_solver/fds_results

    Optal, Fds experimental results, Online, git repository (2023). URL https://gitlab.com/optal_solver/fds_results

    2023

  47. [53]

    URL http://jobshop.jjvh.nl/

    Jongejan, J.V., Job shop problem solver, Online, accessed: April 14, 2023 (n.d.). URL http://jobshop.jjvh.nl/

    2023

  48. [55]

    Brinkk¨ otter, P

    W. Brinkk¨ otter, P. Brucker, Solving open benchmark instances for the job-shop problem by parallel head–tail adjustments, Journal of Schedul- ing 4 (1) (2001) 53–64, https://onlinelibrary.wiley.com/doi/abs/ 10.1002/1099-1425(200101/02)4:1<53::AID-JOS59>3.0.CO;2-Y . doi:10. 10...

    2001 doi

  49. [57]

    Coelho, M

    J. Coelho, M. Vanhoucke, Going to the core of hard resource-constrained project scheduling instances, Computers & Operations Research 121 (2020) 104976. doi:https://doi.org/10.1016/j.cor.2020.104976. URL https://www.sciencedirect.com/science/article/pii/ S0305054820300939

    2020

  50. [58]

    P. Shaw, Using constraint programming and local search methods to solve ve- hicle routing problems, in: International conference on principles and practice of constraint programming, Springer, 1998, pp. 417–431

    1998

  51. [59]

    Godard, P

    D. Godard, P. Laborie, W. Nuijten, Randomized large neighborhood search for cumulative scheduling., in: ICAPS, Vol. 5, 2005, pp. 81–89

    2005

  52. [60]

    Vil ´ ım, Edge finding filtering algorithm for discrete cumulative resources in O(kn log n), in: Principles and Practice of Constraint Programming - CP 2009, 2009, pp

    P. Vil ´ ım, Edge finding filtering algorithm for discrete cumulative resources in O(kn log n), in: Principles and Practice of Constraint Programming - CP 2009, 2009, pp. 802–816. doi:10.1007/978-3-642-04244-7_62

    2009 doi

  53. [61]

    S. Gay, R. Hartert, P. Schaus, Simple and scalable time-table filtering for the cumulative constraint, in: G. Pesant (Ed.), Principles and Practice of Constraint Programming, Springer International Publishing, Cham, 2015, pp. 149–157

    2015

  54. [62]

    Ouellet, C.-G

    P. Ouellet, C.-G. Quimper, Time-table extended-edge-finding for the cumu- lative constraint, in: C. Schulte (Ed.), Principles and Practice of Constraint Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 562– 577

    2013

  55. [63]

    R. P. Vil ´ ım, Global constraints in scheduling, Online, accessed: October 16, 2023 (n.d.). URL https://vilim.eu/petr/disertace.pdf

    2023

  56. [64]

    W. N. Philippe Baptiste, Claude Pape, Constraint-Based Scheduling Applying Constraint Programming to Scheduling Problems, Springer New York, NY,

  57. [65]

    C. P. Gomes, B. Selman, N. Crato, H. Kautz, Heavy-tailed phenomena in satis- fiability and constraint satisfaction problems, Journal of automated reasoning 24 (1) (2000) 67–100

    2000

  58. [66]

    M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, S. Malik, Chaff: En- gineering an efficient SAT solver, in: Proceedings of the 38th annual Design Automation Conference, 2001, pp. 530–535

    2001

  59. [67]

    Lecoutre, L

    C. Lecoutre, L. Sais, S. Tabary, V. Vidal, et al., Nogood recording from restarts., in: IJCAI, Vol. 7, 2007, pp. 131–136

    2007

  60. [68]

    Applegate, R

    D. Applegate, R. Bixby, V. Chvatal, B. Cook, Finding cuts in the tsp (a pre- liminary report), Tech. rep., AT&T Bell Laboratories (1995)

    1995

  61. [69]

    Achterberg, T

    T. Achterberg, T. Koch, A. Martin, Branching rules revisited, Operations Re- search Letters 33 (1) (2005) 42–54. 59

    2005

  62. [70]

    URL https://optalcp.com/docs/api/type-aliases/Parameters/ 60

    ScheduleOpt, Optalcp, Online, optalCP’s parameters (2025). URL https://optalcp.com/docs/api/type-aliases/Parameters/ 60

    2025

  63. [2012]

    doi:https://doi.org/10.1007/978-1-4615-1479-4

    doi

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.