[Clp] question about performance on a strange problem

[Ivo Stefanov]

Hello, I am trying to use Clp to solve a linear problem, but it seems to take too long (I have not actually received a solution in several days).  The problem is not too big (~30 000 variables and about the same number of constraints), but it has a fairly large dense square block of about 10 000 x 10 000 variables.  Because of this block the thing takes huge amount of memory, but that's manageable for now - the problem is that I don't seem to be getting anywhere near a solution.  
  I have tried both the primal() and dual() algorithms with no success.   I know it is hard to tell anything without the exact problem being available, but since the .lp file is 700mb+ I do not have it uploaded anywhere at the moment (and it takes quite a lot time to load anyways).  What I have noticed so far while working with this problem is that the performance of the dual algorithm gets worse with the increase of the size of the dense block, however not always in the same way.
  Certain types of input data may increase the block in terms of rows (number of constraints) and others - in terms of columns (number of variables). The increase in columns seems to be the more problematic part (for example, 10 000 x 500 is fairly trivial, while 10 000 x 10 000 is impossible so far; on the other hand, 50 000 x 500 is still solve-able in a very reasonable timeframe - faster than, for example, 10 000 x 2500).   
  I am wondering which one of the 2 options is more likely to be correct:  1. I am using the solver improperly and there is a way to actually have this passing much faster.  2. I should focus on ways to reformulate the problem (maybe find a way to break the dense block into something more sparse?) rather than trying to fine-tune the settings of the solver.  
  Any tips on the solver usage for such a problem will be greatly appreciated.  
  Thank you very much! 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20181203/0c9b29a0/attachment.html>