Machine learning has tremendously benefited from graphics processing units (GPUs) to accelerate training and inference by several orders of magnitude. However, this success has not been replicated in general and exact combinatorial optimization. Our key contribution is to propose a general-purpose discrete constraint programming solver fully implemented on GPU. It is based on integer interval bound propagation and backtracking search. The two main ingredients are (1) ternary constraint network optimized for GPU architectures, and (2) an on-demand subproblems generation strategy. Our constraint solving algorithm is significantly simpler than those found in optimized CPU constraint solvers, yet is competitive with sequential solvers in the MiniZinc 2024 challenge.

Many real-life problems involve multiple conflicting objectives; hence, the decision maker is provided with a set of trade-off solutions, the Pareto front. While many methods to compute Pareto fronts have been proposed in the mathematical programming literature, comparatively few approaches are available for constraint programming (CP). One of the main state-of-the-art algorithms in CP is a branch-and-bound method that uses a Pareto global constraint, denoted here as MOBAB-CP. In this work, we adapt the SAUGMECON algorithm, a well-known and efficient ε-constraint method, in a CP solver. We also propose a new algorithm that combines SAUGMECON with the Pareto global constraint. Experimental results show that the proposed algorithm consistently achieves better results than our CP implementation of SAUGMECON and is competitive with MOBAB-CP, outperforming it on several of the studied problems.

In the field of constraint programming, selecting the most effective search strategy for a new problem is a complex task. Despite the existence of numerous autonomous search strategies, the effectiveness of a strategy is highly problem-specific and no single strategy can universally excel. Therefore, for the solver's developers, it is difficult to find a good default strategy working across many problems. For the end-user, it is a daunting task to select the best search strategy, and they will usually rely on the solver's default, missing out better strategies. In this paper, we introduce the probe and solve algorithm which explores different search strategies in a probing phase, using a portion of the global timeout, and uses the best strategy found to solve the problem. By viewing the search strategy as hyperparameters, we leverage Bayesian optimization, a hyperparameter optimization technique well-known in machine learning but, to the best of our knowledge, not used in constraint programming. A key strength of our approach is to be generic and non-invasive: it can be used on top of any MiniZinc or XCSP3-compatible solvers, without modifying those. Further, probe and solve consistently achieved better results in the XCSP3 and MiniZinc competitions than the solver's default search and modern dynamic search strategies: DomWDeg/CACD, FrbaOnDom and PickOnDom, with the ACE and Choco constraint solvers.

Satellite imagery solutions are widely used to study and monitor different regions of the Earth. However, a single satellite image can cover only a limited area. In cases where a larger area of interest is studied, several images must be stitched together to create a single larger image, called a mosaic, that can cover the area. Today, with the increasing number of satellite images available for commercial use, selecting the images to build the mosaic is challenging, especially when the user wants to optimize one or more parameters, such as the total cost and the cloud coverage percentage in the mosaic. More precisely, for this problem the input is an area of interest, several satellite images intersecting the area, a list of requirements relative to the image and the mosaic, such as cloud coverage percentage, image resolution, and a list of objectives to optimize. We contribute to the constraint and mixed integer lineal programming formulation of this new problem, which we call the satellite image mosaic selection problem, which is a multi-objective extension of the polygon cover problem. We propose a dataset of realistic and challenging instances, where the images were captured by the satellite constellations SPOT, Pléiades and Pléiades Neo. We evaluate and compare the two proposed models and show their efficiency for large instances, up to 200 images.

Abstract Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for various constraint solvers. In particular, it relies on abstract domains which capture constraint languages as ordered structures. The key insight of this paper is viewing cooperation schemes as abstract domains combinations. We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. This differs from existing approaches such as SMT where the cooperation scheme is usually fixed (e.g., Nelson-Oppen). We contribute to two new cooperation schemes: (i)interval propagators completionthat allows abstract domains to exchange bound constraints, and (ii)delayed productwhich exchanges over-approximations of constraints between two abstract domains. Moreover, the delayed product is based on delayed goal of logic programming, and it shows that abstract domains can also capture control aspects of constraint solving. Finally, to achieve modularity, we propose theshared productto combine abstract domains and cooperation schemes. Our approach has been fully implemented, and we provide various examples on the flexible job shop scheduling problem.

Constraint programming initially aims to be a declarative paradigm, but its quest for efficiency is mainly achieved through the development of ad-hoc algorithms, which are encapsulated in global constraints. In this paper, we explore the idea of extending constraint programming with abstract domains, a structure from program analysis by abstract interpretation. Abstract domains allow us to efficiently process constraints of the same form, such as linear constraints or difference constraints. This classification by constraint sub-languages instead of sub-problems, makes abstract domains more general and more reusable in many problems. We contribute to the definition of an abstract domain encapsulating a constraint solver in a conservative way w.r.t. constraint programming. We also define a product of abstract domains based on reified constraints and under-approximations. We study a well-known scheduling problem to motivate our approach and experiment its feasibility.

Search strategies are crucial to efficiently solve constraint satisfaction problems. However, programming search strategies in the existing constraint solvers is a daunting task and constraint-based languages usually have compositionality issues. We propose spacetime programming, a paradigm extending the synchronous language Esterel and timed concurrent constraint programming with backtracking, for creating and composing search strategies. In this formalism, the search strategies are composed in the same way as we compose concurrent processes. Our contributions include the design and behavioral semantics of spacetime programming, and the proofs that spacetime programs are deterministic, reactive and extensive functions. Moreover, spacetime programming provides a bridge between the theoretical foundations of constraint-based concurrency and the practical aspects of constraint solving. We developed a prototype of the compiler that produces search strategies with a small overhead compared to the hard-coded ones.

Solving constraint satisfaction problems (CSP) efficiently depends on the solver configuration and the search strategy. However, it is difficult to customize the constraint solvers because they are not modular enough, and it is hard to create new search strategies by composition. To solve these problems, we propose spacetime programming, a paradigm based on lattices and synchronous process calculi that views search strategies as processes working collaboratively towards the resolution of a CSP. We implement the compiler of the language and use it to replace the search module of Choco, a state of the art constraint solver, with an efficient spacetime program that offers better modularity and compositionality of search strategies.