zbMATH — the first resource for mathematics

Prior reduced fill-in in solving equations in interior point algorithms. (English) Zbl 0767.90044
Summary: The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are \(Ax\leq b\), \(x\geq 0)\), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of \((AA^ T)\). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of \((A^ TA)\). Depending on the structure of the matrix \(A\), one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints.

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] Arantes, J; Birge, J, Computational results using interior point methods for two-stage stochastic programs, ()
[2] Barnes, E.R, A variation on Karmarkar’s algorithm for solving linear programming problems, Math. programming, 36, 174-182, (1990) · Zbl 0626.90052
[3] Den Hertog, D; Roos, C, A survey of search directions in interior point methods for linear programming, () · Zbl 0739.90041
[4] Dikin, I.I, Iterative solution of problems of linear and quadratic programming, Dokl. akad. nauk SSSR, 174, 747-748, (1967) · Zbl 0189.19504
[5] Gay, D.M, Electronic mail distribution of linear programming test problems, Mathematical programming society COAL newsletter, 13, 10-12, (1985)
[6] Gonzaga, C.C, Search directions for interior linear programming methods, () · Zbl 1146.90038
[7] Karmarkar, N, A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[8] Vanderbei, R.J; Meketon, M.S; Freedman, B.A, A modification of Karmarkar’s linear programming algorithm, Algorithmica, 1, 395-407, (1986) · Zbl 0626.90056
[9] Vanderbei, R.J, Dense columns and interior point methods for LP, () · Zbl 0825.90681
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.