Re: [Help-glpk] path constrained to a certain distance

[Andrew Makhorin]

> I #8217;ve tried to find the path in a graph constrained to a certain
> distance L #8217; starting from the shortest path formulation.

> Yes, the idea is to minimize the absolute difference between L and L
> #8217; but spurious paths (i.e. additional closed subcycles) comes
> out. For example consider the attached graph.

> Setting the target distance from node 2 to node 16 and
> the target distance to 1111 km, you get the path:

> 2->6->11->12->14->16, plus the
> subcycle 13->15->13

> How can the constraint  #8220;no subcycles #8221;
> could be formulated in Mathprog?

Subtours can be eliminated in various ways. The example model tsp.mod
(included in the glpk distribution) gives an example of closed
formulation, when all necessary constraints are introduced into the
problem from the very beginning. However the closed formulation may
be inefficient for larger instances.

Another well-known way is to add the following constraints (V is the
set of nodes of the network):

   sum{(i,j) in d(W)} x[i,j] >= 2
   
   for all W within V, W != empty, W != V,

where

     d(W) = {(i,j):i in W and j not in W or i not in W and j in W},

i.e. d(W) is the set of edges which have exactly one endnode in W.

However, the number of subtour elimination constraints in the latter
approach is exponential on the number of nodes, so it assumes row
generation (that needs solving the minimal cut problem to generate one
such constraint).

For yet another way based on the MTZ formulation (which is closed)
see, for example, http://www.unc.edu/~pataki/papers/teachtsp.pdf .

As I understand you need to find a (simple?) path from s to t whose
length is as closest to the given length as possible. It seems to me
that there must be articles dedicated to this problem and available
on the internet.


Andrew Makhorin