<div dir="ltr"><div>Dear Marc, <br></div><div><br></div><div>The error is triply subtle:<br></div><div><br></div><div>First, I think there's a mistake in pricer_coloring.c, line 320. The given if statement is often always false: I think this should be used<br><pre style="background-color:rgb(43,43,43);color:rgb(169,183,198);font-family:"JetBrains Mono",monospace;font-size:9.8pt"><span style="color:rgb(204,120,50)">if </span>( pricerdata-><span style="color:rgb(147,115,165)">actindex</span>+<span style="color:rgb(104,151,187)">1 </span>== pricerdata-><span style="color:rgb(147,115,165)">maxvarsround </span>)<br></pre></div><div><div>Because now, the relevant code below is never hit (by what seems according to the documentation, by accident), and the pricing problem always solved to optimality, even if bestonly = FALSE.<br></div></div><div><br></div><div>In the solution callback of tclique, the computation can be stopped early. Although the 'onlybest' variable is TRUE in the default settings, preventing this issue from happening, it can stop the clique algorithm early when not using these default settings. (See lines 320-331, pricer_coloring.c), In this case, the generated bound would be invalid (or atleast, you can not certify that the bound is valid). <br></div><div><br></div><div>With these changes, one can for example run the test instance queen9_9.col and find a invalid lower bound of 9.26 in the root node (it should be 9), by setting max_vars_round = 1 (this needs to be done in heur_init.c, as otherwise it is overwritten by it), and onlybest = FALSE. The third subtlety is that since the bound is only used when doing early branching, it is very easy
 for it to go 'undetected' as it is discarded after solving the branch 
and bound node. Only when I printed this value, I detected the above issues.<br></div><div><br></div><div>The numerical issues you mention can also be significant; for some difficult instances the pricer as implemented in SCIP cannot find the last few columns and stops pricing too early (for example, the dimacs instance DSJC125.1 has fractional coloring in the root node of 4.45222 when using 'safe lower bounds' / better pricing algorithms, but the coloring application puts it at 4.46.... ).<br></div><div><br></div><div>As a general note, I would not recommend to always solve the pricing problem to optimality for graph coloring from my computational experience. It is often quite expensive to solve the pricing problem to optimality compared to the cost of finding a negative reduced cost column, particularly for larger, more difficult, graphs. Solving until finding a reduced cost column is typically much faster for difficult instances, and smart pricing schemes which alternate between finding columns quickly and between solving to optimality can in some instances be orders of magnitude faster. (for reference, see 'graph coloring problems via constraint programming and column generation' by Gaulandi and Malucelli).<span style="font-size:28.6923px;font-family:sans-serif" dir="ltr"></span></div><div><br></div><div>Best,<br><br></div><div>Rolf<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 7, 2021 at 12:00 PM Marc Pfetsch <<a href="mailto:pfetsch@mathematik.tu-darmstadt.de">pfetsch@mathematik.tu-darmstadt.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
Dear Rolf,<br>
<br>
you mentioned below that the tcliqueMaxClique algorithm may terminate <br>
early. I have looked in the code and there are no limits (e.g., node <br>
limits etc.) that would imply that this may happen. What may happen is <br>
that the precision of the computations is not enough, so rounding errors <br>
might cause problems.<br>
<br>
Can you send me directly (off the list) an example where things go wrong <br>
and maybe a way to reproduce that pricing does not produce correct bounds?<br>
<br>
Best<br>
<br>
Marc<br>
<br>
On 07/07/2021 08.22, Rolf van der Hulst wrote:<br>
> <br>
> <br>
> ---------- Forwarded message ---------<br>
> From: *Rolf van der Hulst* <<a href="mailto:rolfvdhulst@gmail.com" target="_blank">rolfvdhulst@gmail.com</a> <br>
> <mailto:<a href="mailto:rolfvdhulst@gmail.com" target="_blank">rolfvdhulst@gmail.com</a>>><br>
> Date: Wed, Jul 7, 2021 at 8:17 AM<br>
> Subject: Re: [SCIP] A specific question about the Graph Coloring Application<br>
> To: Yunzhuang Shen <<a href="mailto:s3640365@student.rmit.edu.au" target="_blank">s3640365@student.rmit.edu.au</a> <br>
> <mailto:<a href="mailto:s3640365@student.rmit.edu.au" target="_blank">s3640365@student.rmit.edu.au</a>>><br>
> <br>
> <br>
> Dear Yunzhuang,<br>
> <br>
> For my thesis I am also working on Graph Coloring and used SCIP as my <br>
> starting point. I think I can help you a bit:<br>
> In the attachment is a pdf which explains the bound (see section 2.1).<br>
> What may be a source of confusion is that for graph coloring, the <br>
> pricing problem is typically negated to make it more readable. e.g.:<br>
> Minimal_reduced_cost = 1 - Maximum Weight Stable Set. This is, where the <br>
> (1- obj) part comes in.<br>
> <br>
> Note the bound given in SCIP is not in fact the strongest lower bound: <br>
> the bound<br>
> LP_obj / (1- c*)  = LP_obj / (maximum_stable_set_weight)<br>
> <br>
> is stronger and valid here (given that the pricing problem is solved to <br>
> optimality). This is also used in the paper 'An Exact approach for the <br>
> vertex coloring problem' by Malaguti, Monaci and Toth (equation 15) and <br>
> many more important papers in this area.<br>
> <br>
> However, in my applications, I've had to adjust the code around this <br>
> bound as well; the given SCIP coloring is not necessarily optimal as the <br>
> tcliqueMaxClique algorithm may terminate early. In this case, the bounds <br>
> above are not valid, as they rely on knowledge of the optimal/minimal <br>
> reduced cost. This is *not* currently implemented correctly in SCIP as <br>
> far as I know, and for some instances, you may get invalid lower bounds <br>
> which are too high as a result. I've encountered this for several <br>
> instances (particularly, very large ones).<br>
> <br>
> Note I'm working in SCIP 7.0.2: The above /may/ be fixed in 7.0.3 but I <br>
> haven't seen anything about it in the release notes.<br>
> <br>
> Feel free to ask any more questions if you have any.<br>
> <br>
> Best,<br>
> <br>
> Rolf<br>
> <br>
> <br>
> On Wed, Jul 7, 2021 at 6:05 AM Yunzhuang Shen <br>
> <<a href="mailto:s3640365@student.rmit.edu.au" target="_blank">s3640365@student.rmit.edu.au</a> <mailto:<a href="mailto:s3640365@student.rmit.edu.au" target="_blank">s3640365@student.rmit.edu.au</a>>> wrote:<br>
> <br>
>     Hi SCIP Team,<br>
> <br>
>     I am doing research about Branch-and-Price, using the code of the<br>
>     Graph Coloring Problem provided in the SCIP applications folder.<br>
> <br>
>     In `pricer_coloring.c', lines 717-725 are for updating the lower<br>
>     bound using the Lagrangian bound of the current LP to my understanding.<br>
> <br>
>     However, The equation for computing the Lagrangian bound seems to be<br>
>     incorrect. Specifically, why the primal bound is used to multiple by<br>
>     the reduced cost?<br>
>     SCIPgetLPObjval(scip) + ((1.0 - max_obj) * SCIPgetPrimalbound(scip))<br>
> <br>
>     However, the Lagrangian bound to the current RMP seems to be simply<br>
>     the optimal LP objective value of the current restricted master<br>
>     problem plus the optimum of the current pricing problem.<br>
> <br>
>     I would like to confirm this with you either this is a typo or I<br>
>     misunderstood something.<br>
> <br>
>     Regards,<br>
>     Yunzhuang<br>
> <br>
>     _______________________________________________<br>
>     Scip mailing list<br>
>     <a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a> <mailto:<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>><br>
>     <a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
>     <<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>><br>
> <br>
> <br>
> _______________________________________________<br>
> Scip mailing list<br>
> <a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
> <a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
> <br>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>