<div dir="ltr"><div><div><div>Good evening,<br></div><div><br></div><div><br></div><div>Please find 2 "hard" LP instances (don't solve them as MIP, first convert them to LP) :<br><br></div>
<div><a href="http://www.4shared.com/archive/s1NOU9gyce/ills_LPtar.html" target="_blank">http://www.4shared.com/archive/s1NOU9gyce/ills_LPtar.html</a><br><br></div>I removed all the extra artificial variables.<br><br></div>
<div>deg5.lp<br>
75 000 * 130 000<br></div>> 1 800 s. CPLEX 12.6<br></div><div>265 000 simplex iterations<br><br></div><div>deg7.lp<br></div><div>77 000 * 135 000<br></div><div>> 2 400 s. CPLEX 12.6<br></div><div>? simplex iterations (I had to stop)<br>
<br></div><div>Best regards,<br><br></div><div>Xavier<br></div><div><br><br>
</div><div><br></div><div><br></div><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">2014-02-26 19:46 GMT+01:00 Gerald Gamrath <span dir="ltr"><<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Xavier,<br>
<div class=""><br>
> I realized that in the LP files I sent to you,<br>
> there are a lot of extra artificial variables (at least one by<br>
> constraint),<br>
> whereas in the first log I sent to you, there were only two artifical<br>
> variables for all constraints.<br>
> Please excuse me for that, I had to produce results using this<br>
> initialization, with smaller instances, for another purpose,<br>
> and I forgot to change the code before generating LP files.<br>
> If you need them, I will be able to generate the LP files with two<br>
> artificial variables next week.<br>
</div>yes, that would be good.<br>
<div class="">><br>
> Anyway, SCIPprintStatistics tells that, a 65000 * 20000 LP,<br>
> with at least 20000 artificial variables is solved in 300 sec at root<br>
> node.<br>
><br>
> Then, during column generation, 6920 of 7200 seconds are spent<br>
> reoptimising LPs.<br>
> There are 35 column generation iterations.<br>
> All negative reduced cost columns are added at each iteration (full<br>
> pricing).<br>
><br>
> In a 7200 seconds run, 223 seconds were spent pricing.<br>
> Almost all the time was spent solving LPs ...<br>
> SCIPprintStatistics output :<br>
><br>
> Pricers : ExecTime SetupTime Calls Vars<br>
> problem variables: 0.00 - 0 0<br>
> Exact pricer : 223.51 0.01 34 605<br>
><br>
> LP : Time Calls Iterations Iter/call<br>
> Iter/sec Time-0-It Calls-0-It<br>
> primal LP : 6920.86 34 661444 19454.24<br>
> 95.57 0.00 0<br>
> dual LP : 54.79 1 35700 35700.00<br>
> 651.58 0.00 0<br>
><br>
> Column generation has not the time to terminate at root node.<br>
><br>
> Is the LP solved again and again from scratch ?<br>
<br>
</div>Yes, this looks like SCIP is solving the LP from scratch over and over<br>
again. This is a known issue which will be fixed in the upcoming SCIP<br>
release. SCIP applies an objective limit for LP solving, which means<br>
that the dual simplex stops when reaching the objective limit. Normally,<br>
the current node could be cut off, in a branch-and-price context,<br>
pricing has to be done, but this can also be done with the current dual<br>
solution values. Actually, you can see this as a kind of stabilization.<br>
On the other hand, the current basis is then only dual feasible and<br>
adding new columns leads to loosing the dual feasibility as well and the<br>
LP needs to be reoptimized from scratch. In particular with as many<br>
variables as you have, this can slow down your LP solving significantly.<br>
<br>
We are working hard on finishing the release until tomorrow, please<br>
check it out then and try it. It should resolve your problem and reduce<br>
the LP reoptimization time.<br>
<br>
Best,<br>
Gerald<br>
<br>
</blockquote></div><br></div>