[Scip] Fwd: stop condition of pricing routine

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100728/30910e68/attachment.html