Groupe d’études et de recherche en analyse des décisions

G-2009-15

Improved Primal Simplex Version 3: Cold Start, Generalization for Bounded Variable Problems and a New Implementation

, et

The improved primal simplex (IPS) method has been proposed by Elhallaoui et al. (2008). We rewrite the theory of IPS for a cold start with an initial feasible solution instead of an initial basic feasible solution. This allows us to use an heuristic first - optimization second strategy. We generalize this algorithm so that it can handle bounds on variables. We show that variables at upper bounds augment degeneracy, and consequently, increase performance of IPS compared to CPLEX. We simplify the implementation by replacing the UMFPACK (Davis and Duff, 1997) procedure by certain modules of the CPLEX library. This allows the user to work with only one commercial software package. We obtain a reduction factor of solution time of 20 on fleet assignment instances with bounded variables.

, 17 pages