Benders doesn't work correctly for all problems

[RalfGollmer]

Test on the NEOS-Server with dcap233_200 gives wrong optimal objective value with Benders.
Using SCIP
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 1.77
Solving Nodes : 1 (total of 2 nodes in 2 runs)
Primal Bound : +8.82615182183168e+02 (4 solutions)
Dual Bound : +8.82615182183168e+02
Gap : 0.00 %

while dual decomposition gives the correct result
86 +1.833403e+03 +1.835343e+03 +1.833403e+03 0.00 0.11 6777.5
D 87 +1.833403e+03 +1.835343e+03 +1.833403e+03 0.00 0.11 6796.7
Tr STOP with gap tolerance +4.914982e-05 (0.00%).
Status: 3000
Primal Bound: 1835.34
Dual Bound : 1833.4

So if Benders is not applicable for the dcap test problem, the code should detect that and issue a corresponding message instead of pretending to have solved the problem.

See Neos jobs
#8227684
#8226078
#8228073

[kibaekkim]

The Benders algorithm implemented in the solver is not able to address integer variables in the second stage. Hence, DSP would relaxes the second-stage integrality. I realized that this must confuse users. Thank for reporting!

I will also add the code to display the corresponding message when the Benders is used.

[RalfGollmer]

The objective value reported by Benders doesn't correpond to the problem without integrality (see below for the det. equivalent). That dcap test problem has got 6 continous first-stage variables, so by relaxing the second stage leaves a stochastic LP, no MIP. https://www2.isye.gatech.edu/~sahmed/siplib/dcap/dcap.html Seems that DSP with Benders does solve yet another problem. Best regards Ralf Gollmer formerly: Fakultät f. Mathematik, Universität Duisbug-Essen

…

-------- Original Message -------- Subject: NEOS Results for Job #8232448 Date: 22.05.2020 00:36 From: neos@neos-server.org To: ralf.gollmer@uni-due.de Executing on prod-exec-5.neos-server.org Creating DSP environment Reading SMPS files: DSP Coin0001I At line 1 NAME dcap233_200 Coin0001I At line 2 ROWS Coin0001I At line 25 COLUMNS Coin0001I At line 91 RHS Coin0001I At line 97 BOUNDS Coin0001I At line 131 ENDATA Coin0002I Problem dcap233_200 has 21 rows, 39 columns and 69 elements Coin0001I At line 1 TIME Warning: Time file name no_name does not match problem file name dcap233_200 Coin0001I At line 2 PERIODS IP Coin0001I At line 5 ENDATA Coin0001I At line 1 STOCH Warning: Time file name no_name does not match problem file name dcap233_200 Coin0001I At line 2 SCENARIOS DISCRETE Coin0001I At line 3803 ENDATA Read SMPS files: 0.006932 sec. Reading parameter files: DSP.opt WARNING: There is no parameter <DW/SUB/TIME_LIM> .WARNING: There is no parameter <DW/TIME_LIM> .WARNING: There is no parameter <DD/TIME_LIM> .WARNING: There is no parameter <DW/GAPTOL> .WARNING: There is no parameter <DW/SUB/GAPTOL> .WARNING: There is no parameter <DW/EVAL_UB> .Clp0006I 0 Obj 0 Primal inf 1799.9998 (1800) Clp0006I 200 Obj 28.836865 Primal inf 1751.99 (1748) Clp0006I 400 Obj 37.62043 Primal inf 1683.5573 (1664) Clp0006I 600 Obj 43.863103 Primal inf 1593.8731 (1560) Clp0006I 800 Obj 49.980135 Primal inf 1505.8479 (1461) Clp0006I 1000 Obj 55.965242 Primal inf 1398.3034 (1345) Clp0006I 1200 Obj 61.802779 Primal inf 1276.857 (1220) Clp0006I 1400 Obj 70.546499 Primal inf 1159.546 (1106) Clp0006I 1600 Obj 78.260414 Primal inf 994.14732 (928) Clp0006I 1800 Obj 84.314484 Primal inf 863.10254 (780) Clp0006I 2000 Obj 90.412638 Primal inf 725.04207 (629) Clp0006I 2200 Obj 96.397369 Primal inf 564.42043 (489) Clp0006I 2400 Obj 484.26784 Primal inf 575.78078 (1125) Clp0006I 2600 Obj 677.05329 Primal inf 367.50853 (864) Clp0006I 2800 Obj 744.15617 Primal inf 164.112 (502) Clp0006I 3000 Obj 854.52918 Primal inf 40.046703 (219) Clp0006I 3200 Obj 877.62527 Primal inf 0.12863954 (13) Clp0006I 3211 Obj 877.6523 Clp0000I Optimal - objective value 877.6523 Status: 3000 Primal Bound: 877.652 Dual Bound : 877.652 Deleting DSP environment

[kibaekkim]

OK, then this must be reopened. Thanks for the report again!

[RalfGollmer]

Hi, sorry to irritate you - the last result was my fault. I had relaxed ALL integrality requirements, but in dcap233 the u_* variables are first-stage and have to be kept binary. Doing that the result is the same as with Benders, so there is no problem apart from the silent relaxation by DSP with Benders algorithm. In case integer second-stage variables are present in the problem there two possibilities: a) issue a message that these variables are relaxed and continue with Benders or b) issue a message that Benders algorithm cannot handle such problem, propose the use of one of the other two possibilities and stop execution. Best regards Ralf Gollmer formerly: Fakultät f. Mathematik, Universität Duisbug-Essen

…

On 22.05.2020 03:18, Kibaek Kim wrote: OK, then this must be reopened. Thanks for the report again! -- You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub [1], or unsubscribe [2]. Links: ------ [1] #59 (comment) [2] https://github.com/notifications/unsubscribe-auth/AE2X6GMHLNT446THTP4LAWLRSXHFRANCNFSM4NGTX3HQ

[kibaekkim]

No worries. I will add a code to print out the warning message in the code.
Thank you!