Scippy

    SCIP

    Solving Constraint Integer Programs

    benders.c
    Go to the documentation of this file.
    1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    2/* */
    3/* This file is part of the program and library */
    4/* SCIP --- Solving Constraint Integer Programs */
    5/* */
    6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
    7/* */
    8/* Licensed under the Apache License, Version 2.0 (the "License"); */
    9/* you may not use this file except in compliance with the License. */
    10/* You may obtain a copy of the License at */
    11/* */
    12/* http://www.apache.org/licenses/LICENSE-2.0 */
    13/* */
    14/* Unless required by applicable law or agreed to in writing, software */
    15/* distributed under the License is distributed on an "AS IS" BASIS, */
    16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
    17/* See the License for the specific language governing permissions and */
    18/* limitations under the License. */
    19/* */
    20/* You should have received a copy of the Apache-2.0 license */
    21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
    22/* */
    23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
    24
    25/**@file MinIISC/src/benders.c
    26 * @brief run Benders algorithm
    27 * @author Marc Pfetsch
    28 *
    29 * Run Benders algorithm using an oracle for solving the subproblems and solving the master problem to optimality.
    30 */
    31
    32#include "benders.h"
    33
    34/* other parameters */
    35#define MAXITERATIONS 10000 /**< maximal number of iterations of main loop */
    36
    37
    38/** output status */
    39static
    40SCIP_RETCODE printStatus(
    41 SCIP* masterscip, /**< master problem SCIP instance */
    42 SCIP_STATUS status /**< solution status */
    43 )
    44{
    45 SCIPinfoMessage(masterscip, NULL, "SCIP Status : ");
    46 switch ( status )
    47 {
    48 case SCIP_STATUS_UNKNOWN:
    49 SCIPinfoMessage(masterscip, NULL, "unknown");
    50 break;
    51 case SCIP_STATUS_USERINTERRUPT:
    52 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [user interrupt]");
    53 break;
    54 case SCIP_STATUS_NODELIMIT:
    55 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [node limit reached]");
    56 break;
    57 case SCIP_STATUS_TIMELIMIT:
    58 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [time limit reached]");
    59 break;
    60 case SCIP_STATUS_MEMLIMIT:
    61 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [memory limit reached]");
    62 break;
    63 case SCIP_STATUS_GAPLIMIT:
    64 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [gap limit reached]");
    65 break;
    66 case SCIP_STATUS_OPTIMAL:
    67 SCIPinfoMessage(masterscip, NULL, "problem is solved [optimal solution found]");
    68 break;
    69 case SCIP_STATUS_INFEASIBLE:
    70 SCIPinfoMessage(masterscip, NULL, "problem is solved [infeasible]");
    71 break;
    72 case SCIP_STATUS_UNBOUNDED:
    73 SCIPinfoMessage(masterscip, NULL, "problem is solved [unbounded]");
    74 break;
    75 case SCIP_STATUS_TOTALNODELIMIT:
    76 SCIPinfoMessage(masterscip, NULL, "solving was interrupted [iteration limit reached]");
    77 break;
    78 case SCIP_STATUS_STALLNODELIMIT:
    79 case SCIP_STATUS_SOLLIMIT:
    80 case SCIP_STATUS_BESTSOLLIMIT:
    81 case SCIP_STATUS_RESTARTLIMIT:
    82 case SCIP_STATUS_INFORUNBD:
    83 SCIPerrorMessage("unexpected status code <%d>\n", status);
    84 return SCIP_INVALIDDATA;
    85 default:
    86 SCIPerrorMessage("invalid status code <%d>\n", status);
    87 return SCIP_INVALIDDATA;
    88 }
    89 SCIPinfoMessage(masterscip, NULL, "\n");
    90
    91 return SCIP_OKAY;
    92}
    93
    94
    95/** output short statistics */
    96static
    97SCIP_RETCODE printShortStatistics(
    98 SCIP* masterscip, /**< master problem SCIP instance */
    99 SCIP_STATUS status, /**< solution status */
    100 SCIP_CLOCK* totaltimeclock, /**< clock for total time */
    101 SCIP_Real primalbound, /**< primal bound */
    102 SCIP_Real dualbound, /**< dual bound */
    103 SCIP_Longint ntotalnodes, /**< total number of nodes */
    104 int niter /**< number of iterations */
    105 )
    106{
    107 SCIP_Real gap = 1e20;
    108
    109 if ( ! SCIPisInfinity(masterscip, primalbound) && ! SCIPisInfinity(masterscip, -dualbound) )
    110 gap = fabs(primalbound - dualbound)/(MAX3(fabs(primalbound), fabs(dualbound), 1.0));
    111
    112 /* start output */
    113 SCIPinfoMessage(masterscip, NULL, "\n");
    114
    115 SCIP_CALL( printStatus(masterscip, status) );
    116 SCIPinfoMessage(masterscip, NULL, "Solving Time (sec) : %.2f\n", SCIPgetClockTime(masterscip, totaltimeclock));
    117 SCIPinfoMessage(masterscip, NULL, "Solving Nodes : %" SCIP_LONGINT_FORMAT " (total of %" SCIP_LONGINT_FORMAT " nodes in %d runs)\n",
    118 ntotalnodes, ntotalnodes, niter);
    119 SCIPinfoMessage(masterscip, NULL, "Primal Bound : %+21.14e\n", primalbound);
    120 SCIPinfoMessage(masterscip, NULL, "Dual Bound : %+21.14e\n", dualbound);
    121 if ( SCIPisInfinity(masterscip, gap) )
    122 SCIPinfoMessage(masterscip, NULL, "Gap : infinite\n");
    123 else
    124 SCIPinfoMessage(masterscip, NULL, "Gap : %.2f %%\n", 100.0 * gap);
    125 SCIPinfoMessage(masterscip, NULL, "\n");
    126
    127 return SCIP_OKAY;
    128}
    129
    130
    131/** output long statistics */
    132static
    133SCIP_RETCODE printLongStatistics(
    134 SCIP* masterscip, /**< master problem SCIP instance */
    135 SCIP_STATUS status, /**< solution status */
    136 SCIP_CLOCK* totaltimeclock, /**< clock for total time */
    137 SCIP_CLOCK* oracletimeclock, /**< clock for oracle */
    138 SCIP_CLOCK* mastertimeclock, /**< clock for master problem */
    139 SCIP_Real primalbound, /**< primal bound */
    140 SCIP_Real dualbound, /**< dual bound */
    141 SCIP_Longint ntotalnodes, /**< total number of nodes */
    142 SCIP_Longint ntotalcuts, /**< total number of cuts */
    143 int niter /**< number of iterations */
    144 )
    145{
    146 SCIP_Real gap = 1e20;
    147
    148 if ( ! SCIPisInfinity(masterscip, primalbound) && ! SCIPisInfinity(masterscip, -dualbound) )
    149 gap = fabs(primalbound - dualbound)/(MAX3(fabs(primalbound), fabs(dualbound), 1.0));
    150
    151 /* start output */
    152 SCIPinfoMessage(masterscip, NULL, "\n");
    153
    154 /* print main part of statistics */
    155 SCIP_CALL( printStatus(masterscip, status) );
    156
    157 SCIPinfoMessage(masterscip, NULL, "Total Time : %10.2f\n", SCIPgetClockTime(masterscip, totaltimeclock));
    158 SCIPinfoMessage(masterscip, NULL, " solving : %10.2f\n", SCIPgetClockTime(masterscip, totaltimeclock));
    159 SCIPinfoMessage(masterscip, NULL, " master : %10.2f (included in solving)\n", SCIPgetClockTime(masterscip, mastertimeclock));
    160 SCIPinfoMessage(masterscip, NULL, " oracle : %10.2f (included in solving)\n", SCIPgetClockTime(masterscip, oracletimeclock));
    161
    162 SCIPinfoMessage(masterscip, NULL, "Original Problem :\n");
    163 SCIPinfoMessage(masterscip, NULL, " Problem name : %s\n", SCIPgetProbName(masterscip));
    164 SCIPinfoMessage(masterscip, NULL, " Variables : %d (%d binary, %d integer, %d implicit integer, %d continuous)\n",
    165 SCIPgetNVars(masterscip), SCIPgetNOrigVars(masterscip), 0, 0, 0);
    166 SCIPinfoMessage(masterscip, NULL, " Constraints : %d initial, %d maximal\n", 1, SCIPgetNOrigConss(masterscip));
    167 SCIPinfoMessage(masterscip, NULL, " Objective sense : minimize\n");
    168
    169 SCIPinfoMessage(masterscip, NULL, "Presolved Problem :\n");
    170 SCIPinfoMessage(masterscip, NULL, " Problem name : %s\n", SCIPgetProbName(masterscip));
    171 SCIPinfoMessage(masterscip, NULL, " Variables : %d (%d binary, %d integer, %d implicit integer, %d continuous)\n",
    172 SCIPgetNVars(masterscip), SCIPgetNBinVars(masterscip), SCIPgetNIntVars(masterscip), SCIPgetNImplVars(masterscip), SCIPgetNContVars(masterscip));
    173 SCIPinfoMessage(masterscip, NULL, " Constraints : %d initial, %d maximal\n", SCIPgetNConss(masterscip), SCIPgetNOrigConss(masterscip));
    174
    175 SCIPinfoMessage(masterscip, NULL, "Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children\n");
    176 SCIPinfoMessage(masterscip, NULL, " %-17.17s: %10d %10d %10d %10d %10d %10d %10d %10d %10d %10d %10d %10d %10" SCIP_LONGINT_FORMAT " %10d\n",
    177 "benders", 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ntotalcuts, 0);
    178
    179 SCIPinfoMessage(masterscip, NULL, "Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp SB-Prop\n");
    180 SCIPinfoMessage(masterscip, NULL, " %-17.17s: %10.2f %10.2f %10.2f %10.2f %10.2f %10.2f %10.2f %10.2f %10.2f\n", "benders",
    181 SCIPgetClockTime(masterscip, oracletimeclock), 0.0, SCIPgetClockTime(masterscip, oracletimeclock), 0.0, 0.0, 0.0, 0.0, 0.0, 0.0);
    182
    183 SCIPinfoMessage(masterscip, NULL, "B&B Tree :\n");
    184 SCIPinfoMessage(masterscip, NULL, " number of runs : %10d\n", niter);
    185 SCIPinfoMessage(masterscip, NULL, " nodes (total) : %10" SCIP_LONGINT_FORMAT "\n", ntotalnodes);
    186
    187 SCIPinfoMessage(masterscip, NULL, "Solution :\n");
    188 SCIPinfoMessage(masterscip, NULL, " Primal Bound : %+21.14e\n", primalbound);
    189 SCIPinfoMessage(masterscip, NULL, " Dual Bound : %+21.14e\n", dualbound);
    190 if ( SCIPisInfinity(masterscip, gap) )
    191 SCIPinfoMessage(masterscip, NULL, " Gap : infinite\n");
    192 else
    193 SCIPinfoMessage(masterscip, NULL, " Gap : %10.2f %%\n", 100.0 * gap);
    194
    195#ifdef SCIP_OUTPUT
    196 SCIPinfoMessage(masterscip, NULL, "\nTotal used time:\t %f\n", SCIPgetClockTime(masterscip, totaltimeclock));
    197 SCIPinfoMessage(masterscip, NULL, "Oracle time:\t\t %f\n", SCIPgetClockTime(masterscip, oracletimeclock));
    198 SCIPinfoMessage(masterscip, NULL, "Master problem time:\t %f\n", SCIPgetClockTime(masterscip, mastertimeclock));
    199 SCIPinfoMessage(masterscip, NULL, "Number of iterations:\t %d\n", niter);
    200#endif
    201
    202 return SCIP_OKAY;
    203}
    204
    205
    206/** run Benders algorithm using an oracle for the subproblems */
    207SCIP_RETCODE runBenders(
    208 SCIP* masterscip, /**< master SCIP instance */
    209 BENDERS_CUTORACLE((*Oracle)), /**< oracle for Benders subproblem */
    210 BENDERS_DATA* data, /**< user data for oracle */
    211 SCIP_Real timelimit, /**< time limit read from arguments */
    212 SCIP_Real memlimit, /**< memory limit read from arguments */
    213 int dispfreq, /**< display frequency */
    214 SCIP_Bool usereopt, /**< Use reoptimization? */
    215 SCIP_Bool solvemasterapprox, /**< Solve master problem approximately? */
    216 SCIP_Longint masterstallnodes, /**< stall nodes for master problem if solvemasterapprox is true */
    217 SCIP_Real mastergaplimit, /**< gap limit for master problem if solvemasterapprox is true */
    218 SCIP_VERBLEVEL verblevel, /**< verbosity level for output */
    219 SCIP_STATUS* status /**< status of optimization */
    220 )
    221{ /*lint --e{788}*/
    222 SCIP_CLOCK* totaltimeclock;
    223 SCIP_CLOCK* oracletimeclock;
    224 SCIP_CLOCK* mastertimeclock;
    225 SCIP_Bool masteroptimal = TRUE;
    226 const int maxIters = MAXITERATIONS;
    227 SCIP_Longint ntotalnodes = 0LL;
    228 SCIP_Longint ntotalcuts = 0LL;
    229 SCIP_VAR** mastervars;
    230 SCIP_Real* mastersolution;
    231 SCIP_Real primalbound = 1e20;
    232 SCIP_Real dualbound = -1e20;
    233 SCIP_Real mastersolobj = 0.0;
    234 int nmastervars;
    235 int niter = 0;
    236
    237 assert( status != NULL );
    238 *status = SCIP_STATUS_UNKNOWN;
    239
    240 SCIP_CALL( SCIPgetOrigVarsData(masterscip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
    241
    242 SCIP_CALL( SCIPallocClearBlockMemoryArray(masterscip, &mastersolution, nmastervars) );
    243
    244 /* set output to console */
    245#ifdef SCIP_DEBUG
    246 SCIP_CALL( SCIPsetIntParam(masterscip, "display/verblevel", 5) );
    247#else
    248 SCIP_CALL( SCIPsetIntParam(masterscip, "display/verblevel", 0) );
    249#endif
    250
    251 if ( ! SCIPisInfinity(masterscip, memlimit) )
    252 {
    253 SCIP_CALL( SCIPsetRealParam(masterscip, "limits/memory", memlimit) );
    254 }
    255
    256 if ( dispfreq >= 0 )
    257 SCIP_CALL( SCIPsetIntParam(masterscip, "display/freq", dispfreq) );
    258 else
    259 SCIP_CALL( SCIPsetIntParam(masterscip, "display/freq", 1000) );
    260
    261 /* possibly use reoptimization */
    262 if ( usereopt )
    263 {
    264 assert( SCIPgetNIntVars(masterscip) == 0 );
    265 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    266 SCIPinfoMessage(masterscip, NULL, "\nUsing reoptimization.\n");
    267 SCIP_CALL( SCIPenableReoptimization(masterscip, TRUE) );
    268 }
    269
    270 /* set up clocks */
    271 SCIP_CALL( SCIPcreateClock(masterscip, &totaltimeclock) );
    272 SCIP_CALL( SCIPstartClock(masterscip, totaltimeclock) );
    273
    274 SCIP_CALL( SCIPcreateClock(masterscip, &oracletimeclock) );
    275 SCIP_CALL( SCIPcreateClock(masterscip, &mastertimeclock) );
    276
    277 /* output */
    278 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    279 {
    280 if ( solvemasterapprox )
    281 {
    282 if ( ! SCIPisInfinity(masterscip, timelimit) )
    283 SCIPinfoMessage(masterscip, NULL, "\nApproximately solving master problem with time limit %.1f and gap limit %.2f%% ...\n", timelimit, 100.0 * mastergaplimit);
    284 else
    285 SCIPinfoMessage(masterscip, NULL, "\nApproximately solving master problem with gap limit %.2f%% ...\n", 100.0 * mastergaplimit);
    286 }
    287 else
    288 {
    289 if ( ! SCIPisInfinity(masterscip, timelimit) )
    290 SCIPinfoMessage(masterscip, NULL, "\nOptimally solving master problem with time limit: %.1f ...\n", timelimit);
    291 else
    292 SCIPinfoMessage(masterscip, NULL, "\nOptimally solving master problem ...\n");
    293 }
    294 }
    295
    296 /* print banner */
    297 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    298 {
    299 if ( solvemasterapprox )
    300 SCIPinfoMessage(masterscip, NULL, " time | niter |nconss | nvars |master|totalnodes|oracle| ncuts | dualbound | gap\n");
    301 else
    302 SCIPinfoMessage(masterscip, NULL, " time | niter |nconss | nvars |master|totalnodes|oracle| ncuts | dualbound\n");
    303 }
    304
    305 /* iterate */
    306 do
    307 {
    308 BENDERS_STATUS substatus = BENDERS_STATUS_UNKNOWN;
    309 SCIP_STATUS masterstatus = SCIP_STATUS_UNKNOWN;
    310 SCIP_Bool success = FALSE;
    311 SCIP_Real currenttime;
    312 SCIP_Real subtimelimit;
    313 SCIP_SOL* mastersol = NULL;
    314 SCIP_Real mastergap = 1e20;
    315 int ncuts = 0;
    316 int v;
    317
    318 ++niter;
    319 SCIPdebugMessage("Iteration %d.\n", niter);
    320
    321 /* --------- solve Benders subproblem */
    322
    323 /* compute current time limit */
    324 currenttime = SCIPgetClockTime(masterscip, totaltimeclock);
    325 if ( ! SCIPisInfinity(masterscip, timelimit) )
    326 {
    327 subtimelimit = timelimit - currenttime;
    328 if ( subtimelimit <= 0.1 )
    329 {
    330 SCIPdebugMessage("Time limit exceeded.\n");
    331 goto TERMINATE;
    332 }
    333 SCIPdebugMessage("Solving separation problem ... (time limit: %g)\n", subtimelimit);
    334 }
    335 else
    336 {
    337 subtimelimit = SCIPinfinity(masterscip);
    338 SCIPdebugMessage("Solving separation problem ...\n");
    339 }
    340
    341 /* free solving data in order to add constraints */
    342 if ( usereopt )
    343 {
    344 SCIP_CALL( SCIPfreeReoptSolve(masterscip) );
    345 }
    346 else
    347 {
    348 SCIP_CALL( SCIPfreeTransform(masterscip) );
    349 }
    350
    351 /* check for Benders cuts */
    352 SCIP_CALL( SCIPstartClock(masterscip, oracletimeclock) );
    353 SCIP_CALL( Oracle(masterscip, nmastervars, mastervars, mastersolution, data, timelimit, ntotalcuts, &ncuts, &substatus) );
    354 SCIP_CALL( SCIPstopClock(masterscip, oracletimeclock) );
    355 ntotalcuts += (SCIP_Longint) ncuts;
    356
    357 switch ( substatus )
    358 {
    359 case BENDERS_STATUS_ADDEDCUT:
    360 break;
    361
    362 case BENDERS_STATUS_SUCCESS:
    363 success = TRUE;
    364 primalbound = mastersolobj;
    365 break;
    366
    367 case BENDERS_STATUS_TIMELIMIT:
    368 *status = SCIP_STATUS_TIMELIMIT;
    369 goto TERMINATE;
    370
    371 case BENDERS_STATUS_USERINTERRUPT:
    372 *status = SCIP_STATUS_USERINTERRUPT;
    373 goto TERMINATE;
    374
    375 default:
    376 SCIPerrorMessage("Subproblem returned with status %d. Exiting ...\n", substatus);
    377 return SCIP_ERROR;
    378 }
    379
    380 /* if not cuts could be found, the master problem is solved optimally */
    381 if ( success )
    382 {
    383 /* if last master problem was solved to optimality, we are done */
    384 if ( masteroptimal )
    385 break;
    386 /* otherwise, we have to resolve the master to optimality */
    387 solvemasterapprox = FALSE;
    388
    389 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    390 SCIPinfoMessage(masterscip, NULL, "Switching to optimally solving the master problem.\n");
    391 }
    392
    393 /* --------- solve Benders master problem */
    394
    395 /* set current time limit */
    396 currenttime = SCIPgetClockTime(masterscip, totaltimeclock);
    397 if ( ! SCIPisInfinity(masterscip, timelimit) )
    398 {
    399 subtimelimit = timelimit - currenttime;
    400 if ( subtimelimit <= 0.1 )
    401 {
    402 SCIPdebugMessage("Time limit exceeded.\n");
    403 *status = SCIP_STATUS_TIMELIMIT;
    404 goto TERMINATE;
    405 }
    406 }
    407 else
    408 subtimelimit = SCIPinfinity(masterscip);
    409 SCIP_CALL( SCIPsetRealParam(masterscip, "limits/time", subtimelimit) );
    410
    411 /* SCIP_CALL( SCIPprintOrigProblem(masterscip, NULL, "cip", FALSE) ); */
    412
    413 /* set gap limit if we do not have to solve the master to optimality */
    414 if ( solvemasterapprox )
    415 {
    416 SCIP_CALL( SCIPsetLongintParam(masterscip, "limits/stallnodes", masterstallnodes) );
    417 SCIP_CALL( SCIPsetRealParam(masterscip, "limits/gap", mastergaplimit) );
    418 }
    419
    420 /* solve master problem */
    421 SCIP_CALL( SCIPstartClock(masterscip, mastertimeclock) );
    422 SCIP_CALL( SCIPsolve(masterscip) );
    423
    424 ntotalnodes += SCIPgetNTotalNodes(masterscip);
    425
    426 /* possibly reset gap limit */
    427 if ( solvemasterapprox )
    428 {
    429 SCIP_CALL( SCIPsetLongintParam(masterscip, "limits/stallnodes", -1LL) );
    430 SCIP_CALL( SCIPsetRealParam(masterscip, "limits/gap", 0.0) );
    431 }
    432 SCIP_CALL( SCIPstopClock(masterscip, mastertimeclock) );
    433
    434 masterstatus = SCIPgetStatus(masterscip);
    435
    436 /* determine master problem solution status */
    437 masteroptimal = FALSE;
    438 switch ( masterstatus )
    439 {
    440 case SCIP_STATUS_OPTIMAL:
    441 masteroptimal = TRUE;
    442 break;
    443
    444 case SCIP_STATUS_GAPLIMIT:
    445 case SCIP_STATUS_STALLNODELIMIT:
    446 case SCIP_STATUS_UNBOUNDED:
    447 /* do nothing */
    448 break;
    449
    450 case SCIP_STATUS_INFEASIBLE:
    451 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    452 SCIPinfoMessage(masterscip, NULL, "Master problem infeasible.\n");
    453 *status = SCIP_STATUS_INFEASIBLE;
    454 goto TERMINATE;
    455
    456 case SCIP_STATUS_TIMELIMIT:
    457 *status = SCIP_STATUS_TIMELIMIT;
    458 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    459 SCIPinfoMessage(masterscip, NULL, "Time limit exceeded.\n");
    460 goto TERMINATE;
    461
    462 case SCIP_STATUS_USERINTERRUPT:
    463 *status = SCIP_STATUS_USERINTERRUPT;
    464 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    465 SCIPinfoMessage(masterscip, NULL, "User interrupt.\n");
    466 goto TERMINATE;
    467
    468 default:
    469 SCIPerrorMessage("Master problem returned with status %d. Exiting ...\n", masterstatus);
    470 return SCIP_ERROR;
    471 }
    472
    473 mastersol = SCIPgetBestSol(masterscip);
    474 if ( mastersol == NULL )
    475 {
    476 SCIPerrorMessage("Benders master problem does not have a primal solution!\n");
    477 return SCIP_ERROR;
    478 }
    479 mastersolobj = SCIPgetSolOrigObj(masterscip, mastersol);
    480 mastergap = SCIPgetGap(masterscip);
    481
    482 dualbound = MAX(dualbound, SCIPgetDualbound(masterscip));
    483
    484 /* copy solution */
    485 for (v = 0; v < nmastervars; ++v)
    486 {
    487 SCIP_Real val;
    488
    489 val = SCIPgetSolVal(masterscip, mastersol, mastervars[v]);
    490 assert( SCIPisIntegral(masterscip, val) );
    491 mastersolution[v] = val;
    492 }
    493
    494 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    495 {
    496 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, " ");
    497 SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, totaltimeclock), 6);
    498 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    499 SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, niter, 7);
    500 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    501 SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetNOrigConss(masterscip), 7);
    502 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    503 SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetNOrigVars(masterscip), 7);
    504 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    505 SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, mastertimeclock), 6);
    506 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    507 SCIPdispLongint(SCIPgetMessagehdlr(masterscip), NULL, ntotalnodes, 10);
    508 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    509 SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, oracletimeclock), 6);
    510 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
    511 SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, ncuts, 7);
    512 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|%13.6e", mastersolobj);
    513 if ( solvemasterapprox )
    514 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, " | %6.2f%%", 100.0 * mastergap);
    515 SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "\n");
    516 }
    517 }
    518 while ( niter < maxIters );
    519
    520 SCIPdebugMessage("Solution process finished.\n");
    521
    522 if ( niter >= maxIters )
    523 {
    524 *status = SCIP_STATUS_TOTALNODELIMIT;
    525 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    526 SCIPinfoMessage(masterscip, NULL, "Reached iteration limit.\n");
    527 }
    528
    529 if ( masteroptimal )
    530 {
    531 assert( *status == SCIP_STATUS_UNKNOWN );
    532 *status = SCIP_STATUS_OPTIMAL;
    533 }
    534
    535 TERMINATE:
    536
    537 if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
    538 {
    539 SCIP_CALL( printShortStatistics(masterscip, *status, totaltimeclock, primalbound, dualbound, ntotalnodes, niter) );
    540 SCIP_CALL( printLongStatistics(masterscip, *status, totaltimeclock, oracletimeclock, mastertimeclock, primalbound, dualbound, ntotalnodes, ntotalcuts, niter) );
    541 }
    542
    543 SCIPfreeBlockMemoryArray(masterscip, &mastersolution, nmastervars);
    544
    545 SCIP_CALL( SCIPfreeClock(masterscip, &mastertimeclock) );
    546 SCIP_CALL( SCIPfreeClock(masterscip, &oracletimeclock) );
    547 SCIP_CALL( SCIPfreeClock(masterscip, &totaltimeclock) );
    548
    549 return SCIP_OKAY;
    550}
    printStatus
    static SCIP_RETCODE printStatus(SCIP *masterscip, SCIP_STATUS status)
    Definition: benders.c:40
    printLongStatistics
    static SCIP_RETCODE printLongStatistics(SCIP *masterscip, SCIP_STATUS status, SCIP_CLOCK *totaltimeclock, SCIP_CLOCK *oracletimeclock, SCIP_CLOCK *mastertimeclock, SCIP_Real primalbound, SCIP_Real dualbound, SCIP_Longint ntotalnodes, SCIP_Longint ntotalcuts, int niter)
    Definition: benders.c:133
    runBenders
    SCIP_RETCODE runBenders(SCIP *masterscip, BENDERS_CUTORACLE((*Oracle)), BENDERS_DATA *data, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq, SCIP_Bool usereopt, SCIP_Bool solvemasterapprox, SCIP_Longint masterstallnodes, SCIP_Real mastergaplimit, SCIP_VERBLEVEL verblevel, SCIP_STATUS *status)
    Definition: benders.c:207
    MAXITERATIONS
    #define MAXITERATIONS
    Definition: benders.c:35
    printShortStatistics
    static SCIP_RETCODE printShortStatistics(SCIP *masterscip, SCIP_STATUS status, SCIP_CLOCK *totaltimeclock, SCIP_Real primalbound, SCIP_Real dualbound, SCIP_Longint ntotalnodes, int niter)
    Definition: benders.c:97
    BENDERS_STATUS_ADDEDCUT
    @ BENDERS_STATUS_ADDEDCUT
    Definition: benders.h:45
    BENDERS_STATUS_USERINTERRUPT
    @ BENDERS_STATUS_USERINTERRUPT
    Definition: benders.h:48
    BENDERS_STATUS_SUCCESS
    @ BENDERS_STATUS_SUCCESS
    Definition: benders.h:46
    BENDERS_STATUS_UNKNOWN
    @ BENDERS_STATUS_UNKNOWN
    Definition: benders.h:44
    BENDERS_STATUS_TIMELIMIT
    @ BENDERS_STATUS_TIMELIMIT
    Definition: benders.h:47
    BENDERS_CUTORACLE
    #define BENDERS_CUTORACLE(x)
    Definition: benders.h:70
    BENDERS_STATUS
    enum BENDERS_Status BENDERS_STATUS
    Definition: benders.h:51
    NULL
    #define NULL
    Definition: def.h:248
    SCIP_Longint
    #define SCIP_Longint
    Definition: def.h:141
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    MAX3
    #define MAX3(x, y, z)
    Definition: def.h:228
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:156
    TRUE
    #define TRUE
    Definition: def.h:93
    FALSE
    #define FALSE
    Definition: def.h:94
    MAX
    #define MAX(x, y)
    Definition: def.h:220
    SCIP_LONGINT_FORMAT
    #define SCIP_LONGINT_FORMAT
    Definition: def.h:148
    SCIP_CALL
    #define SCIP_CALL(x)
    Definition: def.h:355
    SCIPgetStatus
    SCIP_STATUS SCIPgetStatus(SCIP *scip)
    Definition: scip_general.c:562
    SCIPgetNIntVars
    int SCIPgetNIntVars(SCIP *scip)
    Definition: scip_prob.c:2340
    SCIPgetOrigVarsData
    SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
    Definition: scip_prob.c:2753
    SCIPgetNImplVars
    int SCIPgetNImplVars(SCIP *scip)
    Definition: scip_prob.c:2387
    SCIPgetProbName
    const char * SCIPgetProbName(SCIP *scip)
    Definition: scip_prob.c:1242
    SCIPgetNContVars
    int SCIPgetNContVars(SCIP *scip)
    Definition: scip_prob.c:2569
    SCIPgetNOrigConss
    int SCIPgetNOrigConss(SCIP *scip)
    Definition: scip_prob.c:3712
    SCIPgetNVars
    int SCIPgetNVars(SCIP *scip)
    Definition: scip_prob.c:2246
    SCIPgetNConss
    int SCIPgetNConss(SCIP *scip)
    Definition: scip_prob.c:3620
    SCIPgetNOrigVars
    int SCIPgetNOrigVars(SCIP *scip)
    Definition: scip_prob.c:2838
    SCIPgetNBinVars
    int SCIPgetNBinVars(SCIP *scip)
    Definition: scip_prob.c:2293
    SCIPinfoMessage
    void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
    Definition: scip_message.c:208
    SCIPgetMessagehdlr
    SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
    Definition: scip_message.c:88
    SCIPsetLongintParam
    SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
    Definition: scip_param.c:545
    SCIPsetIntParam
    SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
    Definition: scip_param.c:487
    SCIPsetRealParam
    SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
    Definition: scip_param.c:603
    SCIPdispLongint
    void SCIPdispLongint(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Longint val, int width)
    Definition: disp.c:581
    SCIPdispTime
    void SCIPdispTime(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Real val, int width)
    Definition: disp.c:643
    SCIPdispInt
    void SCIPdispInt(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, int val, int width)
    Definition: disp.c:627
    SCIPfreeBlockMemoryArray
    #define SCIPfreeBlockMemoryArray(scip, ptr, num)
    Definition: scip_mem.h:110
    SCIPallocClearBlockMemoryArray
    #define SCIPallocClearBlockMemoryArray(scip, ptr, num)
    Definition: scip_mem.h:97
    SCIPenableReoptimization
    SCIP_RETCODE SCIPenableReoptimization(SCIP *scip, SCIP_Bool enable)
    Definition: scip_solve.c:3153
    SCIPfreeReoptSolve
    SCIP_RETCODE SCIPfreeReoptSolve(SCIP *scip)
    Definition: scip_solve.c:3399
    SCIPgetBestSol
    SCIP_SOL * SCIPgetBestSol(SCIP *scip)
    Definition: scip_sol.c:2981
    SCIPgetSolOrigObj
    SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
    Definition: scip_sol.c:1892
    SCIPgetSolVal
    SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
    Definition: scip_sol.c:1765
    SCIPfreeTransform
    SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
    Definition: scip_solve.c:3462
    SCIPsolve
    SCIP_RETCODE SCIPsolve(SCIP *scip)
    Definition: scip_solve.c:2635
    SCIPgetGap
    SCIP_Real SCIPgetGap(SCIP *scip)
    Definition: scip_solvingstats.c:1900
    SCIPgetDualbound
    SCIP_Real SCIPgetDualbound(SCIP *scip)
    Definition: scip_solvingstats.c:1428
    SCIPgetNTotalNodes
    SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
    Definition: scip_solvingstats.c:241
    SCIPcreateClock
    SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
    Definition: scip_timing.c:76
    SCIPstopClock
    SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
    Definition: scip_timing.c:178
    SCIPfreeClock
    SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
    Definition: scip_timing.c:127
    SCIPgetClockTime
    SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
    Definition: scip_timing.c:319
    SCIPstartClock
    SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
    Definition: scip_timing.c:161
    SCIPinfinity
    SCIP_Real SCIPinfinity(SCIP *scip)
    Definition: scip_numerics.c:501
    SCIPisIntegral
    SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:585
    SCIPisInfinity
    SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
    Definition: scip_numerics.c:512
    SCIPmessageFPrintInfo
    void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
    Definition: message.c:618
    SCIPerrorMessage
    #define SCIPerrorMessage
    Definition: pub_message.h:64
    SCIPdebugMessage
    #define SCIPdebugMessage
    Definition: pub_message.h:96
    benders.h
    internal methods for Benders' decomposition
    BENDERS_Data
    Definition: classify.c:48
    SCIP_Clock
    Definition: struct_clock.h:65
    SCIP_Sol
    Definition: struct_sol.h:74
    SCIP_Var
    Definition: struct_var.h:262
    SCIP_VERBLEVEL
    enum SCIP_VerbLevel SCIP_VERBLEVEL
    Definition: type_message.h:64
    SCIP_VERBLEVEL_NORMAL
    @ SCIP_VERBLEVEL_NORMAL
    Definition: type_message.h:60
    SCIP_INVALIDDATA
    @ SCIP_INVALIDDATA
    Definition: type_retcode.h:52
    SCIP_OKAY
    @ SCIP_OKAY
    Definition: type_retcode.h:42
    SCIP_ERROR
    @ SCIP_ERROR
    Definition: type_retcode.h:43
    SCIP_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63
    SCIP_STATUS_OPTIMAL
    @ SCIP_STATUS_OPTIMAL
    Definition: type_stat.h:43
    SCIP_STATUS_TOTALNODELIMIT
    @ SCIP_STATUS_TOTALNODELIMIT
    Definition: type_stat.h:50
    SCIP_STATUS_BESTSOLLIMIT
    @ SCIP_STATUS_BESTSOLLIMIT
    Definition: type_stat.h:60
    SCIP_STATUS_SOLLIMIT
    @ SCIP_STATUS_SOLLIMIT
    Definition: type_stat.h:59
    SCIP_STATUS_UNBOUNDED
    @ SCIP_STATUS_UNBOUNDED
    Definition: type_stat.h:45
    SCIP_STATUS_UNKNOWN
    @ SCIP_STATUS_UNKNOWN
    Definition: type_stat.h:42
    SCIP_STATUS_GAPLIMIT
    @ SCIP_STATUS_GAPLIMIT
    Definition: type_stat.h:56
    SCIP_STATUS_USERINTERRUPT
    @ SCIP_STATUS_USERINTERRUPT
    Definition: type_stat.h:47
    SCIP_STATUS_INFORUNBD
    @ SCIP_STATUS_INFORUNBD
    Definition: type_stat.h:46
    SCIP_STATUS_STALLNODELIMIT
    @ SCIP_STATUS_STALLNODELIMIT
    Definition: type_stat.h:52
    SCIP_STATUS_TIMELIMIT
    @ SCIP_STATUS_TIMELIMIT
    Definition: type_stat.h:54
    SCIP_STATUS_INFEASIBLE
    @ SCIP_STATUS_INFEASIBLE
    Definition: type_stat.h:44
    SCIP_STATUS_NODELIMIT
    @ SCIP_STATUS_NODELIMIT
    Definition: type_stat.h:49
    SCIP_STATUS_MEMLIMIT
    @ SCIP_STATUS_MEMLIMIT
    Definition: type_stat.h:55
    SCIP_STATUS_RESTARTLIMIT
    @ SCIP_STATUS_RESTARTLIMIT
    Definition: type_stat.h:62
    SCIP_STATUS
    enum SCIP_Status SCIP_STATUS
    Definition: type_stat.h:64