A DANTZIG-WOLFE-LIKE VARIANT OF KARMARKAR INTERIOR-POINT LINEAR-PROGRAMMING ALGORITHM

• 成果类型: Article
• 署名作者: TODD, MJ
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.38.6.1006
• 发表日期: 1990
• 页码: 1006-1018
• 关键词: programming; LINEAR; algorithms; Dantzig-Wolfe decomposition; INTERIOR-POINT METHOD; SIMPLEX PIVOT RULE

摘要

We show that a variant of Karmarkar's projective algorithm for linear programming can be viewed as following the approach of Dantzig-Wolfe decomposition. At each iteration, the current primal feasible solution generates prices which are used to form a simple subproblem. The solution to the subproblem is then incorporated into the current feasible solution. With a suitable choice of stepsize a constant reduction in potential function is achieved at each iteration. We also use our analysis to motivate a new primal simplex pivot rule that is closely related to rules used by E. Klotz and L. Schrage.