An interior point method for bordered block-diagonal linear programs

作     者：Grigoriadis, MD Khachiyan, LG 

作者机构：Department of Computer Science Hill Center Rutgers University New Brunswick NJ 08903 United States 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：1996年第6卷第4期

页      面：913-932页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：structured linear programs bordered block-diagonal problems interior point methods 

摘      要：This paper presents an interior point method for solving a bordered block-diagonal linear program which consists of a number of disjoint blocks coupled by a total of p variables and constraints. This structure includes the well-known block-angular and dual block-angular structures, as well as their special cases, such as staircase problems, generalized bounds, and multicommodity flows. When p is small relative to the total dimension of the problem, the method achieves a substantial speedup relative to other general-purpose methods.