A CLUSTERING HEURISTIC TO DETECT STAIRCASE STRUCTURES IN LARGE-SCALE LINEAR-PROGRAMMING MODELS

作     者：JAYAKUMAR, MD RAMASESH, RV 

作者机构：TEXAS CHRISTIAN UNIVFT WORTHTX 76129 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：1994年第76卷第1期

页      面：229-239页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：CLUSTERING HEURISTIC FOR DECOMPOSITION LARGE SCALE LINEAR PROGRAMMING MATHEMATICAL PROGRAMMING 

摘      要：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, we 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 it linear time of the problem size. We 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.