[Help-glpk] path constrained to a certain distance

[Gianmarco Bruno]

Hi,

 

I’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.

I started from the idea explained by Andrew Makhorin in examples/tsp.mod in the GLPK distribution, then I consider n as a variable (the number of traversed nodes) instead of a parameter.

 

n is computed as the sum over (i,j) of x[i,j] plus 1.

 

Then, quoting from example/tsp.mod we have:

 

s.t. cap{(i,j) in E}: y[i,j] <= (n-1) * x[i,j];

/* if arc (i,j) does not belong to the salesman's tour, its capacity

   must be zero; it is obvious that on leaving a node, it is sufficient

   to have not more than n-1 cars */

 

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

Is this a bad approach or the problem cannot be solved by LP?

 

Many thanks

 

Gianmarco Bruno