Handling dense columns in Interior-Point Methods
DOI:
https://doi.org/10.5540/03.2023.010.01.0060Keywords:
Linear programming, Interior-point methods, PreconditionerAbstract
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
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.
