Min-conflicts algorithm

Last updated

In computer science, a min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems.

Contents

One such algorithm is min-conflicts hill-climbing. [1] Given an initial assignment of values to all the variables of a constraint satisfaction problem (with one or more constraints not satisfied), select a variable from the set of variables with conflicts violating one or more of its constraints. Assign to this variable a value that minimizes the number of conflicts (usually breaking ties randomly). Repeat this process of conflicted variable selection and min-conflict value assignment until a solution is found or a pre-selected maximum number of iterations is reached. If a solution is not found the algorithm can be restarted with a different initial assignment.

Because a constraint satisfaction problem can be interpreted as a local search problem when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair heuristic [2] that chooses the state with the minimum number of conflicts.

Algorithm

algorithm MIN-CONFLICTS isinput: console.csp, A constraint satisfaction problem.            max_steps, The number of steps allowed before giving up.            current_state, An initial assignment of values for the variables in the csp.     output: A solution set of values for the variable orfailure.      for i ← 1 to max_steps doifcurrent_state is a solution of cspthenreturncurrent_statesetvar ← a randomly chosen variable from the set of conflicted variables CONFLICTED[csp]         setvalue ← the value v for var that minimizes CONFLICTS(var,v,current_state,csp)         setvar ← value in current_statereturnfailure

Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a greedy algorithm with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. Map coloring problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known.

History

Although Artificial Intelligence and Discrete Optimization had known and reasoned about Constraint Satisfaction Problems for many years, it was not until the early 1990s that this process for solving large CSPs had been codified in algorithmic form. Early on, Mark Johnston of the Space Telescope Science Institute looked for a method to schedule astronomical observations on the Hubble Space Telescope. In collaboration with Hans-Martin Adorf of the Space Telescope European Coordinating Facility, he created a neural network capable of solving a toy n-queens problem (for 1024 queens). [3] [4] Steven Minton and Andy Philips analyzed the neural network algorithm and separated it into two phases: (1) an initial assignment using a greedy algorithm and (2) a conflict minimization phases (later to be called "min-conflicts"). A paper was written and presented at AAAI-90; Philip Laird provided the mathematical analysis of the algorithm.

Subsequently, Mark Johnston and the STScI staff used min-conflicts to schedule astronomers' observation time on the Hubble Space Telescope.

Example

Animation of min-conflicts resolution of 8-queens. First stage assigns columns greedily minimizing conflicts, then solves 8queensminconflict.gif
Animation of min-conflicts resolution of 8-queens. First stage assigns columns greedily minimizing conflicts, then solves

Min-Conflicts solves the N-Queens Problem by selecting a column from the chess board for queen reassignment. The algorithm searches each potential move for the number of conflicts (number of attacking queens), shown in each square. The algorithm moves the queen to the square with the minimum number of conflicts, breaking ties randomly. Note that the number of conflicts is generated by each new direction that a queen can attack from. If two queens would attack from the same direction (row, or diagonal) then the conflict is only counted once. Also note that if a queen is in a position in which a move would put it in greater conflict than its current position, it does not make a move. It follows that if a queen is in a state of minimum conflict, it does not have to move.

This algorithm's performance depends greatly on the choice of starting position. A good starting position can be generated by assigning queens column by column with each assignment being to a row that minimizes the number of constraint violations. This results in a starting position with an average number of constraint violations that is surprisingly small and grows very slowly with n (e.g. 12.8 for n=106).

Given a good starting position, the number of reassignments required for a solution is similarly constant: this algorithm will even solve the million-queens problem in approximately 50 reassignments. The number of constraint evaluations for each reassignment grows with n leading to nearly linear run-time.

This discovery and observations led to a great amount of research in 1990 and began research on local search problems and the distinctions between easy and hard problems. N-Queens is easy for local search because solutions are densely distributed throughout the state space. It is also effective for hard problems. For example, it has been used to schedule observations for the Hubble Space Telescope, reducing the time taken to schedule a week of observations from three weeks to around 10 minutes. [5]

See also

Related Research Articles

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.

<span class="mw-page-title-main">Search algorithm</span> Any algorithm which solves the search problem

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

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.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

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.

In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems.

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.

<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

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.

<span class="mw-page-title-main">Linear programming relaxation</span>

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

Guided local search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behavior.

The constraint composite graph is a node-weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli, the idea of the constraint composite graph is a big step towards unifying different approaches for exploiting "structure" in weighted constraint satisfaction problems.

In artificial intelligence and operations research, a Weighted Constraint Satisfaction Problem (WCSP), also known as Valued Constraint Satisfaction Problem (VCSP), 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.

In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables A and B in a CSP may be swapped for each other without changing the nature of the problem or its solutions, then A and B are interchangeable variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with A=1 and B=2 have been tried, then by interchange symmetry, solutions with B=1 and A=2 need not be investigated.

The Boolean satisfiability problem can be stated formally as: given a Boolean expression with variables, finding an assignment of the variables such that is true. It is seen as the canonical NP-complete problem. While no efficient algorithm is known to solve this problem in the general case, there are certain heuristics, informally called 'rules of thumb' in programming, that can usually help solve the problem reasonably efficiently.

References

  1. ↑ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1990). "Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method" (PDF). Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, Massachusetts: 17–24. Retrieved 27 March 2013.
  2. ↑ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1992). "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems" (PDF). Artificial Intelligence. 58 (1): 161–205. CiteSeerX   10.1.1.308.6637 . doi:10.1016/0004-3702(92)90007-k. S2CID   14830518 . Retrieved 27 March 2013.
  3. ↑ Johnston, M. D.; Adorf, H.-M. (1989). "Learning in Stochastic Neural Networks for Constraint Satisfaction Problems". NASA Conf. On Space Telerobotics 1989, Pasadena, CA; G. Rodriguez, H. Seraji (Eds.): 367–376 vol.II.
  4. ↑ Adorf, H.-M.; Johnston, M. D. (1990). "A discrete stochastic neural network algorithm for constraint satisfaction problems". 1990 IJCNN International Joint Conference on Neural Networks. pp. 917–924 vol.3. doi:10.1109/IJCNN.1990.137951. S2CID   26917432.
  5. ↑ Stuart Russell, Peter Norvig, “Artificial Intelligence: A Modern Approach (3rd Edition)”, pp. 220-222, December 11, 2009.
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.