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-2024 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:267
SCIP_Longint
#define SCIP_Longint
Definition: def.h:158
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MAX3
#define MAX3(x, y, z)
Definition: def.h:247
SCIP_Real
#define SCIP_Real
Definition: def.h:173
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:239
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:374
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIPgetOrigVarsData
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2357
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIPgetNOrigConss
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3134
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
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:3043
SCIPfreeReoptSolve
SCIP_RETCODE SCIPfreeReoptSolve(SCIP *scip)
Definition: scip_solve.c:3281
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIPfreeTransform
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIPgetGap
SCIP_Real SCIPgetGap(SCIP *scip)
Definition: scip_solvingstats.c:1667
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1347
SCIPgetNTotalNodes
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
Definition: scip_solvingstats.c:238
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:510
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:594
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:521
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:208
SCIP_VERBLEVEL
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:59
SCIP_VERBLEVEL_NORMAL
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
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:61
SCIP_STATUS_TOTALNODELIMIT
@ SCIP_STATUS_TOTALNODELIMIT
Definition: type_stat.h:45
SCIP_STATUS_BESTSOLLIMIT
@ SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:57
SCIP_STATUS_SOLLIMIT
@ SCIP_STATUS_SOLLIMIT
Definition: type_stat.h:56
SCIP_STATUS_UNBOUNDED
@ SCIP_STATUS_UNBOUNDED
Definition: type_stat.h:63
SCIP_STATUS_UNKNOWN
@ SCIP_STATUS_UNKNOWN
Definition: type_stat.h:42
SCIP_STATUS_GAPLIMIT
@ SCIP_STATUS_GAPLIMIT
Definition: type_stat.h:53
SCIP_STATUS_USERINTERRUPT
@ SCIP_STATUS_USERINTERRUPT
Definition: type_stat.h:43
SCIP_STATUS_INFORUNBD
@ SCIP_STATUS_INFORUNBD
Definition: type_stat.h:64
SCIP_STATUS_STALLNODELIMIT
@ SCIP_STATUS_STALLNODELIMIT
Definition: type_stat.h:48
SCIP_STATUS_TIMELIMIT
@ SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:51
SCIP_STATUS_INFEASIBLE
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62
SCIP_STATUS_NODELIMIT
@ SCIP_STATUS_NODELIMIT
Definition: type_stat.h:44
SCIP_STATUS_MEMLIMIT
@ SCIP_STATUS_MEMLIMIT
Definition: type_stat.h:52
SCIP_STATUS_RESTARTLIMIT
@ SCIP_STATUS_RESTARTLIMIT
Definition: type_stat.h:60
SCIP_STATUS
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67