[Scip] Fwd: Fwd: stop condition of pricing routine

Mattia Barbieri barbieri.mattia at gmail.com
Wed Jul 28 16:51:30 MEST 2010


---------- Forwarded message ----------
From: Mattia Barbieri <barbieri.mattia at gmail.com>
Date: 28 July 2010 16:51
Subject: Re: [Scip] Fwd: stop condition of pricing routine
To: Gerald Gamrath <gamrath at zib.de>




On 28 July 2010 14:57, Gerald Gamrath <gamrath at zib.de> wrote:

>  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.
>

You're right. Now I will try in this way.

>
> 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).
>

I attach the file of the "presentation" from which I took out the ideas
above.

>
> 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?
>

Also this idea sounds good. Perhaps the overhead introduced by the LP
solving is too heavy, but this has to be tested experimentally. If I
understood correctly, the primal solution given by the LP solver will be
used to start the LP probing node, and this hopefully would speed up the
solving process. Is that right?

>
> 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> 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>
>> Date: 28 July 2010 11:57
>> Subject: Re: [Scip] stop condition of pricing routine
>> To: Martin Bergner <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> wrote:
>>
>>> Hello Mattia,
>>>
>>> I forgot: There is a method SCIPdeactivatePricer, would that work?
>>>
>>> Regards,
>>> Martin
>>>
>>>
>>
>>
>>   --
>> Mattia Barbieri
>> barbieri.mattia at gmail.com
>>
>>
>>
>> --
>> Mattia Barbieri
>> barbieri.mattia at gmail.com
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>
>
> --
> Mattia Barbieri
> barbieri.mattia at gmail.com
>
>
>


-- 
Mattia Barbieri
barbieri.mattia at gmail.com



-- 
Mattia Barbieri
barbieri.mattia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100728/00e42d47/attachment.html


More information about the Scip mailing list