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

[Andrew Makhorin]

> I #8217;m working on a method to find a path in a network from two
> different nodes with the total distance being as closest as possible
> to a certain number.

Tsp.mod finds the shortest hamiltonian cycle, i.e. simple closed
path through all nodes of the network. Do you really need to find a
hamiltonian cycle having a certain property? If not, you should
consider other formulations like the shortest path problem.

> The problem is that the constraint becomes nonlinear
> because of the product between n and x[i,j].

> Is this a bad approach

It seems so :)

>  or the problem cannot be
> solved by LP?

You need to reformulate your problem. For example, the following
formulation may be used:

   minimize max|L - L'|,
   s.t. other constraints

where L is the length of the path to be found (in tsp.mod it is
sum{(i,j) in E} c[i,j] * x[i,j]), and L' is the desired length.
Using the standard mip modeling technique we can replace the non-linear
convex objective function above by the following equivalent linear
formulation:

   minimize z
   s.t. z >= L - L'
        z >= L' - L
        other constraints