ABSTRACT. Constraint programming (CP) is a well-established method for tackling combinatorial problems. Traditionally, CP has focused on solving isolated problem instances, often overlooking the fact that these instances frequently originate from related data distributions. In recent years, there has been a growing interest in leveraging machine learning, particularly neural networks, to enhance CP solvers by utilizing historical data. Despite this interest, it remains unclear how to effectively integrate learning into CP engines to boost overall performance. In this presentation, I will share my journey in tackling this challenge, from my initial attempts to my current research directions. I will offer personal advice for researchers interested in exploring this fascinating field, highlighting the potential and opportunities for integrating machine learning with constraint programming.

ABSTRACT. This presentation will explore recent advancements in Decision-Focused Learning (DFL), an emerging approach in artificial intelligence (AI) that integrates machine learning (ML) prediction with combinatorial optimization to train ML models for optimal decision-making. DFL predicts the unknown parameters of combinatorial optimization problems by focusing on the outcomes obtained using these predicted parameters. This presentation will start by providing an overview of various DFL techniques and introduce a taxonomy that categorizes these methods based on their distinct features. It will then highlight the scalability challenge, a major bottleneck for real-world DFL applications. The presentation will summarize existing strategies developed to address this issue and conclude by exploring potential future directions in the field.

ABSTRACT. When solving decision and optimisation problems, many competing algorithms (model and solver choices) have complementary strengths. Typically, there is no single algorithm that works well for all instances of a problem. Automated algorithm selection has been shown to work very well for choosing a suitable algorithm for a given instance. However, the cost of training can be prohibitively large due to running candidate algorithms on a representative set of training instances. In this work, we explore reducing this cost by choosing a subset of the training instances on which to train. We approach this problem in three ways: using active learning to decide based on prediction uncertainty, augmenting the algorithm predictors with a timeout predictor, and collecting training data using a progressively increasing timeout. We evaluate combinations of these approaches on six datasets from ASLib and present the reduction in labelling cost achieved by each option.

ABSTRACT. Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation due to CP's struggle with implementing "meaning" and ML's difficulty with structural constraints. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP. The LLM handles word generation and meaning, while CP manages structural constraints. This approach builds on On-the-fly Constraint Programming Search (OTFS), improving it using LLM-generated domains. Compared to Beam Search (BS), a standard NLP method, this combined approach (OTFS with LLM) is faster and produces better results, ensuring all constraints are satisfied. This fusion of CP and ML presents new possibilities for enhancing text generation under constraints.

ABSTRACT. Constraint Programming (CP) allows for the modelling and solving of a wide range of combinatorial problems. However, modelling such problems using constraints over decision variables still requires significant expertise, both in conceptual thinking and syntactic use of modelling languages. In this paper, we explore the potential of using pre-trained Large Language Models (LLMs) as coding assistants, to transform textual problem descriptions into concrete and executable CP specifications. We investigate different transformation pipelines with explicit intermediate representations, and we investigate the potential benefit of various retrieval-augmented example selection strategies for in-context learning. We evaluate our approach on 2 datasets from the literature, namely NL4Opt (optimisation) and Logic Grid Puzzles (satisfaction), and on a heterogeneous set of exercises from a CP course. The results show that pre-trained LLMs have promising potential for initialising the modelling process, with retrieval-augmented in-context learning significantly enhancing their modelling capabilities.

ABSTRACT. Constraint programming (CP) modeling languages, like Minizinc and CPMpy, play a crucial role in making CP technology accessible to non-experts. Both solver-independent modeling languages and solvers themselves are complex pieces of software that can contain bugs, which undermines their usefulness. Mutational fuzz testing is a way to test complex systems by stochastically mutating input and verifying preserved properties of the mutated output. We investigate different mutations and verification methods that can be used in the context of constraint programming. This includes methods proposed in the context of SMT-solving, as well as new methods related to global constraints, optimization, and solution counting/preservation. Our results show that such a fuzz testing approach improves the overall code coverage of a modeling system compared to only unit testing, and is able to find bugs in the whole toolchain, from the modeling language transformations themselves to the underlying solvers.

ABSTRACT. Pseudo-Boolean proof logging has been used successfully to provide certificates of optimality from a variety of constraint- and satisifability-style solvers that combine reasoning with a backtracking or clause-learning search. Another paradigm, occurring in dynamic programming and decision diagram solving, instead reasons about partial states and possible transitions between them. We describe a framework for generating clean and efficient pseudo-Boolean proofs for these kinds of algorithm. Because we use a common proof system, we can even reason about hybrid solving algorithms: we demonstrate this by providing proof logging for a dynamic programming based knapsack propagator inside a constraint programming solver.

ABSTRACT. Proof logging is a method used to increase trust in the optimality and unsatisfiability claims of solvers. However, no constraint programming solver can practically log proofs without significantly impacting performance, which hinders mainstream adoption. We present a proof logging framework for constraint programming, together with a CP proof format and proof checker. Our approach is to require the solver to produce a scaffold, a compressed proof, which is subsequently trimmed, then expanded into our CP proof, and finally verified. The framework is agnostic to the solver and verification approach. Through MiniZinc benchmarks, we demonstrate that with our framework the overhead of logging during solving is less than 10\%, and that an additional processing step can significantly reduce the overall size of the proof and by extension the proof checking time. Our results demonstrate that proof logging has the potential to become an integral part of the CP community.

ABSTRACT. Mixed integer programming (MIP) is a fundamental model in operations research. Local search is a powerful method for solving hard problems, but the development of local search solvers for MIP still needs to be explored. This work develops an efficient local search solver for solving MIP, called Local-MIP. We propose two new operators for MIP to adaptively modify variables for optimizing the objective function and satisfying constraints, respectively. Furthermore, we design a new weighting scheme to dynamically balance the priority between the objective function and each constraint, and propose a two-level scoring function structure to hierarchically guide the search for high-quality feasible solutions. Experiments are conducted on seven public benchmarks to compare Local-MIP with state-of-the-art MIP solvers, which demonstrate that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP and Feasibility Jump, and is competitive with the most powerful commercial solver Gurobi. Moreover, Local-MIP establishes 4 new records for MIPLIB open instances.

ABSTRACT. This tutorial provides a comprehensive guide to solving constraint programming problems using JuMP, a domain-specific modeling language for mathematical optimization in Julia. JuMP supports a wide range of solvers including SAT, CP (both Constraint Programming and Conic Programming), and Mixed-Integer Linear Programming (MILP) solvers, all accessible through a unified interface. One of JuMP's key features is its powerful constraint reformulation mechanism, which allows users and solvers to define new constraint types and reformulations or to disable existing ones. JuMP's automatic reformulation process involves solving a shortest path problem within a hypergraph that represents all possible constraint types and their reformulations. This innovative approach enables users to effectively explore and experiment with different reformulations, ensuring the appropriate model is communicated to the solver. JuMP also implements an interface with MiniZinc which allows it to use any solver that MiniZinc supports. We also show how to use callbacks with MILP solvers, an essential feature to combine the generic heuristic of the solver with the user problem-specific knowledge. During the tutorial, we go through several examples to illustrate each aspect of the talk.

ABSTRACT. We present a novel scheduling model that leverages Constraint Programming (CP) to enhance problem solving performance in Temporal Planning. Building on the established strategy of decomposing causal and temporal reasoning, our approach abstracts two common fact structures present in many Temporal Planning problems -- Semaphores and Envelopes -- and performs temporal reasoning in a CP-based scheduler. At each search node in a heuristic search for a temporal plan, we construct and solve a Constraint Satisfaction Problem (CSP) and integrate feedback from the CP-based scheduler to guide the causal planning search towards a solution. Through experimental analysis, we validate the impact of these advancements, demonstrating a significant reduction in both the number of states searched and in search time alongside an increase in problem-solving coverage.

ABSTRACT. The resource constrained project scheduling problem (RCPSP) consists of scheduling a finite set of resource-consuming tasks within a temporal horizon subject to resource capacities and precedence relations between pairs of tasks. It is NP-hard and many techniques have been introduced to improve the efficiency of CP solvers to solve it. The problem is naturally represented as a directed graph, commonly referred to as the precedence graph, by linking pairs of tasks subject to a precedence. In this paper, we propose to leverage the ability of graph neural networks to extract knowledge from precedence graphs. This is carried out by learning new precedences that can be used either to add redundant constraints or to design a dedicated variable-selection heuristic. Experiments carried out on RCPSP instances from PSPLIB show the potential of learning to predict precedences and how they can help speed up the search for solutions by a CP solver.

ABSTRACT. We investigate using Constraint Programming (CP) and Domain-Independent Dynamic Programming (DIDP) to solve the master problem in Logic-based Benders Decomposition (LBBD) models in particular addressing the challenge of how to formulate feasibility cuts. For CP, we exploit key variable manipulation, constraint-based expressions, and global constraints to construct three combinatorial cut encodings. For the state-based DIDP model, we propose two cut encoding approaches: using additional preconditions of state transitions or adding state constraints. Each of these approaches can be modeled using integer numeric variables or set variables, resulting in four novel encodings. We apply the three CP variants and four DIDP variants to simple assembly line balancing problems with sequence-dependent setup times type-1 (SUALBP-1). Experimental results show all approaches outperform a mixed-integer programming (MIP) based master problem and the state-of-the-art monolithic MIP model, with the three CP variants being superior to all of the DIDP approaches.

ABSTRACT. The success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach is fast and avoids, in practice, a large number of explicit computations of shortest paths.

ABSTRACT. In project scheduling, calendar considerations can increase the duration of a task when its execution overlaps with holidays. On the other hand, the use of overtime may decrease the task’s duration. We introduce the CalendarOvertime constraint which verifies that a task follows a calendar with overtime and holidays. We also introduce the CumulativeOvertime constraint, a variant of the Cumulative constraint, that also reasons with the calendars when propagating according to the resource consumption, the overtime, and the holidays. Experimental results of a RCPSP model on the PSPLIB, BL, and PACK instances augmented with calendars and overtime show that the use of the CalendarOvertime constraint offers a speedup greater than 2.9 on the instances optimally solved and finds better solutions on more than 79% of the remaining instances when compared to a decomposition of the constraint. We also show that the use of our CumulativeOvertime constraint further improves these results.

ABSTRACT. As quantum technology is advancing, the efficient design of quantum circuits has become an important area of research. This paper provides an introduction to the MCT quantum circuit design problem for reversible Boolean functions without assuming a prior background in quantum computing. While this is a well-studied problem, optimization models that minimize the true objective have only been explored recently. This paper introduces a new optimization model and symmetry-breaking constraints that improve solving time by up to two orders of magnitude compared to earlier work when a Constraint Programming solver is used. Experiments with up to seven qubits and using up to 15 quantum gates result in several new best-known circuits for well-known benchmarks. Finally, an extensive comparison with other approaches shows that optimization models may require more time but can provide superior circuits with optimality guarantees.

ABSTRACT. The BinPacking constraint models the requirements of many logistics, resource allocation, and production scheduling applications. This paper explores new avenues based on the impressive computational power of modern GPUs to propagate the BinPacking constraint.

This paper showcases how the perspective of massive parallelization can lead to novel approaches, such as the use of a portfolio of lower bounds, to enhance the pruning of the BinPacking constraints. It delivers insights into the design choices and challenges presented by GPU platform for constraint propagation.

The paper evaluates a GPU-accelerated propagator against both sequential and parallel CPU versions, as well as state-of-the-art approaches. Comparisons across various benchmarks from the literature show strong performances with respect to both CPU versions and the standard pruning approach. When compared to techniques based on Linear Programming, our approach proves valuable for large instances or when spending extensive time to obtain the best possible bound is not convenient.