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

[Michael Hennebry]

On Fri, 12 Sep 2008, Gianmarco Bruno wrote:

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

IIRC the TSP example uses a closed-form formulation,
i.e. one in which all the constraints are applied at the start.
For the TSP, such formulations aren't very efficient,
but they do have the advanage of ease of exposition.

> 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];

I think an upper bound on n is sufficient.
To be sure, you will need to do the math.

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

If an upper bound works, the constraint is no longer nonlinear.
>
> Is this a bad approach or the problem cannot be solved by LP?

It's still an integer problem.

If the paths have to be node-distinct,
an adequate set of constraints is:
no cycles
the endpoints have degree 1
the middle node has degree 2
the other nodes have degree 0 or 2

If the paths do not have to be node-distinct,
I think that you might need two sets of edges.

-- 
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."