Resolution of the problem of degeneracy in a primal and dual simplex algorithm

作     者：Dosios, K Paparrizos, K 

作者机构：UNIV MACEDONIA DEPT APPL INFORMAT THESSALONIKI 54006 GREECE 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：1997年第20卷第1期

页      面：45-50页

核心收录：

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

主　　题：linear programming pivoting rules simplex method exterior point simplex algorithm degeneracy 

摘      要：We resolve the problem of degeneracy in a recently developed primal-dual simplex algorithm for general linear programming problems (Chen et al., 1994). We show that the algorithm cycles. It is also shown that if ties are broken by an arbitrary cycling-free pivot rule of the classical primal simplex algorithm, then the refined primal-dual algorithm does not cycle. Exponential worst-case behaviour is shown and relations with other algorithms are discussed.