The constraint composite graph is a node-weighted undirected graph associated with a given

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

problem posed as a weighted

constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constr ...

. Developed and introduced by Satish Kumar Thittamaranahalli (T. K. Satish Kumar), the idea of the constraint composite graph is a big step towards unifying different approaches for exploiting "structure" in weighted constraint satisfaction problems. A weighted constraint satisfaction problem (WCSP) is a

generalization A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common character ...

of a constraint satisfaction problem in which the constraints are no longer "hard," but are extended to specify

non-negative In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...

costs associated with the

tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

s. The goal is then to find an assignment of values to all the variables from their respective domains so that the total cost is minimized. Weighted constraint satisfaction problems find innumerable applications in

artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech r ...

and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

. They are also variously referred to as

markov random field In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to b ...

s (in statistics and

signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...

) and

energy minimization In the field of computational chemistry, energy minimization (also called energy optimization, geometry minimization, or geometry optimization) is the process of finding an arrangement in space of a collection of atoms where, according to some com ...

problems (in

physics Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which rel ...

). While weighted constraint satisfaction problems are

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

to solve in general, several subclasses can be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

when their weighted constraints exhibit specific kinds of numerical structure. Tractable subclasses can also be identified by analyzing the way constraints are placed over the variables. Specifically, a weighted constraint satisfaction problem can be solved in time exponential only in the

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gr ...

of its variable-interaction graph (constraint network). However, a major drawback of the constraint network is that it does not provide a computational framework for leveraging the numerical structure of the weighted constraints. Unlike the constraint network, the constraint composite graph provides a unifying framework for representing both the graphical structure of the variable-interactions as well as the numerical structure of the weighted constraints. It can be constructed using a simple polynomial-time procedure; and a given weighted constraint satisfaction problem is reducible to the problem of computing the minimum weighted

vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...

for its associated constraint composite graph. The "hybrid" computational properties of the constraint composite graph are reflected in the following two important results: (Result 1) The constraint composite graph of a given weighted constraint satisfaction problem has the same treewidth as its associated constraint network. (Result 2) Many subclasses of weighted constraint satisfaction problems that are tractable by virtue of the numerical structure of their weighted constraints have associated constraint composite graphs that are

bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

in nature. Result 1 shows that the constraint composite graph can be used to capture the graphical structure of the variable-interactions (since a minimum weighted vertex cover for any graph can be computed in time exponential only in the treewidth of that graph). Result 2 shows that the constraint composite graph can also be used to capture the numerical structure of the weighted constraints (since a minimum weighted vertex cover can be computed in polynomial time for bipartite graphs). Empirically, when solving a WCSP, it has been shown that it is more advantageous to apply message passing algorithms and integer linear programming on the WCSP's constraint composite graph than on the WCSP directly.{{Cite conference , last1 = Xu , first1 = Hong , last2 = Koenig , first2 = Sven , last3 = Kumar , first3 = T. K. Satish , title = A constraint composite graph-based ILP encoding of the Boolean weighted CSP , book-title = Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP) , year = 2017 , doi=10.1007/978-3-319-66158-2_40 , pages=630–8 , isbn=978-3-319-66158-2 , series=Lecture Notes in Computer Science book series , volume=10416 , publisher = Springer

References

Constraint programming