Can an exact method use pruning?

Yes, when the pruning rules preserve correctness.

Can there be several exact answers?

Several feasible solutions may tie for the optimal objective value.

Does exactness guarantee a good real-world decision?

No. The inputs, constraints, and objective still need validation.

AI Glossary / Mathematics and optimization / Advanced

Exact algorithm

Definition

An exact algorithm is an algorithm that solves the specified problem correctly rather than returning an approximation. In combinatorial optimization, the term usually emphasizes that it finds a globally optimal feasible solution, or correctly establishes that no feasible solution exists. The guarantee depends on the problem's assumptions and completing the algorithm correctly; a promising intermediate solution alone does not establish optimality.

What it means

Suppose a planner must select projects within a fixed budget. Finding an affordable selection is one task. Showing that no other affordable selection has greater modeled value is another. An exact optimization method addresses both.

Exactness concerns the mathematical problem supplied to the algorithm. It does not establish that project values are accurate, that the budget captures every operational restriction, or that the chosen objective represents all stakeholder preferences. A perfectly solved model can still describe the real decision poorly.

How it works

A simple exact method examines every possible candidate, rejects infeasible ones, and selects the best remaining candidate. More sophisticated methods can avoid much of that work without sacrificing correctness.

For example, dynamic programming can combine optimal solutions to appropriately defined subproblems. Branch-and-bound can discard a search region when a valid bound proves that it cannot improve the best known solution. Such reductions need a sound argument: skipping candidates merely because they look unpromising would not preserve the guarantee.

Exact algorithms can be efficient for some problem classes and costly for others. Exactness does not itself specify running time. In implementation, numerical reliability is also a separate concern; an exact mathematical search strategy does not automatically eliminate floating-point rounding effects.

Three practical examples

1. Project selection: A small portfolio has three candidate projects. Checking all eight subsets is practical and establishes the best affordable combination.

2. Staff assignment: A planner models which worker can perform which job and defines the total cost. An exact assignment method can optimize that model. Omitting a required qualification from the constraints remains a modeling error, even if the solver returns the true mathematical optimum.

3. Route planning: A team compares a quickly found route with a proven optimum on small benchmark instances. The exact results reveal how far the faster method falls short on those instances. They do not prove that the faster method has the same performance on every larger network.

Think of it this way

Think of choosing the cheapest eligible offer from a complete, correctly specified set. An exact method must either examine the relevant alternatives or provide a valid reason why excluded alternatives cannot win. Finding an attractive offer early is useful, but it does not settle whether a better eligible offer remains.

Worked example

Consider an original project-selection problem with capacity eight. Project A consumes six units and gives value 30. B consumes four and gives 19. C also consumes four and gives 19. Each project can be selected at most once, and values add.

There are eight subsets. The empty set has zero capacity and value. A uses six and gives 30. B and C each use four and give 19. AB and AC each use ten and give 49, so both are infeasible. BC uses eight and gives 38. ABC uses fourteen and gives 68, so it is infeasible.

The best feasible subset is therefore BC, with value 38. The complete enumeration proves optimality for this model.

A value-per-capacity greedy rule would prefer A, whose ratio is 30/6 = 5, over B and C, whose ratios are 19/4 = 4.75. After selecting A, only two capacity units remain, so neither other project fits. The rule returns value 30, eight below the optimum. This single counterexample shows that this greedy rule is not an exact algorithm for the general problem.

A dynamic program reaches the same optimum by considering inclusion and exclusion of each project. With D(i,c) denoting the best value from the first i projects at capacity c, the final comparison at capacity eight is max(D(2,8), 19 + D(2,4)) = max(30,38) = 38.

Illustrative case study

In a fictional innovation team, a dashboard recommends project A because it has the highest individual value and value-to-capacity ratio. A reviewer performs the eight-subset check above and identifies BC as the better modeled portfolio.

Before approving BC, the team discovers an omitted dependency: B and C require the same specialist during overlapping work periods and cannot run together. Adding that constraint removes BC from the feasible set. A, with value 30, then becomes the optimum among the remaining feasible subsets.

The earlier calculation was exact for the original model. The revised answer changes because the model changes. The team records both the constraint revision and the new result, avoiding the mistaken conclusion that an optimality guarantee makes requirements validation unnecessary.

Common misconceptions and mistakes

Exact does not mean fast, and it does not necessarily mean exhaustive enumeration. A locally optimal solution is not automatically globally optimal. A feasible solution returned when a time limit expires should not be labeled proven optimal unless the available evidence establishes that conclusion.

Do not confuse optimization exactness with representing every number exactly. Numerical tolerances and arithmetic choices matter in real solvers. Also avoid claiming that all heuristics are necessarily polynomial-time methods; the essential distinction here is the guarantee being made, rather than a universal runtime classification.

Business use

Exact optimization is useful when proving the best result under a defined model has material value. It can also provide benchmarks for evaluating faster decision rules. Teams should retain the model, input version, termination status, and evidence supporting optimality. If a run stops early, report the best feasible solution and any justified remaining gap instead of silently converting an incomplete search into a completed guarantee.

Check your understanding

Why does the greedy rule fail in the example?

Answer: Selecting A prevents the more valuable feasible combination BC.

What proves BC optimal in the original model?

Answer: Every possible subset has been checked.

Why does adding the shared-specialist constraint change the answer?

Answer: It removes BC from the feasible set.

Related terms

Optimization
Heuristic
Dynamic programming
approximation algorithm
branch-and-bound
optimality gap

Learn next

Rework the example at several capacities, recording both feasibility and value. Then implement the dynamic-programming recurrence and compare its results with full enumeration. Study how valid bounds can reduce search while preserving the same optimality claim.

Dynamic programming

Sources

Max Planck Institute for Informatics, Exponential-Time Algorithms course overview, exact optimal-solution objective: https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/ExpTimeAlgo/

SCIP documentation, numerically exact solving and proof certificates: https://www.scipopt.org/scip/doc/html/EXACT.php

The portfolio example, enumeration, recurrence check, and fictional case are original illustrations.

Previous: Ex ante forecast Next: Exact cell decomposition