7
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ So far I could not find a satisfactory explanation of why "relax" would be an appropriate term for this operation. I am wondering if the use of this term is not a historical mistake. I am considering using the expression "enforce arc constraint" instead of "relax arc constraint" for the operation in question. $\endgroup$ – Alexey Feb 16 at 18:12
4
$\begingroup$

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.

enter image description here

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".

| improve this answer | |
$\endgroup$
  • $\begingroup$ I've added a link to some slides where the term is used. I do not see in what sense a constraint is removed. Constraints do not seem to be operated upon explicitly, instead it looks like a search for an "optimal" solution. $\endgroup$ – Alexey Feb 12 at 18:19
  • $\begingroup$ As i said, i do not see the constraint to be removed. Could you explain, please, what constraint satisfaction problem is transformed into what other CSP by removing a constraint when an edge is relaxed? The analogy with springs as shortest paths is quite strange, i do not see what it means... $\endgroup$ – Alexey Feb 12 at 18:45
  • $\begingroup$ Your model of the shortest path problem is not exact: edge weights are not natural numbers, but reals. I suppose that instead of the second family of inequalities, you can use just one: $d_u = 0$. I do not understand the meaning of "the constraint $x_j \le x_i + w_{i,j}$ is only active when $x_i$ is ...". A constraint a priori is a condition on variables. For example, i do not know what it mean "$x < y$ is only active if $x = 0$". Could you give me a reference to a general notion of relaxation where constraints on variables can be active or inactive depending on the values of the variables? $\endgroup$ – Alexey Feb 12 at 21:26
  • $\begingroup$ "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$." -- this is a strange explanation, since all the edges on the "tightest string" have been relaxed. $\endgroup$ – Alexey Feb 12 at 21:31
  • $\begingroup$ @Alexey : 1/ yes of course variables $d_j$ are continuous, thanks. 2/ In the image, if nodes are called $a$, $b$ $c$ from top to bottom : $d_{goal} = d_{a}+20$ but $d_{goal} < d_{b} + 25$ : the constraint is only active for node $a$. 3/all the edges on the tightest string are not relaxed (none are). $\endgroup$ – Kuifje Feb 12 at 22:08
1
$\begingroup$

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:

enter image description here

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Sorry, maybe i was still not clear in my question, but i was asking specifically about the relaxation step in some classical Shortest Path algorithms. What superset of what set is created by the relaxation operation i am asking about? $\endgroup$ – Alexey Feb 13 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.