A clustering heuristic to detect staircase structures in large scale linear programming models

The ‘staircase’ structure is one of the more frequently found structures in large scale linear programs. It is known that the staircase structured problems lend themselves to efficient solution through decomposition based procedures. However, in many large scale problems any underlying structure may be obscured by getting imbedded into other more obvious structures. This paper addresses the identification of the underlying staircase structure in the rectangular matrices of large scale linear programs (LSLPs). The problem is known to be computationally hard. To solve this problem, the authors propose a heuristic algorithm based on the rank order clustering procedure. The results from the application of this algorithm to a number of test problems of known structure indicate that it runs in linear time of the problem size. The authors demonstrate the effectiveness of the algorithm through its ability to identify the correct number of diagonal subproblems that make up the staircase structure in the coefficient matrices of the LSLPs of two test sets: the first, collected from the public domain software server, NETLIB; and the second, randomly generated.