Relationship Tuple
The relationship tuple indicates on how many departments the adjusted relationship is based. Possible options are null, unary, binary, and ternary. The departments then enter the graph by decreasing adjusted relationship. The null tuple indicates that the next department will be chosen at random, without any regard to its relationships with other departments. The unary adjusted relationship sums the relationships of a department with all other departments. The binary adjusted relationship is the relationship between the current department and one other department. The ternary adjusted relationship is the relationship between the current department and two other departments.
Graph Improvement
After the original graph is constructed three possible improvement steps can be executed. The options are none, or steepest descent exchange with two exchange or three exchange.
None does not execute an improvement step.
Two Exchange attempts to improve the graph in a steepest descent manner by attempting two department exchanges. It computes the savings generated by removing two departments out of the graph and swapping their position. The savings are based on an increase in the adjacency score. The exchange with the largest savings among all possible combinations of two departments is determined and if these savings are positive then those two departments are exchanged. The process repeats until no further improvements can be made.
Three Exchange attempts to improve the graph in a steepest descent manner by attempting three department exchanges. It computes the savings generated by removing three departments out of the graph and swapping their position. The savings are based on an increase in the adjacency score. The exchange with the largest savings among all possible combinations of three departments is determined and if these savings are positive then those three departments are exchanged. The process repeats until no further improvements can be made.
Computational processing time increases sharply with the amount of improvement processing.
Department Location Tie Breaker
When locating a department in the partial adjacency graph often alternative positions are possible. Two possible tie breaker rules can be used. The first one is Random, which places the department randomly in one of the alternative positions based on a random number. The second one is Centroid Seeking that places the department in the position closest to the centroid of the current (partial) adjacency graph. If there are still alternative positions after the first tie breaker then a position is chosen at random.
For further information see Goetschalckx (1992).