Using problem solvers

Solving max-flow instances

To call a problem solver, one usually can choose from two interface functions. To the one function, a mathematical method is explicitly specified. The second function looks up the preferred mathematical method in the goblinController default settings.

It is unwanted to call a mathematical implementation method directly, since some code is method independent, and centralized in the interface function. In the max-flow case, the mathematical implementation methods apply to digraphs only. The interface function handles the flow values of undirected edges.

The codes

    TCap flowValue = G.MaxFlow(MXF_SAP_SCALE,source,target);

and

    G.Context().methMaxFlow = G.MXF_SAP_SCALE;
    TCap flowValue = G.MaxFlow(source,target);

are equivalent up to the obvious side-effect of the second code: Later calls of the max-flow solver would also apply the capacity scaling method. This tells that the first version is best practice.

As other solvers, the max-flow solver returns an objective value, and stores the found solutions object internally: The flow is maintained by the subgraph multiplicities, and the dual solution (a minimum edge cut) by the node distance labels". When the object is saved to file, the solutions are also saved.

If the max-flow solver is called again, it starts from the existing subgraph. This might be unwanted, especially in the case of changing source and target nodes:

    sparseDiGraph G(filename);
    TCap lambda = InfCap;
   
    for (TNode source=0;source<n;++source)
    {
       TNode target = (source+1)%n;
   
       G.InitSubgraph();
       TCap flowValue = G.MaxFlow(source,target);
   
       if (flowValue < lambda) lambda = flowValue;
    }

This procedure loads a sparseDiGraph G from file and then determines the strong edge connectivity number of G as the final value of lambda. The flow of the previous iteration is infeasible as a starting solution, since all nodes other than the source and the target must be balanced. The abstractMixedGraph::InitSubgraph() operation reverts to a zero flow - but only if the lower capacity bounds are all zero. Most likely, the lines

    sparseDiGraph G(filename);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCUCap(1);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCLCap(0);
    static_cast<sparseRepresentation*>(G.Representation()) -> SetCDemand(0);
    ...

should be added to obtain the expected result. The graphRepresentation::SetCDemand() call is necessary when the goblinController::methFailSave option is set: Then the max-flow solver verifies on exit if the node demands and flow imbalances match.

The max-flow solver can deal with infinite capacity bounds. But if the lower capacity bounds are non-trivial, the solver must be supplied with a starting solution, by calling abstractMixedGraph::AdmissibleBFlow(). This evaluates the node demands, and calls the max-flow solver for a digraphToDigraph instance (but this is only an implementational detail).

Solving shortest path instances

The determination of shortest paths between two graph nodes is probably the most fundamental task in graph optimization. It forms part of many other graph optimization methods, several min-cost flow methods for example. Usually, it is assumed that all edge lengths are non-negative. If so, the well-known Dijkstra method applies, and this is elementary in that it does not depend on any library configuration parameters. In the setting with negative edge lengths, selecting an adequate methods takes much more care.

Hiding all technical details, the basic application of the shortest path solver is as follows:

    if (ShortestPath(source,target))
    {
       TFloat dt = Dist(target);
       TArc pred = GetPredecessors();
       TNode v = target;
   
       do {
          TArc a = pred[v];
          v = StartNode(a);
       }
       while (v!=source);
    }

The return value of abstractMixedGraph::ShortestPath() tells whether the target node can be accessed on an eligible path from the source node. In occasion, the determined path is stored by the Predecessor labels, and the path length can be retrieved by the abstractMixedGraph::Dist() function which is short-hand for accessing the Distance labels. The loop does nothing else than traversing this path back from the target node to the source node.

A first technical explanation concerns the definition of eligible arcs: In the default setting as above, directed arcs may be traversed only one-way, but undirected edge can be traversed in both directions. By using other interface methods, one might modify this eligibily rule:

    BFS(subgraphArcs(*this),source,target);

would determine a path in the current subgraph. This path does not minimize the sum of edge length but only the number of path edges, as it is computed by breadth-first search. This code is roughly the same as

    ShortestPath(SPX_BFS,SPX_ORIGINAL,subgraphArcs(*this),source,target);

but the latter method requires uniform edge lengths.

There is a strong impact of method selection and solver configuration on the performance:

What method is best performing depends on the input graph. Is the graph acyclic? Is it undirected? Are the edge lengths uniform? Are the edge lengths non-negative? Do negative length cycles exist?
abstractMixedGraph::SPX_Dijkstra() and abstractMixedGraph::BFS() stop when the target node is reached the first time, as the corresponding path is minimal. But if no target node is specified, a shortest path tree is determined. This is a predecessor tree which entirely consists of shortest paths.
For sake of efficiency, one often considers several potential start and target nodes at one time. But this only works for the Dijkstra method.
In order to avoid explicit construction of graph instances, there are modifiers for the edge lengths (abstractMixedGraph::TOptSPX), and arc index sets to vary the eligibility rule.

At the time, there is no implementation to handle the very general setting of mixed graphs with negative edge lengths. This setting is equivalent with the longest path problem in the literature, which can be considered hard to solve.

Even if such a general method would exist, it would be no good idea to apply it by default. There are a lot of applications which can guarantee non-negativity of the edge lengths, and hence can solved by the Dijkstra method.

But what is special about the non-negative edge length setting? To understand this, consider the difference between walks (a series of adjacent arcs), paths (walks without arc repetitions) and simple paths (walks without node repetitions):

When all arc lengths are positive, every minimum length walk is a simple path.
When all arc lengths are non-negative, every minimum length walk can be reduced to a simple path of the same length.
When negative edge lengths are allowed, the problem of finding a shortest simple path is bounded. The problem of finding a shortest walk is unbounded if there is a walk containing a negative length cycle.
In the negative edge length setting, the problem of finding a shortest, not necessarily simple path is bounded, and can be solved efficiently by min-cost flow techniques.

The predecessor labels register can only represent simple paths, and those are the intended output of the shortest path solver. Technically, all methods which deal with negative edge lengths operate on paths rather than simple paths. If no negative length subcycle exists in the found path, it can be reduced to a simple path of the same length.

Accepting negative edge lengths, the following cases can be solved efficiently:

Directed acyclic graphs (DAGs) admit a linear time label setting method (specify abstractMixedGraph::SPX_DAG with the solver interface).
Mixed graphs with negative length arcs, but without negative length cycles admit label correcting methods such as abstractMixedGraph::SPX_FIFOLabelCorrecting(). (specify abstractMixedGraph::SPX_FIFO or abstractMixedGraph::SPX_BELLMAN). Unfortunately, negative length undirected edges constitute negative length cycles which consist of two antiparallel arcs.
Undirected graphs with negative length edges, but without negative length cycles. Can be solved by reduction to a T-Join problem (specify abstractMixedGraph::SPX_TJOIN). And so depends on the min-cost flow and the weighted matching solver.