Conflict analysis has become one of the key techniques behind the success of modern Constraint Programming (CP) solvers. In Lazy Clause Generation (LCG), conflicts are analysed to derive learned constraints, known as nogoods, which help the solver avoid revisiting infeasible regions of the search space. While learned nogoods can substantially improve search efficiency, maintaining large nogood databases introduces computational and memory overheads, making periodic removal of low-quality nogoods essential. Existing approaches largely rely on heuristics adopted from SAT solving, yet their comparative performance in the CP setting has not been systematically studied.

This thesis investigates the impact of nogood quality metrics and database reduction strategies on the performance of CP solvers. We analyse eight nogood quality metrics, including both established measures such as activity and Literal Block Distance (LBD), as well as new CP-specific metrics. We analyse their correlation with nogood usefulness, defined in terms of propagation behaviour across progressively stricter notions of utility. We find that all metrics can, to some extent, predict the usefulness of nogoods, and we identify four metrics for further study.

We then propose and evaluate a set of nogood management schemes that combine these metrics in different ways. Experiments across hundreds of optimisation and satisfaction instances from the MiniZinc Challenge show that a scheme retaining nogoods with either low LBD or high activity achieves the fewest conflicts and outperforms the default management strategy of the state-of-the-art solver Pumpkin. For anytime behaviour, incorporating the number of variables enables faster discovery of high-quality solutions. We further demonstrate that periodic database reductions are necessary, but that the choice of database size parameters involves a trade-off between finding solutions quickly and proving optimality. Finally, we find that differences in solver performance cannot be fully explained by schemes' ability to remove nogoods that cause few propagations and retain the active ones, suggesting avenues for future research. ... Read more

As the relevance of rail transport continues to grow, efficient operational planning becomes increasingly critical. This is also evident at stations, where unused trains must be moved to the yard and returned to the platform when needed. To achieve this, available drivers must be assigned to trains in a way that respects the time constraints of their shifts. This thesis explores the approach of combining the shunt routing problem (SRP), where times for routes of shunt trains are calculated, with the drivers' problem, which deals with creating feasible driver schedules. The resulting Constraint Programming (CP) model is based on an existing CP model for the SRP. This combined model is tested on four stations in the Netherlands and solves the problem in under 200 seconds for the Vlissingen and Enkhuizen stations, while higher runtimes for Enschede and Amersfoort are observed.
Experiments with an alternative model structure highlight how the linking of the train and driver variables influences runtime significantly. Several variable and value selection strategies are examined on multiple variables, improving performance for certain instances. Furthermore, the analysis reveals that runtime is highly dependent on the station and instance characteristics.
By combining the SRP with the drivers’ problem, this thesis delivers a functional CP model applicable across all stations and contributes to a deeper understanding of the integration of the two problems. ... Read more

This thesis introduces Lazy Linear Generation (LLG), a novel conflict analysis and learning framework for Constraint Programming (CP) that incorporates cutting planes reasoning. By leveraging cutting planes, our approach learns potentially stronger linear constraints than traditional clausal learning, allowing for more pruning of the search space while benefiting from strong CP propagation.

LLG generates linear explanations for both propagations and conflicts, which are then used in linear inequality-based conflict analysis. When cutting planes reasoning fails to derive a linear constraint, we employ Lazy Clause Generation (LCG) as a fallback mechanism. We present linear explanations for various arithmetic constraints, including less-than-or-equal, not-equal, absolute value, maximum, integer multiplication, truncating division, element, and reified constraints. Additionally, we introduce techniques for dynamically generating auxiliary Boolean variables to encode conditions within linear explanations.

We evaluate an LLG prototype on 952 benchmark instances, demonstrating a median conflict reduction of 10%, increasing to 60% for the 25th percentile. Our results confirm that linear inequalities enable stronger reasoning than clauses and show that integrating CP propagators with linear conflict analysis outperforms employing a fully linear model. Furthermore, we show that a clausal fallback mechanism is crucial when linear analysis fails.

While further research and engineering efforts are required for full integration into CP solvers, our findings underscore the potential of linear learning in CP, paving the way for more effective conflict analysis and solving. ... Read more

Constraint programming is a paradigm used for solving complex combinatorial problems with applications in logistics, healthcare, telecommunications, and many other fields. Among the many constraints used in constraint programming is the inverse constraint, necessary for matching items one to one, such as the placement of containers on ships and task scheduling. This paper presents a novel propagator for the inverse constraint, leveraging the Dulmage-Mendelsohn decomposition, implemented in the Pumpkin solver, to improve the performance of the solver. Unlike decompositions of the constraint into other simpler constraints, our approach utilizes the full bipartite graph structure of the constraint, generating stronger and more reusable explanations for unsolvable states.
Experiments were conducted on benchmark problems taken from the MiniZinc challenge, including the Time-Dependent Traveling Salesman Problem (TDTSP) and Perfect One-Factorization (P1F). These experiments demonstrated the effectiveness of the propagator. Achieving up to a 35% reduction in the time taken by the solver for some instances of TDTSP,the method also highlights limitations in the symmetric application of the inverse constraint on a single array. These findings advance our understanding of the propagation of the inverse constraint and show the potential of graph based techniques to optimize LCG solvers. Future work aims to optimize the implementation and explore its performance in relation to a broader spectrum of techniques. ... Read more

The regular constraint offers good balance between expressiveness and cost. Despite potential exponential blow-up, existing approaches use deterministic automata. Furthermore, the area of combining conflict-driven learning with regular is unexplored. We combine learning with non-determinism, to produce an NFA-based propagator with explanations, and compare its performance against decomposition of the constraint. Experimental results on Nonogram
instances indicate that our specialized propagator is significantly better than decomposing regular constraint. ... Read more

The table constraint is a fundamental component of constraint programming (CP), used to explicitly define valid value combinations for variables. In modern Lazy Clause Generation (LCG) solvers, constraints rely on explanations to justify value removals and enable efficient conflict analysis through nogood generation. However, table constraints have primarily been implemented using direct SAT encodings, such as the state-of-the-art Bacchus method, rather than explanation-based approaches. This paper introduces two types of explanation-based propagators for table constraints: eager explanations, generated during propagation, and lazy explanations, which adapt explanations to specific conflicts for more general nogoods. Experiments on MiniZinc benchmarks show that Optimized (Lazy) explanations reduce conflicts by an average of 23% across all problems and up to 64% for specific instances compared to the Bacchus encoding, while also reducing learned clause length by 46%. Although the current implementations incur a runtime penalty of up to 2x, these findings highlight the potential of explanation-based propagators to improve conflict resolution and search efficiency with further optimizations. ... Read more

In Constraint Programming, combinatorial problems such as those arising in the fields of artificial intelligence, scheduling, or circuit verification are modeled using mathematical constraints. Algorithms for each type of constraint are implemented in a solver and are known as propagators. Some constraints can be implemented using combinations of smaller existing propagators (this is known as decomposition), which is often used in Lazy Clause Generation (LCG) solvers, where research has shown that decompositions can be competitive or sometimes superior to purpose-built propagators for certain kinds of constraints. However, there is little research about whether a purpose-built propagator is superior to decomposition for the global cardinality constraint when used with an LCG solver. This paper benchmarks both approaches using an experimental Rust-based solver and uses existing algorithms to implement two global cardinality propagators which are then adapted for use in an LCG solver. The benchmarks show that both implementations are competitive or outperform decomposition in a dataset of 90 instances of Sudoku puzzles, being 3.19 and 2.28 times faster for Regin GAC and Basic Filter respectively. On the Minizinc Challenge dataset, the speedup factor is and 1.34 and 1.0.
... Read more

In this paper we embed a solution for bin packing problems in a constraint programming environment.
Existing solutions for bin packing problems are plentiful, but rigid.
We have taken existing solutions of bin packing in constraint programming, and analysed the steps this algorithm takes.
We then developed explanations for these steps in the form of boolean clauses.
Using these explanations, a constraint programming paradigm by the name of lazy clause generation is able to generate new rules, that prevent the solver from making the same mistake twice.
We have compared our implementation to two different solutions.
Firstly we compared it to a decomposition, where the bin packing constraint was broken down into many smaller and simpler constraints.
Secondly, we compared our implementation to a version with naive explanations.
In one benchmark, comparing our version to the decomposition in a pure bin packing problem, our implementation vastly outperformed the decomposition.
In other benchmarks, the results comparing our version to the other two were much more inconclusive.
While showing marginal improvements in some cases, our version performed worse in other cases.
The research performed in this paper definitely shows promise, and there is merit in exploring this approach in further research. ... Read more

The Shunt Routing Problem (SRP) is an important logistic problem at nearly every railway station. It is a subproblem of an even bigger train scheduling problem, the Train Unit Shunting Problem (TUSP). The objective of SRP is to schedule conflict-free routes between the platforms and the yards, for currently non-operational trains that have completed their current journeys and have not yet commenced the next one.
We developed a Constraint Programming (CP) model for the Shunt Routing Problem at NS. The model is intended to replace the current algorithm for constructing the initial solution for the Local Search, addressing the TUSP at NS. The model incorporates all essential feasibility requirements and produces conflict-free solutions, in contrast to its forerunner. Moreover, it can be applied to any instance and station layout.

Initially, the model exhibited an average performance of 7-8 minutes on a real-life instance at Enkhuizen station. We managed to enhance the model and reduce the computation time to less than a second. The key improvements were achieved by changing the solver search strategy, imposing additional search guidelines, or further restricting the domains of influential variables. During experimentation, an optimized second version of the model was proposed.
The evaluation undoubtedly confirmed that it outperforms the first version.

Both versions of the model, without any additional enhancements, perform exceptionally well on a second real-life instance at Amersfoort station, solving it in milliseconds. Even with a considerable number of additional routes, the performance of the second version remained reasonable, with a computation time of 18 seconds.

A final experiment revealed the remarkable performance of Gecode, achieving computation time in milliseconds with the second version of the model implemented for Enkhuizen in MiniZinc. This performance is an order of magnitude faster compared to the default performance of Google OR-Tools on Enkhuizen with the second version.
... Read more

This paper introduces a new approach to the Preemptive Resource Constrained Project Scheduling Problem with setup times. The method makes use of a Constraint Optimization Problem solver, which has been modified to use priority-rule-based heuristics in its variable and value selection procedures. An alternative implementation which uses a combination of a priority-rule heuristic and a domain-independent solver heuristic has also been investigated. Both methods were tested on four well-known problem sets against a problem-independent solver configuration. Experimental results show a significant reduction in the time needed to find optimal solutions for the new methods. ... Read more

This paper looks at the different parts of the Critical Path and Resource Utilization (CPRU) heuristic for use in the Resource Constraint Project Scheduling Problem, with variable resources (RCPSP-t programming problem). RCPSP-t has many real-world instances such as in hospitals or manufacturing. Optimizing the solution generation for these instances may improve the efficiency of these industries. CPRU was split into parts and different versions were compared against VSIDS a more modern heuristic to determine if problem-specific heuristics perform better than generally good ones. A new adaptation of CPRU that adapts the research utilisation score by calculating the fraction used based on the amount of resources available given scheduled activities instead of looking at the resources of the problem instance. From the results, we concluded that CPRU may perform better for large instances of RCPSP- t compared to VSIDS in terms of generating good schedules within a few iterations. We also found that CPRU generates better schedules given a small time limit. We did not find evidence that the CPRU adaptation improved performance compared to CPRU in terms of schedule and time limits. ... Read more

This paper investigates the inclusion of domain-specific variable selection heuristics in Constraint Programming (CP) solvers for the Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR) problem. We propose two variable selection heuristics: a greedy variable selection method based on densities, Highest Density First (HDF), and a modified Variable State Independent Decaying Sum (VSIDS) initialized with job densities, referred to as VSIDS + Density. Experimental results on benchmark instance sets reveal that the proposed heuristics do not outperform the baseline VSIDS heuristic. Overall, they lead to higher conflict counts and slower convergence. These findings highlight the robustness of general purpose heuristics like VSIDS in diverse problem instances. Future research should explore other domain-specific heuristics, as the current experiment demonstrates that the proposed heuristics do not improve performance. ... Read more

Core-guided solvers and Implicit Hitting Set (IHS) solvers have become ubiquitous within the field of Maximum Satisfiability (MaxSAT). While both types of solvers iteratively increase the solution cost until a satisfiable solution is found, the manner in which this relaxation is performed leads to the belief that these techniques are wholly separate from one another. This work exhibits the difficulty of directly translating the cores found by an IHS-solver to cores utilizable by an OLL-solver due to an inherent disconnect between the manner in which both approaches explore the solution space. It will then be shown how this translation can be performed more easily given certain assumptions. Finally, several techniques are introduced for performing a translation from cores of the original formula to OLL-cores which avoids the aforementioned issue, resulting in a hybrid IHS-OLL algorithm. The comparison between the performance of the hybrid algorithm and RC2 shows that the hybrid algorithm achieves analogous performance in terms of the number of instances solved while indicating that utilising cores of the original formula as a starting point for an OLL solver can be beneficial for the performance of the solver in certain cases. ... Read more

The Variable State Independent Decaying Sum (VSIDS) heuristic is one of the most effective variable selection heuristics for Conflict-Driven Clause-Learning (CDCL) SAT solvers. It works by keeping track of the activity values for each variable, which get bumped and decayed based on conflict analysis. These activity values usually start out arbitrarily at zero, which prompts the question if initializing these values can result in better performance.
This paper presents several adaptations of the VSIDS heuristic specialized for solving the Resource-Constraint Project Scheduling Problem with time varying resource availabilities and demands (RCPSP/t). The approach uses domain-specific knowledge to initialize the activity values of VSIDS with more relevant values. The experiments presented in this paper show that this domain-specific knowledge can indeed benefit the heuristic and can lead to better solve times, allowing the solver to find solutions for 17% more of the instances and find proven optimal solutions for 5% more instances of the PSPLIB data set. ... Read more

This paper solves job sequencing with one common and multiple secondary resources (JSOCMSR) problem by encoding it as a Boolean satisfiability (SAT) problem and applying domain-specific heuristics to improve the SAT solver’s performance. JSOCMSR problem is an NP-hard scheduling problem where each job utilizes two resources: a shared resource and a secondary job-dependent resource. First, the problem was modeled as an instance of SAT and then the SAT solver was augmented with a static greedy variable-ordering heuristic. This heuristic has led to significant improvement in the solver’s speed compared to a generic SAT heuristic for problem instances of larger size. ... Read more

This paper provides a novel method of solving the resource-constrained project scheduling problem (RCPSP) with logical constraints (RCPSP-log) using satisfiability (SAT) solving and integrating variable selection heuristics. The extension provides two additional precedences: OR constraints and bidirectional (BI) relations, making it possible to express more complex dependencies between tasks. OR constraints enable a task to be dependent on multiple preceding tasks, while BI relations do not allow tasks to be executed at the same time. Both problems are known to be NP-hard.

The solution method consists of using a max satisfiability (MaxSAT) solver combined with variable selection heuristics. The paper investigates two heuristics, based on the greedy approach of scheduling each activity as early as possible and variable conflict analysis.

The results on well-known datasets from the literature show that most of the instances can be solved within the designated time limit. The proposed approaches contribute to reducing the makespan, especially when dealing with no logical constraints or only OR relations. For BI constraints, the algorithm is having difficulties in finding solutions, especially when increasing the number of activities, reporting fewer solutions than the baselines. Overall, the results provide insight into the integration of variable selection heuristics for SAT solving, with the potential for more investigation into problem-specific ideas. ... Read more

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an extension of the resource-constrained project scheduling problem (RCPSP), which allows activities to be executed in multiple modes. The state-of-the-art solutions for solving this NP-Hard problem are dedicated algorithms and (meta-)heuristics. However, this paper considers a more flexible approach using a MaxSAT solver. The idea is to replace the existing variable selection strategy of the solver, Variable State Independent Decaying Sum (VSIDS), with two scheduling heuristics, Earliest Starting Time (EST) and Shortest Feasible Mode (SFM). We examine that combining the three heuristics results in a more efficient solver. In contrast, scheduling rules alone lead to a solver that performs significantly worse on any of the chosen metrics and benchmarks. ... Read more

This paper presents a new greedy heuristic to extend SAT Solvers when solving the Preemptive resource-constrained project scheduling problem (PRCPSP-ST). The heuristic uses domain-specific knowledge to generate a fixed order of variable selection. We also extend previous work into encoding PRCPSP-ST by providing an alternative upper bound. The heuristic was tested against VSDIS on the J12 dataset. These experiments show that it performed, on average, six times slower than VSDIS.
... Read more