SEER: Supervised Learning to Control Energetic Reasoning

# Supervised Learning to Control Energetic ReasoningThis paper was presented at the CP2014 Doctoral Program of Lyon.
Source: [https://arxiv.org/html/2607.16523](https://arxiv.org/html/2607.16523)
Sascha Van Cauwelaert1, Michele Lombardi2, and Pierre Schaus1 Université Catholique de Louvain, Università di Bologna

###### Abstract

> One of the main strengths of Constraint Programming is the ability to reduce the search space via propagation\. However, propagation is a double\-edged sword, with more pruning power coming at the price of larger computation time\. For each problem constraint, the best propagator depends on the specific instance and may change at search time\. In the literature, Machine Learning \(ML\) techniques and activity\-based heuristics have been applied respectively for choosing \(statically\) the propagators for a batch of problems and to adapt \(dynamically\) the propagation strength\. We propose to merge those efforts by using an oracle function, obtained via ML, to decide whether to run complex propagators for a target constraint\. A combination of design choices makes the approach flexible and easy to embed in state\-of\-the\-art solvers\. In this paper, we focus on investigating the feasibility of building an oracle for the Energetic Reasoning propagator\. Our experiments show that high prediction accuracy can be obtained, provide suggestions for classification features, and highlight important issues to address when building such an oracle\.

## 1Introduction

The ability to reduce the size of the search space via propagation is one of the distinguishing features of Constraint Programming \(CP\), accounting for much of its ability to solve complex combinatorial problems\. Propagation, however, is a double\-edged sword: more powerful filtering algorithms provide an increased chance to prune values, but they also have larger computation time, that must be paid regardless of whether additional propagation is actually achieved\.

For instance, thecumulativeconstraint is widely employed to model resource restrictions for scheduling problems with non\-preemptive activities\. The constraint is one of the best studied in CP and counts a wide range of propagators\. In particular, Timetable\-based algorithms \(such as SWEEP \(?\)\) represent the lightweight end of the spectrum, with a time complexity ofO​\(n2\)O\(n^\{2\}\)\. Timetable propagation \(TT\) is known to be dominated by Energetic Reasoning \(ER, see \(?\)\), which is however seldom used in practice because the algorithm has higher time complexity –O​\(n3\)O\(n^\{3\}\)– and often ends up with the same domain reduction as the Timetable\.

Nevertheless, there are instances where ER can dramatically reduce the search tree\. On the BL benchmarks \(?\), such propagator may reduce the number of backtracks by a factor of 10 on∼65%\\sim 65\\%of the instances when using dichotomic search on the start variables, and on∼88%\\sim 88\\%when using scheduling\-specific search –*SetTimes*, see \(?\)\. A similar behavior occurs whenever a constraint has propagators with different pruning power and complexity\.

The best propagator depends on specificities of the target problem and instance, and it is far from trivial to select\. The choice is typically done by the model designer based on personal experience, intuition, and pilot tests, with mixed outcomes \(we refer to \(?\) for interested reader\)\. Recently, Machine Learning \(ML\) techniques have been proposed as a way to automatize the decision \(?\), with promising results\. Such an approach, however, does not take into account the impact of search decisions on the propagator effectiveness\. This has been recognized in \(?\), where the authors propose to adjust the propagation strength at run time via heuristics based on the solver state\. Unfortunately, designing and choosing the correct heuristics is a complex \(and problem\-dependent\) task\. Parametrized consistency is introduced in \(?\), where a local consistency property is compared to a threshold parameter in order to enforce different consistency levels on values\. Heuristics are considered to dynamically adapt the parameter\.

*We propose to merge the mentioned approaches and use an oracle, obtained via ML, to predict at run time if running a specific propagator for a constraint will be beneficial\. The decision should be based on the current domain of the variables in the constraint scope, i\.e\. on the input of the propagator itself*\. For example such an oracle \(in fact, a classifier\) could be used to decide for a cumulative constraint whether or not to run ER after a TT propagator has reached the fix point\. Compared to \(?\), our approach can be used to adjust the propagation level at search time\. Compared to \(?\), it is less\-problem dependent, because it operates at a single\-constraint level\. Moreover, the use of ML spares the designer the effort to find a good heuristic rule \(though feature selection is still a problem\)\.

Working at a single constraint level makes our approach simple to implement on state\-of\-the\-art solvers\. Additionally, since the prediction we consider concerns a single propagator, there is no need to retrain it when a new propagation algorithm is introduced\. Finally, since the oracle input does not include state information \(except of course for the domains\), the method is well suited for complex search techniques such as non\-chronological backtracking and \(more importantly\) Large Neighborhood Search\.

Deploying effectively such an approach is an ambitious endeavor\. As a start, in this paper we investigate the feasibility of building an oracle for the ER propagator, for which we use the acronym SEER \(Supervised lEarning to control Energetic Reasoning\)\. In particular, we focus on the problem of detecting whether running ER will narrow the domains after TT has reached a fix\-point\. Temporal aspects \(e\.g\. the trade\-off between the amount of propagation and the reduction of the solution time\) are left for future research\. In this study, we show that high prediction rates can indeed be obtained, we provide guidelines about how to define good training sets, we suggest effective features to be used as input for the classifier, and we highlight critical issues to be addressed in the design of the oracle\.

## 2Background and Related Work

### 2\.1CP and Scheduling Problems

Constraint Programming is a technique to solve Constraint Satisfaction Problems \(CSP\)\. A CSP is a triple⟨X,D,C⟩\\langle X,D,C\\rangle, whereXXis a set of variablesxix\_\{i\},DDis the set of their domainsDiD\_\{i\}\(typically finite and integer\), andCCis a set of constraintsckc\_\{k\}that must be satisfied\. Each constraint is defined over a subset of variablesS​\(ck\)S\(c\_\{k\}\), called scope, and has an associated algorithm \(propagator\) that can prune provably infeasible values from the variables inS​\(ck\)S\(c\_\{k\}\)\. A propagator forckc\_\{k\}can be seen as a function:

π:\(Dj\|xj∈S​\(ck\)\)↦\(Dj′\|xj∈S​\(ck\)\)\\pi:\(D\_\{j\}\\ \|\\ x\_\{j\}\\in S\(c\_\{k\}\)\)\\mapsto\(D^\{\\prime\}\_\{j\}\\ \|\\ x\_\{j\}\\in S\(c\_\{k\}\)\)\(1\)
where\(Dj\|xj∈S​\(Ck\)\)\(D\_\{j\}\\ \|\\ x\_\{j\}\\in S\(C\_\{k\}\)\)is a n\-ple with the domains of the variables inS​\(ck\)S\(c\_\{k\}\)\. For all of them it must holdDj′⊆DjD^\{\\prime\}\_\{j\}\\subseteq D\_\{j\}\. Informally, the propagator maps a group of domains to a shrinked version of themselves\. A CSP is typically solved via branching, by posting additional constraints and triggering their propagators\. This causes a domain reduction, potentially awakening other propagators until a fix\-point is reached\. Optimization can be performed by adding, whenever a feasible solution is found, a permanent constraint that requires the future solutions to have a better cost\.

*Resource Constrained Project Scheduling Problems*\(RCPSP\) consist in finding a start time for a setAAof activities\. Each activityaia\_\{i\}has a fixed durationdid\_\{i\}and requires an amountri​kr\_\{ik\}of each resourcerkr\_\{k\}from a setRR\. Each resource has limited capacityc​a​pkcap\_\{k\}and the activities may be connected by precedence constraints\. The goal is to minimize the worst case completion time \(makespan\)\. A RCPSP is modeled in CP by introducing a start variablesis\_\{i\}for each activity and by modeling the resource restrictions viacumulativeconstraints \(?;?\), that enforce the following relation for each resourcerkr\_\{k\}:

∑si≤t<si\+diri​k≤capk∀t=0\.\.eoh\\sum\_\{s\_\{i\}\\leq t<s\_\{i\}\+d\_\{i\}\}r\_\{ik\}\\leq cap\_\{k\}\\quad\\quad\\forall t=0\.\.eoh\(2\)
i\.e\. no resource overusage can occur\. The terme​o​heohrefers to the maximum possible end time, where each end timeeie\_\{i\}corresponds tosi\+dis\_\{i\}\+d\_\{i\}\. The bounds forsis\_\{i\}andeie\_\{i\}have conventional names:e​s​tiest\_\{i\}andl​s​tilst\_\{i\}are the earliest and latest start times, respectively, whilee​c​tiect\_\{i\}andl​c​tilct\_\{i\}are the earliest and latest completion \(end\) times\. Thecumulativeconstraint is one of the most studied in CP and has several propagators \(?;?;?;?;?\)\. In this document, we focus on Energetic Reasoning and \(secondarily\) on Timetable propagation\.

*Timetable propagators*base their deductions on compulsory parts, i\.e\. time intervals where tasks must necessarily be processed\. By aggregating the compulsory parts of all activities we can obtain a minimum resource consumption profile\. Based on this information, we can prune the domain ofsis\_\{i\}if we realize that scheduling the activity at the Earliest Start Times¯i\\underline\{s\}\_\{i\}would exceed the available capacity in the minimum consumption profile\. Several Timetabling based algorithms exist, with complexity ofO​\(n2\)O\(n^\{2\}\)\(?;?\)\.

*Energetic Reasoning*is a propagator based on the concept of energy consumption on a given time interval\. If the minimum consumption is larger than the provided energy on this interval, the constraint cannot be satisfied or at least some bound adjustments can be done\. The algorithm runs inO​\(n3\)O\(n^\{3\}\)\. Note that there existO​\(n2\)O\(n^\{2\}\)algorithms that cannot perform bound adjustments and only detect inconsistencies \(?;?\)\. Nevertheless, using the classical ER algorithm can still considerably reduce the search space compared to the combination of TT and the ER checker: on the BL instances, a reduction by a factor of 3 is achieved in∼45%\\sim 45\\%of the instances with dichotomic search and on∼19%\\sim 19\\%with*SetTimes*\.

### 2\.2Algorithm Selection and Propagation

The problem we consider is strictly related to Algorithm Selection, meaning the activity of deciding the best algorithm for tackling a given problem, that was first formalized in \(?\)\. Since then, the field has received a lot of attention from the Optimization and ML communities and as a consequence the related literature is vast and complex\. There are off\-line approaches, relying on problem features to choose either a single algorithm, or a set of algorithms to be executed in parallel \(or in sequence according to a schedule\)\. On\-line approaches can adjust the selection at run\-time, but incur additional overhead problems\. The selection activity may involve picking altogether different algorithms or adjusting the parameters of a single approach\. Different ML techniques have been employed, ranging from simple heuristic rules to statistical regression and more complex techniques such as Decision Trees, Artificial Neural Networks, Support Vector Machine and Clustering\. For an excellent overview on Algorithm Selection in the context of Combinatorial Optimization \(covering Hydra – and derivatives –, SATzilla, ParamILS and ISAC\), the reader is referred to \(?\)\. For selecting the best learning algorithm for a learning problem \(so\-called meta\-learning\) a nice overview is provided in \(?\)\.

Despite the extensiveness of the literature about Algorithm Selection, only a few works so far have addressed the problem of choosing propagators \(or adjusting the consistency levels\) in CP automatically\. The earliest example is \(?\), where the authors propose a method to detect when using simple Forward checking can achieve the same consistency level as Arc Consistency\. The idea is generalized in the approach from \(?\), that switches back and forth between simpler \(and faster\) consistency algorithms and more powerful \(and slower\) ones depending on their observed and predicted performance\. More recently, heuristic rules to switch between “strong” and “weak” propagation have been proposed in \(?;?\)\. The particular case of ER is considered in \(?\), where an approximative criterion is used to estimate the potential of ER\.

The use of Machine Learning methods for selecting propagators has been considered in \(?\)\. In the paper, the authors use classification techniques to select which propagator \(and which implementation\) to use for thealldiffconstraints on a given instance\. The classifier is trained on a set of benchmark problems and takes as input general attributes of the instance \(e\.g\. the number ofalldiffconstraints\) and more complex features obtained from its primal graph\.

## 3Design Process

### 3\.1Problem Definition

Given a target constraintckc\_\{k\}and the current domains of the variables in its scopeS​\(ck\)S\(c\_\{k\}\), we consider the problem of predicting whether a propagatorπ\\piwill cause some pruning or not, with reasonable probability\. Formally, we are interested in designing an oracle functionOπO\_\{\\pi\}such that:

Oπ\(Di\|xi∈S\(Ck\)\)=\{t​r​u​e​if some value is prunedf​a​l​s​e​otherwiseO\_\{\\pi\}\(D\_\{i\}\|x\_\{i\}\\in S\(C\_\{k\}\)\)=\\left\\\{\\begin\{aligned\} &true\\text\{ if some value is pruned\}\\\\ &false\\text\{ otherwise\}\\end\{aligned\}\\right\.
One can see thatOπO\_\{\\pi\}has the same input asπ\\pi– see Equation \([1](https://arxiv.org/html/2607.16523#S2.E1)\)\. TheOπO\_\{\\pi\}function is meant to be used as a guard condition for the execution of the propagator\.

This problem formulation has a number of advantages: first, the oracle is*guaranteed to have enough information to make a correct guess*\. The challenge is therefore to devise anOπO\_\{\\pi\}function with lower complexity than the propagator itself\. Second, if a new propagator for the constraint is introduced, a new oracle must be trained, but*the existing ones require no modification at all*\. Third, the oracle*can be checked at any point during search*, making the designer completely free about how to combine propagators \(as long as the fallibility of the oracle is taken into account\)\. More importantly, this also makes the approach well suited for use in complex search strategies and Large Neighborhood Search\.

The simplest combination scheme for a set of propagator consists in running a lightweight algorithm \(or even just a checker\) until the fix\-point is reached, and then running a single iteration of a more complex propagator only ifOπO\_\{\\pi\}returns true\. This simple idea is similar to the one used in \(?\)\. As already mentioned, in this paper we consider the specific case of building an oracle function for ER, to be consulted once TT propagation has reached a fix\-point\.

In general, we propose to use ML techniques to obtain the oracleOπO\_\{\\pi\}for complex propagators\. In this context, obtaining the function requires to: 1\) build a representative training set; 2\) selecting features \(based on the variable domains and on static information\) for the classifier; 3\) choosing a classification technique, then training and evaluating a ML model\.

In the following, we will discuss those three steps in detail, with a focus on investigating the feasibility of an*accurate*oracle function\. Before proceeding, it is worth to note that it should be possible to improve the efficacy of our approach by accounting for temporal aspects \(e\.g\. the propagation time\) in the oracle definition\. This is left for future research and discussed in the concluding Section[5](https://arxiv.org/html/2607.16523#S5)\.

### 3\.2Build a Representative Training Set

As a consequence of our problem definition, a \(raw\) training set consists of a number of tuples\(Di\|xi∈S​\(ck\)\)\(D\_\{i\}\\ \|\\ x\_\{i\}\\in S\(c\_\{k\}\)\)\. In other words each tuple corresponds to a possible state for the domains of the constraint variables \(the start times, for the ER propagator\)\. Additionally, any static information concerning the constraint should be considered \(e\.g\. the durations and the resource capacity\)\. Finally, each tuple must be associated to the corresponding exact value of theOπO\_\{\\pi\}function\.

A good training set should be representative of any realistic domain configuration\. Such a set can be obtained by sampling the domains when solving a set of benchmarks problems, provided that:

- •The considered benchmarks and the search strategy used for their solution are representative enough\.
- •The samples are collected at representative times\.
- •The samples come from diverse regions of the search tree\.
- •The samples come from diverse constraints \(e\.g\. with different scopes and different static information\)\.

The exact meaning of the word “representative” depends on the context\. In particular, we can distinguish between two application scenarios\. First, one may want to obtain anOπO\_\{\\pi\}function as general as possible \(e\.g\. for inclusion in a constraint solver\)\. In this case, the samples should be collected using many benchmarks and different search strategies\. Alternatively, one may be interested in a particular benchmark, or a particular search strategy, or a particular combination scheme for the propagators\. In this case, the samples should be collected only for the relevant cases, to increase the chance of obtaining an accurate oracle\.

In this paper we take a mixed approach\. Since we plan to use theOπO\_\{\\pi\}function to decide whether to run ER after TT, we collect samples only after the latter has reached the fix\-point\. We also commit to a single branching strategy \(*SetTimes*\), to avoid overcomplicating the learning problem \(this is a feasibility study, after all\) and because such search strategy is widely used in scheduling\. We do however investigate the impact of using a single or multiple benchmarks for the training set \(see Section[4](https://arxiv.org/html/2607.16523#S4)\)\.

We consider scheduling problems with different number of activities, resources and different resource requirements\. To avoid having overly similar tuples, at search time we perform the sampling with a small, fixed probability\. This method decreases the risk of building a training set with many samples coming from nodes too close to each other in the search tree\.

For quickly collecting samples on diverse regions of the search, we use Randomized Large Neighborhood Search \(?\)\. This may bias the oracle performance, but allows to experiment more easily with different training sets\. Note that using Large Neighborhood Search incurs the risk of generating several times equivalent domains\. It may be a good idea to remove such duplicates to ensure fairness in the training and in the evaluation phase\.

### 3\.3Input Features

Selecting effective features for a classifier is “one of the most important, yet nebulous, aspects of the algorithm selection problem” \(?\)\. In this section, we try to provide guidelines for picking meaningful features by describing the one we used for the oracle function for ER\. In particular, we obtain our features by first extracting intermediate characterizations for the cumulative constraint \(cumulative characterizations\), and then by computing aggregated statistics\. The cumulative characterizations are numbers obtained from static information about the cumulative constraint and from the domains\. For their description it is useful to introduce some definitions, introduced in \(?\) and \(?\):

- •Point of interests considered by ER: O1=\{𝑒𝑠𝑡i\}∪\{𝑒𝑐𝑡i\}∪\{𝑙𝑠𝑡i\}\\displaystyle O\_\{1\}=\\\{\\mathit\{est\}\_\{i\}\\\}\\cup\\\{\\mathit\{ect\}\_\{i\}\\\}\\cup\\\{\\mathit\{lst\}\_\{i\}\\\}O2=\{𝑙𝑐𝑡i\}∪\{𝑙𝑠𝑡i\}∪\{𝑒𝑐𝑡i\}\\displaystyle O\_\{2\}=\\\{\\mathit\{lct\}\_\{i\}\\\}\\cup\\\{\\mathit\{lst\}\_\{i\}\\\}\\cup\\\{\\mathit\{ect\}\_\{i\}\\\}
- •Time Intervals considered by ER: \{\[t,t′\)\}​∀t∈O1,∀t′∈O2,t′≥t∪\{\[t,t′\)\}​∀t∈O1,∀t′∈O​\(t\),t′≥t∪\{\[t,t′\)\}​∀t′∈O2,∀t∈O​\(t′\),t′≥t\\begin\{array\}\[\]\{c\}\\\{\[t,t^\{\\prime\}\)\\\}\\,\\forall t\\in O\_\{1\},\\forall t^\{\\prime\}\\in O\_\{2\},t^\{\\prime\}\\geq t\\\\ \\cup\\,\\\{\[t,t^\{\\prime\}\)\\\}\\,\\forall t\\in O\_\{1\},\\forall t^\{\\prime\}\\in O\(t\),t^\{\\prime\}\\geq t\\\\ \\cup\\,\\\{\[t,t^\{\\prime\}\)\\\}\\,\\forall t^\{\\prime\}\\in O\_\{2\},\\forall t\\in O\(t^\{\\prime\}\),t^\{\\prime\}\\geq t\\end\{array\}whereO​\(t\)=\{𝑒𝑠𝑡i\+𝑙𝑐𝑡i−t\}O\(t\)=\\\{\\mathit\{est\}\_\{i\}\+\\mathit\{lct\}\_\{i\}\-t\\\}
- •Relative Energy: E~i=di⋅ri​kl​c​ti−𝑒𝑠𝑡i\\tilde\{E\}\_\{i\}=\\frac\{d\_\{i\}\\cdot r\_\{ik\}\}\{lct\_\{i\}\-\\mathit\{est\}\_\{i\}\}
- •Relative Energy Histogram: E~​\(t\)=∑ai∈A:𝑒𝑠𝑡i≤t<𝑙𝑐𝑡idi⋅ri​k𝑙𝑐𝑡i−𝑒𝑠𝑡i\\widetilde\{E\}\(t\)=\\sum\_\{a\_\{i\}\\in A:\\mathit\{est\}\_\{i\}\\leq t<\\mathit\{lct\}\_\{i\}\}\\frac\{d\_\{i\}\\cdot r\_\{ik\}\}\{\\mathit\{lct\}\_\{i\}\-\\mathit\{est\}\_\{i\}\}

Generic cumulative characterizations:Table[1](https://arxiv.org/html/2607.16523#S3.T1)presents our generic cumulative characterizations\. They are computed for each activityaia\_\{i\}and haveO​\(1\)O\(1\)complexity, so that for a given cumulative constraint we have a vector of values for each characterization type\. Obtaining each vector has complexityO​\(n\)O\(n\), wherennis the number of activities\. The rationale for usingnormalizedCompulsoryPartanddomainTightnessis the fact that we run ER after TT and the intuition that bound adjustments from ER are more likely to happen when the domains of the start variables are small \(?\)\.

Table 1:Generic cumulative characterizations\.ER specific characterizations:The characterizations in Table[2](https://arxiv.org/html/2607.16523#S3.T2)are specific to ER\. BothtimePointsandintervalSizeare computed for every Time Interval considered in ER\. The notation𝑙𝑢𝑏\\mathit\{lub\}stands for theleast upper boundand is used instead of𝑚𝑎𝑥\\mathit\{max\}as the intervals are right\-open\. The characterizationrelativeEnergyTimePointsis computed for every time point in thetimePointscharacterization\. The size oftimePointsandrelativeEnergyTimePointsareO​\(n\)O\(n\)while the one ofintervalSizeisO​\(n2\)O\(n^\{2\}\)\. For each characterization, the time complexity for computing all the values isO​\(n2\)O\(n^\{2\}\)\.

Table 2:ER specific characterizations\.Final features:The features used as input for the classification algorithm are aggregation statistics computed for each characterization type\. In particular, for each vector of values we consider theminimum,maximum,arithmetic mean,geometric mean,median,first quartile,third quartile,population variance,sample variance,kurtosis,skewness,length,cardinality\(i\.e\., the number of distinct elements\)\.

Complexity:The time complexity to compute a cumulative characterization is at mostO​\(n2\)O\(n^\{2\}\), lower than the one of ER\. Most of the statistics that we employ as features have complexityO​\(m\)O\(m\), wheremmis the size of the vector for which the feature is extracted\. Some statistic operations involve an ordering step and have therefore a complexity ofO​\(m​log⁡\(m\)\)O\(m\\log\(m\)\)\. Hence, the worst time complexity for the feature computation isO\(m2\.log\(m2\)\)O\(m^\{2\}\.log\(m^\{2\}\)\), but most of them are actually obtained inO​\(n\)O\(n\),O​\(n​log⁡\(n\)\)O\(n\\log\(n\)\)orO​\(n2\)O\(n^\{2\}\)\.

### 3\.4Selecting and Evaluating a Classifier

Any classification technique can in principle be used to obtain an oracle function\. In this work \(a feasibility study\) we focus on Random Forests and Support Vector Machines for their prediction power\. In a more practical setting, the best classifiers will be those with a good trade\-off between prediction power and computation cost of the classification\. We evaluate the classifiers on a portion of the set from Section[3\.2](https://arxiv.org/html/2607.16523#S3.SS2), that is not employed for the training phase\. We measure the performance based onT​PTP,T​NTN,F​PFP,F​NFNrepresenting the number of tuples that are correctly classified ast​r​u​etrue, correctly classified asf​a​l​s​efalse, incorrectly classified ast​r​u​etrue, incorrectly classified asf​a​l​s​efalse\. Then we consider the following metrics:

- •The𝐹𝑎𝑙𝑙𝑜𝑢𝑡=𝐹𝑃/\(𝐹𝑃\+𝑇𝑁\)\\mathit\{Fallout\}=\\mathit\{FP\}/\(\\mathit\{FP\}\+\\mathit\{TN\}\), corresponding to the number of erroneous activations of ER over all the cases when it is not supposed to run\. The lower the metric, the fewer times were are paying theO​\(n3\)O\(n^\{3\}\)cost of ER in vain\.
- •The𝑅𝑒𝑐𝑎𝑙𝑙=𝑇𝑃/\(𝑇𝑃\+𝐹𝑁\)\\mathit\{Recall\}=\\mathit\{TP\}/\(\\mathit\{TP\}\+\\mathit\{FN\}\), corresponding to the number of times ER is triggered when it is indeed supposed to run\. The larger the metric, the more benefits we have from the propagation power of ER\.

## 4Experiments

### 4\.1Training Set and Classifiers

We obtained our training set as described in Section[3\.2](https://arxiv.org/html/2607.16523#S3.SS2), by solving via LNS the scheduling problems in the BL benchmark \(?\) and the 20 first elements of the Pack benchmark \(?\)\. The considered instances differ for the number of activities \(15 to 33\), the resource capacities and requirements\. For each instance, we performed 15 LNS iterations, each stopped after 500 fails\. At each iteration, roughly 20% of the activities were relaxed\. For each search node, we sampled the domain state of all constraints with a 0\.1 probability\. Duplicates are removed to prevent unfair results\. This resulted in the generation of a data set of 6515 elements with 20\.87% of cases withOπ=t​r​u​eO\_\{\\pi\}=truefor the BL benchmark, and a data set of 13979 elements with 20\.50% of cases withOπ=t​r​u​eO\_\{\\pi\}=truefor the Pack instances\. We refer to those data set as𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}\. We also built a data set by merging𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}and called it𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}\.

Since in this work we are primarily interested in the accuracy ofOπO\_\{\\pi\}, we decided to focus on Random Forests – RF, \(?\) – and Support Vector Machines – SVM, \(?\) – because of their prediction capabilities when the set of most relevant features is not clearly known\. In particular, we used therandomForest\(?\) ande1071\(?\) R packages\.

Random Forests generally build CART trees \(?\) with no pruning\. The complexity for classifying a new instance \(which is part of the overhead of our approaches\) depends on the actual trees that are learned\. A rather pessimistic approximation of the complexity isO​\(μ​log⁡\(ν\)\)O\(\\mu\\log\(\\nu\)\), whereμ\\muis the number of trees andν\\nuis the number of features\.

A trained linear SVM has a time complexity linear in the number of features \(scalar product evaluation\)\. For a non\-linear kernel function, the classification complexity is linear in the number of support vectors \(SV’s\)\. The complexity of a SVM model thus scales with the most difficult samples, forcing an increase in Support Vectors111In \(?\), they speed up the classification by reducing the number of SV’s\.\.

### 4\.2Evaluation

We trained \(using the default parameters\) and tested classifiers using the data sets𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}\(25% of the set was used for the evaluation\)\. In Table[3\(b\)](https://arxiv.org/html/2607.16523#S4.T3.st2)and[3\(b\)](https://arxiv.org/html/2607.16523#S4.T3.st2)we report the 95% confidence intervals for the Fallout and the Recall metrics\. All the tested classifiers \(in particular the Random Forest\) have good performance, with low Fallout and large Recall values\.

Table 3:95% confidence intervals for Fallout and Recall on the two benchmarks\.\(a\)𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}\(b\)𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}Then, in order to put to the test the generalization ability of the classifiers we tried a cross\-benchmarks experiments\. Namely, we evaluated the classifiers trained on𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}dataset over the𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}one, and vice\-versa\. The results were not satisfactory\. This could be a consequence of the training set not being representative enough, or it could hint at the presence of many non meaningful features in the classifier input\.

With the aim to investigate the possible causes, we tried to use the combined𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}set for the training, and then we tested the obtained classifiers on \(previously unseen\) instances from both𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}\(25% in both cases\)\. The confidence intervals of Fallout and Recall for this experiment are given in Table[4\(b\)](https://arxiv.org/html/2607.16523#S4.T4.st2)and[4\(b\)](https://arxiv.org/html/2607.16523#S4.T4.st2)\. As one can see, the performance of the classifiers are now only slightly worse than the original ones\. This suggests that designing a representative training set \(in particular, including diverse benchmarks\) has a strong impact on the classifier ability to generalize\.

Table 4:95% confidence intervals for Fallout and Recall on the two benchmarks, for classifiers trained over𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}\.\(a\)𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}tested on a disjoint part of𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}\(b\)𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}tested on a disjoint part of𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}Warm\-up:The slightly decreased performance observed in Table[4\(b\)](https://arxiv.org/html/2607.16523#S4.T4.st2)and[4\(b\)](https://arxiv.org/html/2607.16523#S4.T4.st2)suggests also that, in case the focus is on obtaining the best results for a specific benchmark, an excessive diversity of the training set may have adverse effects\. In this setting, it would also be particularly interesting if the classifiers could keep a good predictive power, even when trained on a small dataset\. This would allow to tackle a scheduling benchmark by running a short “warm\-up” phase, for training a classifier to be used when solving the remaining instances\. We tested the feasibility of this approach on the two sets𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}separately\. We divided those data sets in several folds to create training sets of increasing sizes\. Each of them was used to compute average metrics using 10\-fold cross\-validation\. Figure[1](https://arxiv.org/html/2607.16523#S4.F1)and[2](https://arxiv.org/html/2607.16523#S4.F2)show respectively the average Recall and Fallout as a function of the training set size for several approaches\. As one can see, reasonably good prediction rates are obtained with Random Forests when the training set contains as little as 25% of the total number of tuples\.

![Refer to caption](https://arxiv.org/html/2607.16523v1/x1.png)Figure 1:Average Recalls computed on cumulative training sets constructed from𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}![Refer to caption](https://arxiv.org/html/2607.16523v1/x2.png)Figure 2:Average Fallouts computed on cumulative training sets constructed from𝑑𝑠𝑏𝑙\\mathit\{ds\}\_\{\\mathit\{bl\}\}and𝑑𝑠𝑝𝑎𝑐𝑘\\mathit\{ds\}\_\{\\mathit\{pack\}\}Feature importance:Proper feature selection is a complicated task and out of the scope of this paper\. However, theimportancescores \(?\) given to attributes in Random Forests provides an estimate of how discriminant the features are\. In a final experiment, we considered for𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}the best features \(15 out of 137\) , according to their reported Gini index and average accuracy\. We removed from such list the feature*Median\(relativeEnergyTimePoints\)*, because of its large computational complexity, and then we tried to learn classifiers on𝑑𝑠𝑚𝑒𝑟𝑔𝑒\\mathit\{ds\}\_\{\\mathit\{merge\}\}based only on such features\. Table[5](https://arxiv.org/html/2607.16523#S4.T5)reports the 95% confidence intervals of Fallout and Recall for the experiment\. As one can see, a small subset of the features is sufficient to reach good prediction accuracy \(in particular with Random Forests\)\. This enables a considerable reduction of the overhead when the oracle function is embedded in a constraint solver\. In the considered case, the retained features are far fewer than the original ones and their maximum complexity isO​\(n2\)O\(n^\{2\}\)\. Incremental computation could also be used to amortize the computational complexity\.

Table 5:95 % confidence intervals of Fallout and Recall metrics of classifiers built using only the best features\.

## 5Conclusion and Future Work

This paper proposes an approach to take better advantage of complex propagators, by running them only when they provide an actual benefit in terms of pruning\. The main idea is that of*paying for what you get*, so as to make the best possible use of powerful propagators often forsaken for their low scalability\. We propose to achieve this goal by relying on an oracle function, obtained via ML techniques\. A combination of design decisions makes our approach particularly flexible compared to existing alternatives\. In this work we focus on investigating the feasibility of an accurate oracle for ER in the context of thecumulativeconstraint\. We show that a very high prediction accuracy can be obtained a reasonably low time complexity\.

Future work involves in first place making the approach faster, by relying on fewer or cheaper\-to\-compute features, by using incremental computation, or by simplifying the classifiers \(e\.g\. fewer trees in a Random Forest\)\. Reducing the training time and the size of the required training set are also important factors when using a “warm\-up” approach before tackling a large set of instances\. Second, we obviously plan to embed the oracle function in an actual propagator and test its efficacy when solving a variety of scheduling problems\. In this context, we also plan to improve the efficacy of the oracle function by taking into account the trade\-off between the propagation complexity and the expected benefit of pruning values*in terms of solution time*\. Finally, our approach should be tested on other constraints and propagators, and compared with alternative techniques \(e\.g\. state base heuristics\)\. A investigation of alternative ML based configurations may also be interesting\. For example, using a classifier to directly pick a propagator, rather than to predict its pruning power, may incur less overhead \(at the price of reduced flexibility\)\.

## References