org.jgrapht.alg.spanning

Class AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,E>

java.lang.Object

org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree<V,E>

org.jgrapht.alg.spanning.AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

CapacitatedSpanningTreeAlgorithm<V,E>

public class AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,E>
extends AbstractCapacitatedMinimumSpanningTree<V,E>

Implementation of an algorithm for the capacitated minimum spanning tree problem using a cyclic exchange neighborhood, based on Ravindra K. Ahuja, James B. Orlin, Dushyant Sharma, A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem, Operations Research Letters, Volume 31, Issue 3, 2003, Pages 185-194, ISSN 0167-6377, https://doi.org/10.1016/S0167-6377(02)00236-5. (http://www.sciencedirect.com/science/article/pii/S0167637702002365)

A Capacitated Minimum Spanning Tree (CMST) is a rooted minimal cost spanning tree that satisfies the capacity constrained on all trees that are connected to the designated root. The problem is NP-hard. The hard part of the problem is the implicit partition defined by the subtrees. If one can find the correct partition, the MSTs can be calculated in polynomial time.

This algorithm is a very large scale neighborhood search algorithm using a cyclic exchange neighborhood until a local minimum is found. It makes frequently use of a MST algorithm and the algorithm for subset disjoint cycles by Ahuja et al. That is, the algorithm may run in exponential time. This algorithm is implemented in two different version: a local search and a tabu search. In both cases we have to find the best neighbor of the current capacitated spanning tree. For further information about finding such an improving neighbor ImprovementGraph @see ImprovementGraph

Since:

July 11, 2018

Author:

Christoph Grüne

Nested Class Summary

Nested classes/interfaces inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree

AbstractCapacitatedMinimumSpanningTree.CapacitatedSpanningTreeSolutionRepresentation

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.CapacitatedSpanningTreeAlgorithm

CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>, CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTreeImpl<V,E>

Field Summary

Fields inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree

bestSolution, capacity, demands, graph, root

Constructor Summary

Constructors

Constructor and Description
AhujaOrlinSharmaCapacitatedMinimumSpanningTree(CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> initialSolution, Graph<V,E> graph, V root, double capacity, Map<V,Double> demands, int lengthBound) Constructs a new instance of this algorithm with the proposed initial solution.
AhujaOrlinSharmaCapacitatedMinimumSpanningTree(CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> initialSolution, Graph<V,E> graph, V root, double capacity, Map<V,Double> demands, int lengthBound, boolean bestImprovement, boolean useVertexOperation, boolean useSubtreeOperation, boolean useTabuSearch, int tabuTime, int upperLimitTabuExchanges) Constructs a new instance of this algorithm with the proposed initial solution.
AhujaOrlinSharmaCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, Map<V,Double> demands, int lengthBound, boolean bestImprovement, int numberOfOperationsParameter, boolean useVertexOperation, boolean useSubtreeOperation, boolean useTabuSearch, int tabuTime, int upperLimitTabuExchanges) Constructs a new instance of this algorithm.
AhujaOrlinSharmaCapacitatedMinimumSpanningTree(Graph<V,E> graph, V root, double capacity, Map<V,Double> demands, int lengthBound, int numberOfOperationsParameter) Constructs a new instance of this algorithm.

Method Summary

Modifier and Type	Method and Description
CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E>	getCapacitatedSpanningTree() Computes a capacitated spanning tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

AhujaOrlinSharmaCapacitatedMinimumSpanningTree

public AhujaOrlinSharmaCapacitatedMinimumSpanningTree(Graph<V,E> graph,
                                                      V root,
                                                      double capacity,
                                                      Map<V,Double> demands,
                                                      int lengthBound,
                                                      int numberOfOperationsParameter)

Constructs a new instance of this algorithm.

Parameters:

graph - the base graph

root - the designated root of the CMST

capacity - the edge capacity constraint

demands - the demands of the vertices

lengthBound - the length bound of the cycle detection algorithm

numberOfOperationsParameter - the number of operations that are considered in the randomized Esau-Williams algorithm EsauWilliamsCapacitatedMinimumSpanningTree @see EsauWilliamsCapacitatedMinimumSpanningTree

AhujaOrlinSharmaCapacitatedMinimumSpanningTree

public AhujaOrlinSharmaCapacitatedMinimumSpanningTree(CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> initialSolution,
                                                      Graph<V,E> graph,
                                                      V root,
                                                      double capacity,
                                                      Map<V,Double> demands,
                                                      int lengthBound)

Constructs a new instance of this algorithm with the proposed initial solution.

Parameters:

initialSolution - the initial solution

graph - the base graph

root - the designated root of the CMST

capacity - the edge capacity constraint

demands - the demands of the vertices

lengthBound - the length bound of the cycle detection algorithm

AhujaOrlinSharmaCapacitatedMinimumSpanningTree

public AhujaOrlinSharmaCapacitatedMinimumSpanningTree(Graph<V,E> graph,
                                                      V root,
                                                      double capacity,
                                                      Map<V,Double> demands,
                                                      int lengthBound,
                                                      boolean bestImprovement,
                                                      int numberOfOperationsParameter,
                                                      boolean useVertexOperation,
                                                      boolean useSubtreeOperation,
                                                      boolean useTabuSearch,
                                                      int tabuTime,
                                                      int upperLimitTabuExchanges)

Constructs a new instance of this algorithm.

Parameters:

graph - the base graph

root - the designated root of the CMST

capacity - the edge capacity constraint

demands - the demands of the vertices

lengthBound - the length bound of the cycle detection algorithm

bestImprovement - contains whether the best (if true) or the first improvement (if false) is returned in the neighborhood search

numberOfOperationsParameter - the number of operations that are considered in the randomized Esau-Williams algorithm EsauWilliamsCapacitatedMinimumSpanningTree @see EsauWilliamsCapacitatedMinimumSpanningTree

useVertexOperation - contains whether the local search uses the vertex operation

useSubtreeOperation - contains whether the local search uses the subtree operation

useTabuSearch - contains whether a tabu search is used

tabuTime - the tabu time that is the number of iterations an element is in the tabu list

upperLimitTabuExchanges - the upper limit of non-improving exchanges, this is the stopping criterion in the tabu search

AhujaOrlinSharmaCapacitatedMinimumSpanningTree

public AhujaOrlinSharmaCapacitatedMinimumSpanningTree(CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> initialSolution,
                                                      Graph<V,E> graph,
                                                      V root,
                                                      double capacity,
                                                      Map<V,Double> demands,
                                                      int lengthBound,
                                                      boolean bestImprovement,
                                                      boolean useVertexOperation,
                                                      boolean useSubtreeOperation,
                                                      boolean useTabuSearch,
                                                      int tabuTime,
                                                      int upperLimitTabuExchanges)

Constructs a new instance of this algorithm with the proposed initial solution.

Parameters:

initialSolution - the initial solution

graph - the base graph

root - the designated root of the CMST

capacity - the edge capacity constraint

demands - the demands of the vertices

lengthBound - the length bound of the cycle detection algorithm

bestImprovement - contains whether the best (if true) or the first improvement (if false) is returned in the neighborhood search

useVertexOperation - contains whether the local search uses the vertex operation

useSubtreeOperation - contains whether the local search uses the subtree operation

useTabuSearch - contains whether a tabu search is used

tabuTime - the tabu time that is the number of iterations an element is in the tabu list

upperLimitTabuExchanges - the upper limit of non-improving exchanges, this is the stopping criterion in the tabu search

Method Detail

getCapacitatedSpanningTree

public CapacitatedSpanningTreeAlgorithm.CapacitatedSpanningTree<V,E> getCapacitatedSpanningTree()

Description copied from interface: CapacitatedSpanningTreeAlgorithm

Computes a capacitated spanning tree.

Specified by:

getCapacitatedSpanningTree in interface CapacitatedSpanningTreeAlgorithm<V,E>

Specified by:

getCapacitatedSpanningTree in class AbstractCapacitatedMinimumSpanningTree<V,E>

Returns:

a capacitated spanning tree