Experimental investigations in combining primal dual interior point method and simplex based LP solvers

The use of a primal dual interior point method (PD) based optimizer as a robust linear programming (LP) solver is now well established. Instead of replacing the sparse simplex algorithm (SSX), the PD is increasingly seen as complementing it. The progress of PD iterations is not hindered by the degeneracy or stalling problem of SSX, indeed it reaches the near optimum solution very quickly. The SSX algorithm, in contrast, is not affected by the numeral instabilities which slow down the convergence of the PD near the optimal face. If the solution to the LP problem is non-unique, the PD algorithm converges to an interior point of the solution set while the SSX algorithm finds an extreme point solution. To take advantage of the attractive properties of both the PD and the SSX, we have designed a hybrid framework whereby crossover from PD to SSX can take place at any stage of the PD optimization run. The crossover to SSX involves the partition of the PD solution set to active and dormant variables. In this paper we examine the practical difficulties in partitioning the solution set, we discuss the reliability of predicting the solution set partition before optimality is reached and report the results of combining exact and inexact prediction with SSX basis recovery.