Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents' consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying coordination problem to probabilistic inference. Using inference techniques such as expectation-maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an efficient centralized solver show that our approach provides near-optimal solutions, and is significantly faster on larger instances.

In Constraint Programming (CP), a portfolio solver uses a variety of different solvers for solving a given Constraint Satisfaction / Optimization Problem. In this paper we introduce sunny-cp2: the first parallel CP portfolio solver that enables a dynamic, cooperative, and simultaneous execution of its solvers in a multicore setting. It incorporates state-of-the-art solvers, providing also a usable and configurable framework. Empirical results are very promising. sunny-cp2 can even outperform the performance of the oracle solver which always selects the best solver of the portfolio for a given problem.

Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.

For instance, phrase generation problem involves domains having more than d 10, 000 values. Thus, We propose improved algorithms for defining the we cannot use an algorithm whose time or space complexity most common operations on Multi-Valued Decision is mainly based on Ω(nd), where n is the number of nodes Diagrams (MDDs): creation, reduction, complement, of the MDDs. Therefore, we need to improve the algorithms intersection, union, difference, symmetric performing the main operations on MDDs: creation, reduction difference, complement of union and complement and combinations. of intersection. Then, we show that with these algorithms The new creation algorithm we propose, exploits the origin and thanks to the recent development of an of the definition of the MDD. If the MDD represents an automaton efficient algorithm establishing arc consistency for (like with a regular constraint) or a repeated pattern MDD based constraints (MDD4R), we can simply (like with dynamic programming), then its creation may be solve some problems by modeling them as a set of sped-up.

Generalized arc consistency (GAC) is one of the most fundamental properties for reducing the search space when solving constraint satisfaction problems (CSPs). Consistencies stronger than GAC have also been shown useful, but the challenge is to develop efficient and simple filtering algorithms. Several CSP transformations are proposed recently so that the GAC algorithms can be applied on the transformedCSP to enforce stronger consistencies. Among them, the factor encoding (FE) is shown to be promising with respect to recent higher-order consistency algorithms. Nonetheless, one potential drawback of the FE is the fact that it enlarges the table relations as it increases constraint arity. We propose a variation of the FE that aims at reducing redundant columns in the constraints of the FE while still preserving full pairwise consistency. Experiments show that the new approach is competitive over a variety of random and structured benchmarks.

Specifically, we present a top-down algorithm cn2mddg for compiling finite-domain CNs into multivalued decomposable We present and evaluate a top-down algorithm for decision graphs. The input of cn2mddg is a CN compiling finite-domain constraint networks (CNs) represented in the XCSP 2.1 format [Roussel and Lecoutre, into the language MDDG of multivalued decomposable 2009]. The output of our compilation algorithm is a representation decision graphs. Though it includes Decision-of the solutions of the CN in the language MDDG DNNF as a proper subset, MDDG offers the same key of multivalued decomposable decision graphs. MDDG is precisely tractable queries and transformations as Decision-the extension to non-Boolean domains of the language DNNF, which makes it useful for many applications. DDG [Fargier and Marquis, 2006] also known as Decision-Intensive experiments showed that our compiler DNNF [Oztok and Darwiche, 2014]: it is based on decomposable cn2mddg succeeds in compiling CNs which -nodes and (multivalued) decision nodes. Similarly are out of the reach of standard approaches based to Decision-DNNF, the MDDG language offers a number of on a translation of the input network to CNF, followed tractable queries, including (possibly weighted) solution finding by a compilation to Decision-DNNF. Furthermore, and counting, solution enumeration (solutions can be enumerated the sizes of the resulting compiled representations with polynomial delay), and optimization w.r.t. a linear turn out to be much smaller (sometimes by objective function. It also offers tractable transformations, several orders of magnitude).

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.

Core-guided MAXSAT algorithms dominate other methods in solving industrial MAXSAT problems. In this work, we propose a new efficient algorithm that is guided by correction sets and cores. At every iteration, the algorithm obtains a correction set or a core, which is then used to rewrite the formula using incremental and succinct transformations. We theoretically show that correction sets and cores have complementary strengths and empirically demonstrate that their combination leads to an efficient MAXSAT solver that outperforms state-of-the-art WPMS solvers on the 2014 Evaluation on industrial instances.

Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solver-level programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.

The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of the microstructure. One form of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture the well-known property of acyclicity. In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we obtain a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of acyclic instances.