Experiments with Active-Set LP Algorithms Allowing Basis Deficiency
An 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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-12-01
|
| Series: | Computers |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-431X/12/1/3 |
| _version_ | 1797444115719258112 |
|---|---|
| author | Pablo Guerrero-García Eligius M. T. Hendrix |
| author_facet | Pablo Guerrero-García Eligius M. T. Hendrix |
| author_sort | Pablo Guerrero-García |
| collection | DOAJ |
| description | An 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 <i>TomLab</i> <span style="font-variant: small-caps;">LpSimplex v3.0</span> commercial sparse primal simplex commercial implementation. All of them update a sparse QR factorization in <span style="font-variant: small-caps;">Matlab</span>. The first two implementations require fewer iterations and provide better solution quality and running time. |
| first_indexed | 2024-03-09T13:07:54Z |
| format | Article |
| id | doaj.art-a938139f279c4ffeae1cf9ac8c309378 |
| institution | Directory Open Access Journal |
| issn | 2073-431X |
| language | English |
| last_indexed | 2024-03-09T13:07:54Z |
| publishDate | 2022-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Computers |
| spelling | doaj.art-a938139f279c4ffeae1cf9ac8c3093782023-11-30T21:46:19ZengMDPI AGComputers2073-431X2022-12-01121310.3390/computers12010003Experiments with Active-Set LP Algorithms Allowing Basis DeficiencyPablo Guerrero-García0Eligius M. T. Hendrix1Applied Mathematics, Universidad de Málaga, 29071 Málaga, SpainComputer Architecture, Universidad de Málaga, 29071 Málaga, SpainAn 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 <i>TomLab</i> <span style="font-variant: small-caps;">LpSimplex v3.0</span> commercial sparse primal simplex commercial implementation. All of them update a sparse QR factorization in <span style="font-variant: small-caps;">Matlab</span>. The first two implementations require fewer iterations and provide better solution quality and running time.https://www.mdpi.com/2073-431X/12/1/3linear programmingphase Ibasis deficiency-allowing simplex variationsnonsimplex active-set methodFarkas lemmasparse matrices |
| spellingShingle | Pablo Guerrero-García Eligius M. T. Hendrix Experiments with Active-Set LP Algorithms Allowing Basis Deficiency Computers linear programming phase I basis deficiency-allowing simplex variations nonsimplex active-set method Farkas lemma sparse matrices |
| title | Experiments with Active-Set LP Algorithms Allowing Basis Deficiency |
| title_full | Experiments with Active-Set LP Algorithms Allowing Basis Deficiency |
| title_fullStr | Experiments with Active-Set LP Algorithms Allowing Basis Deficiency |
| title_full_unstemmed | Experiments with Active-Set LP Algorithms Allowing Basis Deficiency |
| title_short | Experiments with Active-Set LP Algorithms Allowing Basis Deficiency |
| title_sort | experiments with active set lp algorithms allowing basis deficiency |
| topic | linear programming phase I basis deficiency-allowing simplex variations nonsimplex active-set method Farkas lemma sparse matrices |
| url | https://www.mdpi.com/2073-431X/12/1/3 |
| work_keys_str_mv | AT pabloguerrerogarcia experimentswithactivesetlpalgorithmsallowingbasisdeficiency AT eligiusmthendrix experimentswithactivesetlpalgorithmsallowingbasisdeficiency |