0000599: sactivesets.sasrebuildbasis could be optimized for sparse constraint matrices

Viewing Issue Simple Details [ Jump to Notes ]

[ View Advanced ] [ Issue History ] [ Print ]

Category

Severity

Reproducibility

Date Submitted

Last Update

0000599

[ALGLIB] Optimization

feature

have not tried

2014-02-24 22:06

2018-01-02 17:22

Reporter

nlagerr

View Status

public

Assigned To

SergeyB

Priority

normal

Resolution

open

Status

assigned

Product Version

3.8.1

Summary

0000599: sactivesets.sasrebuildbasis could be optimized for sparse constraint matrices

Description

We are using the Alglib QP solver and were experiencing some performance issues. I profiled the application and it turns out most time was spent in the code that reorthogonalizes the constraint matrices. The documentation already points out the algorithm does not scale well in the number of constraints.

For our particular QP, the constraint matrices are very sparse. I managed to get significant performance improvements by rewriting sasrebuildbasis to exploit this fact. I implemented a vector that:
- Inserts elements in O(1)
- Removes elements in O(1)
- Computes the dot product in O(nr-non-zeros)
This data structure does use more memory than normal matrices to achieve these characteristics.

If you are interested in implementing the above functionality and would like to have a reference implementation in C#, please contact me via email.

Additional Information

Programming language

Attached Files

Relationships

Notes
(0000067) nlagerr (reporter) 2014-06-02 17:37	I am wondering, did my feature request give rise to 0000607? I think you are right that we ought to be using BLEIC-QP instead of Cholesky-QP. As soon as I have time I will experiment with it. But I was under the impression both solvers needed to run sasrebuildbasis, am I right?

Issue History
Date Modified	Username	Field	Change
2014-02-24 22:06	nlagerr	New Issue
2014-02-24 22:06	nlagerr	Programming language	=> C#
2014-06-02 17:37	nlagerr	Note Added: 0000067
2018-01-02 17:22	SergeyB	Status	new => assigned
2018-01-02 17:22	SergeyB	Assigned To	=> SergeyB

Mantis 1.1.6[^]