Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Score calculation in strong branching is broken #512

Closed
rrsadykov opened this issue Apr 23, 2021 · 0 comments · Fixed by #516
Closed

Score calculation in strong branching is broken #512

rrsadykov opened this issue Apr 23, 2021 · 0 comments · Fixed by #516
Labels
bug Something isn't working

Comments

@rrsadykov
Copy link
Collaborator

When running for example gap - strong branching test, scores of all candidates in phase 1 (based on product score) are zero

**** Strong branching phase 1 is started *****
SB phase 1 branch on x[1,4] (lhs=0.5278)  : [ 1552.2815, 1555.6579], score =     0.0000
SB phase 1 branch on x[2,4] (lhs=0.4722)  : [ 1555.6579, 1552.1424], score =     0.0000
SB phase 1 branch on x[3,5] (lhs=0.6389)  : [ 1550.3073, 1555.5000], score =     0.0000
SB phase 1 branch on x[2,19] (lhs=0.6389) : [ 1550.7379, 1552.1471], score =     0.0000
SB phase 1 branch on x[3,2] (lhs=0.3611)  : [ 1555.5000, 1550.2116], score =     0.0000

Also, in the same test gap - strong branching, strong branching is being performed even if the local DB is worse than the global PB (in this case, the node should be pruned immediately) :

***************************************************************************************
**** BaB tree node N° 8, parent N° 6, depth 4, 5 open nodes
**** Local DB = 1554.7379, global bounds : [ 1549.5926 , 1554.0000 ], time = 1.73 sec.
**** Branching constraint: x[2,18]<=0.0
***************************************************************************************
**** Strong branching phase 1 is started *****
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
SB phase 1 branch on x[2,13] (lhs=0.5049) : [       Inf,       Inf], score =     0.0000
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
SB phase 1 branch on x[4,17] (lhs=0.5437) : [       Inf,       Inf], score =     0.0000
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
SB phase 1 branch on x[4,1] (lhs=0.4563)  : [       Inf,       Inf], score =     0.0000
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
SB phase 1 branch on x[5,1] (lhs=0.5437)  : [       Inf,       Inf], score =     0.0000
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
SB phase 1 branch on x[5,13] (lhs=0.4563) : [       Inf,       Inf], score =     0.0000
**** Strong branching phase 2 is started *****
**** SB phase 2 evaluation of candidate 1 (branch 1 : x[2,13]>=1.0), value =    Inf
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
Branch is conquered!
**** SB phase 2 evaluation of candidate 1 (branch 2 : x[2,13]<=0.0), value =    Inf
[ Info: IP Gap is closed: -0.00047459066555197323. Abort treatment.
Branch is conquered!
SB phase 2 branch on x[2,13] (lhs=0.5049) : [       Inf,       Inf], score =    -1.0000
Child nodes generated : N° 10  N° 11 

Earlier, in this test, a node in the strong branching is conquered, but still two child nodes are generated:

**** SB phase 2 evaluation of candidate 1 (branch 2 : x[2,18]>=1.0), value = 1626.11
  <it=  1> <et= 1.62> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.50> <DB= 1552.6400> <mlp= 1626.1111> <PB=1661.0000>
  <it=  2> <et= 1.63> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.55> <DB= 1552.6400> <mlp= 1590.3896> <PB=1661.0000>
  <it=  3> <et= 1.64> <mst= 0.00> <sp= 0.01> <cols= 3> <al= 0.60> <DB= 1552.6400> <mlp= 1564.3704> <PB=1661.0000>
  <it=  4> <et= 1.65> <mst= 0.00> <sp= 0.01> <cols= 3> <al= 0.64> <DB= 1552.6400> <mlp= 1554.0000> <PB=1554.0000>
  <it=  5> <et= 1.66> <mst= 0.00> <sp= 0.01> <cols= 4> <al= 0.67> <DB= 1552.6400> <mlp= 1554.0000> <PB=1554.0000>
  <it=  6> <et= 1.67> <mst= 0.00> <sp= 0.01> <cols= 3> <al= 0.41> <DB= 1553.0415> <mlp= 1554.0000> <PB=1554.0000>
  <it=  7> <et= 1.69> <mst= 0.00> <sp= 0.01> <cols= 4> <al= 0.21> <DB= 1553.4204> <mlp= 1554.0000> <PB=1554.0000>
  <it=  8> <et= 1.70> <mst= 0.00> <sp= 0.01> <cols= 1> <al= 0.50> <DB= 1553.4204> <mlp= 1554.0000> <PB=1554.0000>
  <it=  9> <et= 1.71> <mst= 0.00> <sp= 0.01> <cols= 3> <al= 0.11> <DB= 1553.6787> <mlp= 1554.0000> <PB=1554.0000>
  <it= 10> <et= 1.72> <mst= 0.00> <sp= 0.01> <cols= 0> <al= 0.00> <DB= 1554.0000> <mlp= 1554.0000> <PB=1554.0000>
[ Info: Dual bound reached primal bound.
Branch is conquered!
SB phase 2 branch on x[2,18] (lhs=0.5200) : [ 1554.7379, 1554.0000], score =   -36.9927
Child nodes generated : N° 8  N° 9 

Coluna : master branch

@rrsadykov rrsadykov added the bug Something isn't working label Apr 23, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant