<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Hi Jungeun,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Sorry about the delay in responding to your question. Hopefully we can still be of help.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
First, the assertion error. Does this occur when setting a node estimate in your custom branching rule? If so, you should pay attention to the assertion and only set an estimate that is greater than or equal to the current nodes lower bound.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
The fact that the lower bound doesn't change has nothing to do with the assertion error. The lower bound reported in the progress table is the global lower bound. This bound has been proven to be the lowest possible value for the optimal objective value. The
LP Objective that you report is the objective value of the LP solved at that node. Since you are applying Dantzig-Wolfe reformulation, it is expected that the LP Objective will decrease during the processing of the node.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
You are noticing a difference between the LP Objective and the lower bound. One thing that you have noticed is that the LP Objective is smaller than the reported global lower bound. There are a number of reasons for this. One possible reason is that there could
be an objective offset that has been found after the problem has been transformed. This will be included in the lower bound, but not the LP objective. Alternatively, scaling could be performed on the LP and as a result the LP objective could be less than the
reported lower bound.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
In your example, I expect that the LP objective and the lower bound are reported correctly. When setting the node estimate in your branching rule, you should use the lower bound instead of the LP Objective.</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Cheers,</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Steve<br>
</div>
<div>
<div id="appendonsend"></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> Scip <scip-bounces@zib.de> on behalf of Shin, Jungeun <jungeun4@illinois.edu><br>
<b>Sent:</b> 15 July 2020 19:35<br>
<b>To:</b> scip@zib.de <scip@zib.de><br>
<b>Subject:</b> [SCIP] Assertion error ( Dual bound is not updated in the Branch and Price framework )</font>
<div> </div>
</div>
<div dir="ltr">
<div style="background-color:#FFEB9C; width:100%; border-style:solid; border-color:#9C6500; border-width:1pt; padding:2pt; font-size:10pt; line-height:12pt; font-family:'Calibri'; color:Black; text-align:left">
<span style="color:#9C6500; font-weight:bold">CAUTION:</span> This email originated from outside of the organisation. Do not click links or open attachments unless you recognise the sender and know the content is safe.</div>
<br>
<div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">Hi,</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif">I would like to ask how the dual bound is updated in the SCIP branch and price framework.</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif; font-size:12pt">When the columns generated at the root node, LP obj value decrease. </span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif; font-size:12pt">Thus, I expected dual bound would also be decreased. It was true for some instances but </span><span style="color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif; font-size:12pt">it
doesn't seem to be always this case.</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt"><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif; font-size:12pt">For example, the following is a initial part of output logs of the column generation at the root node.</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif; font-size:12pt">Here, "Depth: 0" means it is at the root node and "LPObj" value is SCIPgetLPObjval</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="color:rgb(0,0,0); font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt"><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<blockquote style="margin:0 0 0 40px; border:none; padding:0px">
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif"><i> Starts CG at a new node: 1. (Depth: 0, LPObj: 11358.02, Parent: 0, Branched var in the parent node: None)</i></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<i><br>
</i></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif"><i> time | node | left |LP iter |LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
</i></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<div><span style="font-family:Calibri,Helvetica,sans-serif"><i> 81.1s | 1 | 0 | 8064 | - | 462M | 0 | 78k| 108k| 108k| 0 | 0 | 0 | 0 | 1.135802e+04 | -- | Inf | unknown</i></span></div>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span style="font-family:Calibri,Helvetica,sans-serif"><i>o 146s| 1 | 0 | 14010 | - |feaspump| 0 | 78k| 108k| 108k| 0 | 0 | 0 | 0 | 1.135802e+04 | 5.000000e+04 | 340.22%| unknown</i></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><i><br>
</i></span></div>
<span style="font-family:Calibri,Helvetica,sans-serif"><i> L Continues CG at the curr node: 1, (Depth: 0, LPObj: 6668.00, N(new columns so far): 1. )</i></span>
<div><font face="Calibri, Helvetica, sans-serif"><i> L Continues CG at the curr node: 1, (Depth: 0, LPObj: 4940.83, N(new columns so far): 2. )
</i></font></div>
<div>
<div style="font-size:12pt; color:rgb(0,0,0)"><font face="Calibri, Helvetica, sans-serif"><i>... (omitted)</i></font></div>
</div>
<div>
<div style="font-size:12pt; color:rgb(0,0,0)"><font face="Calibri, Helvetica, sans-serif"><i> L Continues CG at the curr node: 1, (Depth: 0, LPObj: 5.57, N(new columns so far): 11. )
</i></font></div>
</div>
<div>
<div style="font-size:12pt; color:rgb(0,0,0)"><font face="Calibri, Helvetica, sans-serif"><i><br>
</i></font></div>
</div>
<div>
<div style="font-size:12pt; color:rgb(0,0,0)"><font face="Calibri, Helvetica, sans-serif"><i> 346s| 1 | 0 | 26166 | - | 497M | 0 | 78k| 108k| 108k| 3 | 1 | 0 | 0 | 1.135802e+04 | 5.000000e+04 | 340.22%| unknown</i></font></div>
</div>
</blockquote>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><b></b></span></div>
<div><b><span style="font-family:Calibri,Helvetica,sans-serif"></span></b>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><b></b></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><b><br>
</b></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><b><br>
</b></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><b><br>
</b></span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
LPObj decreases as new columns added, but the dual bound stays at 11358.02 which is the initial LPObj. </div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Isn't the dual bound supposed to be 5.57 after adding 11th columns? </div>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
T<span style="color:rgb(0,0,0); font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt">hen, once the branching starts the following assertion error appears.</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span>scipoptsuite-7.0.0/scip/src/scip/tree.c:2457: SCIPnodeSetEstimate: Assertion `SCIPsetIsRelGE(set, newestimate, node->lowerbound)' failed.<br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span>I guess this assertion error relates to the large gap between LPObj and the dual bound. </span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span><br>
</span></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<span>Thank you.</span></div>
</div>
</div>
</div>
</body>
</html>