[SCIP] Fwd: A specific question about the Graph Coloring Application

Wed Jul 7 12:17:15 CEST 2021

Dear Yunzhuang,

>     However, The equation for computing the Lagrangian bound seems to be
>     incorrect. Specifically, why the primal bound is used to multiple by
>     the reduced cost?
>     SCIPgetLPObjval(scip) + ((1.0 - max_obj) * SCIPgetPrimalbound(scip))
>
>     However, the Lagrangian bound to the current RMP seems to be simply
>     the optimal LP objective value of the current restricted master
>     problem plus the optimum of the current pricing problem.
>
When you compute the Lagrangian bound as the LP optium plus the optimum 
of the pricing problem, this would imply that there is only one pricing 
problem. However, for coloring, there are many identical ones (merged 
into one) and more than one stable set is selected. So taking 
"SCIPgetLPObjval(scip) + (1.0 - max_obj)" just gives you the bound if 
you would only allow one of the stable sets to be changed. Since 
SCIPgetPrimalbound(scip) is an upper bound on how many stable sets you 
may change in the optimal LP solution compared to the RMP, the reduced 
costs are multiplied by that to obtain the Lagrangian bound.

But the formula mentioned by Rolf may give you even better Lagrangian 
bounds. You may also compute both bounds and use the one that is valid 
and better at that particular node.

Best,

Gerald

Am 07.07.21 um 12:00 schrieb Marc Pfetsch:

>
>
> Dear Rolf,
>
> you mentioned below that the tcliqueMaxClique algorithm may terminate 
> early. I have looked in the code and there are no limits (e.g., node 
> limits etc.) that would imply that this may happen. What may happen is 
> that the precision of the computations is not enough, so rounding 
> errors might cause problems.
>
> Can you send me directly (off the list) an example where things go 
> wrong and maybe a way to reproduce that pricing does not produce 
> correct bounds?
>
> Best
>
> Marc
>
> On 07/07/2021 08.22, Rolf van der Hulst wrote:
>>
>>
>> ---------- Forwarded message ---------
>> From: *Rolf van der Hulst* <rolfvdhulst at gmail.com 
>> <mailto:rolfvdhulst at gmail.com>>
>> Date: Wed, Jul 7, 2021 at 8:17 AM
>> Subject: Re: [SCIP] A specific question about the Graph Coloring 
>> Application
>> To: Yunzhuang Shen <s3640365 at student.rmit.edu.au 
>> <mailto:s3640365 at student.rmit.edu.au>>
>>
>>
>> Dear Yunzhuang,
>>
>> For my thesis I am also working on Graph Coloring and used SCIP as my 
>> starting point. I think I can help you a bit:
>> In the attachment is a pdf which explains the bound (see section 2.1).
>> What may be a source of confusion is that for graph coloring, the 
>> pricing problem is typically negated to make it more readable. e.g.:
>> Minimal_reduced_cost = 1 - Maximum Weight Stable Set. This is, where 
>> the (1- obj) part comes in.
>>
>> Note the bound given in SCIP is not in fact the strongest lower 
>> bound: the bound
>> LP_obj / (1- c*)  = LP_obj / (maximum_stable_set_weight)
>>
>> is stronger and valid here (given that the pricing problem is solved 
>> to optimality). This is also used in the paper 'An Exact approach for 
>> the vertex coloring problem' by Malaguti, Monaci and Toth (equation 
>> 15) and many more important papers in this area.
>>
>> However, in my applications, I've had to adjust the code around this 
>> bound as well; the given SCIP coloring is not necessarily optimal as 
>> the tcliqueMaxClique algorithm may terminate early. In this case, the 
>> bounds above are not valid, as they rely on knowledge of the 
>> optimal/minimal reduced cost. This is *not* currently implemented 
>> correctly in SCIP as far as I know, and for some instances, you may 
>> get invalid lower bounds which are too high as a result. I've 
>> encountered this for several instances (particularly, very large ones).
>>
>> Note I'm working in SCIP 7.0.2: The above /may/ be fixed in 7.0.3 but 
>> I haven't seen anything about it in the release notes.
>>
>> Feel free to ask any more questions if you have any.
>>
>> Best,
>>
>> Rolf
>>
>>
>> On Wed, Jul 7, 2021 at 6:05 AM Yunzhuang Shen 
>> <s3640365 at student.rmit.edu.au <mailto:s3640365 at student.rmit.edu.au>> 
>> wrote:
>>
>>     Hi SCIP Team,
>>
>>     I am doing research about Branch-and-Price, using the code of the
>>     Graph Coloring Problem provided in the SCIP applications folder.
>>
>>     In `pricer_coloring.c', lines 717-725 are for updating the lower
>>     bound using the Lagrangian bound of the current LP to my 
>> understanding.
>>
>>     However, The equation for computing the Lagrangian bound seems to be
>>     incorrect. Specifically, why the primal bound is used to multiple by
>>     the reduced cost?
>>     SCIPgetLPObjval(scip) + ((1.0 - max_obj) * SCIPgetPrimalbound(scip))
>>
>>     However, the Lagrangian bound to the current RMP seems to be simply
>>     the optimal LP objective value of the current restricted master
>>     problem plus the optimum of the current pricing problem.
>>
>>     I would like to confirm this with you either this is a typo or I
>>     misunderstood something.
>>
>>     Regards,
>>     Yunzhuang
>>
>>     _______________________________________________
>>     Scip mailing list
>>     Scip at zib.de <mailto:Scip at zib.de>
>>     https://listserv.zib.de/mailman/listinfo/scip
>>     <https://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip