Searching 4 graph optimization software

  • Thread starter AntistatiK
  • Start date
  • #1
I'd like 2 solve the following problem (well, routinely solve a bunch of such problems):
Let us have a number of points (vertices), that can be interconnected. Not any 2 points are connected. Each connection is assigned a value. I want 2 find the maximum path in the graph, that is, the one with the highest connection score (of course, visiting any point only once). Optionally, scores may be direction-dependent, that is, the value of connecting point A 2 B is not necessary equal 2 the value of B -> A. Also optionally, I want 2 specify, or limit, the number of vertices (out of the whole set) I want 2 connect. Also optionally, I want some particular vertices 2 be included by all means.
I found that the problem of minimizing such score is well-known, call it route optimization, or "traveling postman (salesman)". But I haven't found the software that solves my particular problem. Maybe it's realized in a software suite, but I'm not aware of it. I'm waiting 4 your ideas...
 

Answers and Replies

  • #2
Call it "the problem of traveling hauler", it's more intuitive. In the morning, he has a set of requests, such as "carry smth from A to B for $N". If he's on the road with no cargo, traffic cops fine him, also he burns out expensive fuel. He wants 2 earn the highest sum by the end of the day...
 
Last edited:
  • #3
30
2
Notice that if you make the scores negative then minimizing that path is that same as your maximization problem, i.e, your problem is still the traveling salesman problem.

What do you mean by "Not any 2 points are connected"? I read this as meaning your graph doesn't have any connections.

There do exist ways to solve the problem, but none computes in polynomial time. That is, there isn't a known way to solve it other than trying all the possible paths then picking the shortest one.
 

Related Threads on Searching 4 graph optimization software

  • Last Post
Replies
0
Views
185
  • Last Post
Replies
14
Views
1K
Replies
19
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
678
Replies
4
Views
867
Replies
4
Views
699
Replies
3
Views
2K
Top