Starting the dual revised simplex method from an advanced basis
Contributed talk at the 23rd International Symposium on Mathematical Programming, Bordeaux, France, 1-6 July 2018
Julian Hall and Ivet Galabova
Abstract
When the dual revised simplex method for linear programming (LP) problems is started from a basis of slack variables, it is typically accelerated by the use of steepest edge weights on the primal infeasibilities. Crash techniques for the simplex method attempt to find a non-slack basis so that the time overall time required to solve the LP problem is reduced, and are popular when using the primal revised simplex method. In the context of the high performance linear optimization solver HiGHS, this talk will discuss several crash procedures for the dual revised simplex method, their consequences for steepest edge strategies, and the overall effect on solution time. When solving MIP problems using branch-and-bound, the dual simplex method is started from the optimal basis of an LP relaxation. Techniques for computing (approximate) steepest edge weights in this case will be explored.
Slides:
| ISMP18.pdf |