Hybrid algorithm (constraint satisfaction)
Encyclopedia
In constraint satisfaction
, a hybrid algorithm solves a constraint satisfaction problem
by the combination of two different methods, for example variable conditioning (backtracking
, backjumping
, etc.) and constraint inference
(arc consistency, variable elimination, etc.)
Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve. For example, search is efficient when the problem has many solutions, while inference is efficient in proving unsatisfiability of overconstrained problems.
On some kinds of problems, efficient and complete inference algorithms exist. For example, problems whose primal or dual graphs are trees or forests can be solved in polynomial time. This affect the choice of the variables evaluated by search. Indeed, once a variable is evaluated, it can effectively removed from the graph, restricting all constraints it is involved with its value. Alternatively, an evaluated variable can be replaced by a number of distinct variables, one for each constraint, all having a single-value domain.
This mixed algorithm is efficient if the search variables are chosen so that duplicating or deleting them turns the problem into one that can be efficiently solved by inference. In particular, if these variables form a cycle cutset of the graph of the problem, inference is efficient because it has to solve a problem whose graph is a tree
or, more generally, a forest. Such an algorithm is as follows:
find a cycle cutset of the graph of the problem
run search on the variables of the cutset
when a consistent partial assignment to all variables are found,
replace each variable of the cutset with a new variable for each constraint;
set the domains of these new variables to the value of the old variable in the partial assignment
solve the problem using inference
The efficiency of this algorithm depends on two contrasting factors. On the one hand, the smaller the cutset, the smaller the subproblem to be soilved by search; since inference is efficient on trees, search is the part that mostly affects efficiency. On the other hand, finding a minimal-size cutset is a hard problem. As a result, a small cycle cutset may be used instead of a minimal one.
Another alternative to reduce the running time of search is to place more burden on the inference part. In particular, inference can be relatively efficient even if the problem graph is not a forest but a graph of small induced width. This can be exploited by doing search on a set of variables that is not a cycle cutset but leaves the problem, once removed, to be have induced width bounded by some value
. Such set of variables is called a 
-cutset of the problem.
The induced width of a graph after a set of variables is removed is called adjusted induced width. Therefore, the induced width adjusted relative to a
cutset is always 
. Finding a minimal-size 
-cutset is in general hard. However, a 
-cutset of non-minimal size can be found easily for a fixed order of the variables. In particular, such a cutset will leave a remaining graph of width bounded by 
according to that particular order of the variables.
The algorithm for finding such a cutset proceed by mimicking the procedure for finding the induced graph of a problem according to the considered order of the variables (this procedure proceeds from the last node in the ordering to the first, adding an edge between every pair of unconnected parents of every node). Whenever this procedure would find or make a node having more than
parents, the node is removed from the graph and added to the cutset. By definition, the resulting graph contains no node of width greater than 
, and the set of removed nodes is therefore a 
-cutset.
An alternative to using this algorithm is to let search evaluate variables, but check at each step whether the remaining graph is a forest, and run inference if this is the case. In other words, instead of finding a set of variables at the beginning and use only them during search, the algorithm starts as a regular search; at each step, if the assigned variables form a
cutset of the problem, inference is run to check satisfiability. This is feasible because checking whether a given set of nodes is a 
cutset for a fixed 
is a polynomial problem.
. In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm.
One such algorithm is based on first propagating constraints among nodes, and then solving the subproblem in each node. This propagation consists in creating new constraints that represent the effects of the constraints in a node over a joined node. More precisely, if two nodes are joined, they share variables. The allowed evaluations of these variables according to the constraints of the first node tell how the first node affects the variables of the second node. The algorithm works by creating the constraint satisfied by these evaluations and incorporating this new constraint in the second node.
When all constraints have been propagated from the leaves to the root and back to the root, all nodes contain all constraints that are relevant to them. The problem can therefore be solved in each node.
A hybrid approach can be taken by using variable elimination for creating the new constraints that are propagated within nodes, and a search algorithm (such as backtracking
, backjumping
, local search
) on each individual node.
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
, a hybrid algorithm solves a constraint satisfaction problem
Constraint satisfaction problem
Constraint satisfaction problems s are mathematical problems 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 constraints over variables, which is solved by constraint...
by the combination of two different methods, for example variable conditioning (backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
, backjumping
Backjumping
In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels...
, etc.) and constraint inference
Constraint inference
In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints D entails a constraint C if every solution to D is also a solution to C...
(arc consistency, variable elimination, etc.)
Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve. For example, search is efficient when the problem has many solutions, while inference is efficient in proving unsatisfiability of overconstrained problems.
Cycle cutset inference/search algorithm
This hybrid algorithm is based on running search over a set of variables and inference over the other ones. In particular, backtracking or some other form of search is run over a number of variables; whenever a consistent partial assignment over these variable is found, inference is run over the remaining variables to check whether this partial assignment can be extended to form a solution.On some kinds of problems, efficient and complete inference algorithms exist. For example, problems whose primal or dual graphs are trees or forests can be solved in polynomial time. This affect the choice of the variables evaluated by search. Indeed, once a variable is evaluated, it can effectively removed from the graph, restricting all constraints it is involved with its value. Alternatively, an evaluated variable can be replaced by a number of distinct variables, one for each constraint, all having a single-value domain.
This mixed algorithm is efficient if the search variables are chosen so that duplicating or deleting them turns the problem into one that can be efficiently solved by inference. In particular, if these variables form a cycle cutset of the graph of the problem, inference is efficient because it has to solve a problem whose graph is a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
or, more generally, a forest. Such an algorithm is as follows:
find a cycle cutset of the graph of the problem
run search on the variables of the cutset
when a consistent partial assignment to all variables are found,
replace each variable of the cutset with a new variable for each constraint;
set the domains of these new variables to the value of the old variable in the partial assignment
solve the problem using inference
The efficiency of this algorithm depends on two contrasting factors. On the one hand, the smaller the cutset, the smaller the subproblem to be soilved by search; since inference is efficient on trees, search is the part that mostly affects efficiency. On the other hand, finding a minimal-size cutset is a hard problem. As a result, a small cycle cutset may be used instead of a minimal one.
Another alternative to reduce the running time of search is to place more burden on the inference part. In particular, inference can be relatively efficient even if the problem graph is not a forest but a graph of small induced width. This can be exploited by doing search on a set of variables that is not a cycle cutset but leaves the problem, once removed, to be have induced width bounded by some value
. Such set of variables is called a -cutset of the problem.The induced width of a graph after a set of variables is removed is called adjusted induced width. Therefore, the induced width adjusted relative to a
cutset is always . Finding a minimal-size -cutset is in general hard. However, a -cutset of non-minimal size can be found easily for a fixed order of the variables. In particular, such a cutset will leave a remaining graph of width bounded by according to that particular order of the variables.The algorithm for finding such a cutset proceed by mimicking the procedure for finding the induced graph of a problem according to the considered order of the variables (this procedure proceeds from the last node in the ordering to the first, adding an edge between every pair of unconnected parents of every node). Whenever this procedure would find or make a node having more than
parents, the node is removed from the graph and added to the cutset. By definition, the resulting graph contains no node of width greater than , and the set of removed nodes is therefore a -cutset.An alternative to using this algorithm is to let search evaluate variables, but check at each step whether the remaining graph is a forest, and run inference if this is the case. In other words, instead of finding a set of variables at the beginning and use only them during search, the algorithm starts as a regular search; at each step, if the assigned variables form a
cutset of the problem, inference is run to check satisfiability. This is feasible because checking whether a given set of nodes is a cutset for a fixed is a polynomial problem.Tree decomposition hybrid algorithm
Another hybrid search/inference algorithm works on the tree decompositionConstraint satisfaction dual problem
The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such problems...
. In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm.
One such algorithm is based on first propagating constraints among nodes, and then solving the subproblem in each node. This propagation consists in creating new constraints that represent the effects of the constraints in a node over a joined node. More precisely, if two nodes are joined, they share variables. The allowed evaluations of these variables according to the constraints of the first node tell how the first node affects the variables of the second node. The algorithm works by creating the constraint satisfied by these evaluations and incorporating this new constraint in the second node.
When all constraints have been propagated from the leaves to the root and back to the root, all nodes contain all constraints that are relevant to them. The problem can therefore be solved in each node.
A hybrid approach can be taken by using variable elimination for creating the new constraints that are propagated within nodes, and a search algorithm (such as backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
, backjumping
Backjumping
In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels...
, local search
Local search (constraint satisfaction)
In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an...
) on each individual node.