org.jorlib.alg.tsp.separation

Class SubtourSeparator<V,E>

java.lang.Object

org.jorlib.alg.tsp.separation.SubtourSeparator<V,E>

public class SubtourSeparator<V,E>
extends Object

This class separates subtours. These subtours may be used to generate Dantzig Fulkerson Johnson (DFJ) subtour elimination constraints. Let G(V,E) be a undirected graph with vertex set V, edge set E. A valid TSP solution (i.e. a solution without subtours) should satisfy the following constraint: \sum_{e\in \delta{S}} x_e >=2 for all S\subset V, S \noteq \emptyset. Here \delta{S}\subset E is the set of edges where each edge has exactly one endpoint in S, and one endpoint in V\setminus S. x_e is a binary variable indicating whether edge e\in E is used in the TSP solution. Obviously, if there is a set S'\subset V, S' \noteq \emptyset such that \sum_{e\in \delta{S'}} x_e <2, then there is a subtour through the vertices in set S'. It may be the case that multiple subtours exist within a fractional TSP solution. This class identifies the subtour with the highest amount of violation, i.e \min_{S\subset V, S \noteq \emptyset} \sum_{e\in \delta{S}} x_e

Note: the graph must be provided as a JgraphT graph. The graph representing the problem can be directed, undirected, or mixed, complete or incomplete, weighted or without weights. The directed graphs are often useful to model cases where a vehicle can only drive from one city to the other in a particular direction.

Note2: To separate the subtours, we rely on the StoerWagnerMinimumCut implementation from the JgraphT package. This implementation deterministically computes the minimum cut in a graph in O(|V||E| + |V|log|V|) time, see M. Stoer and F. Wagner, "A Simple Min-Cut Algorithm", Journal of the ACM, volume 44, number 4. pp 585-591, 1997.

WARNING: if the input graph is modified, i.e. edges or vertices are added/removed then the behavior of this class is undefined! A new instance should of this class should be made if this happens! A future extension of this class could add a graph listener.

Since:

April 9, 2015

Author:

Joris Kinable

Field Summary

Fields

Modifier and Type	Field and Description
static double	PRECISION Precision 0.000001

Constructor Summary

Constructors

Constructor and Description
SubtourSeparator(org.jgrapht.Graph<V,E> inputGraph) This method instantiates the Subtour Separator.

Method Summary

Modifier and Type	Method and Description
Set<V>	getCutSet() Returns the set S' where \sum_{e\in \delta{S'}} x_e <2, S'\subset V, S' \noteq \emptyset
double	getCutValue() Returns \sum_{e\in \delta{S'}} x_e for the separated subtour through S'.
boolean	hasSubtour() Returns whether a subtour exists in the fractional TSP solution
void	separateSubtour(Map<E,Double> edgeValueMap) Starts the subtour separation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PRECISION

public static final double PRECISION

Precision 0.000001

See Also:

Constant Field Values

Constructor Detail

SubtourSeparator

public SubtourSeparator(org.jgrapht.Graph<V,E> inputGraph)

This method instantiates the Subtour Separator. The input can be any type of graph: directed, undirected, or mixed, complete or incomplete, weighted or without weights. Internally, this class converts the given graph to a undirected graph. Multiple edges between two vertices i,j, for example two direct arc (i,j) and (j,i)) are aggregated into in undirected edge (i,j). WARNING: if the input graph is modified, i.e. edges or vertices are added/removed then the behavior of this class is undefined! A new instance should of this class should be made if this happens!

Parameters:

inputGraph - input graph

Method Detail

separateSubtour

public void separateSubtour(Map<E,Double> edgeValueMap)

Starts the subtour separation.

Parameters:

edgeValueMap - Mapping of edges to their corresponding values, i.e. the x_e variable values for all e \in E. It suffices to provide the values of the non-zero edges. All other edges are presumed to have the value 0.

hasSubtour

public boolean hasSubtour()

Returns whether a subtour exists in the fractional TSP solution

Returns:

whether a subtour exists in the fractional TSP solution

getCutValue

public double getCutValue()

Returns \sum_{e\in \delta{S'}} x_e for the separated subtour through S'.

Returns:

\sum_{e\in \delta{S'}} x_e for the separated subtour through S'.

getCutSet

public Set<V> getCutSet()

Returns the set S' where \sum_{e\in \delta{S'}} x_e <2, S'\subset V, S' \noteq \emptyset

Returns:

the set S' where \sum_{e\in \delta{S'}} x_e <2, S'\subset V, S' \noteq \emptyset