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