[Scip] Pricer regenerates the same column
Gerald Gamrath
gamrath at zib.de
Wed May 21 17:00:15 CEST 2014
Dear Marco, Ambros,
just a short comment: There are also methods in SCIP to compare numbers
using the primal feasibility tolerance, e.g. SCIPisFeasPositive().
Unfortunately, the equivalent for the dual feasibility tolerance was
missing, but will be contained in the next release. Until then, the best
way would be to do as Ambros suggested: check that the reduced costs are
smaller than -SCIPdualfeastol(), with a hard "<" comparison. This would
do what you need without changing any epsilon values in SCIP.
Best,
Gerald
On 21.05.2014 16:14, Marco Casula wrote:
> Dear Ambros,
>
> both parameters were indeed set at e-06; i lowered both as you
> suggested and so far the pricer hasn't got stuck on any instance.
> Thanks for the suggestion!
>
> Best,
> Marco
>
> 2014-05-21 14:48 GMT+02:00 Ambros Gleixner <gleixner at zib.de
> <mailto:gleixner at zib.de>>:
>
> Dear Marco,
>
> I think changing numerics/epsilon is not the best idea. If I
> understand correctly, you are using SCIPisPositive() and friends
> to check the sign of your reduced costs.
>
> Instead you should use the primal and dual feasibility tolerance
> of the LP solver, which is returned by the methods SCIPlpfeastol()
> and SCIPdualfeastol(). (The corresponding parameters are
> numerics/lpfeastol and numerics/dualfeastol.) I believe you want
> to compare your reduced costs to SCIPdualfeastol().
>
> Changing numerics/epsilon has many other side effects, so I would
> really not recommend it.
>
> ambros
>
>
>
> On 05/21/2014 10:41 AM, Marco Casula wrote:
>
> Dear Gerald,
>
> thanks for the input (also, thanks to Martin for ccing me his
> answer to
> Cristina).
> In the end, I think it was just a matter of solver tolerance:
> I am using
> SoPlex 1.7.2, and though I believed its tolerance to be e-12,
> by means
> of display/lpinfo I noticed a number of tolerance parameters
> set to
> e-06. Since I am not sure how to change the value of all of
> them, I
> lowered scip "numerics/epsilon" from the default e-09 to e-06,
> and so
> far the problem has not reappeared.
>
> Best,
> Marco
>
>
> 2014-05-16 19:07 GMT+02:00 Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>
> <mailto:gamrath at zib.de <mailto:gamrath at zib.de>>>:
>
>
> Dear Marco,
>
> sorry for the late reply. What you write sounds quite
> reasonable and
> you already tried most things that I would normally aks
> you for. So
> I don't see an obvious thing that might have gone wrong,
> and we
> probably need to dig a bit more into what happens.
>
> Therefore, please check the solution status of the LP when
> your
> pricer is called by calling SCIPgetLPSolstat(). Are you
> already in
> reduced cost pricing when the pricer keeps generating the same
> column? Also, please enable LP solver output by setting the
> parameter "display/lpinfo" to TRUE. When you checked the
> reduced
> cost of the previously generated variables, they were
> negative? What
> is the LP solution value of the "old" variable and what
> are its bounds?
>
> Another thing: did you mark all constraints to be modifiable?
>
> Best,
> Gerald
>
> Am 06.05.2014 18:59, schrieb Marco Casula:
>
> Dear all,
>
> I am working on a branch and price algorithm for the
> VRP with time
> windows and stochastic travel times. While on many
> instances the
> algorithm terminates correctly, with a number of
> instances/parameters (delay distributions, penalties)
> combinations, the algorithm gets stuck as the pricer keeps
> regenerating the same column.
>
> I have found a similar case in the mailing list
> archives, and I
> tried every suggestion I found there, without success:
> the delay flag of the pricer is set to TRUE, as is the
> initial
> flag for the new variables (I had previously set this
> to FALSE,
> with the same result);
> the variables are added via SCIPaddPricedVar;
> I checked SCIPvarIsInLP for the variable added in the
> previous
> iteration of the pricer, and it is true;
> the reduced cost of the variable added in the previous
> iteration
> (via SCIPgetVarRedCost) coincides with the one i
> compute for the
> variable in the current iteration;
> I changed the upper bound on the variables from 1.0 to
> SCIPinfinity, with no effect.
>
> I was hoping for some more insight on the matter.
> Please find attached a logfile for a non working instance
> (terminated early), and the Pricer code.
> For completeness, here's a link to a full-working folder
> (including all source files)
> https://www.dropbox.com/sh/664n10xssiicd4o/G0xtWoLH2T
>
> Thanks for any help
> Marco Casula
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de <mailto:Scip at zib.de> <mailto:Scip at zib.de
> <mailto:Scip at zib.de>>
> http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de <mailto:Scip at zib.de>
> http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140521/789ece7f/attachment.html>
More information about the Scip
mailing list