The most frequent application of the quadratic assignment problem has been in facility layout, which is concerned with locating the activities or departments of an organization in a fixed set of locations such that those activities with the strongest interrelationships are closest to each other. Early attempts to explain the varying performance of optimal and heuristic solution procedures on different layout problems focused on a univariate complexity measure such as the coefficient of variation. Recently, a multivariate measure for assessing the complexity of the quadratic assignment problem (QAP) formulation of the facility layout problem has been proposed. This paper introduces a new thresholding procedure for capturing critical relationship information, expands the eight components of the multivariate complexity measure by adding two new components, demonstrates a new solution value bound and experimentally determines the effect on solution quality of using either one of two heuristic solution procedures versus an optimal procedure. This result is important because it enables layout planners to determine in advance the likelihood of obtaining an optimal solution. It also tells them which problem characteristics are important and their relative weights in determining the solution outcome.