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

[Rolf van der Hulst]

---------- Forwarded message ---------
From: Rolf van der Hulst <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>


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>
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
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20210707/052783d4/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Selected Topics in Column Generation.pdf
Type: application/pdf
Size: 198994 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20210707/052783d4/attachment.pdf>