Is a relaxed solution always feasible in the original problem?

No. It may exploit exactly the restrictions that were removed.

Is every simplified problem a relaxation?

No. Simplification must preserve the required relationship between feasible solutions and costs to support the stated bound.

Does a lower bound prove a proposed plan is optimal?

Only if a feasible plan matches that bound, or another valid argument closes the remaining gap.

AI Glossary / Graphs and symbolic AI / Intermediate

Relaxed problem

Definition

A relaxed problem is a version of an original problem in which selected constraints are removed or weakened. Every original solution should remain possible in the relaxation, although additional solutions may become available. For a minimization problem with corresponding costs, the optimal relaxed cost can provide a lower bound on the original optimum.

What it means

Imagine estimating the shortest walking route while temporarily ignoring walls. The resulting distance may be unrealistically short, but it can still tell you that the real route cannot be shorter. The simplification is useful because it answers a limited question cheaply.

In AI search and planning, relaxed problems often help construct heuristic estimates. A planner can use such an estimate to decide which states appear promising while still enforcing the original rules when producing a usable plan. Solving the easier model is therefore part of solving the real problem, not permission to ignore its constraints during execution.

How it works

Identify which restrictions make the original problem difficult, then define a relaxation that preserves its solutions and does not increase their costs. Solve the relaxed problem optimally when practical, or derive an appropriate bound from it.

In classical planning, one relaxation ignores actions' delete effects: facts already achieved are not lost. Another may remove selected preconditions. The exact transformation matters, because different relaxations retain different amounts of useful structure.

Use the resulting estimate with a search algorithm whose requirements are understood. The optimal relaxed cost is a lower bound under the stated relationship between the models. The cost of an arbitrary, nonoptimal relaxed solution does not inherit that guarantee automatically. Computing an optimal delete-relaxed plan can itself be computationally difficult.

Three practical examples

Route search: ignore obstacles to obtain a distance estimate, then search the actual map using the real movement restrictions.
Task planning: ignore conflicts caused by actions undoing earlier achievements to estimate how much work remains before all goals are reached.
Scheduling analysis: temporarily remove a shared-resource constraint to obtain an optimistic completion bound, then compare it with schedules that respect the resource limit.

Think of it this way

Think of checking how quickly a building project could finish if a scarce tool were always available. This gives an optimistic benchmark against which actual schedules can be compared. The analogy assumes the simplified model retains the real tasks and comparable durations; changing the objective or adding new restrictions would require a different argument about the bound.

Worked example

Consider a fictional delivery planner. A robot starts at depot D, and must visit locations A and B before finishing anywhere. Traveling from D to either location costs 1. Traveling between A and B requires going through D and costs 2. Marking a location as visited costs nothing.

In the original model, the robot has exactly one current location. The shortest plan is D to A to D to B, or the reverse, with total travel cost 3.

Now apply a delete relaxation to the location facts. Traveling from D to A adds AtA but does not remove AtD. The relaxed planner can then use the still-available AtD fact to travel directly from D to B. It pays 1 + 1 = 2 and has visited both destinations. The relaxed state incorrectly represents the robot as being in several places, which is allowed only inside this estimate.

The relaxed cost 2 is a valid lower bound on the original cost 3. Its two travel actions do not form an executable physical route because the second action assumes the robot is still at D.

Suppose a careless relaxed solver instead returns a redundant relaxed plan costing 4. That cost exceeds the original optimum of 3. Merely calling a plan “relaxed” therefore does not make its returned cost an admissible heuristic; optimality or another valid lower-bound construction matters.

Illustrative case study

Fictional case: Birch Planning Workshop teaches warehouse routing with a small simulator. Students first compute estimates that let a robot retain every location it has reached.

One student mistakes the relaxed action sequence for a dispatch plan. Forward validation against the original state-transition rules exposes an action whose departure location is wrong. The class keeps the relaxed model for estimating remaining effort and uses the real model for candidate route validation.

The exercise separates an optimistic calculation from an operational instruction. A real warehouse model also needs realistic travel, capacity, and scheduling constraints.

Common misconceptions and mistakes

Removing constraints does not always make a problem trivial. A relaxation can remain expensive to solve, and time spent obtaining a stronger estimate may outweigh the search it saves.

A lower bound is not a forecast of actual completion time. The gap can be large when the removed constraints dominate the real task.

Do not assume all relaxation-based heuristics are admissible. Practical methods sometimes trade a guaranteed lower bound for speed or guidance. Their use may be appropriate, but any optimality claim must match the heuristic and search procedure actually used.

Business use

Relaxed models can support planning systems and explain why a proposed target is optimistic. They are particularly useful when teams need a benchmark for assessing schedules or routes rather than an unsupported claim that a plan is optimal.

Record relaxed constraints, the objective, and whether the calculation produced an optimum, a lower bound, or a candidate solution. Compare computation time and search effort together. A stronger heuristic is valuable only if its benefits justify the work needed to compute it for the relevant workload.

Check your understanding

An original feasible plan costs 12 and a valid relaxed lower bound is 9. Is the plan necessarily optimal?

Answer: No. The original optimum lies between 9 and 12, inclusive. A feasible plan costing 9 would close the gap, but the bound alone does not rule out costs 10 or 11.

Related terms

Learn next

Create a tiny route problem and remove one restriction. Check that every original route remains allowed, calculate both optima, and identify why the relaxed solution may be infeasible. Then study admissibility and the distinction between an optimal relaxed plan and a quickly extracted relaxed plan.

Sources

Russell and Norvig, Planning chapter: https://aima.cs.berkeley.edu/newchap11.pdf Hoffmann, Where Ignoring Delete Lists Works: https://arxiv.org/abs/1109.5713 Primary planning material and research abstract were read. Numerical examples and case are original.

Previous: Relaxation labeling Next: Relaxed sequential