The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

Question

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges")

[...][the use of the term "relaxation"] is historical. The outcome of a relaxation step can be viewed as a relaxation of the constraint $d[v] \le d[u] + w(u, v)$, [...]

So, I looked for the general meaning of "constraint relaxation" and found some examples, such as Lagrangian relaxation, but i do not see how Lagrangian relaxation would be relevant to relaxing a single constraint $x_j\le x_i + w_{i,j}$.

Lagrangian relaxation and such modify the problem (making the constraints more "relaxed" in the process), but the relaxation used in the Shortest Path algorithms modifies a tentative solution and does not seem to modify the problem...

What is the general meaning of the "relaxation" used in the Shortest Path Problem?

To be clear, I am asking about the relaxation step described, for example, on pages 276-277 of Algorithms by Jeff Erickson, Chapter 8. Here it is:

Relax(u, v):
    d[v] <- d[u] + w(u, v)
    p[v] <- u

Links:

• Shortest Paths chapter from Algorithms by Jeff Erickson.

• Some blog post where the term is explained.

• Some slides where the term is used.

Answer 1

To my knowledge, the term relaxation is used to indicate that a constraint (or a group of constraints) is removed from the model, rendering a model that is more loose, less constrained.

In the context of Lagrangian relaxation, a constraint (or group of constraints) is removed from the model, and added to the objective function with a coefficient (or more precisely, the right hand term minus the left hand term). The idea is that if this additional term has value $0$ in the objective function, the constraint is satisfied.

The term linear relaxation is also very common. It appears when integrity constraints are removed from the model (variables that have to be discrete can be continuous).

For the shortest path problem, it is the same : one of the constraint that models the shortest path is removed, in some sense. You can model the shortest path problem from $u$ to $v$ in a graph $G=(V,E)$ as follows : $$ \max \; d_v $$ subject to \begin{align} d_j &\le d_i + c_{ij} \quad \forall (i,j) \in E \\ d_u &= 0 \end{align}

In essence, the shortest path from $u$ to $v$, $d_v$, is the largest value that minimizes $d_i+c_{iv}$ for all predecessors $i$ of $v$. The constraint $d_j \le d_i +c_{ij}$ is only active when $d_i$ is the shortest path length to node $i$. When it is not the case, the constraint is inactive and you can relax it from the model. This is what is done dynamically (and not through linear programming) in the slides of the link you have posted.

There is a nice physical interpretation of this. Imagine you have some sort of web with extremities $u$ and $v$. If you stretch $u$ from $v$ as much as possible, the tightest string from $u$ to $v$ is the shortest path from $u$ to $v$. All other strings from $u$ to $v$ are loose or wavy, hence the term "relaxed." This is illustrated in the image below (from Wikipedia) :

Finding the shortest path in a graph using optimal substructure; a straight line indicates a single edge; a wavy line indicates a shortest path between the two vertices it connects (among other paths, not shown, sharing the same two vertices); the bold line is the overall shortest path from start to goal.

For this particular graph, if nodes are named $a$, $b$, $c$ from top to bottom, the above linear formulation yields :

$$ \max \; d_{goal} $$ subject to \begin{align} d_a &\le d_{start}+5 \\ d_b &\le d_{start}+2 \\ d_c &\le d_{start}+11 \\ d_{goal} &\le d_a + 20 \\ d_{goal} &\le d_b + 25 \\ d_{goal} &\le d_c + 17 \\ d_{start} &= 0 \\ \end{align}

Which can easily be simplified to

\begin{align} d_a &\le 5 \\ d_b &\le 2 \\ d_c &\le 11 \\ d_{goal} &\le d_a + 20 \\ d_{goal} &\le d_b + 25 \\ d_{goal} &\le d_c + 17 \end{align}

It is easy to see that the last two constraints could be removed from the model : they can be relaxed. Physically, if you stretch the graph from $start$ to $goal$, edges $(b,goal)$ and $(c,goal)$ end up wavy/loose/"relaxed".

Answer 2

In optimisation theory, creating a relaxation refers to an operation which:

• Creates a superset of an underlying set, if the operation is done on a set
• Produces a new set of functions that define a superset of a set associated with some original function (usually the feasible region).

For instance, if I have a nonconvex function/set, I can create a convex relaxation of that function/set:

Assuming that the set of interest is a feasible region, the usual way to modify the feasible region defined by a constraint is to modify the constraint itself in some way, either by replacing it with a set of different constraints, or by changing that constraint's functional form.

For instance, a convex (and linear) relaxation of $-x^2\leq 0$ is the secant of $-x^2$ between the lower and upper bounds of $x$. Furthermore, said secant (along with the original constraint) defines the convex hull of that set, because that's the tightest possible superset we can produce for that feasible region that is still convex.