Look-ahead (backtracking)

Last updated October 14, 2023

In backtracking algorithms, look ahead is the generic term for a subprocedure that attempts to foresee the effects of choosing a branching variable to evaluate one of its values. The two main aims of look-ahead are to choose a variable to evaluate next and to choose the order of values to assign to it.

Constraint satisfaction

In a general constraint satisfaction problem, every variable can take a value in a domain. A backtracking algorithm therefore iteratively chooses a variable and tests each of its possible values; for each value the algorithm is recursively run. Look ahead is used to check the effects of choosing a given variable to evaluate or to decide the order of values to give to it.

Look ahead techniques

In this example, x1=2 and the tentative assignment x2=1 is considered. Forward-arc-0.svg — In this example, x₁=2 and the tentative assignment x₂=1 is considered.

Forward checking only checks whether each of the unassigned variables x3 and x4 is consistent with the partial assignment, removing the value 2 from their domains. Forward-arc-1.svg — Forward checking only checks whether each of the unassigned variables x₃ and x₄ is consistent with the partial assignment, removing the value 2 from their domains.

The simpler technique for evaluating the effect of a specific assignment to a variable is called forward checking.^[1] Given the current partial solution and a candidate assignment to evaluate, it checks whether another variable can take a consistent value. In other words, it first extends the current partial solution with the tentative value for the considered variable; it then considers every other variable $x_{k}$ that is still unassigned, and checks whether there exists an evaluation of $x_{k}$ that is consistent with the extended partial solution. More generally, forward checking determines the values for $x_{k}$ that are consistent with the extended assignment.

Arc consistency look ahead also checks whether the values of x3 and x4 are consistent with each other (red lines) removing also the value 1 from their domains. Forward-arc-2.svg — Arc consistency look ahead also checks whether the values of x₃ and x₄ are consistent with each other (red lines) removing also the value 1 from their domains.

A look-ahead technique that may be more time-consuming but may produce better results is based on arc consistency. Namely, given a partial solution extended with a value for a new variable, it enforces arc consistency for all unassigned variables. In other words, for any unassigned variables, the values that cannot consistently be extended to another variable are removed. The difference between forward checking and arc consistency is that the former only checks a single unassigned variable at time for consistency, while the second also checks pairs of unassigned variables for mutual consistency. The most common way of using look-ahead for solving constraint satisfaction problems is the maintaining arc-consistency (MAC) algorithm.^[2]

Two other methods involving arc consistency are full and partial look ahead. They enforce arc consistency, but not for every pair of variables. In particular, full look considers every pair of unassigned variables $x_{i},x_{j}$ , and enforces arc consistency between them. This is different than enforcing global arc consistency, which may possibly require a pair of variables to be reconsidered more than once. Instead, once full look ahead has enforced arc consistency between a pair of variables, the pair is not considered any more. Partial look ahead is similar, but a given order of variables is considered, and arc consistency is only enforced once for every pair $x_{i},x_{j}$ with $i<j$ .

Look ahead based on arc consistency can also be extended to work with path consistency and general i-consistency or relational arc consistency.

Use of look ahead

The results of look ahead are used to decide the next variable to evaluate and the order of values to give to this variable. In particular, for any unassigned variable and value, look-ahead estimates the effects of setting that variable to that value.

The choice of the next variable and the choice of the next value to give it are complementary, in that the value is typically chosen in such a way that a solution (if any) is found as quickly as possible, while the next variable is typically chosen in such a way unsatisfiability (if the current partial solution is unsatisfiable) is proven as quickly as possible.

The choice of the next variable to evaluate is particularly important, as it may produce exponential differences in running time. In order to prove unsatisfiability as quickly as possible, variables leaving few alternatives after being assigned are the preferred ones. This idea can be implemented by checking only satisfiability or unsatisfiability of variable/value pairs. In particular, the next variable that is chosen is the one having a minimal number of values that are consistent with the current partial solution. In turn, consistency can be evaluated by simply checking partial consistency, or by using any of the considered look ahead techniques discussed above.

The following are three methods for ordering the values to tentatively assign to a variable:

min-conflicts: the preferred values are those removing the least total values from the domain of unassigned variables as evaluated by look ahead;
max-domain-size: the preferred values are those maximising the number of values in the smallest domain they produce for the unassigned variables, as evaluated by look ahead;
estimate solutions: the preferred values are those producing the maximal number of solutions, as evaluated by look ahead making the assumption that all values left in the domains of unassigned variables are consistent with each other; in other words, the preference for a value is obtained by multiplying the size of all domains resulting from look ahead.

Experiments proved that these techniques are useful for large problems, especially the min-conflicts one.^{[ citation needed ]}

Randomization is also sometimes used for choosing a variable or value. For example, if two variables are equally preferred according to some measure, the choice can be done randomly.

Related Research Articles

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem-specific branching heuristic.

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 constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region.

In constraint satisfaction, the AC-3 algorithm is one of a series of algorithms used for the solution of constraint satisfaction problems. It was developed by Alan Mackworth in 1977. The earlier AC algorithms are often considered too inefficient, and many of the later ones are difficult to implement, and so AC-3 is the one most often taught and used in very simple constraint solvers.

<span class="mw-page-title-main">Hidden transformation</span>

The hidden transformation reformulates a constraint satisfaction problem in such a way all constraints have at most two variables. The new problem is satisfiable if and only if the original problem was, and solutions can be converted easily from one problem to the other.

In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency.

<span class="mw-page-title-main">Backmarking</span>

In constraint satisfaction, backmarking is a variant of the backtracking algorithm.

<span class="mw-page-title-main">Backjumping</span> In backtracking algorithms, technique that reduces search space

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. In this article, a fixed order of evaluation of variables $is used, but the same considerations apply to a dynamic order of evaluation.$

In constraint satisfaction backtracking algorithms, constraint learning is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the search space, as future partial evaluations may be found inconsistent without further search. Clause learning is the name of this technique when applied to propositional satisfiability.

<span class="mw-page-title-main">Local search (constraint satisfaction)</span>

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 assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.

In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combination of two different methods, for example variable conditioning and constraint inference

Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is A(X,Y):-X+Y>0,B(X),C(Y). In this clause, X+Y>0 is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.

Distributed constraint optimization is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.

The complexity of constraint satisfaction is the application of computational complexity theory to constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains.

In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem.

In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem. On input a formula over Boolean variables, such as "(x or y) and (x or not y)", a SAT solver outputs whether the formula is satisfiable, meaning that there are possible values of x and y which make the formula true, or unsatisfiable, meaning that there are no such values of x and y. In this case, the formula is satisfiable when x is true, so the solver should return "satisfiable". Since the introduction of algorithms for SAT in the 1960s, modern SAT solvers have grown into complex software artifacts involving a large number of heuristics and program optimizations to work efficiently.

In artificial intelligence and operations research, a Weighted Constraint Satisfaction Problem (WCSP) is a generalization of a constraint satisfaction problem (CSP) where some of the constraints can be violated and in which preferences among solutions can be expressed. This generalization makes it possible to represent more real-world problems, in particular those that are over-constrained, or those where we want to find a minimal-cost solution among multiple possible solutions.

References

↑ R.M. Haralick and G.L. Elliott (1980), "Increasing tree search efficiency for constraint satisfaction problems". Artificial Intelligence , 14, pp. 263–313.
↑ Sabin, Daniel and Eugene C. Freuder (1994), “Contradicting Conventional Wisdom in Constraint Satisfaction.” Principles and Practice of Constraint Programming, pp. 10-20.

Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7
Ouyang, Ming (1998). "How Good Are Branching Rules in DPLL?". Discrete Applied Mathematics . 89 (1–3): 281–286. doi: 10.1016/S0166-218X(98)00045-6 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] R.M. Haralick and G.L. Elliott (1980), "Increasing tree search efficiency for constraint satisfaction problems". Artificial Intelligence , 14, pp. 263–313.

[2] Sabin, Daniel and Eugene C. Freuder (1994), “Contradicting Conventional Wisdom in Constraint Satisfaction.” Principles and Practice of Constraint Programming, pp. 10-20.

[1]

[2]