### What is a relaxation?

To "relax" a problem is to remove some of the constraints of the
problem, hopefully making the problem easier. The set of feasible
solutions to the relaxed problem includes all feasible solutions to
the original problem (and the cost functions of the two problems agree
on these feasible solutions).

For example, relaxing an IntegerLinearProgram by removing the
integrality constraints yields a LinearProgram .

#### Example: min-cost fractional vertex cover (a relaxation of min-cost vertex cover)

- Minimize ∑
_{v} c(v) x(v) subject to:
- x(v) ≥ 0 for each vertex v ∈ V.
- x(u)+x(v) ≥ 1 for each edge (u,v) ∈ E.

### What is the point?

The cost of the optimal solution to the relaxed solution is a lower
bound on the cost of the optimal solution to the original problem,
because the optimal solution to the original problem is a feasible
solution to the relaxed problem.