[Scip] Fwd: stop condition of pricing routine
Gerald Gamrath
gamrath at zib.de
Wed Jul 28 14:57:12 MEST 2010
Hi Mattia,
correct me if I am wrong, but for me this looks like if you have to
solve the RMP just one time until you find new variables? Or why should
you resolve the RMP in case you did not find an improving variable, the
dual solution should stay the same, shouldn't it? What would you do if
you do not find an improving variable? I suppose you would change the
parameter _alpha_ so that you have another convex combination of the
current dual solution and the old one (I suppose _pi_ is somewhere in
the loop set to _pi_st_ so it is the dual solution of the last
iteration?) ? In this case, why don't you just change the _alpha_
parameter in your current pricing call and do another pricing iteration
until you find improving variables or prove that no such variable exists
(if you finally have _alpha_ = 0)? Then you would not have the problem
that you want to perform another pricing iteration but would either find
a variable or stop because there do not exist any more variables or
because of your stopping criterion. This could be handled as described
by Martin and me earlier.
If I misunderstood your algorithm, could you describe it a bit more or
tell me the paper where to find it (or send it to me directly).
Just a remark for my previous proposals: I talked about the problem with
the trust region with a colleague of mine and he had the following idea
which would work really good, I think. You could omit the trust region
in the LP relaxation of the problem in the branch-and-bound tree, but
introduce it just within the pricer, as described before. But instead of
taking care about the LP solving yourself, you could activate the
probing mode and add a probing node. Then you apply the changes to the
problem in order to stabilize the dual solution and solve the LP at the
current probing node. In this case, you never relax the problem at a
node deeper in the tree, because the LPs corresponding to the nodes
never a have stability box in them, just the probing LPs. You can then
take the dual solution from the probing LP and perform pricing. If you
do not find improving variables, you delete the probing node and create
a new one, with another box. The only disadvantage (which you would have
in the other way, too) is that SCIP solves the "unstabilized" problem at
each node and gets an "extreme" dual solution, even if you do not use
this but solve another LP in the pricing process, anyway. So you have
perhaps a bit more LP-solving effort, however, I think the primal
solution corresponding to the "extreme" solution is also primal feasible
in the stabilized LP so that it can be used to warmstart the LP solving?
Best regard,
Gerald
Am 28.07.2010 12:47, schrieb Mattia Barbieri:
> Hi Gerald,
> I am trying two stabilization methods: the first, the one proposed by
> Ben Amor et al., concerning a 5-piecewise linear penalty function. Is
> in this method that I need a relaxator or to copy the LP at each
> redcost iteration with new penalty terms updated. The second, a new
> method proposed by A. Pessoa, E. Uchoa and M. de Aragao, which is
> still based on the concept of keeping a stability center, but it has
> no need to change the Master LP, because it operate directly on the
> duals: "the pricing problem is not solved with the dual solutions from
> the restricted Master LPs, but with other vectors, that are closer to
> the current stability center." This method have been proved to be
> sound and also its convergence have been proved. The algorithm is as
> follow:
>
> Input: parameter _alpha_, 0 < _alpha_ < 1 and value _eps_
> _pi_ <- 0 (_pi_ is the vector of the dual variables
> associated to the RMP)
> DO {
> Solve the restricted Master LP, obtaining the valule Z_RM and
> the dual vector _pi_RM_;
> _pi_st_ <- _alpha_*_pi_ + (1-_alpha) * _pi_RM;
> Solve the pricing with vector _pi_st_, obtaining column A_j;
> If L(_pi_st_) > L(_pi_) then L(_pi_) <- L(_pi_st_); //L is the
> Lagrangian relaxation
> If A_j has negative reduced cost with respect to _pi_RM, add it
> to the restricted Master LP;
> } UNTIL Z_RM - L(_pi_) < _eps_
>
> The last instruction is that that I would implement in SCIP, the
> stopping criterion. May be could help adding dummy variables to
> continue the pricing process, although they do not have negative
> reduced cost?
>
> Best regards,
>
> On 28 July 2010 12:23, Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>> wrote:
>
> Hi Mattia,
>
> I also understood your question the other way around, so probably
> at least the first part of my last answer won't help you much.
> The only criterion SCIP uses to determine whether the pricing
> process is finished or the pricers should be called again is
> whether new variables were added in the last pricing round.
> Perhaps this could be changed, so that the pricing is continued
> after you changed your trust region, but could you first explain
> how you do this if you must not enlarge the feasible region at a
> node compared to its father node?
>
> If you do it like I wrote, copy the LP within your pricer and
> impose the trust region just in this copy, I think the problem
> with SCIP stopping the pricing process too early should not occur,
> since you can move the trust region and look for new variable
> until you find some or you proved that none exists.
>
> Best regards,
> Gerald
>
> Am 28.07.2010 11:59, schrieb Mattia Barbieri:
>>
>>
>> ---------- Forwarded message ----------
>> From: *Mattia Barbieri* <barbieri.mattia at gmail.com
>> <mailto:barbieri.mattia at gmail.com>>
>> Date: 28 July 2010 11:57
>> Subject: Re: [Scip] stop condition of pricing routine
>> To: Martin Bergner <mbergner at mathematik.tu-darmstadt.de
>> <mailto:mbergner at mathematik.tu-darmstadt.de>>
>>
>>
>> Hi Martin,
>> my problem is the opposite: it might happen (and that is the
>> case) that no variables with negative reduced costs are found, so
>> the pricer leave the node (no improvement due to new reduced cost
>> columns). I want instead that the pricer iterates AGAIN, because,
>> even if no variables have been added to the Master Problem, the
>> dual variables associated will change anyway due to the penalties
>> applied, so it is possible that a new column will be found at the
>> next iteration (may be a misprice column, but this case is
>> considered by the method I use).
>>
>> Regards,
>>
>>
>> On 28 July 2010 11:34, Martin Bergner
>> <mbergner at mathematik.tu-darmstadt.de
>> <mailto:mbergner at mathematik.tu-darmstadt.de>> wrote:
>>
>> Hello Mattia,
>>
>> I forgot: There is a method SCIPdeactivatePricer, would that
>> work?
>>
>> Regards,
>> Martin
>>
>>
>>
>>
>> --
>> Mattia Barbieri
>> barbieri.mattia at gmail.com <mailto:barbieri.mattia at gmail.com>
>>
>>
>>
>> --
>> Mattia Barbieri
>> barbieri.mattia at gmail.com <mailto:barbieri.mattia at gmail.com>
>>
>>
>> _______________________________________________
>> 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 <mailto:Scip at zib.de>
> http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
> --
> Mattia Barbieri
> barbieri.mattia at gmail.com <mailto:barbieri.mattia at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100728/1e4428ed/attachment.html
More information about the Scip
mailing list