Applying L-shaped method using callback in C++
ユーザーの入力を待っています。
Hello,
I’m trying to apply the L-shaped method (Benders Decomposition) to solve a stochastic model using callback function in C++.
I understand that whenever Gurobi found a MIP solution (that is where == GRB_CB_MIPSOL), I must get the incumbent solution of master problem using getSolution, then solve the dual subproblems and check if a cut need to be added using addLazy.
I implement the callback function by defining the CBD_Callback class as follows.
class CBD_Callback : public GRBCallback
{
public:
CBD_Callback(DecompositionModels* theModels, IncumbentSolution* theSolution)
{
modelsPtr = theModels;
incumbentSolutionPtr = theSolution;
dualSubproblems_wereCreated = false;
};
private:
DecompositionModels* modelsPtr;
IncumbentSolution* incumbentSolutionPtr;
bool dualSubproblems_wereCreated; //{False:No ; True:Yes}
void Get_The_Incumbent_Integer_Solution();
void Solve_DualSubProblems_And_Get_Duals();
void Create_and_Add_Generalized_Multiple_Benders_Cuts();
protected:
void callback(){
try{
if (where == GRB_CB_MIPSOL){
// MIP solution callback
Get_The_Incumbent_Integer_Solution();
Solve_DualSubProblems_And_Get_Duals();
Create_and_Add_Generalized_Multiple_Benders_Cuts();
}
}
catch (GRBException e){
cout << "Error number: " << e.getErrorCode() << endl;
cout << e.getMessage() << endl;
}
catch (...){
cout << "Error during callback" << endl;
}
}
};
The DecompositionModels is class I defined to keep the master problem and the dual subproblems as follows. I also keep the index of the variables in this class.
class DecompositionModels : public MasterProblem, public DualSubProblem
{
public:
//Declaration of the environment and models
GRBEnv* env = 0;
GRBModel masterProblem_Model;
vector<GRBModel> dualSubproblem_Model;
VarIndexDecompModels varIndex;
DecompositionModels():
env(new GRBEnv()), masterProblem_Model(*env) {
for (int omega = 0; omega <= numScenarios; omega++) {
dualSubproblem_Model.push_back(GRBModel(*env));
}
varIndex = VarIndexDecompModels();
};
~DecompositionModels(){
//To deallocate memory for env object
delete env;
};
};
To build the master problem and the dual subproblems I use MasterProblem and DualSubProblem classes that are defined in different headers. These classes have different functions to build the required problems.
As you can see in the callback function,
- I use Get_The_Incumbent_Integer_Solution() function to get the incumbent solution of the master problem as follows.
void CBD_Callback::Get_The_Incumbent_Integer_Solution(){
//Get the value of thetaOmega
for (int omega = 1; omega <= numScenarios; omega++){
incumbentSolutionPtr->thetaOmegaVal[omega] = getSolution(modelsPtr->masterProblem_Model.getVar(modelsPtr->varIndex.thetaOmegaIndex[omega]));
}
//Get the value of X, Y and Z
for (int i = 1; i <= numOfNodes; i++){
for (int j = 1; j <= numOfNodes; j++){
for (int t = 1; t <= numOfTimeSlots; t++){
incumbentSolutionPtr->xVal[i][j][t] = getSolution(modelsPtr->masterProblem_Model.getVar(modelsPtr->varIndex.xIndex[i][j][t]));
incumbentSolutionPtr->yVal[i][j][t] = getSolution(modelsPtr->masterProblem_Model.getVar(modelsPtr->varIndex.yIndex[i][j][t]));
incumbentSolutionPtr->zVal[i][j][t] = getSolution(modelsPtr->masterProblem_Model.getVar(modelsPtr->varIndex.zIndex[i][j][t]));
}
}
}
}
- I use Solve_DualSubProblems_And_Get_Duals() function to build (or modify) and solve the dual subproblems as follows
void CBD_Callback::Solve_DualSubProblems_And_Get_Duals(){
// Create or modify dual subproblems
if (dualSubproblems_wereCreated == false){
for (int omega = 1; omega <= numScenarios; omega++){
modelsPtr->Build_Dual_Subproblem_Model_For_First_Iteration(omega, modelsPtr->dualSubproblem_Model[omega], modelsPtr->varIndex, *incumbentSolutionPtr);
}
dualSubproblems_wereCreated = true;
}
else {
for (int omega = 1; omega <= numScenarios; omega++){
modelsPtr->Modify_Objective_Function_Of_The_DualSubproblem(omega, modelsPtr->dualSubproblem_Model[omega], modelsPtr->varIndex, *incumbentSolutionPtr);
}
}
// Solve dual subproblems and get the dual values
for (int omega = 1; omega <= numScenarios; omega++) {
modelsPtr->Solve_Dual_Model(modelsPtr->dualSubproblem_Model[omega], *incumbentSolutionPtr);
modelsPtr->Get_The_Solution_Of_Sub_Dual_Model(omega, modelsPtr->dualSubproblem_Model[omega], modelsPtr->varIndex, *incumbentSolutionPtr);
}
}
- Finally, I use Create_and_Add_Generalized_Multiple_Benders_Cuts() function to build the Benders cuts and add them to the master problem as follows.
void CBD_Callback::Create_and_Add_Generalized_Multiple_Benders_Cuts(){
for (int omega = 1; omega <= numScenarios; omega++){
if (incumbentSolutionPtr->thetaOmegaVal[omega] - incumbentSolutionPtr->objDualSubVal[omega] > comparisonError){
GRBLinExpr cutExpr = 0;
modelsPtr->Create_Generalized_Multiple_Benders_Cuts(omega, cutExpr, *incumbentSolutionPtr);
addLazy(cutExpr, GRB_GREATER_EQUAL, 0.0);
myCuts.push_back(cutExpr);
}
}
}
The algorithm works well for small-sized instances and gives the optimal solution. The solution is valid since I checked it with the extensive model (the model that contains all the scenarios). I got the optimal solution for more than 50 small-sized instances! So, I'm almost sure that the mathematical formulations and decomposition approach work well.
When I run the algorithm for a mid-sized problem, it produces an incorrect optimal solution with a value of 1470.55 (The sense of the objective function is maximization). Initially, I suspected that the Benders cuts added during the callbacks might be invalid. To test this, I stored all generated cuts in a vector. At the end, I created a new master problem, added all the cuts, and solved this problem without using callbacks.
This time, I got a better solution with a value of 1607.82, despite having added all the cuts!
I am totally confused about what is happening here! Could you please help me understand what might be going wrong? Any advice on how to address this issue would be greatly appreciated.
I can provide more details if required.
Thanks,
Amirhossein
0
-
Also, I want to add something else! According to the MIP logging I've attached, Gurobi explored 515 nodes when I used the callback function to solve the master problem. The last node is 514, and the best bound at this node is 1616.99. However, Gurobi stopped at this node and reported that the optimal solution was found. How is this possible?
Set parameter Username
Academic license - for non-commercial use only - expires 2025-03-08
Indices of the middle 5 members of the vector (excluding member with index 0):
Set parameter LazyConstraints to value 1
Set parameter PreCrush to value 1
Set parameter TimeLimit to value 1996.884
Set parameter MIPGap to value 0
Set parameter Threads to value 1
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2))
CPU model: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 1 threads
Optimize a model with 82649 rows, 81586 columns and 415060 nonzeros
Model fingerprint: 0xc270a543
Variable types: 70951 continuous, 10635 integer (0 binary)
Coefficient statistics:
Matrix range [1e-02, 5e+02]
Objective range [1e-02, 1e-02]
Bounds range [2e+09, 2e+09]
RHS range [6e-01, 4e+01]
Warning: Model contains large bounds
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 15900 rows and 13074 columns (presolve time = 5s) ...
Presolve removed 15900 rows and 13074 columns
Presolve time: 5.04s
Presolved: 66749 rows, 68512 columns, 340115 nonzeros
Variable types: 59533 continuous, 8979 integer (5999 binary)
objVal = -1e+100 & bestBound = 5313.23
Root relaxation presolved: 66787 rows, 68512 columns, 352565 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 5.3132300e+03 3.308461e+04 0.000000e+00 24s
9232 3.7692065e+03 6.652288e+04 0.000000e+00 25s
14451 1.6234500e+03 0.000000e+00 0.000000e+00 26s
Root relaxation: objective 1.623450e+03, 14451 iterations, 1.46 seconds (2.69 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1623.45000 0 118 - 1623.45000 - - 26s
objVal = -1e+100 & bestBound = 1623.45
0 0 1623.45000 0 118 - 1623.45000 - - 32s
objVal = -1e+100 & bestBound = 1623.45
objVal = -1e+100 & bestBound = 1623.45
objVal = -1e+100 & bestBound = 1623.45
H 0 0 670.9500000 1623.45000 142% - 33s
objVal = 670.95 & bestBound = 1623.45
0 0 1623.45000 0 118 670.95000 1623.45000 142% - 37s
objVal = 670.95 & bestBound = 1623.45
objVal = 670.95 & bestBound = 1623.45
objVal = 670.95 & bestBound = 1623.45
H 0 0 704.7600000 1623.45000 130% - 39s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 41s
objVal = 704.76 & bestBound = 1623.45
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 48s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 51s
objVal = 704.76 & bestBound = 1623.45
0 0 1623.45000 0 118 704.76000 1623.45000 130% - 55s
0 0 1619.79926 0 142 704.76000 1619.79926 130% - 58s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 62s
objVal = 704.76 & bestBound = 1619.69
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 67s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 70s
objVal = 704.76 & bestBound = 1619.69
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 87s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 103s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 118s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 133s
objVal = 704.76 & bestBound = 1619.69
0 0 1619.68731 0 142 704.76000 1619.68731 130% - 149s
0 0 1619.52699 0 146 704.76000 1619.52699 130% - 153s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 157s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 161s
objVal = 704.76 & bestBound = 1619.49
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 168s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 172s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 181s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 190s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 204s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 215s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 229s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 238s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 245s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 253s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 261s
objVal = 704.76 & bestBound = 1619.49
0 0 1619.48577 0 146 704.76000 1619.48577 130% - 269s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 277s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 283s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 288s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 295s
objVal = 704.76 & bestBound = 1617
0 0 1616.99826 0 266 704.76000 1616.99826 129% - 302s
0 2 1616.99826 0 266 704.76000 1616.99826 129% - 302s
2 4 1616.99826 2 264 704.76000 1616.99826 129% 872 306s
6 8 1616.99826 6 143 704.76000 1616.99826 129% 507 310s
8 10 1616.99826 7 258 704.76000 1616.99826 129% 857 319s
9 11 1616.99826 8 141 704.76000 1616.99826 129% 809 323s
10 12 1616.99826 9 255 704.76000 1616.99826 129% 871 328s
11 13 1616.99826 9 146 704.76000 1616.99826 129% 960 332s
12 14 1616.99826 10 253 704.76000 1616.99826 129% 947 335s
14 16 1616.99826 12 249 704.76000 1616.99826 129% 881 342s
15 17 1616.99826 13 213 704.76000 1616.99826 129% 881 346s
16 18 1616.99826 14 208 704.76000 1616.99826 129% 899 353s
17 19 1616.99826 15 243 704.76000 1616.99826 129% 857 357s
18 20 1616.99826 16 247 704.76000 1616.99826 129% 818 360s
20 22 1616.99826 17 239 704.76000 1616.99826 129% 893 369s
21 23 1616.99826 18 233 704.76000 1616.99826 129% 867 371s
23 25 1616.99826 20 230 704.76000 1616.99826 129% 809 375s
25 27 1616.99826 22 225 704.76000 1616.99826 129% 774 381s
objVal = 704.76 & bestBound = 1617
26 28 1616.99826 23 192 704.76000 1616.99826 129% 765 398s
28 30 1616.99826 25 121 704.76000 1616.99826 129% 739 400s
32 34 1616.99826 29 149 704.76000 1616.99826 129% 729 405s
37 39 1616.99826 33 132 704.76000 1616.99826 129% 679 410s
39 41 1616.99826 35 112 704.76000 1616.99826 129% 703 415s
41 43 1616.99826 36 119 704.76000 1616.99826 129% 713 420s
44 46 1616.99826 39 190 704.76000 1616.99826 129% 702 426s
46 48 1616.99826 41 182 704.76000 1616.99826 129% 687 430s
49 51 1616.99826 44 174 704.76000 1616.99826 129% 656 435s
objVal = 704.76 & bestBound = 1617
52 54 1616.99826 47 155 704.76000 1616.99826 129% 631 464s
53 55 1616.99826 48 153 704.76000 1616.99826 129% 629 465s
60 62 1616.96457 55 157 704.76000 1616.99826 129% 577 470s
68 70 1616.90670 63 108 704.76000 1616.99826 129% 528 475s
75 77 1616.44320 69 96 704.76000 1616.99826 129% 509 480s
88 90 1615.18948 79 85 704.76000 1616.99826 129% 488 485s
101 103 1614.38415 90 76 704.76000 1616.99826 129% 467 490s
108 110 1614.01267 96 76 704.76000 1616.99826 129% 461 495s
117 119 1613.41062 104 70 704.76000 1616.99826 129% 439 500s
127 129 1611.16137 111 67 704.76000 1616.99826 129% 425 505s
143 145 1607.63533 122 36 704.76000 1616.99826 129% 401 510s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
158 160 1513.69200 132 4 704.76000 1616.99826 129% 374 517s
objVal = 704.76 & bestBound = 1617
159 161 1506.86933 133 6 704.76000 1616.99826 129% 372 520s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
160 162 1616.99826 2 262 704.76000 1616.99826 129% 390 532s
161 163 1616.99826 3 280 704.76000 1616.99826 129% 402 539s
162 164 1616.99826 4 261 704.76000 1616.99826 129% 406 545s
163 165 1616.99826 5 253 704.76000 1616.99826 129% 411 551s
164 166 1616.99826 6 322 704.76000 1616.99826 129% 415 555s
165 167 1616.99826 7 329 704.76000 1616.99826 129% 417 560s
166 168 1616.99826 8 325 704.76000 1616.99826 129% 426 567s
167 169 1616.99826 9 302 704.76000 1616.99826 129% 431 572s
168 170 1616.99826 10 216 704.76000 1616.99826 129% 431 575s
170 172 1616.99826 12 169 704.76000 1616.99826 129% 430 580s
172 174 1616.99826 14 171 704.76000 1616.99826 129% 430 587s
174 176 1616.99826 16 173 704.76000 1616.99826 129% 431 591s
176 178 1616.99826 18 176 704.76000 1616.99826 129% 433 596s
178 180 1616.99826 20 188 704.76000 1616.99826 129% 434 600s
181 183 1616.99826 23 172 704.76000 1616.99826 129% 433 606s
184 186 1616.99826 26 185 704.76000 1616.99826 129% 428 610s
187 189 1616.99826 29 187 704.76000 1616.99826 129% 432 617s
189 191 1616.99826 31 183 704.76000 1616.99826 129% 433 621s
192 194 1616.99826 34 131 704.76000 1616.99826 129% 431 626s
196 198 1616.99826 38 129 704.76000 1616.99826 129% 429 630s
206 208 1616.99826 48 134 704.76000 1616.99826 129% 417 635s
216 218 1615.25229 57 119 704.76000 1616.99826 129% 416 643s
219 221 1616.13182 59 103 704.76000 1616.99826 129% 414 645s
229 231 1615.62876 68 115 704.76000 1616.99826 129% 406 650s
239 241 1614.96381 78 90 704.76000 1616.99826 129% 400 655s
248 250 1612.14369 85 63 704.76000 1616.99826 129% 394 660s
objVal = 704.76 & bestBound = 1617
261 263 1606.99926 94 40 704.76000 1616.99826 129% 386 710s
objVal = 704.76 & bestBound = 1617
262 264 1608.22384 95 43 704.76000 1616.99826 129% 384 720s
objVal = 704.76 & bestBound = 1617
281 283 1511.98600 105 12 704.76000 1616.99826 129% 371 727s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
283 285 1537.27280 105 8 704.76000 1616.99826 129% 370 732s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
285 287 1508.72000 106 7 704.76000 1616.99826 129% 369 736s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
288 290 1616.99826 5 275 704.76000 1616.99826 129% 374 747s
289 291 1616.99826 6 270 704.76000 1616.99826 129% 379 752s
290 292 1616.99826 7 274 704.76000 1616.99826 129% 382 758s
291 293 1616.99826 8 213 704.76000 1616.99826 129% 382 761s
292 294 1616.99826 9 262 704.76000 1616.99826 129% 386 767s
293 295 1616.99826 10 280 704.76000 1616.99826 129% 388 773s
294 296 1616.99826 11 224 704.76000 1616.99826 129% 389 776s
295 297 1616.99826 12 342 704.76000 1616.99826 129% 401 789s
296 298 1616.99826 13 356 704.76000 1616.99826 129% 403 793s
297 299 1616.99826 14 253 704.76000 1616.99826 129% 402 795s
299 301 1616.99826 16 165 704.76000 1616.99826 129% 402 802s
301 303 1616.99826 18 215 704.76000 1616.99826 129% 405 807s
303 305 1616.99826 20 211 704.76000 1616.99826 129% 406 811s
objVal = 704.76 & bestBound = 1617
304 306 1616.68602 21 215 704.76000 1616.99826 129% 412 852s
306 308 1616.36788 23 201 704.76000 1616.99826 129% 415 855s
312 314 1616.08488 29 165 704.76000 1616.99826 129% 415 860s
318 320 1614.29378 35 129 704.76000 1616.99826 129% 420 865s
330 332 1611.97319 47 133 704.76000 1616.99826 129% 418 870s
352 354 1610.25306 69 89 704.76000 1616.99826 129% 403 875s
objVal = 704.76 & bestBound = 1617
386 388 1552.51521 91 11 704.76000 1616.99826 129% 379 882s
objVal = 704.76 & bestBound = 1617
387 389 1528.56600 92 9 704.76000 1616.99826 129% 378 885s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
392 394 1485.81619 94 8 704.76000 1616.99826 129% 375 890s
objVal = 704.76 & bestBound = 1617
objVal = 704.76 & bestBound = 1617
* 395 395 96 1470.5500000 1616.99826 10.0% 372 893s
objVal = 1470.55 & bestBound = 1617
397 395 cutoff 98 1470.55000 1616.99826 10.0% 371 895s
399 395 1616.99826 8 272 1470.55000 1616.99826 10.0% 377 902s
400 396 1616.99826 9 224 1470.55000 1616.99826 10.0% 381 908s
401 397 1616.99826 10 274 1470.55000 1616.99826 10.0% 382 912s
402 398 1616.99826 11 263 1470.55000 1616.99826 10.0% 385 919s
403 399 1616.99826 12 362 1470.55000 1616.99826 10.0% 391 930s
404 400 1616.99826 13 265 1470.55000 1616.99826 10.0% 393 936s
405 401 1616.99826 14 268 1470.55000 1616.99826 10.0% 395 943s
406 402 1616.99826 15 280 1470.55000 1616.99826 10.0% 396 948s
407 403 1616.99826 15 197 1470.55000 1616.99826 10.0% 398 953s
408 404 1616.95038 16 196 1470.55000 1616.99826 10.0% 398 956s
410 406 1561.91103 17 227 1470.55000 1616.99826 10.0% 406 968s
411 407 1616.84898 18 227 1470.55000 1616.99826 10.0% 405 970s
412 408 1616.31481 19 227 1470.55000 1616.99826 10.0% 408 975s
414 410 1616.12507 21 193 1470.55000 1616.99826 10.0% 410 980s
418 414 1615.97511 25 217 1470.55000 1616.99826 10.0% 412 986s
420 416 1615.79109 27 225 1470.55000 1616.99826 10.0% 413 990s
427 423 1615.59894 34 195 1470.55000 1616.99826 10.0% 412 996s
431 427 1615.48371 38 166 1470.55000 1616.99826 10.0% 410 1000s
438 434 1615.21606 45 144 1470.55000 1616.99826 10.0% 409 1005s
441 437 1614.64498 48 109 1470.55000 1616.99826 10.0% 410 1010s
445 441 1613.93977 52 112 1470.55000 1616.99826 10.0% 410 1015s
454 450 1612.83692 61 110 1470.55000 1616.99826 10.0% 406 1020s
462 458 1611.53636 68 103 1470.55000 1616.99826 10.0% 404 1025s
480 476 1606.01498 85 54 1470.55000 1616.99826 10.0% 394 1030s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
495 491 1506.73333 95 10 1470.55000 1616.99826 10.0% 385 1038s
objVal = 1470.55 & bestBound = 1617
500 496 1489.84413 98 6 1470.55000 1616.99826 10.0% 381 1040s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
501 495 cutoff 98 1470.55000 1616.99826 10.0% 381 1045s
objVal = 1470.55 & bestBound = 1617
objVal = 1470.55 & bestBound = 1617
503 497 1596.69407 4 237 1470.55000 1616.99826 10.0% 391 1059s
504 498 1596.66326 5 294 1470.55000 1616.99826 10.0% 391 1060s
506 500 1596.13939 7 231 1470.55000 1616.99826 10.0% 396 1068s
507 501 1595.93108 8 339 1470.55000 1616.99826 10.0% 402 1079s
508 502 1595.65134 9 209 1470.55000 1616.99826 10.0% 404 1088s
509 503 1595.59132 10 210 1470.55000 1616.99826 10.0% 405 1090s
511 505 1595.04184 12 209 1470.55000 1616.99826 10.0% 409 1100s
514 508 1595.19540 14 181 1470.55000 1616.99826 10.0% 412 1106s
Cutting planes:
Gomory: 3
MIR: 111
Flow cover: 340
RLT: 2
Lazy constraints: 5434
Explored 515 nodes (238900 simplex iterations) in 1108.01 seconds (1658.27 work units)
Thread count was 1 (of 16 available processors)
Solution count 3: 1470.55 704.76 670.95
Optimal solution found (tolerance 0.00e+00)
Best objective 1.470550000000e+03, best bound 1.470550000000e+03, gap 0.0000%
User-callback calls 73284, time in user-callback 185.07 sec0 -
Hi,
To your first question, why you do not get the same result when adding all generated cuts initially to your master problem: In the second case, the solver follows a different solution path, so potentially other solutions are found. If you do not check them in the callback, they are accepted. This is why you get a better solution in the second approach. You could check the final solution you get in the second run, I bet it is not feasible or would lead to further Benders cuts.
To your second question on the solver log, I guess you added a Benders cut that closed the residual gap. Add some more outputs to debug this case. The solver only outputs log updates every few seconds. If the problem is solved within such an interval, you will see just the final summary, as in your case.
Best regards,
Mario0 -
Dear Mario,
Thank you very much for your reply!You could check the final solution you get in the second run, I bet it is not feasible or would lead to further Benders cuts.
That's exactly why I'm confused here! The solution I got in the second run is both feasible and optimal.
Additionally, I conducted two further tests:- Test 1: I got the optimal solution of the problem using the extensive model (i.e., the model that includes all variables), which I'll refer to as optSol#1. I then solved the problem using Benders Decomposition. At each iteration, I checked the RHS of the generated Benders cut for optSol#1. None of them cut off this solution. However, in the end, I got another solution with a worse objective value. So, why doesn't the solver find optSol#1 (or a solution with the same objective value), especially considering that no cut was generated to exclude optSol#1 in the callback function?
- Test 2: I fixed optSol#1 into the master problem and again solved it using Benders Decomposition. After one iteration, I got the optSol#1.
So,
I have a model for which I know the optimal solution. When I fix this solution into the master problem, everything works well. When I do not fix the solution into the master problem, I get a solution that is not optimal while no cut is generated to exclude the optimal solution!
Could you please help me understand what might be going wrong?Thanks,
Amirhossein0 -
If there are no constraints in the initial master problem and not added Benders cuts that cut off optSol#1, and you obtain an "optimal" solution that is worse than optSol#1, then there is something fishy.
Could you generate a very small example that I can try to reproduce on my side? Please remove all parts that are not needed to show the issue.
0
サインインしてコメントを残してください。
コメント
4件のコメント