Mantis Bugtracker

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID 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 C#
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[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker