not BOUND in this code of the TSP?

Question

I want to know how I could do the BOUND because I generates all possible solutions matrix tsp but not the bound. The problem is the travelling salesman. Is it possible to do this?

public void bnb (int from, ArrayList followedRoute) {
    if (followedRoute.size() == distances.getMatrix().get(0).size()) {

        followedRoute.add(sourceCity);
        nodes++;

        // update the route's cost
        routeCost += distances.getCost(from, sourceCity);

        if (routeCost < optimumCost) {
            optimumCost = routeCost;
            optimumRoute = (ArrayList)followedRoute.clone();
            result += followedRoute.toString() + "// Cost: "+ routeCost + "\n";
            System.out.println(result);
        } 

        routeCost -= distances.getCost(from, sourceCity);

    }
    else {
        for (int to=0; to < distances.getMatrix().get(0).size(); to++){
            if (!followedRoute.contains(to)) {

                // update the route's cost
                routeCost += distances.getCost(from, to);


                if((routeCost < optimumCost) ) {
                    ArrayList increasedRoute = (ArrayList)followedRoute.clone();
                    increasedRoute.add(to);
                    nodes++;
                    bnb(to, increasedRoute);    
                } 


                routeCost -= distances.getCost(from, to);
            }
        }
    }        
}

score 0 · Answer 1 · edited May 23 '17 at 11:52

My apologies for adding this as an answer, I wanted to simply add it as a comment to refer you to another SE question, but I don't have enough reputation for adding comments.

You can probably not except anyone to give you the implementation for computing the bound(s), but for the theory, please refer to this similar question previously asked on SE. TSP - Branch and bound

Both given answers to the question above provide links to thorough explanations of TSP in the context of Branch-and-Bound (BAB), including how to compute lower bounds of BAB branches. Recall that your upper bound in the BAB process is simply the currently best incumbent solution (currently best path), as found previously in BAB tree or via heuristics.

not BOUND in this code of the TSP?

1 Answers1