Find your way in the full schedule with a cost limit and maximum reward

Question

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

I have a complete schedule with a cost for each arch and a reward for each vertex. I only have a starting point, but it does not matter for the end point, because the problem is to find a way to see as many peaks as possible in order to get the maximum reward, but with the maximum cost limit. (for this reason, the end position does not matter).

I think finding the optimal solution is an np-difficult task, but also an approximate solution apprecciated: D

thanks

I am trying to learn how to solve a problem using a branch and related ...

update: full dscription problem

I have a region in which several regions are identified by its id and x, y, z positions. Each vertex identifies one of these areas. The maximum number of ares is 200. From the starting point S, I know the value indicated in seconds and inserted into the arch (so that only integer values) to reach each vertex from each other vertex (a complete graph). When I'm at the top, I get a reward (float valiues).

My goal is to find the paths in the graph that maximize the reward , but I obey the cost constraints on the paths. Indeed, I only have minutes to complete the path (e.g. 600 seconds.)

A graph is made as a matrix adjacency matrix for cost and reward (but if useful, I can change the idea).

I can visit the top for more time, but with only one reward!

Answer 1

Since you are interested in a branch and a border, let's formulate a linear program. Use Floyd-Warshall to minimize costs, 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 the vertex v part of the path and variables 0-1 y(uv) that indicate whether the arc uv part of the path. We strive to maximize

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

Unfortunately, the restrictions are quite complicated. First we bind the variables x and y .

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

Then we pegged the cost.

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

We have (pre) flow restrictions to ensure that the selected arcs look like a path, possibly followed by loops (we will handle loops soon).

 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 process the loops, add cropping restrictions.

 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 

Due to preflow restrictions, the loop necessarily disconnects from the path structure.

There are exponentially many restrictions on coverage overlap, so when solving an LP, we must generate them on demand. This means finding the minimum cut between s and every other vertex t , and then checking that the cut power is not greater than x(t) . If we find a violation, we add a restriction and use the double simplex method to search for a new optimal one (we will repeat if necessary).

I'll talk about branching machines - anyway, this should take care of your LP solver.

Answer 2

Search for the best solution

Here is a recursive approach to solving your problem.

Let's start with some definitions:

• Let A = (A _i ) _{1 ≤ i ≤ N} be regions.
• Let w _{i, j} = w _{j, i be} the time cost for the transition from A _i to A _j and vice versa.
• Let r _{i be the} reward for visiting the area A _i

Here is a recursive procedure that will output the exact requested solution: (pseudocode)

 List<Area> GetBestPath(int time_limit, Area S, int *rwd) { int best_reward(0), possible_reward(0), best_fit(0); List<Area> possible_path[N] = {[]}; if (time_limit < 0) { return []; } if (!S.visited) { *rwd += S.reward; S.visit(); } for (int i = 0; i < N; ++i) { if (S.index != i) { possible_path[i] = GetBestPath(time_limit - W[S.index][i], A[i], &possible_reward); if (possible_reward > best_reward) { best_reward = possible_reward; best_fit = i; } } } *rwd+= best_reward; possible_path[best_fit].push_front(S); return possible_path[best_fit]; } 

For obvious clarity, I suggested that A _i will be available worldwide, as well as w _{i, j} .

Explanation

You start with S. The first thing you do? Collect the reward and mark the node as you visit. Then you need to check which path is best between neighbors S N-1 (allows you to call them N _{S, i} for 1 ≤ i ≤ N-1).

This is the same as solving the problem for N _{S, i} with a time limit:

time_limit - W (S ↔ N _{S, i} )

And since you mark the visited sites when you get into the area, you first check to see if it is checked. If so, you do not have a reward ... You also collect and mark it as you visited ...

Etc!

The final condition is when time_limit (C) becomes negative. This tells us that we have reached the limit and cannot move on: the recursion is complete. The final path may contain useless trips if all the rewards have been collected before reaching the limit C. You will have to "crop" the output list.

Complexity?

Oh, this decision is soooooooo terrible in terms of complexity! Each call leads to N-1 calls ... Until a deadline is reached. The longest possible sequence of calls is obtained with each call forward and backward along the shortest edge. Let w _min be the weight of this edge.

Then, obviously, the overall complexity is bounded by N ^{C / w _min} .C / w _min .
This is huuuuuge.

---

Another approach

Maintain a hash table of all visited nodes. On the other hand, maintain a queue of maximum priority (for example, using MaxHeap) of nodes that are not yet assembled. (The top of the heap is the highest award node). The priority value for each node A _i in the queue is set as a pair (r _i , E [w _{i, j]} )

• Put a bunch: Target <- heap.pop() .
• Calculate the shortest path to this node using Dijkstra's algorithm.
• Check the path: if the cost of the path is too high, then node is not available, add it to the list of inaccessible nodes.
  • Else collect all the unsaved nodes that you find in it, and ...
  • Remove each assembled node from the heap.
  • Set your goal as a new starting point.
• In either case, go to step 1. until the heap is empty.

Note. A hash table is best for tracking collected nodes. Thus, we can check the node according to the path computed using Dijkstra in O (1).

Likewise, storing a hash table leading to the position of each node in the heap can be useful for optimizing heap pruning when collecting nodes along a path.

Small analysis

This approach is slightly better than the first in terms of complexity, but cannot lead to an optimal result. In fact, it may even work poorly on some graphics configurations. For example, if all nodes have a reward r, with the exception of one node T having r + 1 and W (N ↔ T) = C for each node N, but other edges will be available to everyone, this will only make you collect T and skip all the rest of the node. In this particular case, the best solution would be to ignore T and collect all the others, which will result in a reward of (N-1). R instead of just r + 1.