Min-Conflicts Heuristic

Unlike constructive search methods like backtracking, Min-Conflicts operates via iterative repair. It starts with a complete assignment of values to all variables, which may violate many constraints. The algorithm then iteratively selects a conflicted variable and changes its value to reduce the total number of constraint violations, gradually 'repairing' the assignment until a solution (zero conflicts) is found or a limit is reached.

The core of the heuristic is in its name. When a conflicted variable is chosen, it evaluates all values in its domain. It selects the value that results in the minimum number of conflicts with the current values of neighboring variables. This is a greedy, local optimization step. Ties are typically broken randomly, which introduces stochasticity that helps escape local minima.

• Example: In a university timetabling CSP, if a 'Physics 101' class is conflicting with two others, the algorithm will try moving it to a time slot that conflicts with the fewest (ideally zero) other already-scheduled classes.

Min-Conflicts is a form of stochastic hill climbing in the state space defined by complete assignments, where the 'height' is inversely related to the number of conflicts. The random tie-breaking and occasional random walks (in some variants) allow it to escape shallow local minima—states where any single-variable change increases conflicts, but a solution requires a temporary increase. This makes it more robust than pure greedy descent.

Min-Conflicts is an incomplete algorithm; it cannot prove that a CSP is unsatisfiable. If it fails to find a solution after a given number of steps, it may simply restart. This trade-off is why it excels on large, satisfiable problems like the N-Queens puzzle or frequency assignment, where it often finds solutions in linear time (O(n)) compared to the exponential worst-case time of complete backtracking search. Its efficiency comes from focusing computational effort only on the conflicted parts of the assignment.

The heuristic performs best on CSPs where:

• Solutions are densely distributed in the search space.
• The constraint graph is not overly tight.
• The initial random assignment is reasonably good.

It is less effective for problems with very few solutions or highly structured, 'needle-in-a-haystack' constraints. Performance is also sensitive to the choice of conflicted variable; common strategies include picking a random conflicted variable or the variable involved in the most conflicts.

Min-Conflicts is a cornerstone of local search for CSPs. It is often combined with:

• Random Restarts: To reset from a stuck state.
• Constraint Weighting: Making the cost of violating a 'difficult' constraint higher, guiding the search.
• Tabu Search: Maintaining a short-term memory of recent changes to avoid cycles.

It contrasts with systematic methods like Backtracking with MAC, which are complete but slower, and complements variable-ordering heuristics like MRV used in constructive search.

A Constraint Satisfaction Problem (CSP) is the formal framework for which Min-Conflicts is a solving strategy. It is defined by:

• A set of variables {X₁, X₂, ..., Xₙ}.
• A domain for each variable, listing its possible values.
• A set of constraints that specify allowable or forbidden combinations of values for subsets of variables.

The goal is to find an assignment of a value to each variable that satisfies all constraints. Classic examples include the N-Queens problem, graph coloring, and scheduling.

Local search is a family of incomplete algorithms to which Min-Conflicts belongs. Unlike systematic backtracking, local search:

• Starts with a complete assignment (all variables have a value) that may violate constraints.
• Iteratively makes small, local changes to reduce the number of conflicts.
• Uses a heuristic, like Min-Conflicts, to select the best change.

It is highly effective for large, dense CSPs where finding any feasible solution is the priority, and is the basis for algorithms like hill climbing and simulated annealing in this domain.

Hill climbing is a fundamental local search optimization algorithm closely related to Min-Conflicts. Its process is:

1. Start with a random candidate solution.
2. Evaluate its neighbors (solutions reachable by a small change).
3. Move to the neighbor with the best improvement in the objective function.
4. Repeat until no better neighbor exists.

Min-Conflicts is a specialized form of hill climbing for CSPs, where the 'height' to climb is the inverse of the number of constraint violations. Its key innovation is the heuristic for choosing which variable to change and to what value.

A Constraint Optimization Problem (COP) extends a CSP by adding an objective function to maximize or minimize. The goal is no longer just any feasible solution, but the optimal one.

• Example: In vehicle routing, a CSP finds a route that meets delivery windows. A COP finds the route that meets windows and minimizes total distance or fuel cost.

While Min-Conflicts finds feasible solutions, it can be integrated into larger frameworks like large neighborhood search to iteratively improve solutions for COPs, balancing constraint satisfaction with objective quality.

The Boolean Satisfiability Problem (SAT) is a canonical NP-complete problem and a specific type of CSP where:

• Variables are Boolean (True/False).
• Constraints are clauses (disjunctions of literals, e.g., (A OR NOT B)).

The GSAT algorithm is a direct analog of Min-Conflicts for SAT problems. It starts with a random truth assignment and iteratively flips the variable that results in the greatest increase in the number of satisfied clauses. This highlights Min-Conflicts' role within the broader ecosystem of stochastic local search for combinatorial problems.

Heuristic search algorithms use problem-specific rules of thumb to guide exploration efficiently. Min-Conflicts is a local search heuristic. Other critical heuristics in systematic CSP search include:

• Minimum Remaining Values (MRV): Choose the variable with the fewest legal values left (fail-first).
• Least Constraining Value (LCV): Given a variable, assign the value that rules out the fewest choices for neighboring variables.

These variable and value ordering heuristics are used in backtracking and maintaining arc consistency (MAC) algorithms, representing the systematic counterpart to Min-Conflicts' stochastic, repair-based approach.