forum.alglib.net
http://forum.alglib.net/

slow minqpoptimize when I have a lot of linear constraints
http://forum.alglib.net/viewtopic.php?f=2&t=4603		 Page 1 of 1
Author:  Argyris [ Wed May 15, 2024 1:22 pm ]
Post subject:  slow minqpoptimize when I have a lot of linear constraints
Hello,

I tried to solve a quadratic programming problem with linear equality constraints, and minqpoptimize takes so much time (~2.5 hours).
I have 1350354 variables and 2343648 linear equality constraints.
The algorithm I used is sparse-ipm with eps = 1e-4.
Also, I have enabled internal parallelism.

Could you please tell me, what can I do in order to reduce the time of execution?

Thanks,
Argyris
Author:  Argyris [ Wed May 15, 2024 1:40 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
P.S. The version I use is 4.01.0.
Author:  Sergey.Bochkanov [ Wed May 15, 2024 2:22 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi!

It is hard to tell without actually looking into your problem. Possible reasons are: (a) your problem is big and has too many dense entries, or (b) something in your problem (e.g. constraints degeneracy) slows down convergence of the solver.

Would you like to activate solver logging by means of alglib::trace_file("ipm","trace.log") and send me a trace.log file?

Sergey
Author:  Argyris [ Thu May 16, 2024 12:39 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi,

thanks a lot for your response.

I am sending you the trace.log file.
About the possible reasons you mentioned:
a) the constraint matrix contains rows of 2 or 4 nonzero entries only
b) how can I detect if such degeneracies exist and how can I eliminate these using alglib?

Thanks,
Argyris

Attachments:
trace.log [18.38 KiB]
Downloaded 1754 times
Author:  Sergey.Bochkanov [ Thu May 16, 2024 11:27 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
The solver seems to be ok, it took just 19 iterations to converge, it is ok for an interior point method. Anything beyond 100 iterations is a sign of potential issues, but 19 are ok.

Probably, it is about sparsity pattern of the problem. Depending on the pattern, the same amount of nonzeros can be very easy problem, or a very difficult one with terrible fill-in.

I would like to take a closer look at your problem. Would you like to send to my email the following info:
* linear term
* box constraints
* sparse quadratic term and sparse linear constraints

You can save linear term and box constraints to a CSV/TXT file. As for the sparse quantities (quadratic term and constraint matrices), you may either save them to CSV/TXT too as a coordinate/value arrays, or use alglib::sparseserialize() function that exports them directly from ALGLIB.
Author:  Argyris [ Mon May 20, 2024 1:56 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi,

the 3 txt files are 643 ΜΒ. How could I send these to you?
Also, the txt files containing the quadratic term and the linear constraints respectively seems to be weird. I have extracted them using alglib::sparseserialize() function as you said.

Thanks,
Argyris
Author:  Sergey.Bochkanov [ Mon May 20, 2024 8:56 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi!

Can you upload it to some cloud drive, possibly with ZIP compression, and send a download link to my email address (one that I used to contact you directly)?

Also, please include both constraint matrix AND constraint right hand sides (or ranges AL, AU, if you used modern two-sided format).

Sergey
Author:  Argyris [ Tue May 21, 2024 7:21 am ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi,

I have sent you a download link to your email. There are 3 txt files in the folder, containing the linear term, the quadratic term and the linear constraints respectively. All of the linear constraints are of the type Ax=0.

Argyris
Author:  Sergey.Bochkanov [ Tue May 21, 2024 9:16 pm ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi! Received.

Quote:
Also, the txt files containing the quadratic term and the linear constraints respectively seems to be weird

That's ok, it is not a human-readable format. A special binary-to-text format that uses only alphanumerics and several special chars that do not interfere with XML, UTF8, Windows/Unix line breas and other portability issues. Can be moved between different ALGLIB versions, even written in different languages.

I have checked ALGLIB performance on your problem. Such a long running time is partly because your problem is big. You have quite a lot tightly interacting constraints, and a non-trivial quadratic factor too.

However, I see a potential point for improvement. Your problem has A LOT doubleton rows (equality constraints with just two elements) that can be used to factor out some variables during presolve. Such many doubletons in one place are rarely seen. That kind of presolve heuristic has mixed effects on the running time because it decreases cols count but makes them more dense, that's why it is not implemented in the presolver yet. However, I can spend some time looking into this direction, it is an interesting line of investigation.

May I ask you, do you have any deadline for the project that involves this problem? I plan to release ALGLIB 4.02 this week, so I am quite busy over the next several days :) However, after the release I will be happy to experiment with your problem. I do not expect a 10x improvement in the running time, but maybe we will be able to make it 2x faster. Not 100% sure that we will make it, but it looks possible.
Author:  Argyris [ Thu May 23, 2024 8:24 am ]
Post subject:  Re: slow minqpoptimize when I have a lot of linear constrain
Hi,

ok no problem, I'll be waiting a response next week then. As soon as possible it would be better for me. I understand that it's something that takes time to be done, though.

Thanks,
Argyris
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/