The Graph Upper Bound command of the Algorithms menu computes the upper bound or maximum value of the hexagonal adjacency score for the current project.
The formulation maximizes the adjacencies between departments and between a department and the outside, subject to the constraint that each department must have exactly six neighbors. These neighboring departments can be the artificial outside department. If a department has at least one outside department as a neighbor the relationship with the outside is satisfied and included in the objective function. In the original formulation all the adjacencies are binary variables, except the adjacencies with the outside department that are integer. To compute the graph upper bound all integer and binary variables are relaxed to their continuous equivalent, i.e. a linear relaxation is used. For further information see the formulation in Graph Algorithms and Goetschalckx (1992).
Since the computation of the upper bound may require a significant amount of time, the program allows you to limit the maximum execution time with the Time Limit command of the Edit.