As lazy clause generation has seen much success in recent years, the generation of explanations has become the focus of much research. This paper describes how explanations can be generated for detectable precedences in the disjunctive constraint. We also provide a method to incorporate these explanations into the filtering algorithm proposed by Fahimi et al. [7] by adapting Vilím’s explanations [18]. We proposed two approaches to generating explanations: an approach using only the previously scheduled tasks to explain propagation and an approach using an even smaller subset of tasks combined with explanation lifting. An empirical evaluation of two of our approaches for generating explanations compared to a baseline with naïve explanations found that both approaches performed better in terms of conflicts, LBD, learned clause length and runtime. The most advanced approach of the two (last cluster) performed the best. We believe that using the last cluster approach to generating explanations with other propagators for the disjunctive constraint could be successful.

The cumulative constraint is often used when modeling constraint programming problems, frequently seen in scheduling and planning problems. Energetic reasoning is one of the propagators used to enforce this constraint. However, not much has been done to explore strategies for generating explanations, which are then used by the solver for conflict analysis. This paper addresses this gap by applying strategies used in time-table edge-finding to the energetic reasoning propagator. The strategies are initial bounds relaxations and reducing the overload. Furthermore the paper compares two old strategies (naive and greedy task removal) for reducing the overload and proposes two new ones: greedy task shift and a probabilistic heuristic utilizing the knapsack problem. Results on the MiniZinc RCPSP benchmarks show that the initial bounds adjustments provide great benefit, reducing the number of conflicts by at least twenty-five percent. Reducing the overload provided a small improvement (less than five percent) and results suggest there is not much of a difference between the different strategies.

Currently explanations for the Not-First/Not-Last propagators for the disjunctive constraint have not been explored thoroughly, and have room for improvement.
In this paper, we look into attempting to give more general explanations by looking through the powerset of tasks and finding a smaller set which still propagates.
We have implemented naive, the state-of-the-art and our subset-finding explanations and compared them all.
Experimentally, around 50\% of the results show a lower amount of conflicts and average literal bound distance, however a majority have a higher runtime.
In addition, the more subsets we consider the bigger the runtime, however it not necessarily decrease in amount of conflicts and average literal bound distance.

Explanations have been shown to significantly increase the performance of propagators, when applied to solvers that make use of Lazy Clause Generation. However, to date, there has been little work in exploring explanations for the disjunctive constraint and how they perform compared to simple propagation making use of Naive Explanations. I address this gap by considering an Edge-Finding propagation algorithm for the disjunctive and evaluating the performance of three variants of a solver on job-shop problems, each of them using different explanation techniques, which have been adapted from previous work. I also provide an algorithm serving as an extension to Edge-Finding, which can be used to generate explanations. Then, I compare all approaches in relation to a baseline consisting of a solver that has no support for the disjunctive and uses decomposition. Through experiments, I demonstrate that good explanations provide a significant improvement in terms of recorded metrics compared to the naive method, even if generating them requires additional computational overhead.

Core-guided search has been prevalent in the field of Maximum Satisfiability (MaxSAT), largely due to the application of additional techniques that improve performance. With core-guided search being recently applied to Constraint Programming (CP), the question emerges whether such additional techniques can be applied to CP as well. In this thesis, four such features are implemented: weight-aware core extraction (WCE), which extracts multiple disjoint cores, reducing core size and overhead to improve efficiency; stratification, which extracts high-weighing cores first, allowing it to give better estimates and often to require fewer cores to be found; hardening, which prunes suboptimal parts of the search space, guiding search closer to the optimal solution; and partitioning, which divides the terms in the objective function into disjoint, strongly intra-related groups, thereby causing smaller cores to be found efficiently. With the exception of hardening which is used in conjunction with either WCE or stratification these are individually combined with the four approaches used to apply core-guided search to CP. This evaluation results in an in-depth analysis on which features combine well with which approaches, and why, as well as the individual strengths of the approaches and features. We observed that the variable-based approach generally perform better than the slice-based approach, with coefficient elimination increasing this difference. Hardened WCE has the largest positive effect, especially in the slice-based approach; it causes speedups in all four base approaches, resulting in an overall performance increase in three of those. The variable-based coefficient eliminating variant without additional features was able to solve the most instances; all additional features decreased performance. The current implementation of partitioning was able to improve on some key metrics, but decreased overall performance in all four cases. Other important conclusions are that no solver strictly outperformed any other, advocating that different solvers are best suited for different problems. Secondly, the order of assumptions has been proven to cause significant changes in the performance of solvers. Finally, we concluded that considering relaxations generally helps prove unsatisfiability.

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.

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.