Splitting dense columns of constraint matrix in interior point methods for large scale linear programming.

*(English)*Zbl 0814.65056Summary: A method is proposed for handling dense columns of the constraint matrix of large scale linear programming problems. Such columns are known to create dense windows in the matrices \(AA^ T\) which are inverted at every iteration of the interior point method. Consequently, the Cholesky factor of \(AA^ T\) becomes dense, which degrades the efficiency of the \(LP\) code. In the method considered, all dense columns are then split into shorter ones. One dense \(AA^ T\) window of large size is thus replaced with \(p\) windows each of size \(p\) times smaller, leading to a remarkable reduction of the number of nonzeros in the matrix to be inverted and in its Cholesky factor.

##### MSC:

65K05 | Numerical mathematical programming methods |

90C05 | Linear programming |

65F05 | Direct numerical methods for linear systems and matrix inversion |

90C06 | Large-scale problems in mathematical programming |

##### Keywords:

dense columns; Karmarkov’s projections; large scale linear programming; interior point method; Cholesky factor##### Software:

symrcm
Full Text:
DOI

##### References:

[1] | Adler I., ORSA Journal on Computing 1 pp 84– (1989) |

[2] | DOI: 10.1007/BF01587095 · Zbl 0682.90061 |

[3] | Choi I.C., ORSA Journal on Computing 2 pp 304– (1990) |

[4] | Duff I.S., Direct methods for sparse matrices (1989) · Zbl 0666.65024 |

[5] | Gay D. M., Electronic mail distribution of linear programming test problems, Mathematical Programming Socicty COAL Newsletter (1985) |

[6] | George A., Computer Solution of Large Sparse Positive Definite Systems (1981) · Zbl 0516.65010 |

[7] | DOI: 10.1007/BF02592025 · Zbl 0624.90062 |

[8] | Gill, P.E., Murray, W. and Saunders, M.A. 1988. ”A single-phase dual barrier method for linear programming”. Stan-ford: Stanford University. Report SOL 88-10, Systems Optimization Laboratory |

[9] | Golub G.H., Matrix Computations (1983) · Zbl 0559.65011 |

[10] | Gondzio J., An advanced implementation of Cholesky factorization for computing projections in interior point methods of large scale linear programming (1991) |

[11] | DOI: 10.1137/1031049 · Zbl 0671.65018 |

[12] | DOI: 10.1287/opre.39.5.757 · Zbl 0739.90048 |

[13] | Lustig, I.J, Marsten, R.E. and Shanno, D. F. 1990. On implementing Mehrotra’s predictor-corrector interior point method for linear programming, Technical Report SOR 90-03. 1990. Princeton: Department of civil Engineering and Operations Research, Princeton University, · Zbl 0771.90066 |

[14] | Mulvey, J. M. and Ruszczynski, A. 1990. A diagonal quadratic approximation method for large scale linear programs, Department of Civil Engineering and Operations Research, Princeton University. 091990. Princeton: Department of civil Engineering and Operations Research, Princeton University. |

[15] | DOI: 10.1145/355887.355893 · Zbl 0438.65035 |

[16] | DOI: 10.1287/moor.16.1.119 · Zbl 0729.90067 |

[17] | DOI: 10.1016/0024-3795(91)90269-3 · Zbl 0727.65034 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.