Retrieving vertex path from linear-programming solution

Question

I have been trying to solve a routing problem, like the TSP (traveling salesman problem) but with some twists. I have modeled the problem using linear-programming (CPlex library) and a directed graph (with an Origin vertex) (Coin-Or::Lemon library).

The linear program finds the solution, but my question lies in how to retrieve the path. I can iterate each vertex and edge of the graph to find out which the linear program is using, so I thought I'd just start on the Origin and use the chosen edges to get to next node until I reached the Origin again.

The problem was that the CPlex path may walk through any vertex more than once. So I decided to use a recursive algorithm. But I can't quite figure it out. Here's what I've tried:

FindPath ( node N, path P)
    AddedAnyPath <- false
    for each edge E out of N that hasn't been used yet
        T is the target of E
        add T to P

        if findPath ( E, P )
            AddedAnyPath = true
    end for each
    
    if AddedAnyPath 
        if all edges were used
            return true
        else
            return false
        end if
    endif
end

This algorithm fails to find a path. If you please could point me in any direction I would be very grateful.

Edit

The answer provided helped me find the answer. Here's the code in C++:

bool findPath2 ( Store_Instance &T, DiNode &current, list <DiNode> &path, ListDigraph::ArcMap<bool> &usedArcs, IloCplex &cplex, ListDigraph::ArcMap<IloNumVar> &x) {
DiNode currentNode = current;
bool success = false;
int positionToInsert = 1;
while (true) {
    //Find an unvisited edge E whose value is 1.
    Arc unvisitedArc = INVALID;
    for(Digraph::OutArcIt a(T.g, currentNode); a != INVALID; ++a) {
        if(cplex.getValue(x[a]) >= 1-EPS && !usedArcs[a]) {
            unvisitedArc = a;
            break;
        }
    }
    if (unvisitedArc != INVALID) {
        //Mark edge as visited
        usedArcs[unvisitedArc] = true;
        //Get the target T of the edge
        DiNode target = T.g.target(unvisitedArc);
        //Add Edge E to the path
        list<DiNode>::iterator iterator = path.begin();
        advance(iterator, positionToInsert);
        path.insert(iterator, target);
        //Increase the iterator
        positionToInsert++;
        //If all the edges whose value is 1 are visited, stop
        bool usedAllEdges = true;
        for (ArcIt a(T.g); a != INVALID; ++a){
            if (cplex.getValue(x[a]) > 1-EPS && usedArcs[a] == false) {
                usedAllEdges = false;
                break;
            }
        }
        if (usedAllEdges) {
            success = true;
            break;
        }
        //Else, Set N to be T and repeat
        else currentNode = target;
    } else {
        //No arcs were found. Find a node from the path that has unvisited Arc
        positionToInsert = 0;
        DiNode target = INVALID;
        for (list<DiNode>::const_iterator iterator = path.begin(), end = path.end(); iterator != end; ++iterator) {
            DiNode v = *iterator;
            for(Digraph::OutArcIt a(T.g, v); a != INVALID; ++a) {
                if(cplex.getValue(x[a]) >= 1-EPS && !usedArcs[a]) {
                    target = v;
                    break;
                }
            }
            positionToInsert ++;
            if (target != INVALID) break;
        }

        if (target != INVALID) {
            //cout << "found lost node" << endl;
            currentNode = target;
        } else {
            success = false;
            break;
        }
    }
}
return success;
}

Answer 1

The solution to a TSP (the path) is an ordered list of vertices, that start and end at the origin, visiting each vertex. There are two possible cases.

If you have allowed a vertex to be visited twice, then in your variation, you are allowing `sub-tours'. (Case 2)

You will have variables X_nt which will be 1. (Edge variables connecting node n to node t).

If you have no subtours: Case 1, you can stop once you come back to the origin node.

It looks like you are allowing sub-tours (multiple cycles, case 2 above). If so, you have to visit all edges that are part of the TSP solution, whose value is 1. (Modify your code to follow any one edge out of each node to its terminal node, one edge at a time.)

Let starting n = origin node
For node n:
  Find an unvisited edge E whose value is 1. 
  Mark edge as visited
  Get the target T of the edge
  Add Edge E to the path
  If all the edges whose value is 1 are visited, stop
  Else, Set N to be T and repeat

Hope that helps.