Find a path in a complete graph with cost limit and max reward

Question

I'm looking for an algorithm to solve this problem. I have to implement it (so I need a not np solution XD)

I have a complete graph with a cost on each arch and a reward on each vertex. I have only a start point, but it doesn't matter the end point, becouse the problem is to find a path to see as many vertex as possible, in order to have the maximum reward possible, but subject to a maximum cost limit. (for this reason it doesn't matter the end position).

I think to find the optimum solution is a np-hard problem, but also an approximate solution is apprecciated :D

Thanks

I'm trying study how to solve the problem with branch & bound...

update: complete problem dscription

I have a region in which there are several areas identify by its id and x,y,z position. Each vertex identifies one ot these areas. The maximum number of ares is 200. From a start point S, I know the cost, specified in seconds and inserted in the arch (so only integer values), to reach each vertex from each other vertex (a complete graph). When I visit a vertex I get a reward (float valiues).

My objective is to find a paths in a the graph that maximize the reward but I'm subject to a cost constraint on the paths. Indeed I have only limited minutes to complete the path (for example 600 seconds.)

The graph is made as matrix adjacency matrix for the cost and reward (but if is useful I can change the representation).

I can visit vertex more time but with one reward only!

Answer 1

Since you're interested in branch and bound, let's formulate a linear program. Use Floyd–Warshall to adjust the costs minimally downward so that cost(uw) ≤ cost(uv) + cost(vw) for all vertices u, v, w.

Let s be the starting vertex. We have 0-1 variables x(v) that indicate whether vertex v is part of the path and 0-1 variables y(uv) that indicate whether the arc uv is part of the path. We seek to maximize

sum over all vertices v of reward(v) x(v).

The constraints unfortunately are rather complicated. We first relate the x and y variables.

for all vertices v ≠ s,  x(v) - sum over all vertices u of y(uv) = 0

Then we bound the cost.

sum over all arcs uv of cost(uv) y(uv) ≤ budget

We have (pre)flow constraints to ensure that the arcs chosen look like a path possibly accompanied by cycles (we'll handle the cycles shortly).

for all vertices v,  sum over all vertices u of y(uv)
                       - sum over all vertices w of y(vw)
                         ≥ -1 if v = s
                            0 if v ≠ s

To handle the cycles, we add cut covering constraints.

for all subsets of vertices T such that s is not in T,
  for all vertices t in T,
    x(t) - sum over all vertices u not in T and v in T of y(uv) ≥ 0

Because of the preflow constraints, a cycle necessarily is disconnected from the path structure.

There are exponentially many cut covering constraints, so when solving the LP, we have to generate them on demand. This means finding the minimum cut between s and each other vertex t, then verifying that the capacity of the cut is no greater than x(t). If we find a violation, then we add the constraint and use the dual simplex method to find the new optimum (repeat as necessary).

I'm going to pass on describing the branching machinery – this should be taken care of by your LP solver anyway.