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 2002-2022 Zuse Institute Berlin */
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 */
39 static
40 SCIP_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 */
96 static
97 SCIP_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 */
132 static
133 SCIP_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 */
207 SCIP_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_SUCESS:
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 }
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIPenableReoptimization
SCIP_RETCODE SCIPenableReoptimization(SCIP *scip, SCIP_Bool enable)
Definition: scip_solve.c:3166
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2090
BENDERS_CUTORACLE
#define BENDERS_CUTORACLE(x)
Definition: benders.h:70
printStatus
static SCIP_RETCODE printStatus(SCIP *masterscip, SCIP_STATUS status)
Definition: benders.c:40
SCIPallocClearBlockMemoryArray
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2440
SCIPdispLongint
void SCIPdispLongint(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Longint val, int width)
Definition: disp.c:581
SCIP_Var
Definition: struct_var.h:207
SCIP_STATUS_INFORUNBD
Definition: type_stat.h:64
SCIPstopClock
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:178
FALSE
#define FALSE
Definition: def.h:96
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
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:512
TRUE
#define TRUE
Definition: def.h:95
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_VERBLEVEL
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:57
BENDERS_Data
Definition: classify.c:47
SCIP_STATUS_MEMLIMIT
Definition: type_stat.h:52
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
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIPgetOrigVarsData
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2365
SCIPgetMessagehdlr
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:88
SCIPfreeClock
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:127
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIPdispInt
void SCIPdispInt(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, int val, int width)
Definition: disp.c:627
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2180
SCIP_STATUS_USERINTERRUPT
Definition: type_stat.h:43
SCIP_STATUS_NODELIMIT
Definition: type_stat.h:44
SCIP_Sol
Definition: struct_sol.h:73
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1075
SCIP_STATUS_TOTALNODELIMIT
Definition: type_stat.h:45
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2622
SCIPcreateClock
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:76
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:64
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
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1348
SCIP_STATUS_OPTIMAL
Definition: type_stat.h:61
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:483
NULL
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_OKAY
Definition: type_retcode.h:42
SCIP_STATUS_UNKNOWN
Definition: type_stat.h:42
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:393
SCIPgetNTotalNodes
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
Definition: scip_solvingstats.c:239
SCIPgetNOrigConss
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3142
SCIPdispTime
void SCIPdispTime(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_Real val, int width)
Definition: disp.c:643
SCIP_ERROR
Definition: type_retcode.h:43
SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:53
SCIPfreeTransform
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3467
SCIP_Bool
#define SCIP_Bool
Definition: def.h:93
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2135
SCIP_STATUS
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
SCIPgetClockTime
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:319
SCIPgetGap
SCIP_Real SCIPgetGap(SCIP *scip)
Definition: scip_solvingstats.c:1668
MAX
#define MAX(x, y)
Definition: tclique_def.h:92
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
BENDERS_STATUS
enum BENDERS_Status BENDERS_STATUS
Definition: benders.h:51
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1444
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:523
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2045
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
SCIP_STATUS_STALLNODELIMIT
Definition: type_stat.h:48
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2313
SCIP_STATUS_GAPLIMIT
Definition: type_stat.h:53
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:596
SCIP_STATUS_SOLLIMIT
Definition: type_stat.h:54
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3050
SCIPmessageFPrintInfo
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
MAXITERATIONS
#define MAXITERATIONS
Definition: benders.c:35
SCIP_Real
#define SCIP_Real
Definition: def.h:186
SCIP_Longint
#define SCIP_Longint
Definition: def.h:171
benders.h
run Benders algorithm
SCIPfreeReoptSolve
SCIP_RETCODE SCIPfreeReoptSolve(SCIP *scip)
Definition: scip_solve.c:3404
SCIP_INVALIDDATA
Definition: type_retcode.h:52
SCIP_Clock
Definition: struct_clock.h:64
SCIPstartClock
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:161
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62
SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:57
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:51
SCIP_STATUS_RESTARTLIMIT
Definition: type_stat.h:60
SCIP_STATUS_UNBOUNDED
Definition: type_stat.h:63