A linear programming decomposition focusing on the span of the nondegenerate columns

摘要: Abstract The improved primal simplex (IPS) was recently developed by Elhalaloui et al. to take advantage of degeneracy when solving linear programs with the simplex. It implements a dynamic constraint reduction based on compatible columns, i.e., those that belong span given subset basic columns including nondegenerate ones. identification variables may however be computationally costly and large number are solved enlarge variables. In this article, we first show how positive edge criterion Raymond et al. can included in IPS for fast Our algorithm then proceeds through series augmentation phases until optimality is reached. phase, identify focus them make quick progress toward optimality. During an compute one greatest normalized improving direction select should considered reduced problem. Compared IPS, program find involves data original matrix. This new tested over Mittelmann’s benchmark programming instances arising from industrial applications. results outperforms CPLEX most highly degenerate which sufficient nonbasic compatible. contrast, has difficulties eleven largest Mittelmann instances.