Modified TSP with Branch-and-Bound algorithm

I've been struggling to solve it using branch-and-bound to find the optimal path for the next task:

There's a list of cities, that are all connected with each other, basically, a complete graph, each city has a interest index ( city 'A' has 8 interest points, city 'B' has 9). There's a limited budget for travelling and we need to come up with a path that gets the most possible interest indices. Also, the path must start and end at the same city, so we need to return back to the city 'A' from the last one if we started there, for example.

It is not necessary to visit all the cities, sometimes the budget doesn't allow this. Starting city can be chosen as well as the ending one, but the thing is you need to return back to the starting one.

Visiting one city twice is not allowed, the only situation you can visit the same city twice is when returning back to the starting one.

Also, travelling across the cities X and Y via some other city may be cheaper so the graph is non-metric.

Someone has asked about the real world problem this task covers, it's the tourism path algorithm. We need to create the path with most interest covered with available money.

What other algorithms are suitable for this kind of task?

I tried greedy algorithm and there was an attempt to solve it with branch and bound

I expect a valid solution with branch-and-bound on any language.

The branch and bound version of the TSP algorithm is only necessary if the graph is not metric. ( A metric graph means that for any two vertices ( X and Y ) the direct edge between X and Y is always cheaper than the travelling between X and Y via a third vertex ). Most graphs modelling real world problems are metric. The metric version of the TSP algorithm is simpler to code and runs much faster than branch&bound.

Since your example graph is not metric, I have implemented the TSP branch&bound solution to your problem.

Here is the algorithm:

Solve travelling salesman problem to visit every city once as cheaply as possible

If solution cost is less than budget, SOLVED

Delete city with smallest interest, and all its links

Repeat until solution found.

Here is the output from a run on your example graph for a budget of 1000

Minimum cost : 750 Budget : 1000
Path Taken : a d b c e

and for budget of 500

Dropping e ( 6 ) from itinerary
Dropping c ( 7 ) from itinerary
Minimum cost : 200 Budget : 500
Path Taken : a b d

The complete application C++ code, documentation and discussion can be found in the github repository https://github.com/JamesBremner/so76213744