ABSTRACT. Conflict based clause learning is known to be an important component in Modern SAT solving. Because of the exponential blow up of the size of learnt clauses database, maintaining a relevant and polynomially bounded set of learnt clauses is crucial for the efficiency of clause learning based SAT solvers. In this paper, we first compare several criteria for selecting the most relevant learnt clauses with a simple random selection strategy. We then propose new criteria allowing us to select relevant clauses w.r.t. a given search state. Then, we use such strategies as a means to diversify the search in a portfolio based parallel solver. An experimental evaluation comparing the classical ManySAT solver with the one augmented with multiple deletion strategies, shows the interest of such approach.

ABSTRACT. Constraintsatisfactionandcombinatorialoptimizationprob- lems, even when modeled with efficient metaheurisics such as local search remain computationally very intensive. Solvers stand to benefit significantly from execution on parallel systems, which are increasingly available. The architectural diversity and complexity of the latter means that these systems pose ever greater challenges in order to be effectively used, both from the point of view of the modeling effort and from that of the degree of coverage of the available computing resources. In this article we discuss impositions and design issues for a framework to make efficient use of various parallel architectures

ABSTRACT. We propose to apply a general framework for estimating the parallel performance of Las Vegas algorithms to randomized propagation-based constraint solvers, i.e., when, in the labeling phase, both the variable to instantiate and its value are chosen randomly. Indeed, by analyzing the runtime of the sequential process (which is variable from one run to another because of the stochastic nature of the algorithm) and approximating this runtime distribution with statistical methods, the runtime behavior of the parallel process can be predicted by a model based on order statistics. We apply this approach to study the behavior of a randomized version of the Gecode solver on three classical CSPs problems, and compare the predicted performances to the results of an actual experimentation on parallel hardware up to 256 cores.

ABSTRACT. Many network design problems arising in areas as diverse as VLSI circuit design, QoS routing, traffic engineering, and computational sustainability require clients to be connected to a facility under path-length constraints and budget limits. These problems can be modelled as Rooted Distance-Constrained Minimum Spanning-Tree Problem (RDCMST), which is NP-hard. These networks are vulnerable to a failure. Therefore, it is often important to ensure that all clients are connected to two or more facilities via edge-disjoint paths. We call this problem the Disjoint RDCMST (DRDCMST). We present a constraint-based parallel local search algorithm for solving DRDCMST. Traditional way of extending a sequential algorithm to run in parallel is to either perform portfolio-based search in parallel or to perform parallel neighbourhood search. We rather exploit the semantics of the constraints of the problem to perform multiple moves in parallel by ensuring that they are mutually independent. The ideas presented in this paper are general and can be adapted to any other problem. The effectiveness of our approach is demonstrated by experimenting with a set of problem instances taken from real-world passive optical network deployments in Ireland and the UK. Results show that performing moves in parallel can significantly reduce the time required by our local-search approach.

ABSTRACT. This panel discussion be a forum for considering the main issues and future challenges in the domain of parallel search and optimization

ABSTRACT. Constraint programming has gained prominence as an effective and declarative paradigm for modeling and solving complex combinatorial problems. In spite of the natural presence of concurrency, there has been relatively limited effort to use novel massively parallel architectures-such as those found in modern Graphical Processing Units (GPUs)-to speedup constraint programming algorithms. This paper presents an ongoing work for the development of a constraint solver which exploits GPU parallelism. The work is based on two previous results where constraint propagation and approximated search have been parallelized. We summarize these result and discuss the features we have planned to carry on.