Class AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,E>
- Type Parameters:
V
- the vertex typeE
- the edge type
- All Implemented Interfaces:
CapacitatedSpanningTreeAlgorithm<V,
E>
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.
- Since:
- July 11, 2018
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
This class realises the improvement graph for the composite multi-exchange large neighborhood search.private static enum
This enums contains the vertex types of the improvement graph.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
FieldsModifier and TypeFieldDescriptionprivate final boolean
contains whether the best (if true) or the first improvement (if false) is returned in the neighborhood searchthe initial solutionprivate boolean
contains whether the algorithm was executedprivate final int
the maximal length of the cycle in the neighborhoodprivate final int
the number of the most profitable operations considered in the GRASP procedure for the initial solution.private final int
the tabu time that is the number of iterations an element is in the tabu listprivate final int
the upper limit of non-improving exchanges, this is the stopping criterion in the tabu searchprivate final boolean
contains whether the local search uses the subtree operationprivate final boolean
contains whether a tabu search is usedprivate final boolean
contains whether the local search uses the vertex operationFields inherited from class org.jgrapht.alg.spanning.AbstractCapacitatedMinimumSpanningTree
bestSolution, capacity, demands, graph, root
-
Constructor Summary
ConstructorsConstructorDescriptionAhujaOrlinSharmaCapacitatedMinimumSpanningTree
(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 TypeMethodDescriptionprivate Map
<Integer, SpanningTreeAlgorithm.SpanningTree<E>> calculateSpanningTrees
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> affectedLabels) Updates the map containing the MSTs for every subset of the partition.calculateSubtreesOfVertices
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTree, Set<Integer> affectedLabels) Updates the map containing the subtrees of all vertices in the graph with respect to the MST in the partition and returns them in map.executeNeighborhoodOperation
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<Integer, V> improvementGraphVertexMapping, Map<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, Integer> pathExchangeVertexMapping, Map<V, Pair<Set<V>, Double>> subtrees, GraphWalk<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, DefaultWeightedEdge> cycle) Executes the move operations induced by the calculated cycle in the improvement graph.Computes a capacitated spanning tree.Calculates an initial solution depending on whether an initial solution was transferred while construction of the algorithm.subtree
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Set<V> modifiableSet, V v, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTree) Calculates the subtree ofv
with respect to the MST given inpartitionSpanningTree
.
-
Field Details
-
lengthBound
private final int lengthBoundthe maximal length of the cycle in the neighborhood -
bestImprovement
private final boolean bestImprovementcontains whether the best (if true) or the first improvement (if false) is returned in the neighborhood search -
numberOfOperationsParameter
private final int numberOfOperationsParameterthe number of the most profitable operations considered in the GRASP procedure for the initial solution. -
initialSolution
the initial solution -
useVertexOperation
private final boolean useVertexOperationcontains whether the local search uses the vertex operation -
useSubtreeOperation
private final boolean useSubtreeOperationcontains whether the local search uses the subtree operation -
useTabuSearch
private final boolean useTabuSearchcontains whether a tabu search is used -
tabuTime
private final int tabuTimethe tabu time that is the number of iterations an element is in the tabu list -
upperLimitTabuExchanges
private final int upperLimitTabuExchangesthe upper limit of non-improving exchanges, this is the stopping criterion in the tabu search -
isAlgorithmExecuted
private boolean isAlgorithmExecutedcontains whether the algorithm was executed
-
-
Constructor Details
-
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 graphroot
- the designated root of the CMSTcapacity
- the edge capacity constraintdemands
- the demands of the verticeslengthBound
- the length bound of the cycle detection algorithmnumberOfOperationsParameter
- the number of operations that are considered in the randomized Esau-Williams algorithmEsauWilliamsCapacitatedMinimumSpanningTree
@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 solutiongraph
- the base graphroot
- the designated root of the CMSTcapacity
- the edge capacity constraintdemands
- the demands of the verticeslengthBound
- 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 graphroot
- the designated root of the CMSTcapacity
- the edge capacity constraintdemands
- the demands of the verticeslengthBound
- the length bound of the cycle detection algorithmbestImprovement
- contains whether the best (if true) or the first improvement (if false) is returned in the neighborhood searchnumberOfOperationsParameter
- the number of operations that are considered in the randomized Esau-Williams algorithmEsauWilliamsCapacitatedMinimumSpanningTree
@see EsauWilliamsCapacitatedMinimumSpanningTreeuseVertexOperation
- contains whether the local search uses the vertex operationuseSubtreeOperation
- contains whether the local search uses the subtree operationuseTabuSearch
- contains whether a tabu search is usedtabuTime
- the tabu time that is the number of iterations an element is in the tabu listupperLimitTabuExchanges
- 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 solutiongraph
- the base graphroot
- the designated root of the CMSTcapacity
- the edge capacity constraintdemands
- the demands of the verticeslengthBound
- the length bound of the cycle detection algorithmbestImprovement
- contains whether the best (if true) or the first improvement (if false) is returned in the neighborhood searchuseVertexOperation
- contains whether the local search uses the vertex operationuseSubtreeOperation
- contains whether the local search uses the subtree operationuseTabuSearch
- contains whether a tabu search is usedtabuTime
- the tabu time that is the number of iterations an element is in the tabu listupperLimitTabuExchanges
- the upper limit of non-improving exchanges, this is the stopping criterion in the tabu search
-
-
Method Details
-
getCapacitatedSpanningTree
Description copied from interface:CapacitatedSpanningTreeAlgorithm
Computes a capacitated spanning tree.- Specified by:
getCapacitatedSpanningTree
in interfaceCapacitatedSpanningTreeAlgorithm<V,
E> - Specified by:
getCapacitatedSpanningTree
in classAbstractCapacitatedMinimumSpanningTree<V,
E> - Returns:
- a capacitated spanning tree
-
getInitialSolution
private AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation getInitialSolution()Calculates an initial solution depending on whether an initial solution was transferred while construction of the algorithm. If no initial solution was proposed, the algorithm of Esau-Williams is used.- Returns:
- an initial solution
-
executeNeighborhoodOperation
private Pair<Set<Integer>,Set<V>> executeNeighborhoodOperation(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<Integer, V> improvementGraphVertexMapping, Map<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, Integer> pathExchangeVertexMapping, Map<V, Pair<Set<V>, Double>> subtrees, GraphWalk<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, DefaultWeightedEdge> cycle) Executes the move operations induced by the calculated cycle in the improvement graph. It returns the set of labels of the subsets that were affected by the move operations.- Parameters:
improvementGraphVertexMapping
- the mapping from the index of the improvement graph vertex to the correspondent vertex in the base graphpathExchangeVertexMapping
- the mapping from the improvement graph pseudo vertices to their subset that they representsubtrees
- the map containing the subtree for every vertexcycle
- the calculated cycle in the improvement graph- Returns:
- the set of affected labels of subsets that were affected by the move operations
-
calculateSpanningTrees
private Map<Integer,SpanningTreeAlgorithm.SpanningTree<E>> calculateSpanningTrees(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> affectedLabels) Updates the map containing the MSTs for every subset of the partition.- Parameters:
partitionSpanningTrees
- the map containing the MST for every subset of the partitionaffectedLabels
- the labels of the subsets of the partition that were changed due to the multi-exchange- Returns:
- the updated map containing the MST for every subset of the partition
-
calculateSubtreesOfVertices
private Map<V,Pair<Set<V>, calculateSubtreesOfVerticesDouble>> (AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTree, Set<Integer> affectedLabels) Updates the map containing the subtrees of all vertices in the graph with respect to the MST in the partition and returns them in map.- Parameters:
subtrees
- the subtree map to updatepartitionSpanningTree
- the map containing the MST for every subset of the partitionaffectedLabels
- the labels of the subsets of the partition that were changed due to the multi-exchange- Returns:
- the updated map of vertices to their subtrees
-
subtree
private Pair<Set<V>,Double> subtree(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Set<V> modifiableSet, V v, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTree) Calculates the subtree ofv
with respect to the MST given inpartitionSpanningTree
.- Parameters:
v
- the vertex to calculate the subtree forpartitionSpanningTree
- the map from labels to spanning trees of the partition.- Returns:
- the subtree of
v
with respect to the MST given inpartitionSpanningTree
.
-