[SCIP] Assertion error ( Dual bound is not updated in the Branch and Price framework )

[Maher, Stephen]

Hi Jungeun,

Sorry about the delay in responding to your question. Hopefully we can still be of help.

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.

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.

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.

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.

Cheers,

Steve

________________________________
From: Scip <scip-bounces at zib.de> on behalf of Shin, Jungeun <jungeun4 at illinois.edu>
Sent: 15 July 2020 19:35
To: scip at zib.de <scip at zib.de>
Subject: [SCIP] Assertion error ( Dual bound is not updated in the Branch and Price framework )

CAUTION: 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.

Hi,

I would like to ask how the dual bound is updated in the SCIP branch and price framework.

When the columns generated at the root node, LP obj value decrease.
Thus, I expected dual bound would also be decreased. It was true for some instances but it doesn't seem to be always this case.

For example, the following is a initial part of output logs of the column generation at the root node.
Here, "Depth: 0" means it is at the root node and "LPObj" value is  SCIPgetLPObjval


 Starts CG at a new node: 1. (Depth: 0, LPObj: 11358.02, Parent: 0, Branched var in the parent node: None)

 time   | node  | left  |LP iter  |LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 81.1s |     1    |     0 |  8064  |     -    |   462M    |   0    |  78k| 108k| 108k|   0 |  0 |   0 |   0 | 1.135802e+04 |      --      |    Inf | unknown
o 146s|     1    |     0 | 14010 |     -    |feaspump|   0    |  78k| 108k| 108k|   0 |  0 |   0 |   0 | 1.135802e+04 | 5.000000e+04 | 340.22%| unknown

 L Continues CG at the curr node: 1, (Depth: 0, LPObj: 6668.00, N(new columns so far): 1.  )
 L Continues CG at the curr node: 1, (Depth: 0, LPObj: 4940.83, N(new columns so far): 2.  )
... (omitted)
 L Continues CG at the curr node: 1, (Depth: 0, LPObj: 5.57, N(new columns so far): 11.  )

  346s|     1 |     0 | 26166 |     - |   497M |   0 |  78k| 108k| 108k|   3 |  1 |   0 |   0 | 1.135802e+04 | 5.000000e+04 | 340.22%| unknown



LPObj decreases as new columns added, but the dual bound stays at 11358.02 which is the initial LPObj.
Isn't the dual bound supposed to be 5.57 after adding 11th columns?

Then, once the branching starts the following assertion error appears.
scipoptsuite-7.0.0/scip/src/scip/tree.c:2457: SCIPnodeSetEstimate: Assertion `SCIPsetIsRelGE(set, newestimate, node->lowerbound)' failed.

I guess this assertion error relates to the large gap between LPObj and the dual bound.



Thank you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200731/a20cfdb4/attachment.html>