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-2020 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);
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  SCIP_CALL( SCIPfreeTransform(masterscip) );
334 
335  /* check for Benders cuts */
336  SCIP_CALL( SCIPstartClock(masterscip, oracletimeclock) );
337  SCIP_CALL( Oracle(masterscip, nmastervars, mastervars, mastersolution, data, timelimit, ntotalcuts, &ncuts, &substatus) );
338  SCIP_CALL( SCIPstopClock(masterscip, oracletimeclock) );
339  ntotalcuts += (SCIP_Longint) ncuts;
340 
341  switch ( substatus )
342  {
343  case BENDERS_STATUS_ADDEDCUT:
344  break;
345 
346  case BENDERS_STATUS_SUCESS:
347  success = TRUE;
348  primalbound = mastersolobj;
349  break;
350 
351  case BENDERS_STATUS_TIMELIMIT:
352  *status = SCIP_STATUS_TIMELIMIT;
353  goto TERMINATE;
354 
355  case BENDERS_STATUS_USERINTERRUPT:
356  *status = SCIP_STATUS_USERINTERRUPT;
357  goto TERMINATE;
358 
359  default:
360  SCIPerrorMessage("Subproblem returned with status %d. Exiting ...\n", substatus);
361  return SCIP_ERROR;
362  }
363 
364  /* if not cuts could be found, the master problem is solved optimally */
365  if ( success )
366  {
367  /* if last master problem was solved to optimality, we are done */
368  if ( masteroptimal )
369  break;
370  /* otherwise, we have to resolve the master to optimality */
371  solvemasterapprox = FALSE;
372 
373  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
374  SCIPinfoMessage(masterscip, NULL, "Switching to optimally solving the master problem.\n");
375  }
376 
377  /* --------- solve Benders master problem */
378 
379  /* set current time limit */
380  currenttime = SCIPgetClockTime(masterscip, totaltimeclock);
381  if ( ! SCIPisInfinity(masterscip, timelimit) )
382  {
383  subtimelimit = timelimit - currenttime;
384  if ( subtimelimit <= 0.1 )
385  {
386  SCIPdebugMessage("Time limit exceeded.\n");
387  *status = SCIP_STATUS_TIMELIMIT;
388  goto TERMINATE;
389  }
390  }
391  else
392  subtimelimit = SCIPinfinity(masterscip);
393  SCIP_CALL( SCIPsetRealParam(masterscip, "limits/time", subtimelimit) );
394 
395  /* SCIP_CALL( SCIPprintOrigProblem(masterscip, NULL, "cip", FALSE) ); */
396 
397  /* set gap limit if we do not have to solve the master to optimality */
398  if ( solvemasterapprox )
399  {
400  SCIP_CALL( SCIPsetLongintParam(masterscip, "limits/stallnodes", masterstallnodes) );
401  SCIP_CALL( SCIPsetRealParam(masterscip, "limits/gap", mastergaplimit) );
402  }
403 
404  /* solve master problem */
405  SCIP_CALL( SCIPstartClock(masterscip, mastertimeclock) );
406  SCIP_CALL( SCIPsolve(masterscip) );
407 
408  ntotalnodes += SCIPgetNTotalNodes(masterscip);
409 
410  /* possibly reset gap limit */
411  if ( solvemasterapprox )
412  {
413  SCIP_CALL( SCIPsetLongintParam(masterscip, "limits/stallnodes", -1LL) );
414  SCIP_CALL( SCIPsetRealParam(masterscip, "limits/gap", 0.0) );
415  }
416  SCIP_CALL( SCIPstopClock(masterscip, mastertimeclock) );
417 
418  masterstatus = SCIPgetStatus(masterscip);
419 
420  /* determine master problem solution status */
421  masteroptimal = FALSE;
422  switch ( masterstatus )
423  {
424  case SCIP_STATUS_OPTIMAL:
425  masteroptimal = TRUE;
426  break;
427 
428  case SCIP_STATUS_GAPLIMIT:
429  case SCIP_STATUS_STALLNODELIMIT:
430  case SCIP_STATUS_UNBOUNDED:
431  /* do nothing */
432  break;
433 
434  case SCIP_STATUS_INFEASIBLE:
435  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
436  SCIPinfoMessage(masterscip, NULL, "Master problem infeasible.\n");
437  *status = SCIP_STATUS_INFEASIBLE;
438  goto TERMINATE;
439 
440  case SCIP_STATUS_TIMELIMIT:
441  *status = SCIP_STATUS_TIMELIMIT;
442  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
443  SCIPinfoMessage(masterscip, NULL, "Time limit exceeded.\n");
444  goto TERMINATE;
445 
446  case SCIP_STATUS_USERINTERRUPT:
447  *status = SCIP_STATUS_USERINTERRUPT;
448  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
449  SCIPinfoMessage(masterscip, NULL, "User interrupt.\n");
450  goto TERMINATE;
451 
452  default:
453  SCIPerrorMessage("Master problem returned with status %d. Exiting ...\n", masterstatus);
454  return SCIP_ERROR;
455  }
456 
457  mastersol = SCIPgetBestSol(masterscip);
458  if ( mastersol == NULL )
459  {
460  SCIPerrorMessage("Benders master problem does not have a primal solution!\n");
461  return SCIP_ERROR;
462  }
463  mastersolobj = SCIPgetSolOrigObj(masterscip, mastersol);
464  mastergap = SCIPgetGap(masterscip);
465 
466  dualbound = MAX(dualbound, SCIPgetDualbound(masterscip));
467 
468  /* copy solution */
469  for (v = 0; v < nmastervars; ++v)
470  {
471  SCIP_Real val;
472 
473  val = SCIPgetSolVal(masterscip, mastersol, mastervars[v]);
474  assert( SCIPisIntegral(masterscip, val) );
475  mastersolution[v] = val;
476  }
477 
478  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
479  {
480  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, " ");
481  SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, totaltimeclock), 6);
482  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
483  SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, niter, 7);
484  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
485  SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetNOrigConss(masterscip), 7);
486  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
487  SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetNOrigVars(masterscip), 7);
488  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
489  SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, mastertimeclock), 6);
490  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
491  SCIPdispLongint(SCIPgetMessagehdlr(masterscip), NULL, ntotalnodes, 10);
492  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
493  SCIPdispTime(SCIPgetMessagehdlr(masterscip), NULL, SCIPgetClockTime(masterscip, oracletimeclock), 6);
494  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|");
495  SCIPdispInt(SCIPgetMessagehdlr(masterscip), NULL, ncuts, 7);
496  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "|%13.6e", mastersolobj);
497  if ( solvemasterapprox )
498  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, " | %6.2f%%", 100.0 * mastergap);
499  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(masterscip), NULL, "\n");
500  }
501  }
502  while ( niter < maxIters );
503 
504  SCIPdebugMessage("Solution process finished.\n");
505 
506  if ( niter >= maxIters )
507  {
508  *status = SCIP_STATUS_TOTALNODELIMIT;
509  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
510  SCIPinfoMessage(masterscip, NULL, "Reached iteration limit.\n");
511  }
512 
513  if ( masteroptimal )
514  {
515  assert( *status == SCIP_STATUS_UNKNOWN );
516  *status = SCIP_STATUS_OPTIMAL;
517  }
518 
519  TERMINATE:
520 
521  if ( verblevel >= SCIP_VERBLEVEL_NORMAL )
522  {
523  SCIP_CALL( printShortStatistics(masterscip, *status, totaltimeclock, primalbound, dualbound, ntotalnodes, niter) );
524  SCIP_CALL( printLongStatistics(masterscip, *status, totaltimeclock, oracletimeclock, mastertimeclock, primalbound, dualbound, ntotalnodes, ntotalcuts, niter) );
525  }
526 
527  SCIPfreeBlockMemoryArray(masterscip, &mastersolution, nmastervars);
528 
529  SCIP_CALL( SCIPfreeClock(masterscip, &mastertimeclock) );
530  SCIP_CALL( SCIPfreeClock(masterscip, &oracletimeclock) );
531  SCIP_CALL( SCIPfreeClock(masterscip, &totaltimeclock) );
532 
533  return SCIP_OKAY;
534 }
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:587
BENDERS_CUTORACLE
#define BENDERS_CUTORACLE(x)
Definition: benders.h:61
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:467
printStatus
static SCIP_RETCODE printStatus(SCIP *masterscip, SCIP_STATUS status)
Definition: benders.c:31
SCIPallocClearBlockMemoryArray
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIPcreateClock
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:67
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIPgetGap
SCIP_Real SCIPgetGap(SCIP *scip)
Definition: scip_solvingstats.c:1648
SCIP_Var
Definition: struct_var.h:198
SCIP_STATUS_INFORUNBD
Definition: type_stat.h:55
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
FALSE
#define FALSE
Definition: def.h:73
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
TRUE
#define TRUE
Definition: def.h:72
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_VERBLEVEL
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:48
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
BENDERS_Data
Definition: classify.c:38
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2121
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
SCIPgetClockTime
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:301
SCIPdispLongint
void SCIPdispLongint(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Longint val, int width)
Definition: disp.c:572
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:514
SCIP_STATUS_USERINTERRUPT
Definition: type_stat.h:34
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2076
SCIP_STATUS_NODELIMIT
Definition: type_stat.h:35
SCIPenableReoptimization
SCIP_RETCODE SCIPenableReoptimization(SCIP *scip, SCIP_Bool enable)
Definition: scip_solve.c:3028
SCIP_Sol
Definition: struct_sol.h:64
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:613
SCIP_STATUS_TOTALNODELIMIT
Definition: type_stat.h:36
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIPgetNTotalNodes
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
Definition: scip_solvingstats.c:227
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
SCIP_STATUS_OPTIMAL
Definition: type_stat.h:52
NULL
#define NULL
Definition: lpi_spx1.cpp:155
fabs
SCIPInterval fabs(const SCIPInterval &x)
Definition: intervalarithext.h:385
SCIP_OKAY
Definition: type_retcode.h:33
SCIPgetNOrigConss
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3128
SCIP_STATUS_UNKNOWN
Definition: type_stat.h:33
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:364
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2426
SCIP_ERROR
Definition: type_retcode.h:34
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:44
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
SCIP_STATUS
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
SCIPgetMessagehdlr
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:91
MAX
#define MAX(x, y)
Definition: tclique_def.h:83
BENDERS_STATUS
enum BENDERS_Status BENDERS_STATUS
Definition: benders.h:42
SCIPstopClock
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:169
SCIPfreeClock
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:118
SCIP_STATUS_STALLNODELIMIT
Definition: type_stat.h:39
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
SCIP_STATUS_GAPLIMIT
Definition: type_stat.h:44
SCIP_STATUS_SOLLIMIT
Definition: type_stat.h:45
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:163
SCIPstartClock
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:152
SCIP_Longint
#define SCIP_Longint
Definition: def.h:148
benders.h
run Benders algorithm
SCIPdispTime
void SCIPdispTime(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Real val, int width)
Definition: disp.c:635
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1335
SCIP_Clock
Definition: struct_clock.h:55
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:53
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIPgetOrigVarsData
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2351
SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:48
SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:42
SCIP_STATUS_RESTARTLIMIT
Definition: type_stat.h:51
SCIPdispInt
void SCIPdispInt(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, int val, int width)
Definition: disp.c:618
SCIP_STATUS_UNBOUNDED
Definition: type_stat.h:54
SCIPfreeTransform
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3329
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436