[Scip] Slow LP re-optimization after branching

[Xavier Schepler]

Hi again,

I realized that in the LP files I sent to you,
there are a lot of extra artificial variables (at least one by constraint),
whereas in the first log I sent to you, there were only two artifical
variables for all constraints.
Please excuse me for that, I had to produce results using this
initialization, with smaller instances, for another purpose,
and I forgot to change the code before generating LP files.
If you need them, I will be able to generate the LP files with two
artificial variables next week.

Anyway, SCIPprintStatistics tells that, a 65000 * 20000 LP,
with at least 20000 artificial variables is solved in 300 sec at root node.

Then, during column generation, 6920 of 7200 seconds are spent reoptimising
LPs.
There are 35 column generation iterations.
All negative reduced cost columns are added at each iteration (full
pricing).

In a 7200 seconds run, 223 seconds were spent pricing.
Almost all the time was spent solving LPs ...
SCIPprintStatistics output :

Pricers            :   ExecTime  SetupTime      Calls       Vars
  problem variables:       0.00          -          0          0
  Exact pricer     :     223.51       0.01         34        605

LP                 :       Time      Calls Iterations  Iter/call
Iter/sec  Time-0-It Calls-0-It
  primal LP        :    6920.86         34     661444   19454.24
95.57       0.00          0
  dual LP          :      54.79          1      35700   35700.00
651.58       0.00          0

Column generation has not the time to terminate at root node.

Is the LP solved again and again from scratch ?

Best regards,

Xavier Schepler


2014-02-24 14:03 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com>:

> Dear doctor Timo,
>
> Thank you very much for your answer.
>
> Le 23/02/2014 14:36, Timo Berthold a écrit :
>
>  1. You imposed a time limit of half an hour to SCIP.
>>
> I get it ... This is what is causing "LP solver hit time limit" message ...
> The fact that this message appeared several times in different rows led me
> to a misunderstanding.
>
>  whenyou create them on your own, you should consider using the specialized
>>
>> versions of linear constraints (setppc, logicor, kanpsack...)
>>
> Thanks for your advice, I will create specialized versions of linear
> constraints.
>
>
>  3. You are not using SoPlex as LP solver, but Cplex. Also, you seem to do
>> some postprocessing with Cplex as standalone MIP solver.
>>
> In fact, CPLEX is the LP solver for 1 instances (strange 1.txt), and
> SoPlex for the 2 others.
>
>
>  4. Not to solve a 100kx100k LP within 20 minutes is unusual, unless it is
>> really ill-conditioned. It would be interesting to see how any LP solver
>> behaves on it standalone.
>> Is it possible that you write it to a file and upload it somewhere
>>
>>  2 LP files can be downloaded at this URL:
>
> http://www.filedropper.com/lpstar
>
> Note that, calling
>
> SCIPprintTransProblem
>
> produced an empty file (maybe because the problem is not transformed ?),
> so I used SCIPwriteMIP to  produce these files.
>
> On my computer, CPLEX solves each of these two instances in a little more
> than 10 minutes,
> when used independently in interactive mode.
>
>
>  5. It is conspicuous that your own output of initialization time pretty
>> much fits the difference between this 1/2 hour and the time SCIP needs for
>> the root LP. So might it be that this is called when SCIP is already
>> running and we just the output in different order because it comes via
>> different streams?
>> So or so, you might want to add a SCIP_CALL( SCIPprintStatistics(scip) )
>> after SCIP's termination to see where time went within SCIP.
>>
> From what this command outputs,  initialization time is not included into
> SCIP solving time.
>
> Best regards,
>
> Xavier
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140226/ad0ddc04/attachment.html>