RT Journal Article
T1 Experiments with Active-Set LP Algorithms Allowing Basis Deficiency
A1 Hendrix, Eligius María Theodorus
A1 Guerrero-García, Pablo
K1 Programación lineal
AB n interesting question for linear programming (LP) algorithms is how to deal with solutions in which the number of nonzero variables is less than the number of rows of the matrix in standard form. An approach is that of basis deficiency-allowing (BDA) simplex variations, which work with a subset of independent columns of the coefficient matrix in standard form, wherein the basis is not necessarily represented by a square matrix. We describe one such algorithm with several variants. The research question deals with studying the computational behaviour by using small, extreme cases. For these instances, we must wonder which parameter setting or variants are more appropriate. We compare the setting of two nonsimplex active-set methods with Holmström’s TomLab LpSimplex v3.0 commercial sparse primal simplex commercial implementation. All of them update a sparse QR factorization in Matlab. The first two implementations require fewer iterations and provide better solution quality and running time.
PB IOAP-MDPI
YR 2022
FD 2022-12-23
LK https://hdl.handle.net/10630/25958
UL https://hdl.handle.net/10630/25958
LA eng
NO Guerrero-García P, Hendrix EMT. Experiments with Active-Set LP Algorithms Allowing Basis Deficiency. Computers. 2023; 12(1):3. https://doi.org/10.3390/computers12010003
NO This work has been funded by grant PID2021-123278OB-I00 from the Spanish Ministry of Science and Innovation. Partial funding for open access charge: Universidad de Málaga
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 19 ene 2026