Does a large search space require checking every candidate?

No. Constraints, bounds, and structure can exclude many candidates without explicit enumeration.

Is local search always complete?

No. A method that explores only part of the space may miss existing solutions.

What makes the worked optimum certain?

The constraints leave exactly two feasible assignments, and both costs have been evaluated.

AI Glossary / Graphs and symbolic AI / Intermediate

Combinatorial search

Definition

Combinatorial search explores combinations of discrete choices to find a solution satisfying constraints or optimizing an objective. The candidates may be assignments, subsets, routes, sequences, or other finite structures. Its main challenge is that individually simple choices can combine into an enormous search space, making the organization and pruning of the search important.

What it means

Consider assigning tasks to workers. Each assignment decision may have only a few options, but a complete arrangement combines all of them. Some arrangements are invalid, and valid ones can have different costs. A search procedure must distinguish those possibilities without necessarily constructing every complete arrangement.
The term covers a broad area rather than one algorithm. Backtracking, branch and bound, heuristic state-space search, constraint programming, and local-search methods can all address combinatorial problems. The appropriate method depends on the problem's structure, required guarantees, and available resources. Combinatorial does not by itself establish a particular complexity class.

How it works

Specify the decision variables, their possible values, the constraints, and any objective. Choose a representation of partial or complete candidates. A systematic search extends partial choices and rejects branches that cannot lead to acceptable solutions. Constraint propagation can rule out values early, while bounds can show that a branch cannot improve the best known objective.
Other methods move among complete candidates, improving a score or escaping local traps. Such methods may find useful solutions without proving optimality or impossibility. The search policy and stopping condition must therefore match the claim reported: feasible, best found, proven optimal, proven infeasible, or unresolved.

Three practical examples

A scheduling system searches for assignments of jobs to machines while respecting conflicts and capacity limits.
A routing model searches among possible visit orders to reduce a stated travel cost.
A product configuration tool searches among component combinations that satisfy compatibility and requirement rules.

Think of it this way

Think of assembling a meal from several menus while respecting dietary requirements and a budget. Each individual choice is simple, but choices interact: selecting one item can rule out another or consume the remaining budget. The analogy is limited because a formal search requires precise constraints and costs, whereas everyday preferences may be incomplete or change during the decision.

Worked example

Suppose three tasks, A, B, and C, must each be assigned to either worker X or worker Y. Ignoring constraints, there are 2 cubed, or 8, complete assignments. Require A and B to use different workers, and C to use the same worker as A.
The only feasible assignments are A = X, B = Y, C = X and A = Y, B = X, C = Y. Let assignment costs be A: X costs 2 and Y costs 5; B: X costs 1 and Y costs 4; C: X costs 3 and Y costs 2. The first feasible assignment costs 2 + 4 + 3 = 9. The second costs 5 + 1 + 2 = 8, so the second is optimal in this model.
A search need not inspect all eight completed assignments. Once A is chosen, the constraints force B to the other worker and C to A's worker. That leaves only the two feasible branches to compare. This is an exact reduction from the constraints, not an assumption that unexamined candidates are probably poor.

Illustrative case study

At fictional Linden Scheduling, an assistant proposes a plausible assignment for a small work queue. The team separates generating a candidate from validating its constraints and comparing its cost. A search-based checker finds another feasible arrangement with lower modeled cost.
The team reports the objective and the constraints behind that comparison, rather than calling the alternative universally better. This fictional case illustrates combining proposal generation with explicit search and validation. It does not claim a measured production benefit or that the simplified cost captures every operational preference.

Common misconceptions and mistakes

Combinatorial search is not synonymous with brute force. A major purpose of the field is to exploit structure and avoid unnecessary enumeration. Conversely, applying a heuristic does not automatically preserve completeness or optimality.
The number of candidates is not always a simple power: permutations, subsets, repeated choices, and constraints produce different counts. Another mistake is to prune a branch using an estimate that is not a valid bound while still claiming exact optimality. A failed search within a time limit also does not establish that no solution exists. Finally, the best modeled result may be undesirable if important constraints or costs were omitted.

Business use

Businesses should define what constitutes an acceptable answer before selecting a search method. Some tasks need a good feasible solution quickly; others require evidence that a requirement cannot be met or that no cheaper option exists. Preserve the best solution and any valid bound when an optimization search stops. This communicates the remaining uncertainty more usefully than a single quality label and makes later improvements comparable under the same model.

Check your understanding

Why are there only two feasible assignments in the example despite eight unconstrained combinations?

Answer: Choosing A forces B to the other worker and C to the same worker. Only the initial choice for A remains free.

Related terms

Heuristic search
Local search
Search space
combinatorial optimization
backtracking
branch and bound
constraint programming
feasibility
optimality gap

Learn next

Learn branch and bound next. Add a fourth task to the example and derive a lower bound for a partial assignment. Explain why the bound is safe before using it to discard a branch.

Partial assignment

Sources

Primary sources: Neng-Fa Zhou, Combinatorial Search With Picat, https://arxiv.org/abs/1405.2538 ; Pietracaprina and colleagues, Space-Efficient Parallel Algorithms for Combinatorial Search Problems, https://arxiv.org/abs/1306.2552 ; original AIMA constraint-satisfaction slides, https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter05.pdf . The assignment calculation and fictional case are original illustrations.

Previous: Combinatorial explosion Next: Combinatorics