Handling dense columns in Interior-Point Methods

Authors

  • Catalina J. Villalba
  • Aurelio R.L. Oliveira

DOI:

https://doi.org/10.5540/03.2023.010.01.0060

Keywords:

Linear programming, Interior-point methods, Preconditioner

Abstract

The Interior-Point methods are a type of method used to solve linear programming problems that require solving linear systems. In situations where the constraint matrix has dense columns, it is essential to find an efficient way to solve computationally these systems in order to avoid memory issues or increase the number of operations. This project proposes a precondi- tioner to handle this issue, and it provides both theoretical predictions and computational tests to demonstrate its effectiveness.

Downloads

Download data is not yet available.

Author Biographies

Catalina J. Villalba

UNICAMP, Campinas, SP

Aurelio R.L. Oliveira

UNICAMP, Campinas, SP

References

K. D. Andersen. “A modified Schur-complement method for handling dense columns in interior-point methods for linear programming”. In: ACM Transactions on Mathematical Soft-ware (TOMS) 22.3 (1996), pp. 348–356. doi: 10.1145/232826.232937.

J. Castro. “Minimum-distance controlled perturbation methods for large-scale tabular data protection”. In: European Journal of operational Research 171.1 (2006), pp. 39–52. doi: 10.1016/j.ejor.2004.08.034.

J. Czyzyk et al. “PCx: an interior-point code for linear programming”. In: Optimization Methods and Software 11.1-4 (1999), pp. 397–430. doi: 10.1080/10556789908805757.

D. Goldfarb and K. Scheinberg. “A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming”. In: Mathematical Programming 99.1 (2004), pp. 1–34. doi: 10.1007/s10107-003-0377-7.

J. Gondzio. “Interior point methods 25 years later”. In: European Journal of Operational Research 218.3 (2012), pp. 587–601. doi: 10.1016/j.ejor.2011.09.017.

J. Gondzio. “Splitting dense columns of constraint matrix in interior point methods for large scale linear programming”. In: Optimization 24.3-4 (1992), pp. 285–297. doi: 10.108/02331939208843796.

E. G Ng and B. W. Peyton. “Block sparse Cholesky algorithms on advanced uniprocessor computers”. In: SIAM Journal on Scientific Computing 14.5 (1993), pp. 1034–1056. doi: 10.1137/0914063.

R. J. Vanderbei. “Splitting dense columns in sparse linear systems”. In: Linear Algebra and its Applications 152 (1991), pp. 107–117. doi: 10.1016/0024-3795(91)90269-3.

Downloads

Published

2023-12-18

Issue

Section

Trabalhos Completos