AN INVESTIGATION OF INTERIOR-POINT ALGORITHMS FOR THE LINEAR TRANSPORTATION PROBLEM

Recently, Resende and Veiga [SIAM J. Optim., 3 (1993), pp. 516-537] pr oposed an efficient implementation of the dual affine (DA) interior-po int algorithm for the solution of Linear transportation models with in teger costs and right-hand-side coefficients, This procedure incorpora tes a preconditioned conjugate gradient (PCG) method for solving the l inear system that is required in each iteration of the DA algorithm. I n this paper, we introduce an incomplete QR decomposition (IQRD) preco nditioning for the PCG algorithm, Computational experience shows that the IQRD preconditioning is appropriate in this instance and is more e fficient than the preconditioning introduced by Resende and Veiga. We also show that the primal dual (PD) and the predictor corrector (PC) i nterior-point algorithms can also be implemented by using the same typ e of technique. A comparison among these three algorithms is Included and indicates that the PD and PC algorithms are more appropriate for t he solution of transportation problems with well-scaled cost and right -hand-side coefficients and assignment problems with poorly scaled cos t coefficients. On the other hand, the DA algorithm seems to be more e fficient for assignment problems with well-scaled cost coefficients an d transportation problems whose cost coefficients are badly scaled.