forum.alglib.net

ALGLIB forum
It is currently Sun Dec 01, 2024 6:12 pm

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: slow minqpoptimize when I have a lot of linear constraints
PostPosted: Wed May 15, 2024 1:22 pm 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
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


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Wed May 15, 2024 1:40 pm 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
P.S. The version I use is 4.01.0.


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Wed May 15, 2024 2:22 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Thu May 16, 2024 12:39 pm 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
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 1653 times
Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Thu May 16, 2024 11:27 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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.


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Mon May 20, 2024 1:56 pm 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
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


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Mon May 20, 2024 8:56 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Tue May 21, 2024 7:21 am 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
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


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Tue May 21, 2024 9:16 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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.


Top
 Profile  
 
 Post subject: Re: slow minqpoptimize when I have a lot of linear constrain
PostPosted: Thu May 23, 2024 8:24 am 
Offline

Joined: Wed May 15, 2024 1:11 pm
Posts: 6
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group