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.

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.

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.

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.

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.

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.

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.

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 generalpurpose
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.

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.

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.

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.

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.

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.

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.