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-2018 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip/src/scip/benders.c
17  * @brief methods for Benders' decomposition
18  * @author Stephen J. Maher
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/def.h"
27 #include "scip/set.h"
28 #include "scip/clock.h"
29 #include "scip/paramset.h"
30 #include "scip/lp.h"
31 #include "scip/prob.h"
32 #include "scip/pricestore.h"
33 #include "scip/scip.h"
34 #include "scip/benders.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/cons_linear.h"
38 
39 #include "scip/struct_benders.h"
40 #include "scip/struct_benderscut.h"
41 
42 #include "scip/benderscut.h"
43 
44 /* Defaults for parameters */
45 #define SCIP_DEFAULT_TRANSFERCUTS TRUE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
46 #define SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */
47 #define SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */
48 #define SCIP_DEFAULT_LNSMAXDEPTH -1 /** maximum depth at which the LNS check is performed */
49 #define SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */
50 #define SCIP_DEFAULT_UPDATEAUXVARBOUND TRUE /** should the auxiliary variable lower bound be updated by solving the subproblem */
51 
52 #define BENDERS_MAXPSEUDOSOLS 5 /** the maximum number of pseudo solutions checked before suggesting
53  merge candidates */
54 
55 #define AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */
56 
57 /* event handler properties */
58 #define NODEFOCUS_EVENTHDLR_NAME "bendersnodefocus"
59 #define NODEFOCUS_EVENTHDLR_DESC "node focus event handler for Benders' decomposition"
60 
61 #define MIPNODEFOCUS_EVENTHDLR_NAME "bendersmipsolvenodefocus"
62 #define MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition"
63 
64 #define UPPERBOUND_EVENTHDLR_NAME "bendersupperbound"
65 #define UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound"
66 
67 #define NODESOLVED_EVENTHDLR_NAME "bendersnodesolved"
68 #define NODESOLVED_EVENTHDLR_DESC "node solved event handler for the Benders' integer cuts"
69 
70 
71 /** event handler data */
72 struct SCIP_EventhdlrData
73 {
74  int filterpos; /**< the event filter entry */
75  int numruns; /**< the number of times that the problem has been solved */
76  SCIP_Real upperbound; /**< an upper bound for the problem */
77  SCIP_Bool solvecip; /**< is the event called from a MIP subproblem solve*/
78 };
79 
80 
81 /* ---------------- Local methods for event handlers ---------------- */
82 
83 /** initialises the members of the eventhandler data */
84 static
86  SCIP* scip, /**< the SCIP data structure */
87  SCIP_EVENTHDLRDATA* eventhdlrdata /**< the event handler data */
88  )
89 {
90  assert(scip != NULL);
91  assert(eventhdlrdata != NULL);
92 
93  eventhdlrdata->filterpos = -1;
94  eventhdlrdata->numruns = 0;
95  eventhdlrdata->upperbound = -SCIPinfinity(scip);
96  eventhdlrdata->solvecip = FALSE;
97 
98  return SCIP_OKAY;
99 }
100 
101 /** initsol method for the event handlers */
102 static
104  SCIP* scip, /**< the SCIP data structure */
105  SCIP_EVENTHDLR* eventhdlr, /**< the event handlers data structure */
106  SCIP_EVENTTYPE eventtype /**< event type mask to select events to catch */
107  )
108 {
109  SCIP_EVENTHDLRDATA* eventhdlrdata;
110 
111  assert(scip != NULL);
112  assert(eventhdlr != NULL);
113 
114  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
115 
116  SCIP_CALL(SCIPcatchEvent(scip, eventtype, eventhdlr, NULL, &eventhdlrdata->filterpos));
117 
118  return SCIP_OKAY;
119 }
120 
121 /** the exit sol method for the event handlers */
122 static
124  SCIP* scip, /**< the SCIP data structure */
125  SCIP_EVENTHDLR* eventhdlr, /**< the event handlers data structure */
126  SCIP_EVENTTYPE eventtype /**< event type mask to select events to catch */
127  )
128 {
129  SCIP_EVENTHDLRDATA* eventhdlrdata;
130 
131  assert(scip != NULL);
132  assert(eventhdlr != NULL);
133 
134  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
135 
136  if( eventhdlrdata->filterpos >= 0 )
137  {
138  SCIP_CALL(SCIPdropEvent(scip, eventtype, eventhdlr, NULL, eventhdlrdata->filterpos));
139  eventhdlrdata->filterpos = -1;
140  }
141 
142  return SCIP_OKAY;
143 }
144 
145 /** the exit method for the event handlers */
146 static
148  SCIP* scip, /**< the SCIP data structure */
149  SCIP_EVENTHDLR* eventhdlr /**< the event handlers data structure */
150  )
151 {
152  SCIP_EVENTHDLRDATA* eventhdlrdata;
153 
154  assert(scip != NULL);
155  assert(eventhdlr != NULL);
156 
157  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
158 
159  /* reinitialise the event handler data */
160  SCIP_CALL( initEventhandlerData(scip, eventhdlrdata) );
161 
162  return SCIP_OKAY;
163 }
164 
165 /** free method for the event handler */
166 static
168  SCIP* scip, /**< the SCIP data structure */
169  SCIP_EVENTHDLR* eventhdlr /**< the event handlers data structure */
170  )
171 {
172  SCIP_EVENTHDLRDATA* eventhdlrdata;
173 
174  assert(scip != NULL);
175  assert(eventhdlr != NULL);
176 
177  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
178  assert(eventhdlrdata != NULL);
179 
180  SCIPfreeBlockMemory(scip, &eventhdlrdata);
181 
182  SCIPeventhdlrSetData(eventhdlr, NULL);
183 
184  return SCIP_OKAY;
185 }
186 
187 
188 
189 /* ---------------- Callback methods of node focus event handler ---------------- */
190 
191 /** exec the event handler */
192 static
193 SCIP_DECL_EVENTEXEC(eventExecBendersNodefocus)
194 { /*lint --e{715}*/
195  SCIP_EVENTHDLRDATA* eventhdlrdata;
196 
197  assert(scip != NULL);
198  assert(eventhdlr != NULL);
199  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
200 
201  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
202 
203  /* sending an interrupt solve signal to return the control back to the Benders' decomposition plugin.
204  * This will ensure the SCIP stage is SCIP_STAGE_SOLVING, allowing the use of probing mode. */
206 
207  SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
208  eventhdlrdata->filterpos = -1;
209 
210  return SCIP_OKAY;
211 }
212 
213 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
214 static
215 SCIP_DECL_EVENTINITSOL(eventInitsolBendersNodefocus)
216 {
217  assert(scip != NULL);
218  assert(eventhdlr != NULL);
219  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
220 
222 
223  return SCIP_OKAY;
224 }
225 
226 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
227 static
228 SCIP_DECL_EVENTEXITSOL(eventExitsolBendersNodefocus)
229 {
230  assert(scip != NULL);
231  assert(eventhdlr != NULL);
232  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
233 
235 
236  return SCIP_OKAY;
237 }
238 
239 /** deinitialization method of event handler (called before transformed problem is freed) */
240 static
241 SCIP_DECL_EVENTEXIT(eventExitBendersNodefocus)
242 {
243  assert(scip != NULL);
244  assert(eventhdlr != NULL);
245  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
246 
247  SCIP_CALL( exitEventhandler(scip, eventhdlr) );
248 
249  return SCIP_OKAY;
250 }
251 
252 /** deinitialization method of event handler (called before transformed problem is freed) */
253 static
254 SCIP_DECL_EVENTFREE(eventFreeBendersNodefocus)
255 {
256  assert(scip != NULL);
257  assert(eventhdlr != NULL);
258  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
259 
260  SCIP_CALL( freeEventhandler(scip, eventhdlr) );
261 
262  return SCIP_OKAY;
263 }
264 
265 
266 /* ---------------- Callback methods of MIP solve node focus event handler ---------------- */
267 
268 /** exec the event handler */
269 static
270 SCIP_DECL_EVENTEXEC(eventExecBendersMipnodefocus)
271 { /*lint --e{715}*/
272  SCIP_EVENTHDLRDATA* eventhdlrdata;
273 
274  assert(scip != NULL);
275  assert(eventhdlr != NULL);
276  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
277 
278  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
279 
280  /* interrupting the solve so that the control is returned back to the Benders' core. */
281  if( eventhdlrdata->numruns == 0 && !eventhdlrdata->solvecip )
282  {
284  }
285 
286  SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
287  eventhdlrdata->filterpos = -1;
288 
289  eventhdlrdata->numruns++;
290 
291  return SCIP_OKAY;
292 }
293 
294 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
295 static
296 SCIP_DECL_EVENTINITSOL(eventInitsolBendersMipnodefocus)
297 {
298  assert(scip != NULL);
299  assert(eventhdlr != NULL);
300  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
301 
303 
304  return SCIP_OKAY;
305 }
306 
307 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
308 static
309 SCIP_DECL_EVENTEXITSOL(eventExitsolBendersMipnodefocus)
310 {
311  assert(scip != NULL);
312  assert(eventhdlr != NULL);
313  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
314 
316 
317  return SCIP_OKAY;
318 }
319 
320 /** deinitialization method of event handler (called before transformed problem is freed) */
321 static
322 SCIP_DECL_EVENTEXIT(eventExitBendersMipnodefocus)
323 {
324  assert(scip != NULL);
325  assert(eventhdlr != NULL);
326  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
327 
328  SCIP_CALL( exitEventhandler(scip, eventhdlr) );
329 
330  return SCIP_OKAY;
331 }
332 
333 /** deinitialization method of event handler (called before transformed problem is freed) */
334 static
335 SCIP_DECL_EVENTFREE(eventFreeBendersMipnodefocus)
336 {
337  assert(scip != NULL);
338  assert(eventhdlr != NULL);
339  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
340 
341  SCIP_CALL( freeEventhandler(scip, eventhdlr) );
342 
343  return SCIP_OKAY;
344 }
345 
346 /* ---------------- Callback methods of solution found event handler ---------------- */
347 
348 /** exec the event handler */
349 static
350 SCIP_DECL_EVENTEXEC(eventExecBendersUpperbound)
351 { /*lint --e{715}*/
352  SCIP_EVENTHDLRDATA* eventhdlrdata;
353  SCIP_SOL* bestsol;
354 
355  assert(scip != NULL);
356  assert(eventhdlr != NULL);
357  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
358 
359  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
360  assert(eventhdlrdata != NULL);
361 
362  bestsol = SCIPgetBestSol(scip);
363 
364  if( SCIPisLT(scip, SCIPgetSolOrigObj(scip, bestsol), eventhdlrdata->upperbound) )
365  {
367  }
368 
369  return SCIP_OKAY;
370 }
371 
372 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
373 static
374 SCIP_DECL_EVENTINITSOL(eventInitsolBendersUpperbound)
375 {
376  assert(scip != NULL);
377  assert(eventhdlr != NULL);
378  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
379 
381 
382  return SCIP_OKAY;
383 }
384 
385 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
386 static
387 SCIP_DECL_EVENTEXITSOL(eventExitsolBendersUpperbound)
388 {
389  assert(scip != NULL);
390  assert(eventhdlr != NULL);
391  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
392 
394 
395  return SCIP_OKAY;
396 }
397 
398 /** deinitialization method of event handler (called before transformed problem is freed) */
399 static
400 SCIP_DECL_EVENTEXIT(eventExitBendersUpperbound)
401 {
402  assert(scip != NULL);
403  assert(eventhdlr != NULL);
404  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
405 
406  SCIP_CALL( exitEventhandler(scip, eventhdlr) );
407 
408  return SCIP_OKAY;
409 }
410 
411 /** deinitialization method of event handler (called before transformed problem is freed) */
412 static
413 SCIP_DECL_EVENTFREE(eventFreeBendersUpperbound)
414 {
415  assert(scip != NULL);
416  assert(eventhdlr != NULL);
417  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
418 
419  SCIP_CALL( freeEventhandler(scip, eventhdlr) );
420 
421  return SCIP_OKAY;
422 }
423 
424 /** updates the upper bound in the event handler data */
425 static
427  SCIP_BENDERS* benders, /**< Benders' decomposition */
428  int probnumber, /**< the subproblem number */
429  SCIP_Real upperbound /**< the upper bound value */
430  )
431 {
432  SCIP_EVENTHDLR* eventhdlr;
433  SCIP_EVENTHDLRDATA* eventhdlrdata;
434 
435  assert(benders != NULL);
436  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
437 
438  eventhdlr = SCIPfindEventhdlr(SCIPbendersSubproblem(benders, probnumber), UPPERBOUND_EVENTHDLR_NAME);
439  assert(eventhdlr != NULL);
440 
441  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
442  assert(eventhdlrdata != NULL);
443 
444  eventhdlrdata->upperbound = upperbound;
445 
446  return SCIP_OKAY;
447 }
448 
449 /* ---------------- Callback methods of the node solved event handler ---------------- */
450 
451 /** Updates the cut constant of the Benders' cuts data.
452  * This function solves the master problem with only the auxiliary variables in the objective function.
453  */
454 static
456  SCIP* masterprob, /**< the SCIP instance of the master problem */
457  SCIP_BENDERS* benders /**< Benders' decomposition */
458  )
459 {
460  SCIP_VAR** vars;
461  int nvars;
462  int nsubproblems;
463  int i;
464  SCIP_Bool lperror;
465  SCIP_Bool cutoff;
466 
467  assert(masterprob != NULL);
468  assert(benders != NULL);
469 
470  /* don't run in probing or in repropagation */
471  if( SCIPinProbing(masterprob) || SCIPinRepropagation(masterprob) || SCIPinDive(masterprob) )
472  return SCIP_OKAY;
473 
474  nsubproblems = SCIPbendersGetNSubproblems(benders);
475 
476  SCIP_CALL( SCIPstartProbing(masterprob) );
477 
478  /* change the master problem variables to 0 */
479  nvars = SCIPgetNVars(masterprob);
480  vars = SCIPgetVars(masterprob);
481 
482  /* setting the objective function coefficient to 0 for all variables */
483  for( i = 0; i < nvars; i++ )
484  {
485  if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
486  {
487  SCIP_CALL( SCIPchgVarObjProbing(masterprob, vars[i], 0.0) );
488  }
489  }
490 
491  /* solving an LP for all subproblems to find the lower bound */
492  for( i = 0; i < nsubproblems; i++)
493  {
494  SCIP_VAR* auxiliaryvar;
495 
496  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, i);
497 
498  if( SCIPvarGetStatus(auxiliaryvar) != SCIP_VARSTATUS_COLUMN )
499  continue;
500 
501  SCIP_CALL( SCIPchgVarObjProbing(masterprob, auxiliaryvar, 1.0) );
502 
503  /* solving the probing LP to get a lower bound on the auxiliary variables */
504  SCIP_CALL( SCIPsolveProbingLP(masterprob, -1, &lperror, &cutoff) );
505 
506  if( !SCIPisInfinity(masterprob, -SCIPgetSolTransObj(masterprob, NULL)) )
508 
509  SCIPdebugMsg(masterprob, "Cut constant for subproblem %d: %g\n", i,
511 
512  SCIP_CALL( SCIPchgVarObjProbing(masterprob, auxiliaryvar, 0.0) );
513  }
514 
515  SCIP_CALL( SCIPendProbing(masterprob) );
516 
517  return SCIP_OKAY;
518 }
519 
520 /** exec the event handler */
521 static
522 SCIP_DECL_EVENTEXEC(eventExecBendersNodesolved)
523 { /*lint --e{715}*/
524  SCIP_BENDERS* benders;
525 
526  assert(scip != NULL);
527  assert(eventhdlr != NULL);
528  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODESOLVED_EVENTHDLR_NAME) == 0);
529 
530  benders = (SCIP_BENDERS*)SCIPeventhdlrGetData(eventhdlr); /*lint !e826*/
531 
532  if( SCIPbendersGetNSubproblems(benders) > 0
534  {
536  }
537 
539 
540  return SCIP_OKAY;
541 }
542 
543 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
544 static
545 SCIP_DECL_EVENTINITSOL(eventInitsolBendersNodesolved)
546 {
547  SCIP_BENDERS* benders;
548 
549  assert(scip != NULL);
550  assert(eventhdlr != NULL);
551  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODESOLVED_EVENTHDLR_NAME) == 0);
552 
553  /* getting the Benders' decomposition data structure */
554  benders = (SCIP_BENDERS*)SCIPeventhdlrGetData(eventhdlr); /*lint !e826*/
555 
556  /* The event is only caught if there is an active Benders' decomposition */
557  if( SCIPbendersIsActive(benders) && !SCIPbendersOnlyCheckConvexRelax(benders) )
558  {
560  }
561 
562  return SCIP_OKAY;
563 }
564 
565 
566 
567 /* Local methods */
568 
569 /** A workaround for GCG. This is a temp vardata that is set for the auxiliary variables */
570 struct SCIP_VarData
571 {
572  int vartype; /**< the variable type. In GCG this indicates whether the variable is a
573  * master problem or subproblem variable. */
574 };
575 
576 
577 /** adds the auxiliary variables to the Benders' decomposition master problem */
578 static
580  SCIP* scip, /**< SCIP data structure */
581  SCIP_BENDERS* benders /**< Benders' decomposition structure */
582  )
583 {
584  SCIP_BENDERS* topbenders; /* the highest priority Benders' decomposition */
585  SCIP_VAR* auxiliaryvar;
586  SCIP_VARDATA* vardata;
587  char varname[SCIP_MAXSTRLEN]; /* the name of the auxiliary variable */
588  SCIP_Bool shareauxvars;
589  int i;
590 
591  /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
592  SCIP_CALL( SCIPallocBlockMemory(scip, &vardata) );
593  vardata->vartype = -1;
594 
595  /* getting the highest priority Benders' decomposition */
596  topbenders = SCIPgetBenders(scip)[0];
597 
598  /* if the current Benders is the highest priority Benders, then we need to create the auxiliary variables.
599  * Otherwise, if the shareauxvars flag is set, then the auxiliary variables from the highest priority Benders' are
600  * stored with this Benders. */
601  shareauxvars = FALSE;
602  if( topbenders != benders && SCIPbendersShareAuxVars(benders) )
603  shareauxvars = TRUE;
604 
605  for( i = 0; i < SCIPbendersGetNSubproblems(benders); i++ )
606  {
607  /* if the auxiliary variables are shared, then a pointer to the variable is retrieved from topbenders,
608  * otherwise the auxiliaryvariable is created. */
609  if( shareauxvars )
610  {
611  auxiliaryvar = SCIPbendersGetAuxiliaryVar(topbenders, i);
612 
613  SCIP_CALL( SCIPcaptureVar(scip, auxiliaryvar) );
614  }
615  else
616  {
617  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders) );
618  SCIP_CALL( SCIPcreateVarBasic(scip, &auxiliaryvar, varname, -SCIPinfinity(scip), SCIPinfinity(scip), 1.0,
620 
621  SCIPvarSetData(auxiliaryvar, vardata);
622 
623  SCIP_CALL( SCIPaddVar(scip, auxiliaryvar) );
624  }
625 
626  benders->auxiliaryvars[i] = auxiliaryvar;
627  }
628 
629  SCIPfreeBlockMemory(scip, &vardata);
630 
631  return SCIP_OKAY;
632 }
633 
634 /** assigns the copied auxiliary variables in the target SCIP to the target Benders' decomposition data */
635 static
637  SCIP* scip, /**< SCIP data structure, the target scip */
638  SCIP_BENDERS* benders /**< Benders' decomposition */
639  )
640 {
641  SCIP_BENDERS* topbenders; /* the highest priority Benders' decomposition */
642  SCIP_VAR* targetvar;
643  SCIP_VARDATA* vardata;
644  char varname[SCIP_MAXSTRLEN]; /* the name of the auxiliary variable */
645  SCIP_Bool shareauxvars;
646  int i;
647 
648  assert(scip != NULL);
649  assert(benders != NULL);
650 
651  /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
652  SCIP_CALL( SCIPallocBlockMemory(scip, &vardata) );
653  vardata->vartype = -1;
654 
655  /* getting the highest priority Benders' decomposition */
656  topbenders = SCIPgetBenders(scip)[0];
657 
658  /* if the auxiliary variable are shared, then the variable name will have a suffix of the highest priority Benders'
659  * name. So the shareauxvars flag indicates how to search for the auxiliary variables */
660  shareauxvars = FALSE;
661  if( topbenders != benders && SCIPbendersShareAuxVars(benders) )
662  shareauxvars = TRUE;
663 
664  for( i = 0; i < SCIPbendersGetNSubproblems(benders); i++ )
665  {
666  if( shareauxvars )
667  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(topbenders));
668  else
669  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders));
670 
671  /* finding the variable in the copied problem that has the same name as the auxiliary variable */
672  targetvar = SCIPfindVar(scip, varname);
673  assert(targetvar != NULL);
674 
675  SCIPvarSetData(targetvar, vardata);
676 
677  benders->auxiliaryvars[i] = SCIPvarGetTransVar(targetvar);
678 
679  SCIP_CALL( SCIPcaptureVar(scip, benders->auxiliaryvars[i]) );
680  }
681 
682  SCIPfreeBlockMemory(scip, &vardata);
683 
684  return SCIP_OKAY;
685 }
686 
687 /** sets the subproblem objective value array to -infinity */
688 static
690  SCIP_BENDERS* benders /**< the Benders' decomposition structure */
691  )
692 {
693  SCIP* subproblem;
694  int nsubproblems;
695  int i;
696 
697  assert(benders != NULL);
698 
699  nsubproblems = SCIPbendersGetNSubproblems(benders);
700 
701  for( i = 0; i < nsubproblems; i++ )
702  {
703  subproblem = SCIPbendersSubproblem(benders, i);
704  SCIPbendersSetSubproblemObjval(benders, i, SCIPinfinity(subproblem));
705  }
706 }
707 
708 /** compares two Benders' decompositions w. r. to their priority */
709 SCIP_DECL_SORTPTRCOMP(SCIPbendersComp)
710 { /*lint --e{715}*/
711  return ((SCIP_BENDERS*)elem2)->priority - ((SCIP_BENDERS*)elem1)->priority;
712 }
713 
714 /** comparison method for sorting Benders' decompositions w.r.t. to their name */
715 SCIP_DECL_SORTPTRCOMP(SCIPbendersCompName)
716 {
717  return strcmp(SCIPbendersGetName((SCIP_BENDERS*)elem1), SCIPbendersGetName((SCIP_BENDERS*)elem2));
718 }
719 
720 /** method to call, when the priority of a Benders' decomposition was changed */
721 static
722 SCIP_DECL_PARAMCHGD(paramChgdBendersPriority)
723 { /*lint --e{715}*/
724  SCIP_PARAMDATA* paramdata;
725 
726  paramdata = SCIPparamGetData(param);
727  assert(paramdata != NULL);
728 
729  /* use SCIPsetBendersPriority() to mark the Benders' decompositions as unsorted */
730  SCIPsetBendersPriority(scip, (SCIP_BENDERS*)paramdata, SCIPparamGetInt(param)); /*lint !e740*/
731 
732  return SCIP_OKAY;
733 }
734 
735 /** creates a variable mapping between the master problem variables of the source scip and the sub scip */
736 static
738  SCIP_BENDERS* benders, /**< Benders' decomposition of the target SCIP instance */
739  SCIP_SET* sourceset, /**< global SCIP settings from the source SCIP */
740  SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables corresponding
741  * target variables; must not be NULL */
742  )
743 {
744  SCIP_VAR** vars;
745  SCIP_VAR* targetvar;
746  int nvars;
747  int i;
748 
749  assert(benders != NULL);
750  assert(sourceset != NULL);
751  assert(benders->iscopy);
752  assert(benders->mastervarsmap == NULL);
753 
754  /* getting the master problem variable data */
755  vars = SCIPgetVars(sourceset->scip);
756  nvars = SCIPgetNVars(sourceset->scip);
757 
758  /* creating the hashmap for the mapping between the master variable of the target and source scip */
759  SCIP_CALL( SCIPhashmapCreate(&benders->mastervarsmap, SCIPblkmem(sourceset->scip), nvars) );
760 
761  for( i = 0; i < nvars; i++ )
762  {
763  /* getting the variable pointer for the target SCIP variables. The variable mapping returns the target SCIP
764  * varibale for a given source SCIP variable. */
765  targetvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
766  if( targetvar != NULL )
767  {
768  SCIP_CALL( SCIPhashmapInsert(benders->mastervarsmap, targetvar, vars[i]) );
769  SCIP_CALL( SCIPcaptureVar(sourceset->scip, vars[i]) );
770  }
771  }
772 
773  return SCIP_OKAY;
774 }
775 
776 /** copies the given Benders' decomposition to a new SCIP */
778  SCIP_BENDERS* benders, /**< Benders' decomposition */
779  SCIP_SET* sourceset, /**< SCIP_SET of SCIP to copy from */
780  SCIP_SET* targetset, /**< SCIP_SET of SCIP to copy to */
781  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
782  * target variables; must not be NULL */
783  SCIP_Bool* valid /**< was the copying process valid? */
784  )
785 {
786  SCIP_BENDERS* targetbenders; /* the copy of the Benders' decomposition struct in the target set */
787  int i;
788 
789  assert(benders != NULL);
790  assert(targetset != NULL);
791  assert(varmap != NULL);
792  assert(valid != NULL);
793  assert(targetset->scip != NULL);
794 
795  (*valid) = FALSE;
796 
797  if( benders->benderscopy != NULL && targetset->benders_copybenders && SCIPbendersIsActive(benders) )
798  {
799  SCIPsetDebugMsg(targetset, "including Benders' decomposition %s in subscip %p\n", SCIPbendersGetName(benders), (void*)targetset->scip);
800  SCIP_CALL( benders->benderscopy(targetset->scip, benders) );
801 
802  /* copying the Benders' cuts */
803  targetbenders = SCIPsetFindBenders(targetset, SCIPbendersGetName(benders));
804 
805  /* storing the pointer to the source scip instance */
806  targetbenders->sourcescip = sourceset->scip;
807 
808  /* the flag is set to indicate that the Benders' decomposition is a copy */
809  targetbenders->iscopy = TRUE;
810 
811  /* calling the copy method for the Benders' cuts */
813  for( i = 0; i < benders->nbenderscuts; i++ )
814  {
815  SCIP_CALL( SCIPbenderscutCopyInclude(targetbenders, benders->benderscuts[i], targetset) );
816  }
817 
818  /* When the Benders' decomposition is copied then a variable mapping between the master problem variables is
819  * required. This variable mapping is used to transfer the cuts generated in the target SCIP to the source SCIP.
820  * The variable map is stored in the target Benders' decomposition. This will be freed when the sub-SCIP is freed.
821  */
822  SCIP_CALL( createMasterVarMapping(targetbenders, sourceset, varmap) );
823  }
824 
825  /* if the Benders' decomposition is active, then copy is not valid. */
826  (*valid) = !SCIPbendersIsActive(benders);
827 
828  return SCIP_OKAY;
829 }
830 
831 /** creates a Benders' decomposition structure
832  *
833  * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
834  */
836  SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
837  SCIP_SET* set, /**< global SCIP settings */
838  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
839  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
840  const char* name, /**< name of Benders' decomposition */
841  const char* desc, /**< description of Benders' decomposition */
842  int priority, /**< priority of the Benders' decomposition */
843  SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */
844  SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */
845  SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */
846  SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */
847  SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
848  SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */
849  SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */
850  SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */
851  SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
852  SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
853  SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
854  SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
855  SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
856  SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
857  SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
858  SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
859  SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
860  SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
861  SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
862  SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */
863  )
864 {
865  char paramname[SCIP_MAXSTRLEN];
866  char paramdesc[SCIP_MAXSTRLEN];
867 
868  assert(benders != NULL);
869  assert(name != NULL);
870  assert(desc != NULL);
871 
872  /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */
873  if( (benderssolvesubconvex == NULL && benderssolvesub == NULL && bendersfreesub != NULL)
874  || ((benderssolvesubconvex != NULL || benderssolvesub != NULL) && bendersfreesub == NULL) )
875  {
876  SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is implemented, then at least "
877  "one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented.\n", name, name, name, name);
878  return SCIP_INVALIDCALL;
879  }
880 
881  SCIP_ALLOC( BMSallocMemory(benders) );
882  BMSclearMemory(*benders);
883  SCIP_ALLOC( BMSduplicateMemoryArray(&(*benders)->name, name, strlen(name)+1) );
884  SCIP_ALLOC( BMSduplicateMemoryArray(&(*benders)->desc, desc, strlen(desc)+1) );
885  (*benders)->priority = priority;
886  (*benders)->cutlp = cutlp;
887  (*benders)->cutpseudo = cutpseudo;
888  (*benders)->cutrelax = cutrelax;
889  (*benders)->shareauxvars = shareauxvars;
890  (*benders)->benderscopy = benderscopy;
891  (*benders)->bendersfree = bendersfree;
892  (*benders)->bendersinit = bendersinit;
893  (*benders)->bendersexit = bendersexit;
894  (*benders)->bendersinitpre = bendersinitpre;
895  (*benders)->bendersexitpre = bendersexitpre;
896  (*benders)->bendersinitsol = bendersinitsol;
897  (*benders)->bendersexitsol = bendersexitsol;
898  (*benders)->bendersgetvar = bendersgetvar;
899  (*benders)->benderscreatesub = benderscreatesub;
900  (*benders)->benderspresubsolve = benderspresubsolve;
901  (*benders)->benderssolvesubconvex = benderssolvesubconvex;
902  (*benders)->benderssolvesub = benderssolvesub;
903  (*benders)->benderspostsolve = benderspostsolve;
904  (*benders)->bendersfreesub = bendersfreesub;
905  (*benders)->bendersdata = bendersdata;
906  SCIP_CALL( SCIPclockCreate(&(*benders)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
907  SCIP_CALL( SCIPclockCreate(&(*benders)->bendersclock, SCIP_CLOCKTYPE_DEFAULT) );
908 
909  /* add parameters */
910  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/priority", name);
911  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of Benders' decomposition <%s>", name);
912  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
913  &(*benders)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
914  paramChgdBendersPriority, (SCIP_PARAMDATA*)(*benders)) ); /*lint !e740*/
915 
916  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutlp", name);
917  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
918  "should Benders' cuts be generated for LP solutions?", &(*benders)->cutlp, FALSE, cutlp, NULL, NULL) ); /*lint !e740*/
919 
920  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutpseudo", name);
921  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
922  "should Benders' cuts be generated for pseudo solutions?", &(*benders)->cutpseudo, FALSE, cutpseudo, NULL, NULL) ); /*lint !e740*/
923 
924  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutrelax", name);
925  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
926  "should Benders' cuts be generated for relaxation solutions?", &(*benders)->cutrelax, FALSE, cutrelax, NULL, NULL) ); /*lint !e740*/
927 
928  /* These parameters are left for the user to decide in a settings file. This departs from the usual SCIP convention
929  * where the settings available at the creation of the plugin can be set in the function call.
930  */
931  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/transfercuts", name);
932  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
933  "should Benders' cuts from LNS heuristics be transferred to the main SCIP instance?", &(*benders)->transfercuts,
934  FALSE, SCIP_DEFAULT_TRANSFERCUTS, NULL, NULL) ); /*lint !e740*/
935 
936  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnscheck", name);
937  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
938  "should Benders' decomposition be used in LNS heurisics?", &(*benders)->lnscheck, FALSE, SCIP_DEFAULT_LNSCHECK,
939  NULL, NULL) ); /*lint !e740*/
940 
941  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnsmaxdepth", name);
942  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
943  "maximum depth at which the LNS check is performed (-1: no limit)", &(*benders)->lnsmaxdepth, TRUE,
945 
946  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutsasconss", name);
947  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
948  "should the transferred cuts be added as constraints?", &(*benders)->cutsasconss, FALSE,
949  SCIP_DEFAULT_CUTSASCONSS, NULL, NULL) ); /*lint !e740*/
950 
951  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/subprobfrac", name);
952  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
953  "fraction of subproblems that are solved in each iteration", &(*benders)->subprobfrac, FALSE,
954  SCIP_DEFAULT_SUBPROBFRAC, 0.0, 1.0, NULL, NULL) ); /*lint !e740*/
955 
956  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/updateauxvarbound", name);
957  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
958  "should the auxiliary variable bound be updated by solving the subproblem?", &(*benders)->updateauxvarbound,
959  FALSE, SCIP_DEFAULT_UPDATEAUXVARBOUND, NULL, NULL) ); /*lint !e740*/
960 
961  return SCIP_OKAY;
962 }
963 
964 
965 /** releases the variables that have been captured in the hashmap */
966 static
968  SCIP* scip, /**< the SCIP data structure */
969  SCIP_BENDERS* benders /**< Benders' decomposition */
970  )
971 {
972  int nentries;
973  int i;
974 
975  assert(scip != NULL);
976  assert(benders != NULL);
977 
978  assert(benders->mastervarsmap != NULL);
979 
980  nentries = SCIPhashmapGetNEntries(benders->mastervarsmap);
981 
982  for( i = 0; i < nentries; ++i )
983  {
984  SCIP_HASHMAPENTRY* entry;
985  entry = SCIPhashmapGetEntry(benders->mastervarsmap, i);
986 
987  if( entry != NULL )
988  {
989  SCIP_VAR* var;
990  var = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
991 
992  SCIP_CALL( SCIPreleaseVar(scip, &var) );
993  }
994  }
995 
996  return SCIP_OKAY;
997 }
998 
999 
1000 /** calls destructor and frees memory of Benders' decomposition */
1002  SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
1003  SCIP_SET* set /**< global SCIP settings */
1004  )
1005 {
1006  int i;
1007 
1008  assert(benders != NULL);
1009  assert(*benders != NULL);
1010  assert(!(*benders)->initialized);
1011  assert(set != NULL);
1012 
1013  /* call destructor of Benders' decomposition */
1014  if( (*benders)->bendersfree != NULL )
1015  {
1016  SCIP_CALL( (*benders)->bendersfree(set->scip, *benders) );
1017  }
1018 
1019  /* if the Benders' decomposition is a copy, then the variable map between the source and the target SCIP needs to be
1020  * freed.
1021  */
1022  if( (*benders)->iscopy )
1023  {
1024  SCIP_CALL( releaseVarMappingHashmapVars((*benders)->sourcescip, (*benders)) );
1025  SCIPhashmapFree(&(*benders)->mastervarsmap);
1026  }
1027 
1028  /* freeing the Benders' cuts */
1029  for( i = 0; i < (*benders)->nbenderscuts; i++ )
1030  {
1031  SCIP_CALL( SCIPbenderscutFree(&((*benders)->benderscuts[i]), set) );
1032  }
1033  BMSfreeMemoryArrayNull(&(*benders)->benderscuts);
1034 
1035  SCIPclockFree(&(*benders)->bendersclock);
1036  SCIPclockFree(&(*benders)->setuptime);
1037  BMSfreeMemoryArray(&(*benders)->name);
1038  BMSfreeMemoryArray(&(*benders)->desc);
1039  BMSfreeMemory(benders);
1040 
1041  return SCIP_OKAY;
1042 }
1043 
1044 /** initialises a MIP subproblem by putting the problem into SCIP_STAGE_SOLVING. This is achieved by calling SCIPsolve
1045  * and then interrupting the solve in a node focus event handler.
1046  * The LP subproblem is also initialised using this method; however, a different event handler is added. This event
1047  * handler will put the LP subproblem into probing mode.
1048  * The MIP solving function is called to initialise the subproblem because this function calls SCIPsolve with the
1049  * appropriate parameter settings for Benders' decomposition.
1050  */
1051 static
1053  SCIP_BENDERS* benders, /**< Benders' decomposition */
1054  SCIP_SET* set, /**< global SCIP settings */
1055  int probnumber, /**< the subproblem number */
1056  SCIP_Bool* success /**< was the initialisation process successful */
1057  )
1058 {
1059  SCIP* subproblem;
1060  SCIP_Bool infeasible;
1061  SCIP_Bool cutoff;
1062 
1063  assert(benders != NULL);
1064  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
1065  assert(success != NULL);
1066 
1067  (*success) = FALSE;
1068 
1069  subproblem = SCIPbendersSubproblem(benders, probnumber);
1070  assert(subproblem != NULL);
1071 
1072  /* Getting the problem into the right SCIP stage for solving */
1073  SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &infeasible, SCIP_BENDERSENFOTYPE_LP,
1074  FALSE) );
1075 
1076  /* Constructing the LP that can be solved in later iterations */
1077  if( SCIPgetStatus(subproblem) != SCIP_STATUS_BESTSOLLIMIT && SCIPgetStatus(subproblem) != SCIP_STATUS_TIMELIMIT
1078  && SCIPgetStatus(subproblem) != SCIP_STATUS_MEMLIMIT )
1079  {
1080  assert(SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING);
1081 
1082  SCIP_CALL( SCIPconstructLP(subproblem, &cutoff) );
1083  (*success) = TRUE;
1084  }
1085 
1086 
1087  return SCIP_OKAY;
1088 }
1089 
1090 
1091 /** initialises an LP subproblem by putting the problem into probing mode. The probing mode is invoked in a node focus
1092  * event handler. This event handler is added just prior to calling the initialise subproblem function.
1093  */
1094 static
1096  SCIP_BENDERS* benders, /**< Benders' decomposition */
1097  SCIP_SET* set, /**< global SCIP settings */
1098  int probnumber /**< the subproblem number */
1099  )
1100 {
1101  SCIP* subproblem;
1102  SCIP_EVENTHDLR* eventhdlr;
1103  SCIP_EVENTHDLRDATA* eventhdlrdata;
1104  SCIP_Bool success;
1105 
1106  assert(benders != NULL);
1107  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
1108 
1109  subproblem = SCIPbendersSubproblem(benders, probnumber);
1110  assert(subproblem != NULL);
1111 
1112  /* include event handler into SCIP */
1113  SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata) );
1114 
1115  SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata) );
1116 
1118  eventExecBendersNodefocus, eventhdlrdata) );
1119  SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersNodefocus) );
1120  SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersNodefocus) );
1121  SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersNodefocus) );
1122  SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersNodefocus) );
1123  assert(eventhdlr != NULL);
1124 
1125  /* calling an initial solve to put the problem into probing mode */
1126  SCIP_CALL( initialiseSubproblem(benders, set, probnumber, &success) );
1127 
1128  return SCIP_OKAY;
1129 }
1130 
1131 /** creates the subproblems and registers it with the Benders' decomposition struct */
1132 static
1134  SCIP_BENDERS* benders, /**< Benders' decomposition */
1135  SCIP_SET* set /**< global SCIP settings */
1136  )
1137 {
1138  SCIP* subproblem;
1139  SCIP_EVENTHDLR* eventhdlr;
1140  SCIP_VAR* mastervar;
1141  SCIP_VAR** vars;
1142  int nvars;
1143  int nbinvars;
1144  int nintvars;
1145  int nimplintvars;
1146  int nsubproblems;
1147  int i;
1148  int j;
1149 
1150  assert(benders != NULL);
1151  assert(set != NULL);
1152 
1153  /* if the subproblems have already been created, then they will not be created again. This is the case if the
1154  * transformed problem has been freed and then retransformed. The subproblems should only be created when the problem
1155  * is first transformed. */
1156  if( benders->subprobscreated )
1157  return SCIP_OKAY;
1158 
1159  nsubproblems = SCIPbendersGetNSubproblems(benders);
1160 
1161  /* creating all subproblems */
1162  for( i = 0; i < nsubproblems; i++ )
1163  {
1164  /* calling the create subproblem call back method */
1165  SCIP_CALL( benders->benderscreatesub(set->scip, benders, i) );
1166 
1167  subproblem = SCIPbendersSubproblem(benders, i);
1168 
1169  assert(subproblem != NULL);
1170 
1171  /* setting global limits for the subproblems. This overwrites the limits set by the user */
1172  SCIP_CALL( SCIPsetIntParam(subproblem, "limits/maxorigsol", 0) );
1173 
1174  /* getting the number of integer and binary variables to determine the problem type */
1175  SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, &nbinvars, &nintvars, &nimplintvars, NULL) );
1176 
1177  /* The objective function coefficients of the master problem are set to zero. This is necessary for the Benders'
1178  * decomposition algorithm, since the cut methods and the objective function check assumes that the objective
1179  * coefficients of the master problem variables are zero.
1180  *
1181  * This only occurs if the Benders' decomposition is not a copy. It is assumed that the correct objective
1182  * coefficients are given during the first subproblem creation.
1183  */
1184  if( !benders->iscopy )
1185  {
1186  SCIP_Bool objchanged = FALSE;
1187 
1188  assert(SCIPgetStage(subproblem) == SCIP_STAGE_PROBLEM);
1189  for( j = 0; j < nvars; j++ )
1190  {
1191  /* retrieving the master problem variable */
1192  SCIP_CALL( SCIPbendersGetVar(benders, set, vars[j], &mastervar, -1) );
1193 
1194  /* if mastervar is not NULL, then the subproblem variable has a corresponding master problem variable */
1195  if( mastervar != NULL && !SCIPisZero(subproblem, SCIPvarGetObj(vars[j])) )
1196  {
1197  SCIPverbMessage(subproblem, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Changing the objective "
1198  "coefficient of copy of master problem variable <%s> in subproblem %d to zero.\n",
1199  SCIPvarGetName(mastervar), i);
1200  /* changing the subproblem variable objective coefficient to zero */
1201  SCIP_CALL( SCIPchgVarObj(subproblem, vars[j], 0.0) );
1202 
1203  objchanged = TRUE;
1204  }
1205  }
1206 
1207  if( objchanged )
1208  {
1209  SCIPverbMessage(subproblem, SCIP_VERBLEVEL_HIGH, NULL, "Benders' decomposition: Objective coefficients of "
1210  "copied of master problem variables has been changed to zero.\n");
1211  }
1212  }
1213 
1214  /* if there are no binary and integer variables, then the subproblem is an LP.
1215  * In this case, the SCIP instance is put into probing mode via the use of an event handler. */
1216  if( nbinvars == 0 && nintvars == 0 && nimplintvars == 0 )
1217  {
1219 
1220  /* if the user has not implemented a solve subproblem callback, then the subproblem solves are performed
1221  * internally. To be more efficient the subproblem is put into probing mode. */
1222  if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL
1223  && SCIPgetStage(subproblem) <= SCIP_STAGE_PROBLEM )
1224  {
1225  SCIP_CALL( initialiseLPSubproblem(benders, set, i) );
1226  }
1227  }
1228  else
1229  {
1230  SCIP_EVENTHDLRDATA* eventhdlrdata_mipnodefocus;
1231  SCIP_EVENTHDLRDATA* eventhdlrdata_upperbound;
1232 
1234 
1235  /* because the subproblems could be reused in the copy, the event handler is not created again.
1236  * NOTE: This currently works with the benders_default implementation. It may not be very general. */
1237  if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL && !benders->iscopy )
1238  {
1239  SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata_mipnodefocus) );
1240  SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata_upperbound) );
1241 
1242  SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata_mipnodefocus) );
1243  SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata_upperbound) );
1244 
1245  /* include the first LP solved event handler into the subproblem */
1247  MIPNODEFOCUS_EVENTHDLR_DESC, eventExecBendersMipnodefocus, eventhdlrdata_mipnodefocus) );
1248  SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersMipnodefocus) );
1249  SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersMipnodefocus) );
1250  SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersMipnodefocus) );
1251  SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersMipnodefocus) );
1252  assert(eventhdlr != NULL);
1253 
1254  /* include the upper bound interrupt event handler into the subproblem */
1256  UPPERBOUND_EVENTHDLR_DESC, eventExecBendersUpperbound, eventhdlrdata_upperbound) );
1257  SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersUpperbound) );
1258  SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersUpperbound) );
1259  SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersUpperbound) );
1260  SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersUpperbound) );
1261  assert(eventhdlr != NULL);
1262  }
1263  }
1264  }
1265 
1266  benders->subprobscreated = TRUE;
1267 
1268  return SCIP_OKAY;
1269 }
1270 
1271 
1272 /** initializes Benders' decomposition */
1274  SCIP_BENDERS* benders, /**< Benders' decomposition */
1275  SCIP_SET* set /**< global SCIP settings */
1276  )
1277 {
1278  int i;
1279 
1280  assert(benders != NULL);
1281  assert(set != NULL);
1282 
1283  if( benders->initialized )
1284  {
1285  SCIPerrorMessage("Benders' decomposition <%s> already initialized\n", benders->name);
1286  return SCIP_INVALIDCALL;
1287  }
1288 
1289  if( set->misc_resetstat )
1290  {
1291  SCIPclockReset(benders->setuptime);
1292  SCIPclockReset(benders->bendersclock);
1293 
1294  benders->ncalls = 0;
1295  benders->ncutsfound = 0;
1296  benders->ntransferred = 0;
1297  }
1298 
1299  /* start timing */
1300  SCIPclockStart(benders->setuptime, set);
1301 
1302  if( benders->bendersinit != NULL )
1303  {
1304  SCIP_CALL( benders->bendersinit(set->scip, benders) );
1305  }
1306 
1307  benders->initialized = TRUE;
1308 
1309  /* creates the subproblems and sets up the probing mode for LP subproblems. This function calls the benderscreatesub
1310  * callback. */
1311  SCIP_CALL( createSubproblems(benders, set) );
1312 
1313  /* initialising the Benders' cuts */
1314  SCIPbendersSortBenderscuts(benders);
1315  for( i = 0; i < benders->nbenderscuts; i++ )
1316  {
1317  SCIP_CALL( SCIPbenderscutInit(benders->benderscuts[i], set) );
1318  }
1319 
1320  /* stop timing */
1321  SCIPclockStop(benders->setuptime, set);
1322 
1323  return SCIP_OKAY;
1324 }
1325 
1326 
1327 /** Transfers Benders' cuts that were generated while solving a sub-SCIP to the original SCIP instance. This involves
1328  * creating a constraint/cut that is equivalent to the generated cut in the sub-SCIP. This new constraint/cut is then
1329  * added to the original SCIP instance.
1330  */
1331 static
1333  SCIP* sourcescip, /**< the source SCIP from when the Benders' decomposition was copied */
1334  SCIP_BENDERS* benders, /**< the Benders' decomposition structure of the sub SCIP */
1335  SCIP_VAR** vars, /**< the variables from the source constraint */
1336  SCIP_Real* vals, /**< the coefficients of the variables in the source constriant */
1337  SCIP_Real lhs, /**< the LHS of the source constraint */
1338  SCIP_Real rhs, /**< the RHS of the source constraint */
1339  int nvars /**< the number of variables in the source constraint */
1340  )
1341 {
1342  SCIP_BENDERS* sourcebenders; /* the Benders' decomposition of the source SCIP */
1343  SCIP_CONSHDLR* consbenders; /* a helper variable for the Benders' decomposition constraint handler */
1344  SCIP_CONS* transfercons; /* the constraint that is generated to transfer the constraints/cuts */
1345  SCIP_ROW* transfercut; /* the cut that is generated to transfer the constraints/cuts */
1346  SCIP_VAR* sourcevar; /* the source variable that will be added to the transferred cut */
1347  SCIP_VAR* origvar;
1348  SCIP_Real scalar;
1349  SCIP_Real constant;
1350  char cutname[SCIP_MAXSTRLEN]; /* the name of the transferred cut */
1351  int i;
1352  SCIP_Bool fail;
1353 
1354  assert(sourcescip != NULL);
1355  assert(benders != NULL);
1356  assert(vars != NULL);
1357  assert(vals != NULL);
1358 
1359  /* retrieving the source Benders' decomposition structure */
1360  sourcebenders = SCIPfindBenders(sourcescip, SCIPbendersGetName(benders));
1361 
1362  /* retrieving the Benders' decomposition constraint handler */
1363  consbenders = SCIPfindConshdlr(sourcescip, "benders");
1364 
1365  /* setting the name of the transferred cut */
1366  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "transferredcut_%d",
1367  SCIPbendersGetNTransferredCuts(sourcebenders) );
1368 
1369  /* TODO: It could be more efficient to pass an updated vars array with the vals array to the
1370  * SCIPcreateConsBasicLinear/SCIPcreateEmptyRowCons. This should be implemented to improve the performance of the
1371  * Large Neighbourhood Benders Search.
1372  */
1373 
1374  /* creating an empty row/constraint for the transferred cut */
1375  if( sourcebenders->cutsasconss )
1376  {
1377  SCIP_CALL( SCIPcreateConsBasicLinear(sourcescip, &transfercons, cutname, 0, NULL, NULL, lhs, rhs) );
1378  SCIP_CALL( SCIPsetConsRemovable(sourcescip, transfercons, TRUE) );
1379  }
1380  else
1381  {
1382  SCIP_CALL( SCIPcreateEmptyRowCons(sourcescip, &transfercut, consbenders, cutname, lhs, rhs, FALSE,
1383  FALSE, TRUE) );
1384  }
1385 
1386  fail = FALSE;
1387  for( i = 0; i < nvars; i++ )
1388  {
1389  /* getting the original variable for the transformed variable */
1390  origvar = vars[i];
1391  scalar = 1.0;
1392  constant = 0.0;
1393  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
1394 
1395  /* getting the source var from the hash map */
1396  sourcevar = (SCIP_VAR*) SCIPhashmapGetImage(benders->mastervarsmap, origvar);
1397 
1398  /* if the source variable is not found, then the mapping in incomplete. So the constraint can not be
1399  * transferred. */
1400  if( sourcevar == NULL )
1401  {
1402  fail = TRUE;
1403  break;
1404  }
1405 
1406  if( sourcebenders->cutsasconss )
1407  {
1408  SCIP_CALL( SCIPaddCoefLinear(sourcescip, transfercons, sourcevar, vals[i]) ); /*lint !e644*/
1409  }
1410  else
1411  {
1412  SCIP_CALL( SCIPaddVarToRow(sourcescip, transfercut, sourcevar, vals[i]) ); /*lint !e644*/
1413  }
1414  }
1415 
1416  /* if all of the source variables were found to generate the cut */
1417  if( !fail )
1418  {
1419  if( sourcebenders->cutsasconss )
1420  {
1421  SCIP_CALL( SCIPaddCons(sourcescip, transfercons) );
1422  }
1423  else
1424  {
1425  SCIP_CALL( SCIPaddPoolCut(sourcescip, transfercut) );
1426  }
1427 
1428  sourcebenders->ntransferred++;
1429  }
1430 
1431  /* release the row/constraint */
1432  if( sourcebenders->cutsasconss )
1433  {
1434  SCIP_CALL( SCIPreleaseCons(sourcescip, &transfercons) );
1435  }
1436  else
1437  {
1438  SCIP_CALL( SCIPreleaseRow(sourcescip, &transfercut) );
1439  }
1440 
1441  return SCIP_OKAY;
1442 }
1443 
1444 
1445 /** transfers the cuts generated in a subscip to the source scip */
1446 static
1448  SCIP* sourcescip, /**< the source SCIP from when the Benders' decomposition was copied */
1449  SCIP* subscip, /**< the sub SCIP where the Benders' cuts were generated */
1450  SCIP_BENDERS* benders /**< the Benders' decomposition structure of the sub SCIP */
1451  )
1452 {
1453  SCIP_BENDERS* sourcebenders; /* the Benders' decomposition of the source SCIP */
1454  SCIP_BENDERSCUT* benderscut; /* a helper variable for the Benders' cut plugin */
1455  SCIP_CONS** addedcons; /* the constraints added by the Benders' cut */
1456  SCIP_ROW** addedcuts; /* the cuts added by the Benders' cut */
1457  SCIP_VAR** vars; /* the variables of the added constraint/row */
1458  SCIP_Real* vals; /* the values of the added constraint/row */
1459  SCIP_Real lhs; /* the LHS of the added constraint/row */
1460  SCIP_Real rhs; /* the RHS of the added constraint/row */
1461  int naddedcons;
1462  int naddedcuts;
1463  int nvars;
1464  int i;
1465  int j;
1466  int k;
1467 
1468  assert(subscip != NULL);
1469  assert(benders != NULL);
1470 
1471  /* retrieving the source Benders' decomposition structure */
1472  sourcebenders = SCIPfindBenders(sourcescip, SCIPbendersGetName(benders));
1473 
1474  /* exit if the cuts should not be transferred from the sub SCIP to the source SCIP. */
1475  if( !sourcebenders->transfercuts )
1476  return SCIP_OKAY;
1477 
1478  for( i = 0; i < benders->nbenderscuts; i++ )
1479  {
1480  benderscut = benders->benderscuts[i];
1481 
1482  /* retreiving the Benders' cuts constraints */
1483  SCIP_CALL( SCIPbenderscutGetAddedConss(benderscut, &addedcons, &naddedcons) );
1484 
1485  /* looping over all added constraints to construct the cut for the source scip */
1486  for( j = 0; j < naddedcons; j++ )
1487  {
1488  SCIP_CONSHDLR* conshdlr;
1489  const char * conshdlrname;
1490 
1491  conshdlr = SCIPconsGetHdlr(addedcons[j]);
1492  assert(conshdlr != NULL);
1493  conshdlrname = SCIPconshdlrGetName(conshdlr);
1494 
1495  /* it is only possible to transfer linear constraints. If the Benders' cut has been added as another
1496  * constraint, then this will not be transferred to the source SCIP */
1497  if( strcmp(conshdlrname, "linear") == 0 )
1498  {
1499  /* collecting the variable information from the constraint */
1500  nvars = SCIPgetNVarsLinear(subscip, addedcons[j]);
1501  vars = SCIPgetVarsLinear(subscip, addedcons[j]);
1502  vals = SCIPgetValsLinear(subscip, addedcons[j]);
1503 
1504  /* collecting the bounds from the constraint */
1505  lhs = SCIPgetLhsLinear(subscip, addedcons[j]);
1506  rhs = SCIPgetRhsLinear(subscip, addedcons[j]);
1507 
1508  if( nvars > 0 )
1509  {
1510  /* create and add the cut to be transferred from the sub SCIP to the source SCIP */
1511  SCIP_CALL( createAndAddTransferredCut(sourcescip, benders, vars, vals, lhs, rhs, nvars) );
1512  }
1513  }
1514  }
1515 
1516  /* retreiving the Benders' cuts added cuts */
1517  SCIP_CALL( SCIPbenderscutGetAddedCuts(benderscut, &addedcuts, &naddedcuts) );
1518 
1519  /* looping over all added constraints to costruct the cut for the source scip */
1520  for( j = 0; j < naddedcuts; j++ )
1521  {
1522  SCIP_COL** cols;
1523  int ncols;
1524 
1525  cols = SCIProwGetCols(addedcuts[j]);
1526  ncols = SCIProwGetNNonz(addedcuts[j]);
1527 
1528  /* get all variables of the row */
1529  SCIP_CALL( SCIPallocBufferArray(subscip, &vars, ncols) );
1530  for( k = 0; k < ncols; ++k )
1531  vars[k] = SCIPcolGetVar(cols[k]);
1532 
1533  /* collecting the variable information from the constraint */
1534  vals = SCIProwGetVals(addedcuts[j]);
1535 
1536  /* collecting the bounds from the constraint */
1537  lhs = SCIProwGetLhs(addedcuts[j]) - SCIProwGetConstant(addedcuts[j]);
1538  rhs = SCIProwGetRhs(addedcuts[j]) - SCIProwGetConstant(addedcuts[j]);
1539 
1540  /* create and add the cut to be transferred from the sub SCIP to the source SCIP */
1541  SCIP_CALL( createAndAddTransferredCut(sourcescip, benders, vars, vals, lhs, rhs, ncols) );
1542 
1543  SCIPfreeBufferArray(subscip, &vars);
1544  }
1545  }
1546 
1547  return SCIP_OKAY;
1548 }
1549 
1550 
1551 /** calls exit method of Benders' decomposition */
1553  SCIP_BENDERS* benders, /**< Benders' decomposition */
1554  SCIP_SET* set /**< global SCIP settings */
1555  )
1556 {
1557  int nsubproblems;
1558  int i;
1559 
1560  assert(benders != NULL);
1561  assert(set != NULL);
1562 
1563  if( !benders->initialized )
1564  {
1565  SCIPerrorMessage("Benders' decomposition <%s> not initialized\n", benders->name);
1566  return SCIP_INVALIDCALL;
1567  }
1568 
1569  /* start timing */
1570  SCIPclockStart(benders->setuptime, set);
1571 
1572  if( benders->bendersexit != NULL )
1573  {
1574  SCIP_CALL( benders->bendersexit(set->scip, benders) );
1575  }
1576 
1577  /* if the Benders' decomposition is a copy, then the generated cuts will be transferred to the source scip */
1578  if( benders->iscopy )
1579  {
1580  SCIP_CALL( transferBendersCuts(benders->sourcescip, set->scip, benders) );
1581  }
1582 
1583  /* releasing all of the auxiliary variables */
1584  nsubproblems = SCIPbendersGetNSubproblems(benders);
1585  for( i = 0; i < nsubproblems; i++ )
1586  {
1587  /* it is possible that the master problem is not solved. As such, the auxiliary variables will not be created. So
1588  * we don't need to release the variables
1589  */
1590  if( benders->auxiliaryvars[i] != NULL )
1591  {
1592  SCIP_CALL( SCIPreleaseVar(set->scip, &benders->auxiliaryvars[i]) );
1593  }
1594  }
1595 
1596  /* calling the exit method for the Benders' cuts */
1597  SCIPbendersSortBenderscuts(benders);
1598  for( i = 0; i < benders->nbenderscuts; i++ )
1599  {
1600  SCIP_CALL( SCIPbenderscutExit(benders->benderscuts[i], set) );
1601  }
1602 
1603  benders->initialized = FALSE;
1604 
1605  /* stop timing */
1606  SCIPclockStop(benders->setuptime, set);
1607 
1608  return SCIP_OKAY;
1609 }
1610 
1611 /** Checks whether a subproblem is independent. */
1612 static
1614  SCIP* scip, /**< the SCIP data structure */
1615  SCIP_BENDERS* benders /**< Benders' decomposition */
1616  )
1617 {
1618  SCIP_VAR** vars;
1619  int nvars;
1620  int nsubproblems;
1621  int i;
1622  int j;
1623 
1624  assert(scip != NULL);
1625  assert(benders != NULL);
1626 
1627  /* retrieving the master problem variables */
1628  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1629 
1630  nsubproblems = SCIPbendersGetNSubproblems(benders);
1631 
1632  /* looping over all subproblems to check whether there exists at least one master problem variable */
1633  for( i = 0; i < nsubproblems; i++ )
1634  {
1635  SCIP_Bool independent = FALSE;
1636 
1637  /* if there are user defined solving or freeing functions, then it is not possible to declare the independence of
1638  * the subproblems.
1639  */
1640  if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL
1641  && benders->bendersfreesub == NULL )
1642  {
1643  independent = TRUE;
1644 
1645  for( j = 0; j < nvars; j++ )
1646  {
1647  SCIP_VAR* subprobvar;
1648 
1649  /* getting the subproblem problem variable corresponding to the master problem variable */
1650  SCIP_CALL( SCIPgetBendersSubproblemVar(scip, benders, vars[j], &subprobvar, i) );
1651 
1652  /* if the subporblem variable is not NULL, then the subproblem depends on the master problem */
1653  if( subprobvar != NULL )
1654  {
1655  independent = FALSE;
1656  break;
1657  }
1658  }
1659 
1660  /* setting the independent flag */
1661  SCIPbendersSetSubproblemIsIndependent(benders, i, independent);
1662  }
1663  }
1664 
1665  return SCIP_OKAY;
1666 }
1667 
1668 /** informs the Benders' decomposition that the presolving process is being started */
1670  SCIP_BENDERS* benders, /**< Benders' decomposition */
1671  SCIP_SET* set, /**< global SCIP settings */
1672  SCIP_STAT* stat /**< dynamic problem statistics */
1673  )
1674 {
1675  assert(benders != NULL);
1676  assert(set != NULL);
1677  assert(stat != NULL);
1678 
1679  if( !benders->iscopy )
1680  {
1681  /* check the subproblem independence. This check is only performed if the user has not implemented a solve
1682  * subproblem function.
1683  */
1684  if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL )
1685  SCIP_CALL( checkSubproblemIndependence(set->scip, benders) );
1686 
1687  /* adding the auxiliary variables to the master problem */
1688  SCIP_CALL( addAuxiliaryVariablesToMaster(set->scip, benders) );
1689  }
1690  else
1691  {
1692  /* the copied auxiliary variables must be assigned to the target Benders' decomposition */
1693  SCIP_CALL( assignAuxiliaryVariables(set->scip, benders) );
1694  }
1695 
1696  /* call presolving initialization method of Benders' decomposition */
1697  if( benders->bendersinitpre != NULL )
1698  {
1699  /* start timing */
1700  SCIPclockStart(benders->setuptime, set);
1701 
1702  SCIP_CALL( benders->bendersinitpre(set->scip, benders) );
1703 
1704  /* stop timing */
1705  SCIPclockStop(benders->setuptime, set);
1706  }
1707 
1708  return SCIP_OKAY;
1709 }
1710 
1711 
1712 /** informs the Benders' decomposition that the presolving process has completed */
1714  SCIP_BENDERS* benders, /**< Benders' decomposition */
1715  SCIP_SET* set, /**< global SCIP settings */
1716  SCIP_STAT* stat /**< dynamic problem statistics */
1717  )
1718 {
1719  assert(benders != NULL);
1720  assert(set != NULL);
1721  assert(stat != NULL);
1722 
1723  /* call presolving deinitialization method of Benders' decomposition */
1724  if( benders->bendersexitpre != NULL )
1725  {
1726  /* start timing */
1727  SCIPclockStart(benders->setuptime, set);
1728 
1729  SCIP_CALL( benders->bendersexitpre(set->scip, benders) );
1730 
1731  /* stop timing */
1732  SCIPclockStop(benders->setuptime, set);
1733  }
1734 
1735  return SCIP_OKAY;
1736 }
1737 
1738 /** informs Benders' decomposition that the branch and bound process is being started */
1740  SCIP_BENDERS* benders, /**< Benders' decomposition */
1741  SCIP_SET* set /**< global SCIP settings */
1742  )
1743 {
1744  int i;
1745 
1746  assert(benders != NULL);
1747  assert(set != NULL);
1748 
1749  /* call solving process initialization method of Benders' decomposition */
1750  if( benders->bendersinitsol != NULL )
1751  {
1752  /* start timing */
1753  SCIPclockStart(benders->setuptime, set);
1754 
1755  SCIP_CALL( benders->bendersinitsol(set->scip, benders) );
1756 
1757  /* stop timing */
1758  SCIPclockStop(benders->setuptime, set);
1759  }
1760 
1761  /* calling the initsol method for the Benders' cuts */
1762  SCIPbendersSortBenderscuts(benders);
1763  for( i = 0; i < benders->nbenderscuts; i++ )
1764  {
1765  SCIP_CALL( SCIPbenderscutInitsol(benders->benderscuts[i], set) );
1766  }
1767 
1768  return SCIP_OKAY;
1769 }
1770 
1771 /** informs Benders' decomposition that the branch and bound process data is being freed */
1773  SCIP_BENDERS* benders, /**< Benders' decomposition */
1774  SCIP_SET* set /**< global SCIP settings */
1775  )
1776 {
1777  int nsubproblems;
1778  int i;
1779 
1780  assert(benders != NULL);
1781  assert(set != NULL);
1782 
1783  nsubproblems = SCIPbendersGetNSubproblems(benders);
1784  /* freeing all subproblems that are independent, this is because they have not bee freed during the subproblem
1785  * solving loop.
1786  */
1787  for( i = 0; i < nsubproblems; i++ )
1788  {
1789  if( SCIPbendersSubproblemIsIndependent(benders, i) )
1790  {
1791  /* disabling the independence of the subproblem so that it can be freed */
1793 
1794  /* freeing the independent subproblem */
1795  SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, i) );
1796  }
1797  }
1798 
1799  /* call solving process deinitialization method of Benders' decomposition */
1800  if( benders->bendersexitsol != NULL )
1801  {
1802  /* start timing */
1803  SCIPclockStart(benders->setuptime, set);
1804 
1805  SCIP_CALL( benders->bendersexitsol(set->scip, benders) );
1806 
1807  /* stop timing */
1808  SCIPclockStop(benders->setuptime, set);
1809  }
1810 
1811  /* sorting the Benders' decomposition cuts in order of priority. Only a single cut is generated for each subproblem
1812  * per solving iteration. This is particularly important in the case of the optimality and feasibility cuts. Since
1813  * these work on two different solutions to the subproblem, it is not necessary to generate both cuts. So, once the
1814  * feasibility cut is generated, then no other cuts will be generated.
1815  */
1816  SCIPbendersSortBenderscuts(benders);
1817 
1818  /* calling the exitsol method for the Benders' cuts */
1819  for( i = 0; i < benders->nbenderscuts; i++ )
1820  {
1821  SCIP_CALL( SCIPbenderscutExitsol(benders->benderscuts[i], set) );
1822  }
1823 
1824  return SCIP_OKAY;
1825 }
1826 
1827 /** activates Benders' decomposition such that it is called in LP solving loop */
1829  SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
1830  SCIP_SET* set, /**< global SCIP settings */
1831  int nsubproblems /**< the number subproblems used in this decomposition */
1832  )
1833 {
1834  SCIP_EVENTHDLR* eventhdlr;
1835  SCIP_EVENTHDLRDATA* eventhdlrdata;
1836  int i;
1837 
1838  assert(benders != NULL);
1839  assert(set != NULL);
1840  assert(set->stage == SCIP_STAGE_INIT || set->stage == SCIP_STAGE_PROBLEM);
1841 
1842  if( !benders->active )
1843  {
1844  benders->active = TRUE;
1845  set->nactivebenders++;
1846  set->benderssorted = FALSE;
1847 
1848  benders->nsubproblems = nsubproblems;
1849  benders->nactivesubprobs = nsubproblems;
1850 
1851  /* allocating memory for the subproblems arrays */
1852  SCIP_ALLOC( BMSallocMemoryArray(&benders->subproblems, benders->nsubproblems) );
1853  SCIP_ALLOC( BMSallocMemoryArray(&benders->auxiliaryvars, benders->nsubproblems) );
1854  SCIP_ALLOC( BMSallocMemoryArray(&benders->subprobobjval, benders->nsubproblems) );
1858  SCIP_ALLOC( BMSallocMemoryArray(&benders->subprobsetup, benders->nsubproblems) );
1859  SCIP_ALLOC( BMSallocMemoryArray(&benders->indepsubprob, benders->nsubproblems) );
1862 
1863  for( i = 0; i < benders->nsubproblems; i++ )
1864  {
1865  benders->subproblems[i] = NULL;
1866  benders->auxiliaryvars[i] = NULL;
1867  benders->subprobobjval[i] = SCIPsetInfinity(set);
1868  benders->bestsubprobobjval[i] = SCIPsetInfinity(set);
1869  benders->subproblowerbound[i] = -SCIPsetInfinity(set);
1870  benders->subprobisconvex[i] = FALSE;
1871  benders->subprobsetup[i] = FALSE;
1872  benders->indepsubprob[i] = FALSE;
1873  benders->subprobenabled[i] = TRUE;
1874  benders->mastervarscont[i] = FALSE;
1875  }
1876 
1877  /* adding an eventhandler for updating the lower bound when the root node is solved. */
1878  eventhdlrdata = (SCIP_EVENTHDLRDATA*)benders;
1879 
1880  /* include event handler into SCIP */
1882  eventExecBendersNodesolved, eventhdlrdata) );
1883  SCIP_CALL( SCIPsetEventhdlrInitsol(set->scip, eventhdlr, eventInitsolBendersNodesolved) );
1884  assert(eventhdlr != NULL);
1885  }
1886 
1887  return SCIP_OKAY;
1888 }
1889 
1890 /** deactivates Benders' decomposition such that it is no longer called in LP solving loop */
1892  SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
1893  SCIP_SET* set /**< global SCIP settings */
1894  )
1895 {
1896  assert(benders != NULL);
1897  assert(set != NULL);
1898  assert(set->stage == SCIP_STAGE_INIT || set->stage == SCIP_STAGE_PROBLEM);
1899 
1900  if( benders->active )
1901  {
1902 #ifndef NDEBUG
1903  int nsubproblems;
1904  int i;
1905 
1906  nsubproblems = SCIPbendersGetNSubproblems(benders);
1907 
1908  /* checking whether the auxiliary variables and subproblems are all NULL */
1909  for( i = 0; i < nsubproblems; i++ )
1910  assert(benders->auxiliaryvars[i] == NULL);
1911 #endif
1912 
1913  benders->active = FALSE;
1914  set->nactivebenders--;
1915  set->benderssorted = FALSE;
1916 
1917  /* freeing the memory allocated during the activation of the Benders' decomposition */
1920  BMSfreeMemoryArray(&benders->indepsubprob);
1921  BMSfreeMemoryArray(&benders->subprobsetup);
1925  BMSfreeMemoryArray(&benders->subprobobjval);
1926  BMSfreeMemoryArray(&benders->auxiliaryvars);
1927  BMSfreeMemoryArray(&benders->subproblems);
1928  }
1929 }
1930 
1931 /** returns whether the given Benders' decomposition is in use in the current problem */
1933  SCIP_BENDERS* benders /**< the Benders' decomposition structure */
1934  )
1935 {
1936  assert(benders != NULL);
1937 
1938  return benders->active;
1939 }
1940 
1941 /** updates the lower bound for all auxiliary variables. This is called if the first LP enforced is unbounded. */
1942 static
1944  SCIP_BENDERS* benders, /**< Benders' decomposition */
1945  SCIP_SET* set, /**< global SCIP settings */
1946  SCIP_RESULT* result /**< the result from updating the auxiliary variable lower bound */
1947  )
1948 {
1949  int nsubproblems;
1950  int i;
1951 
1952  assert(benders != NULL);
1953  assert(set != NULL);
1954 
1955  (*result) = SCIP_DIDNOTRUN;
1956 
1957  nsubproblems = SCIPbendersGetNSubproblems(benders);
1958 
1959  for( i = 0; i < nsubproblems; i++ )
1960  {
1961  SCIP_VAR* auxiliaryvar;
1962  SCIP_Real lowerbound;
1963  SCIP_Bool infeasible;
1964 
1965  infeasible = FALSE;
1966 
1967  /* computing the lower bound of the subproblem by solving it without any variable fixings */
1968  SCIP_CALL( SCIPbendersComputeSubproblemLowerbound(benders, set, i, &lowerbound, &infeasible) );
1969 
1970  /* if the subproblem is infeasible, then the original problem is infeasible */
1971  if( infeasible )
1972  {
1973  (*result) = SCIP_INFEASIBLE;
1974  break;
1975  }
1976 
1977  /* retrieving the auxiliary variable */
1978  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, i);
1979 
1980  /* only update the lower bound if it is greater than the current lower bound */
1981  if( SCIPsetIsGT(set, lowerbound, SCIPvarGetLbGlobal(auxiliaryvar)) )
1982  {
1983  SCIPsetDebugMsg(set, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
1984  /* updating the lower bound of the auxiliary variable */
1985  SCIP_CALL( SCIPchgVarLb(set->scip, auxiliaryvar, lowerbound) );
1986  (*result) = SCIP_REDUCEDDOM;
1987  }
1988 
1989  /* stores the lower bound for the subproblem */
1990  SCIPbendersUpdateSubproblemLowerbound(benders, i, lowerbound);
1991  }
1992 
1993  return SCIP_OKAY;
1994 }
1995 
1996 /** Returns whether only the convex relaxations will be checked in this solve loop
1997  * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
1998  * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
1999  * that all subproblems are convex relaxations.
2000  */
2002  SCIP_BENDERS* benders /**< Benders' decomposition */
2003  )
2004 {
2005  return benders->iscopy && benders->lnscheck;
2006 }
2007 
2008 /** returns the number of subproblems that will be checked in this iteration */
2009 static
2011  SCIP_BENDERS* benders, /**< Benders' decomposition */
2012  SCIP_SET* set, /**< global SCIP settings */
2013  SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */
2014  )
2015 {
2016  if( benders->ncalls == 0 || type == SCIP_BENDERSENFOTYPE_CHECK || SCIPbendersOnlyCheckConvexRelax(benders) )
2017  return SCIPbendersGetNSubproblems(benders);
2018  else
2019  return (int) SCIPsetCeil(set, (SCIP_Real) SCIPbendersGetNSubproblems(benders)*benders->subprobfrac);
2020 }
2021 
2022 /** returns whether the solving of the given subproblem needs to be executed */
2023 static
2025  SCIP_BENDERS* benders, /**< Benders' decomposition */
2026  int probnumber /**< the subproblem index */
2027  )
2028 {
2029  return (!SCIPbendersSubproblemIsIndependent(benders, probnumber)
2030  && SCIPbendersSubproblemIsEnabled(benders, probnumber));
2031 }
2032 
2033 /** Solves each of the Benders' decomposition subproblems for the given solution. All, or a fraction, of subproblems are
2034  * solved before the Benders' decomposition cuts are generated.
2035  * Since a convex relaxation of the subproblem could be solved to generate cuts, a parameter nverified is used to
2036  * identified the number of subproblems that have been solved in their "original" form. For example, if the subproblem
2037  * is a MIP, then if the LP is solved to generate cuts, this does not constitute a verification. The verification is
2038  * only performed when the MIP is solved.
2039  */
2040 static
2042  SCIP_BENDERS* benders, /**< Benders' decomposition */
2043  SCIP_SET* set, /**< global SCIP settings */
2044  SCIP_SOL* sol, /**< primal CIP solution */
2045  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
2046  SCIP_BENDERSSOLVELOOP solveloop, /**< the current solve loop */
2047  SCIP_Bool checkint, /**< are the subproblems called during a check/enforce of integer sols? */
2048  int* nchecked, /**< the number of subproblems checked in this solve loop, they may not be solved */
2049  int* nverified, /**< the number of subproblems verified in the current loop */
2050  SCIP_Bool** subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
2051  SCIP_BENDERSSUBSTATUS** substatus, /**< array to store the status of the subsystem */
2052  SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
2053  SCIP_Bool* optimal, /**< is the current solution optimal? */
2054  SCIP_Bool* stopped /**< was the solving process stopped? */
2055  )
2056 {
2057  SCIP_Bool onlyconvexcheck;
2058  int nsubproblems;
2059  int numtocheck;
2060  int numnotopt;
2061  int subproblemcount;
2062  int i;
2063 
2064  assert(benders != NULL);
2065  assert(set != NULL);
2066 
2067  (*stopped) = FALSE;
2068 
2069  /* getting the number of subproblems in the Benders' decompsition */
2070  nsubproblems = SCIPbendersGetNSubproblems(benders);
2071 
2072  /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
2073  * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
2074  * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
2075  * employed.
2076  */
2077  onlyconvexcheck = SCIPbendersOnlyCheckConvexRelax(benders);
2078 
2079  /* it is possible to only solve a subset of subproblems. This is given by a parameter. */
2080  numtocheck = numSubproblemsToCheck(benders, set, type);
2081 
2082  SCIPsetDebugMsg(set, "Performing the subproblem solving process. Number of subproblems to check %d\n", numtocheck);
2083 
2084  SCIPsetDebugMsg(set, "Benders' decomposition - solve loop %d\n", solveloop);
2085  numnotopt = 0;
2086  subproblemcount = 0;
2087 
2088  if( type == SCIP_BENDERSENFOTYPE_CHECK && sol == NULL )
2089  {
2090  /* TODO: Check whether this is absolutely necessary. I think that this if statment can be removed. */
2091  (*infeasible) = TRUE;
2092  }
2093  else
2094  {
2095  /* solving each of the subproblems for Benders' decomposition */
2096  /* TODO: ensure that the each of the subproblems solve and update the parameters with the correct return values
2097  */
2098  i = benders->firstchecked;
2099  /*for( i = 0; i < nsubproblems; i++ )*/
2100  while( subproblemcount < nsubproblems && numnotopt < numtocheck && !(*stopped) )
2101  {
2102  SCIP_Bool subinfeas = FALSE;
2103  SCIP_Bool convexsub = SCIPbendersSubproblemIsConvex(benders, i);
2104  SCIP_Bool solvesub = TRUE;
2105  SCIP_Bool solved;
2106 
2107  /* the subproblem is initially flagged as not solved for this solving loop */
2108  (*subprobsolved)[i] = FALSE;
2109 
2110  /* setting the subsystem status to UNKNOWN at the start of each solve loop */
2111  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_UNKNOWN;
2112 
2113  /* for the second solving loop, if the problem is an LP, it is not solved again. If the problem is a MIP,
2114  * then the subproblem objective function value is set to infinity. However, if the subproblem is proven
2115  * infeasible from the LP, then the IP loop is not performed.
2116  * If the solve loop is SCIP_BENDERSSOLVELOOP_USERCIP, then nothing is done. It is assumed that the user will
2117  * correctly update the objective function within the user-defined solving function.
2118  */
2119  if( solveloop == SCIP_BENDERSSOLVELOOP_CIP )
2120  {
2121  if( convexsub || (*substatus)[i] == SCIP_BENDERSSUBSTATUS_INFEAS )
2122  solvesub = FALSE;
2123  else
2125  }
2126 
2127  /* if the subproblem is independent, then it does not need to be solved. In this case, the nverified flag will
2128  * increase by one. When the subproblem is not independent, then it needs to be checked.
2129  */
2130  if( !subproblemIsActive(benders, i) )
2131  {
2132  /* NOTE: There is no need to update the optimal flag. This is because optimal is always TRUE until a
2133  * non-optimal subproblem is found.
2134  */
2135  /* if the auxiliary variable value is infinity, then the subproblem has not been solved yet. Currently the
2136  * subproblem statue is unknown. */
2137  if( SCIPsetIsInfinity(set, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i))
2138  || SCIPsetIsInfinity(set, -SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i))
2140  {
2142  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_UNKNOWN;
2143  (*optimal) = FALSE;
2144 
2145  SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, but has not been solved."
2146  " setting status to UNKNOWN\n", i);
2147  }
2148  else
2149  {
2150  SCIP_Real soltol;
2151 
2152  SCIP_CALL( SCIPsetGetRealParam(set, "benders/solutiontol", &soltol) );
2153 
2155  SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i)) < soltol )
2156  {
2157  SCIPbendersSetSubproblemObjval(benders, i, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i));
2158  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_OPTIMAL;
2159  }
2160  else
2161  {
2163  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_AUXVIOL;
2164  }
2165 
2166  SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, setting status to OPTIMAL\n",
2167  i);
2168 
2169  }
2170 
2171  (*subprobsolved)[i] = TRUE;
2172 
2173  /* the nverified counter is only increased in the convex solving loop */
2174  if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
2175  (*nverified)++;
2176  }
2177  else if( solvesub )
2178  {
2179  SCIP_CALL( SCIPbendersExecSubproblemSolve(benders, set, sol, i, solveloop, FALSE, &solved, &subinfeas, type) );
2180 
2181 #ifdef SCIP_DEBUG
2182  if( type == SCIP_BENDERSENFOTYPE_LP )
2183  {
2184  SCIPsetDebugMsg(set, "LP: Subproblem %d (%f < %f)\n", i, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i),
2185  SCIPbendersGetSubproblemObjval(benders, i));
2186  }
2187 #endif
2188  (*subprobsolved)[i] = solved;
2189 
2190  (*infeasible) = (*infeasible) || subinfeas;
2191  if( subinfeas )
2192  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_INFEAS;
2193 
2194  /* if the subproblems are solved to check integer feasibility, then the optimality check must be performed.
2195  * This will only be performed if checkint is TRUE and the subproblem was solved. The subproblem may not be
2196  * solved if the user has defined a solving function
2197  */
2198  if( checkint && (*subprobsolved)[i] )
2199  {
2200  /* if the subproblem is feasible, then it is necessary to update the value of the auxiliary variable to the
2201  * objective function value of the subproblem.
2202  */
2203  if( !subinfeas )
2204  {
2205  SCIP_Bool subproboptimal = FALSE;
2206 
2207  SCIP_CALL( SCIPbendersCheckSubproblemOptimality(benders, set, sol, i, &subproboptimal) );
2208 
2209  if( subproboptimal )
2210  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_OPTIMAL;
2211  else
2212  (*substatus)[i] = SCIP_BENDERSSUBSTATUS_AUXVIOL;
2213 
2214  /* It is only possible to determine the optimality of a solution within a given subproblem in four
2215  * different cases:
2216  * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX or USERCONVEX and the subproblem is convex.
2217  * ii) solveloop == SCIP_BENDERSOLVELOOP_CONVEX and only the convex relaxations will be checked.
2218  * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP and the subproblem was solved, since the user has
2219  * defined a solve function, it is expected that the solving is correctly executed.
2220  * iv) solveloop == SCIP_BENDERSSOLVELOOP_CIP and the MIP for the subproblem has been solved.
2221  */
2222  if( convexsub || onlyconvexcheck
2223  || solveloop == SCIP_BENDERSSOLVELOOP_CIP
2224  || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
2225  (*optimal) = (*optimal) && subproboptimal;
2226 
2227 #ifdef SCIP_DEBUG
2228  if( convexsub || solveloop >= SCIP_BENDERSSOLVELOOP_CIP )
2229  {
2230  if( subproboptimal )
2231  {
2232  SCIPsetDebugMsg(set, "Subproblem %d is Optimal (%f >= %f)\n", i,
2233  SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
2234  }
2235  else
2236  {
2237  SCIPsetDebugMsg(set, "Subproblem %d is NOT Optimal (%f < %f)\n", i,
2238  SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i), SCIPbendersGetSubproblemObjval(benders, i));
2239  }
2240  }
2241 #endif
2242 
2243  /* the nverified variable is only incremented when the original form of the subproblem has been solved.
2244  * What is meant by "original" is that the LP relaxation of CIPs are solved to generate valid cuts. So
2245  * if the subproblem is defined as a CIP, then it is only classified as checked if the CIP is solved.
2246  * There are three cases where the "original" form is solved are:
2247  * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX or USERCONVEX and the subproblem is an LP
2248  * - the original form has been solved.
2249  * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP or USERCIP and the CIP for the subproblem has been
2250  * solved.
2251  * iii) or, only a convex check is performed.
2252  */
2253  if( ((solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX)
2254  && convexsub)
2255  || ((solveloop == SCIP_BENDERSSOLVELOOP_CIP || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP)
2256  && !convexsub)
2257  || onlyconvexcheck )
2258  (*nverified)++;
2259 
2260  if( !subproboptimal )
2261  {
2262  numnotopt++;
2263  assert(numnotopt <= nsubproblems);
2264  }
2265  }
2266  else
2267  {
2268  numnotopt++;
2269  assert(numnotopt <= nsubproblems);
2270  }
2271  }
2272  }
2273 
2274  subproblemcount++;
2275  i++;
2276  if( i >= nsubproblems )
2277  i = 0;
2278  benders->lastchecked = i;
2279 
2280  /* checking whether the limits have been exceeded in the master problem */
2281  (*stopped) = SCIPisStopped(set->scip);
2282  }
2283  }
2284 
2285  (*nchecked) = subproblemcount;
2286 
2287  return SCIP_OKAY;
2288 }
2289 
2290 /** Calls the Benders' decompsition cuts for the given solve loop. There are four cases:
2291  * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX - only the LP Benders' cuts are called
2292  * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP - only the CIP Benders' cuts are called
2293  * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX - only the LP Benders' cuts are called
2294  * iv) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP - only the CIP Benders' cuts are called
2295  *
2296  * The priority of the results are: SCIP_CONSADDED (SCIP_SEPARATED), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_DIDNOTRUN. In
2297  * this function, there are four levels of results that need to be assessed. These are:
2298  * i) The result from the individual cut for the subproblem
2299  * ii) The overall result for the subproblem from all cuts
2300  * iii) the overall result for the solve loop from all cuts
2301  * iv) the over all result from all solve loops.
2302  * In each level, the priority of results must be adhered to.
2303  */
2304 static
2306  SCIP_BENDERS* benders, /**< Benders' decomposition */
2307  SCIP_SET* set, /**< global SCIP settings */
2308  SCIP_SOL* sol, /**< primal CIP solution */
2309  SCIP_RESULT* result, /**< result of the pricing process */
2310  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
2311  SCIP_BENDERSSOLVELOOP solveloop, /**< the current solve loop */
2312  SCIP_Bool checkint, /**< are the subproblems called during a check/enforce of integer sols? */
2313  int nchecked, /**< the number of subproblems checked in this solve loop, they may not be solved */
2314  SCIP_Bool* subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
2315  SCIP_BENDERSSUBSTATUS* substatus, /**< array to store the status of the subsystem */
2316  int** mergecands, /**< the subproblems that are merge candidates */
2317  int* npriomergecands, /**< the number of priority merge candidates. */
2318  int* nmergecands, /**< the number of merge candidates. */
2319  int* nsolveloops /**< the number of solve loops, is updated w.r.t added cuts */
2320  )
2321 {
2322  SCIP_BENDERSCUT** benderscuts;
2323  SCIP_RESULT solveloopresult;
2324  int nbenderscuts;
2325  int nsubproblems;
2326  int subproblemcount;
2327  SCIP_Longint addedcuts = 0;
2328  int i;
2329  int j;
2330  SCIP_Bool onlyconvexcheck;
2331 
2332  assert(benders != NULL);
2333  assert(set != NULL);
2334 
2335  /* getting the Benders' decomposition cuts */
2336  benderscuts = SCIPbendersGetBenderscuts(benders);
2337  nbenderscuts = SCIPbendersGetNBenderscuts(benders);
2338 
2339  solveloopresult = SCIP_DIDNOTRUN;
2340 
2341  /* getting the number of subproblems in the Benders' decomposition */
2342  nsubproblems = SCIPbendersGetNSubproblems(benders);
2343 
2344  /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
2345  * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
2346  * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
2347  * employed.
2348  */
2349  onlyconvexcheck = SCIPbendersOnlyCheckConvexRelax(benders);
2350 
2351  /* It is only possible to add cuts to the problem if it has not already been solved */
2353  {
2354  /* This is done in two loops. The first is by subproblem and the second is by cut type. */
2355  i = benders->firstchecked;
2356  subproblemcount = 0;
2357  while( subproblemcount < nchecked )
2358  {
2359  SCIP_RESULT subprobresult;
2360  SCIP_Bool convexsub = SCIPbendersSubproblemIsConvex(benders, i);
2361 
2362  /* cuts can only be generated if the subproblem is not independent and if it has been solved. The subproblem
2363  * solved flag is important for the user-defined subproblem solving methods
2364  */
2365  if( subproblemIsActive(benders, i) && subprobsolved[i] )
2366  {
2367  subprobresult = SCIP_DIDNOTRUN;
2368  for( j = 0; j < nbenderscuts; j++ )
2369  {
2370  SCIP_RESULT cutresult;
2371  SCIP_Longint prevaddedcuts;
2372 
2373  assert(benderscuts[j] != NULL);
2374 
2375  prevaddedcuts = SCIPbenderscutGetNFound(benderscuts[j]);
2376  cutresult = SCIP_DIDNOTRUN;
2377 
2378  /* the result is updated only if a Benders' cut is generated or one was not found. However, if a cut has
2379  * been found in a previous iteration, then the result is returned as SCIP_CONSADDED or SCIP_SEPARATED.
2380  * This result is permitted because if a constraint was added, the solution that caused the error in the cut
2381  * generation will be cutoff from the master problem.
2382  */
2383  if( (SCIPbenderscutIsLPCut(benderscuts[j]) && (solveloop == SCIP_BENDERSSOLVELOOP_CONVEX
2384  || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX))
2385  || (!SCIPbenderscutIsLPCut(benderscuts[j]) && ((solveloop == SCIP_BENDERSSOLVELOOP_CIP && !convexsub)
2386  || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP)) )
2387  SCIP_CALL( SCIPbenderscutExec(benderscuts[j], set, benders, sol, i, type, &cutresult) );
2388 
2389  addedcuts += (SCIPbenderscutGetNFound(benderscuts[j]) - prevaddedcuts);
2390 
2391  /* the result is updated only if a Benders' cut is generated */
2392  if( cutresult == SCIP_CONSADDED || cutresult == SCIP_SEPARATED )
2393  {
2394  subprobresult = cutresult;
2395 
2396  benders->ncutsfound++;
2397 
2398  /* at most a single cut is generated for each subproblem */
2399  break;
2400  }
2401  else
2402  {
2403  /* checking from lowest priority result */
2404  if( subprobresult == SCIP_DIDNOTRUN )
2405  subprobresult = cutresult;
2406  else if( subprobresult == SCIP_FEASIBLE && cutresult == SCIP_DIDNOTFIND )
2407  subprobresult = cutresult;
2408  /* if the subprobresult is SCIP_DIDNOTFIND, then it can't be updated. */
2409  }
2410  }
2411 
2412  /* the highest priority for the results is CONSADDED and SEPARATED. The solveloopresult will always be
2413  * updated if the subprobresult is either of these.
2414  */
2415  if( subprobresult == SCIP_CONSADDED || subprobresult == SCIP_SEPARATED )
2416  {
2417  solveloopresult = subprobresult;
2418  }
2419  else if( subprobresult == SCIP_FEASIBLE )
2420  {
2421  /* updating the solve loop result based upon the priority */
2422  if( solveloopresult == SCIP_DIDNOTRUN )
2423  solveloopresult = subprobresult;
2424  }
2425  else if( subprobresult == SCIP_DIDNOTFIND )
2426  {
2427  /* updating the solve loop result based upon the priority */
2428  if( solveloopresult == SCIP_DIDNOTRUN || solveloopresult == SCIP_FEASIBLE )
2429  solveloopresult = subprobresult;
2430 
2431  /* since a cut was not found, then merging could be useful to avoid this in subsequent iterations. The
2432  * candidate is labelled as a non-priority merge candidate
2433  */
2434  if( substatus[i] != SCIP_BENDERSSUBSTATUS_OPTIMAL )
2435  {
2436  (*mergecands)[(*nmergecands)] = i;
2437  (*nmergecands)++;
2438  }
2439  }
2440  else if( subprobresult == SCIP_DIDNOTRUN )
2441  {
2442  /* if the subproblem is infeasible and no cut generation methods were run, then the infeasibility will
2443  * never be resolved. As such, the subproblem will be merged into the master problem. If the subproblem
2444  * was not infeasible, then it is added as a possible merge candidate
2445  */
2446  if( substatus[i] == SCIP_BENDERSSUBSTATUS_INFEAS )
2447  {
2448  (*mergecands)[(*nmergecands)] = (*mergecands)[(*npriomergecands)];
2449  (*mergecands)[(*npriomergecands)] = i;
2450  (*npriomergecands)++;
2451  (*nmergecands)++;
2452  }
2453  else if( substatus[i] != SCIP_BENDERSSUBSTATUS_OPTIMAL )
2454  {
2455  (*mergecands)[(*nmergecands)] = i;
2456  (*nmergecands)++;
2457  }
2458  }
2459  }
2460 
2461  subproblemcount++;
2462  i++;
2463  if( i >= nsubproblems )
2464  i = 0;
2465  }
2466  }
2467 
2468  /* updating the overall result based upon the priorities */
2469  if( solveloopresult == SCIP_CONSADDED || solveloopresult == SCIP_SEPARATED )
2470  {
2471  (*result) = solveloopresult;
2472  }
2473  else if( solveloopresult == SCIP_FEASIBLE )
2474  {
2475  /* updating the solve loop result based upon the priority */
2476  if( (*result) == SCIP_DIDNOTRUN )
2477  (*result) = solveloopresult;
2478  }
2479  else if( solveloopresult == SCIP_DIDNOTFIND )
2480  {
2481  /* updating the solve loop result based upon the priority */
2482  if( (*result) == SCIP_DIDNOTRUN || (*result) == SCIP_FEASIBLE )
2483  (*result) = solveloopresult;
2484  }
2485 
2486  /* if no cuts were added, then the number of solve loops is increased */
2487  if( addedcuts == 0 && SCIPbendersGetNConvexSubproblems(benders) < SCIPbendersGetNSubproblems(benders)
2488  && checkint && !onlyconvexcheck )
2489  (*nsolveloops) = 2;
2490 
2491  return SCIP_OKAY;
2492 }
2493 
2494 /** Solves the subproblem using the current master problem solution.
2495  *
2496  * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
2497  * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
2498  * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
2499  * solution feasibility.
2500  *
2501  * TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip
2502  * instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an
2503  * LP solver for LP subproblems.
2504  */
2506  SCIP_BENDERS* benders, /**< Benders' decomposition */
2507  SCIP_SET* set, /**< global SCIP settings */
2508  SCIP_SOL* sol, /**< primal CIP solution */
2509  SCIP_RESULT* result, /**< result of the pricing process */
2510  SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
2511  SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
2512  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
2513  SCIP_Bool checkint /**< should the integer solution be checked by the subproblems */
2514  )
2515 {
2516  int nsubproblems;
2517  int subproblemcount;
2518  int nchecked;
2519  int nsolveloops;
2520  int nverified;
2521  int* mergecands;
2522  int npriomergecands;
2523  int nmergecands;
2524  SCIP_Bool* subprobsolved;
2525  SCIP_BENDERSSUBSTATUS* substatus;
2526  SCIP_Bool optimal;
2527  SCIP_Bool allverified;
2528  SCIP_Bool success;
2529  SCIP_Bool stopped;
2530  int i;
2531  int l;
2532 
2533  success = TRUE;
2534  stopped = FALSE;
2535 
2536  SCIPsetDebugMsg(set, "Starting Benders' decomposition subproblem solving. type %d checkint %d\n", type, checkint);
2537 
2538  /* start timing */
2539  SCIPclockStart(benders->bendersclock, set);
2540 
2541  nsubproblems = SCIPbendersGetNSubproblems(benders);
2542 
2543  (*auxviol) = FALSE;
2544  (*infeasible) = FALSE;
2545 
2546  /* It is assumed that the problem is optimal, until a subproblem is found not to be optimal. However, not all
2547  * subproblems could be checked in each iteration. As such, it is not possible to state that the problem is optimal
2548  * if not all subproblems are checked. Situations where this may occur is when a subproblem is a MIP and only the LP
2549  * is solved. Also, in a distributed computation, then it may be advantageous to only solve some subproblems before
2550  * resolving the master problem. As such, for a problem to be optimal, then (optimal && allverified) == TRUE
2551  */
2552  optimal = TRUE;
2553  nverified = 0;
2554 
2555  assert(benders != NULL);
2556  assert(result != NULL);
2557  assert(infeasible != NULL);
2558  assert(auxviol != NULL);
2559 
2560  /* if the Benders' decomposition is called from a sub-scip, it is assumed that this is an LNS heuristic. As such, the
2561  * check is not performed and the solution is assumed to be feasible
2562  */
2563  if( benders->iscopy
2564  && (!benders->lnscheck
2565  || (benders->lnsmaxdepth > -1 && SCIPgetDepth(benders->sourcescip) > benders->lnsmaxdepth)) )
2566  {
2567  (*result) = SCIP_DIDNOTRUN;
2568  return SCIP_OKAY;
2569  }
2570 
2571  /* it is not necessary to check all primal solutions by solving the Benders' decomposition subproblems.
2572  * Only the improving solutions are checked to improve efficiency of the algorithm.
2573  * If the solution is non-improving, the result FEASIBLE is returned. While this may be incorrect w.r.t to the
2574  * Benders' subproblems, this solution will never be the optimal solution. A non-improving solution may be used
2575  * within LNS primal heuristics. If this occurs, the improving solution, if found, will be checked by the solving
2576  * the Benders' decomposition subproblems.
2577  * TODO: Add a parameter to control this behaviour.
2578  */
2579  if( checkint && SCIPsetIsFeasLE(set, SCIPgetPrimalbound(set->scip), SCIPgetSolOrigObj(set->scip, sol)) )
2580  {
2581  (*result) = SCIP_DIDNOTRUN;
2582  return SCIP_OKAY;
2583  }
2584 
2585  /* if the enforcement type is SCIP_BENDERSENFOTYPE_LP and the LP is currently unbounded. This could mean that there
2586  * is no lower bound on the auxiliary variables. In this case, we try to update the lower bound for the auxiliary
2587  * variables.
2588  */
2590  && benders->updateauxvarbound )
2591  {
2592  SCIP_CALL( updateAuxiliaryVarLowerbound(benders, set, result) );
2593 
2594  /* the auxiliary variable bound will only be updated once. */
2595  benders->updateauxvarbound = FALSE;
2596  }
2597 
2598  /* setting the first subproblem to check in this round of subproblem checks */
2599  benders->firstchecked = benders->lastchecked;
2600 
2601  /* sets the stored objective function values of the subproblems to infinity */
2603 
2604  *result = SCIP_DIDNOTRUN;
2605 
2606  if( benders->benderspresubsolve != NULL )
2607  {
2608  SCIP_Bool skipsolve;
2609 
2610  skipsolve = FALSE;
2611  SCIP_CALL( benders->benderspresubsolve(set->scip, benders, sol, type, checkint, &skipsolve, result) );
2612 
2613  /* evaluate result */
2614  if( (*result) != SCIP_DIDNOTRUN
2615  && (*result) != SCIP_FEASIBLE
2616  && (*result) != SCIP_INFEASIBLE
2617  && (*result) != SCIP_CONSADDED
2618  && (*result) != SCIP_SEPARATED )
2619  {
2620  SCIPerrorMessage("the user-defined pre subproblem solving method for the Benders' decomposition <%s> returned "
2621  "invalid result <%d>\n", benders->name, *result);
2622  return SCIP_INVALIDRESULT;
2623  }
2624 
2625  /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
2626  if( skipsolve )
2627  {
2628  SCIPsetDebugMsg(set, "skipping the subproblem solving for Benders' decomposition <%s>. "
2629  "returning result <%d>\n", benders->name, *result);
2630  return SCIP_OKAY;
2631  }
2632  }
2633 
2634  /* allocating memory for the infeasible subproblem array */
2635  SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &subprobsolved, nsubproblems) );
2636  SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &substatus, nsubproblems) );
2637  SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &mergecands, nsubproblems) );
2638  npriomergecands = 0;
2639  nmergecands = 0;
2640 
2641  /* by default the number of solve loops is 1. This is the case if all subproblems are LP or the user has defined a
2642  * benderssolvesub callback. If there is a subproblem that is not an LP, then 2 solve loops are performed. The first
2643  * loop is the LP solving loop, the second solves the subproblem to integer optimality.
2644  */
2645  nsolveloops = 1;
2646 
2647  for( l = 0; l < nsolveloops; l++ )
2648  {
2649  SCIP_BENDERSSOLVELOOP solveloop; /* identifies what problem type is solve in this solve loop */
2650 
2651  /* if either benderssolvesubconvex or benderssolvesub are implemented, then the user callbacks are invoked */
2652  if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL )
2653  {
2654  if( l == 0 )
2656  else
2657  solveloop = SCIP_BENDERSSOLVELOOP_USERCIP;
2658  }
2659  else
2660  solveloop = (SCIP_BENDERSSOLVELOOP) l;
2661 
2662  /* solving the subproblems for this round of enforcement/checking. */
2663  SCIP_CALL( solveBendersSubproblems(benders, set, sol, type, solveloop, checkint, &nchecked, &nverified,
2664  &subprobsolved, &substatus, infeasible, &optimal, &stopped) );
2665 
2666  /* if the solving has been stopped, then the subproblem solving and cut generation must terminate */
2667  if( stopped )
2668  goto TERMINATE;
2669 
2670  /* Generating cuts for the subproblems. Cuts are only generated when the solution is from primal heuristics,
2671  * relaxations or the LP
2672  */
2673  if( type != SCIP_BENDERSENFOTYPE_PSEUDO )
2674  {
2675  SCIP_CALL( generateBendersCuts(benders, set, sol, result, type, solveloop, checkint, nchecked,
2676  subprobsolved, substatus, &mergecands, &npriomergecands, &nmergecands, &nsolveloops) );
2677  }
2678  else
2679  {
2680  /* The first solving loop solves the convex subproblems and the convex relaxations of the CIP subproblems. The
2681  * second solving loop solves the CIP subproblems. The second solving loop is only called if the integer
2682  * feasibility is being checked and if the convex subproblems and convex relaxations are not infeasible.
2683  */
2684  if( !(*infeasible) && checkint && !SCIPbendersOnlyCheckConvexRelax(benders)
2686  nsolveloops = 2;
2687  }
2688  }
2689 
2690  allverified = (nverified == nsubproblems);
2691 
2692  SCIPsetDebugMsg(set, "End Benders' decomposition subproblem solve. result %d infeasible %d auxviol %d nverified %d\n",
2693  *result, *infeasible, *auxviol, nverified);
2694 
2695 #ifdef SCIP_DEBUG
2696  if( (*result) == SCIP_CONSADDED )
2697  {
2698  SCIPsetDebugMsg(set, "Benders' decomposition: Cut added\n");
2699  }
2700 #endif
2701 
2702  /* if the number of checked pseudo solutions exceeds a set limit, then all subproblems are passed as merge
2703  * candidates. Currently, merging subproblems into the master problem is the only method for resolving numerical
2704  * troubles.
2705  *
2706  * We are only interested in the pseudo solutions that have been checked completely for integrality. This is
2707  * identified by checkint == TRUE. This means that the Benders' decomposition constraint is one of the last
2708  * constraint handlers that must resolve the infeasibility. If the Benders' decomposition framework can't resolve the
2709  * infeasibility, then this will result in an error.
2710  */
2711  if( type == SCIP_BENDERSENFOTYPE_PSEUDO && checkint )
2712  {
2713  benders->npseudosols++;
2714 
2715  if( benders->npseudosols > BENDERS_MAXPSEUDOSOLS )
2716  {
2717  /* if a priority merge candidate already exists, then no other merge candidates need to be added.*/
2718  if( npriomergecands == 0 )
2719  {
2720  /* all subproblems are added to the merge candidate list. The first active subproblem is added as a
2721  * priority merge candidate
2722  */
2723  nmergecands = 0;
2724  npriomergecands = 1;
2725  for( i = 0; i < nsubproblems; i++ )
2726  {
2727  /* only active subproblems are added to the merge candidate list */
2728  if( subproblemIsActive(benders, i) )
2729  {
2730  mergecands[nmergecands] = i;
2731  nmergecands++;
2732  }
2733  }
2734 
2735  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " The number of checked pseudo solutions exceeds the "
2736  "limit of %d. All active subproblems are merge candidates, with subproblem %d a priority candidate.\n",
2737  BENDERS_MAXPSEUDOSOLS, mergecands[0]);
2738  }
2739  }
2740  }
2741  else
2742  benders->npseudosols = 0;
2743 
2744  /* if the result is SCIP_DIDNOTFIND, then there was a error in generating cuts in all subproblems that are not
2745  * optimal. This result does not cutoff any solution, so the Benders' decomposition algorithm will fail.
2746  * TODO: Work out a way to ensure Benders' decomposition does not terminate due to a SCIP_DIDNOTFIND result.
2747  */
2748  if( (*result) == SCIP_DIDNOTFIND )
2749  {
2750  if( type == SCIP_BENDERSENFOTYPE_PSEUDO )
2751  (*result) = SCIP_SOLVELP;
2752  else
2753  (*result) = SCIP_INFEASIBLE;
2754 
2755  SCIPerrorMessage("An error was found when generating cuts for non-optimal subproblems of Benders' "
2756  "decomposition <%s>. Consider merging the infeasible subproblems into the master problem.\n", SCIPbendersGetName(benders));
2757 
2758  /* since no other cuts are generated, then this error will result in a crash. It is possible to avoid the error,
2759  * by merging the affected subproblem into the master problem.
2760  */
2761  success = FALSE;
2762 
2763  goto POSTSOLVE;
2764  }
2765 
2766  if( type == SCIP_BENDERSENFOTYPE_PSEUDO )
2767  {
2768  if( (*infeasible) || !allverified )
2769  (*result) = SCIP_SOLVELP;
2770  else
2771  {
2772  (*result) = SCIP_FEASIBLE;
2773 
2774  /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
2775  * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
2776  * TRUE.
2777  */
2778  (*auxviol) = !optimal;
2779  }
2780  }
2781  else if( checkint && (type == SCIP_BENDERSENFOTYPE_CHECK || (*result) != SCIP_CONSADDED) )
2782  {
2783  /* if the subproblems are being solved as part of conscheck, then the results flag must be returned after the solving
2784  * has completed.
2785  */
2786  if( (*infeasible) || !allverified )
2787  (*result) = SCIP_INFEASIBLE;
2788  else
2789  {
2790  (*result) = SCIP_FEASIBLE;
2791 
2792  /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
2793  * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
2794  * TRUE.
2795  */
2796  (*auxviol) = !optimal;
2797  }
2798  }
2799 
2800 POSTSOLVE:
2801  /* calling the post-solve call back for the Benders' decomposition algorithm. This allows the user to work directly
2802  * with the solved subproblems and the master problem */
2803  if( benders->benderspostsolve != NULL )
2804  {
2805  SCIP_Bool merged;
2806 
2807  merged = FALSE;
2808 
2809  SCIP_CALL( benders->benderspostsolve(set->scip, benders, sol, type, mergecands, npriomergecands, nmergecands,
2810  checkint, (*infeasible), &merged) );
2811 
2812  if( merged )
2813  {
2814  (*result) = SCIP_CONSADDED;
2815 
2816  /* since subproblems have been merged, then constraints have been added. This could resolve the unresolved
2817  * infeasibility, so the error has been corrected.
2818  */
2819  success = TRUE;
2820  }
2821  else if( !success )
2822  {
2823  SCIPerrorMessage("An error occurred during Benders' decomposition cut generations and no merging had been "
2824  "performed. It is not possible to continue solving the problem by Benders' decomposition\n");
2825  }
2826  }
2827 
2828 TERMINATE:
2829  /* freeing the subproblems after the cuts are generated */
2830  i = benders->firstchecked;
2831  subproblemcount = 0;
2832 
2833  /* if the solving process has stopped, then all subproblems need to be freed */
2834  if( stopped )
2835  nchecked = nsubproblems;
2836 
2837  while( subproblemcount < nchecked )
2838  {
2839  SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, i) );
2840 
2841  subproblemcount++;
2842  i++;
2843  if( i >= nsubproblems )
2844  i = 0;
2845  }
2846 
2847 #ifndef NDEBUG
2848  for( i = 0; i < nsubproblems; i++ )
2850  || !SCIPinProbing(SCIPbendersSubproblem(benders, i)) || !subproblemIsActive(benders, i));
2851 #endif
2852 
2853  /* increment the number of calls to the Benders' decomposition subproblem solve */
2854  benders->ncalls++;
2855 
2856  SCIPsetDebugMsg(set, "End Benders' decomposition execution method. result %d infeasible %d auxviol %d\n", *result,
2857  *infeasible, *auxviol);
2858 
2859  /* end timing */
2860  SCIPclockStop(benders->bendersclock, set);
2861 
2862  /* freeing memory */
2863  SCIPfreeBlockMemoryArray(set->scip, &mergecands, nsubproblems);
2864  SCIPfreeBlockMemoryArray(set->scip, &substatus, nsubproblems);
2865  SCIPfreeBlockMemoryArray(set->scip, &subprobsolved, nsubproblems);
2866 
2867  if( !success )
2868  return SCIP_ERROR;
2869  else
2870  return SCIP_OKAY;
2871 }
2872 
2873 /** solves the user-defined subproblem solving function */
2874 static
2876  SCIP_BENDERS* benders, /**< Benders' decomposition */
2877  SCIP_SET* set, /**< global SCIP settings */
2878  SCIP_SOL* sol, /**< primal CIP solution */
2879  int probnumber, /**< the subproblem number */
2880  SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
2881  SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
2882  SCIP_Real* objective, /**< the objective function value of the subproblem */
2883  SCIP_RESULT* result /**< the result from solving the subproblem */
2884  )
2885 {
2886  assert(benders != NULL);
2887  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
2888  assert(benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL);
2889 
2890  assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
2891 
2892  (*objective) = -SCIPsetInfinity(set);
2893 
2894  /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
2895  * Neighbourhood Benders' Search. */
2896  if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
2897  {
2898  if( benders->benderssolvesubconvex != NULL )
2899  {
2900  SCIP_CALL( benders->benderssolvesubconvex(set->scip, benders, sol, probnumber,
2901  SCIPbendersOnlyCheckConvexRelax(benders), objective, result) );
2902  }
2903  else
2904  (*result) = SCIP_DIDNOTRUN;
2905  }
2906  else if( solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
2907  {
2908  if( benders->benderssolvesub != NULL )
2909  {
2910  SCIP_CALL( benders->benderssolvesub(set->scip, benders, sol, probnumber, objective, result) );
2911  }
2912  else
2913  (*result) = SCIP_DIDNOTRUN;
2914  }
2915 
2916  /* evaluate result */
2917  if( (*result) != SCIP_DIDNOTRUN
2918  && (*result) != SCIP_FEASIBLE
2919  && (*result) != SCIP_INFEASIBLE
2920  && (*result) != SCIP_UNBOUNDED )
2921  {
2922  SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned invalid result <%d>\n",
2923  benders->name, *result);
2924  return SCIP_INVALIDRESULT;
2925  }
2926 
2927  if( (*result) == SCIP_INFEASIBLE )
2928  (*infeasible) = TRUE;
2929 
2930  if( (*result) == SCIP_FEASIBLE
2931  && (SCIPsetIsInfinity(set, -(*objective)) || SCIPsetIsInfinity(set, (*objective))) )
2932  {
2933  SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned objective value %g\n",
2934  benders->name, (*objective));
2935  return SCIP_ERROR;
2936  }
2937 
2938  /* if the result is SCIP_DIDNOTFIND, then an error is returned and SCIP will terminate. */
2939  if( (*result) == SCIP_DIDNOTFIND )
2940  return SCIP_ERROR;
2941  else
2942  return SCIP_OKAY;
2943 }
2944 
2945 /** executes the subproblem solving process */
2947  SCIP_BENDERS* benders, /**< Benders' decomposition */
2948  SCIP_SET* set, /**< global SCIP settings */
2949  SCIP_SOL* sol, /**< primal CIP solution */
2950  int probnumber, /**< the subproblem number */
2951  SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
2952  SCIP_Bool enhancement, /**< is the solve performed as part of and enhancement? */
2953  SCIP_Bool* solved, /**< flag to indicate whether the subproblem was solved */
2954  SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
2955  SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */
2956  )
2957 {
2958  SCIP* subproblem;
2959  SCIP_SOL* bestsol;
2960  SCIP_RESULT result;
2961  SCIP_Real objective;
2962 
2963  assert(benders != NULL);
2964  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
2965 
2966  SCIPsetDebugMsg(set, "Benders' decomposition: solving subproblem %d\n", probnumber);
2967 
2968  result = SCIP_DIDNOTRUN;
2969  objective = SCIPsetInfinity(set);
2970 
2971  subproblem = SCIPbendersSubproblem(benders, probnumber);
2972 
2973  /* initially setting the solved flag to FALSE */
2974  (*solved) = FALSE;
2975 
2976  /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
2977  if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
2978  {
2979  /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
2980  * Neighbourhood Benders' Search. */
2981  SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &objective, &result) );
2982 
2983  /* if the result is DIDNOTRUN, then the subproblem was not solved */
2984  (*solved) = (result != SCIP_DIDNOTRUN);
2985  }
2986  else
2987  {
2988  /* setting up the subproblem */
2989  if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX )
2990  {
2991  SCIP_CALL( SCIPbendersSetupSubproblem(benders, set, sol, probnumber) );
2992 
2993  /* if the limits of the master problem were hit during the setup process, then the subproblem will not have
2994  * been setup. In this case, the solving function must be exited.
2995  */
2996  if( !SCIPbendersSubproblemIsSetup(benders, probnumber) )
2997  {
2998  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
2999  (*solved) = FALSE;
3000  return SCIP_OKAY;
3001  }
3002  }
3003  else
3004  {
3005  SCIP_CALL( updateEventhdlrUpperbound(benders, probnumber, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, probnumber)) );
3006  }
3007 
3008  /* solving the subproblem
3009  * the LP of the subproblem is solved in the first solveloop.
3010  * In the second solve loop, the MIP problem is solved */
3011  if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || SCIPbendersSubproblemIsConvex(benders, probnumber) )
3012  {
3013  SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, infeasible) );
3014 
3015  /* if the LP was solved without error, then the subproblem is labelled as solved */
3016  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL
3017  || SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_INFEASIBLE )
3018  (*solved) = TRUE;
3019  }
3020  else
3021  {
3022  SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, infeasible, type, FALSE) );
3023 
3024  /* if the generic subproblem solving methods are used, then the CIP subproblems are always solved. */
3025  (*solved) = TRUE;
3026  }
3027  }
3028 
3029  bestsol = SCIPgetBestSol(subproblem);
3030 
3031  if( !enhancement )
3032  {
3033  /* The following handles the cases when the subproblem is OPTIMAL, INFEASIBLE and UNBOUNDED.
3034  * If a subproblem is unbounded, then the auxiliary variables are set to -infinity and the unbounded flag is
3035  * returned as TRUE. No cut will be generated, but the result will be set to SCIP_FEASIBLE.
3036  */
3037  if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX )
3038  {
3039  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_OPTIMAL )
3040  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPgetSolOrigObj(subproblem, NULL));
3041  else if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_INFEASIBLE )
3042  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
3043  else if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_UNBOUNDEDRAY )
3044  {
3045  SCIPerrorMessage("The LP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
3046  probnumber);
3047  SCIPABORT();
3048  }
3049  else if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_ERROR
3050  || SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_NOTSOLVED
3051  || SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_TIMELIMIT )
3052  {
3053  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, " Benders' decomposition: Error solving LP "
3054  "relaxation of subproblem %d. No cut will be generated for this subproblem.\n", probnumber);
3055  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
3056  }
3057  else
3058  {
3059  SCIPerrorMessage("Invalid status returned from solving the LP of Benders' decomposition subproblem %d. LP status: %d\n",
3060  probnumber, SCIPgetLPSolstat(subproblem));
3061  SCIPABORT();
3062  }
3063  }
3064  else if( solveloop == SCIP_BENDERSSOLVELOOP_CIP )
3065  {
3066  /* TODO: Consider whether other solutions status should be handled */
3067  if( SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL )
3068  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPgetSolOrigObj(subproblem, bestsol));
3069  else if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
3070  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
3071  else if( SCIPgetStatus(subproblem) == SCIP_STATUS_USERINTERRUPT || SCIPgetStatus(subproblem) == SCIP_STATUS_BESTSOLLIMIT )
3072  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPgetSolOrigObj(subproblem, bestsol));
3073  else if( SCIPgetStatus(subproblem) == SCIP_STATUS_MEMLIMIT
3074  || SCIPgetStatus(subproblem) == SCIP_STATUS_TIMELIMIT )
3075  {
3076  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, " Benders' decomposition: Error solving CIP "
3077  "of subproblem %d. No cut will be generated for this subproblem.\n", probnumber);
3078  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
3079  }
3080  else if( SCIPgetStatus(subproblem) == SCIP_STATUS_UNBOUNDED )
3081  {
3082  SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
3083  probnumber);
3084  SCIPABORT();
3085  }
3086  else
3087  {
3088  SCIPerrorMessage("Invalid status returned from solving Benders' decomposition subproblem %d. Solution status: %d\n",
3089  probnumber, SCIPgetStatus(subproblem));
3090  SCIPABORT();
3091  }
3092  }
3093  else
3094  {
3095  assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
3096  if( result == SCIP_FEASIBLE )
3097  SCIPbendersSetSubproblemObjval(benders, probnumber, objective);
3098  else if( result == SCIP_INFEASIBLE )
3099  SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
3100  else if( result == SCIP_UNBOUNDED )
3101  {
3102  SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
3103  probnumber);
3104  SCIPABORT();
3105  }
3106  else if( result != SCIP_DIDNOTRUN )
3107  {
3108  SCIPerrorMessage("Invalid result <%d> from user-defined subproblem solving method. This should not happen.\n",
3109  result);
3110  }
3111  }
3112  }
3113 
3114  return SCIP_OKAY;
3115 }
3116 
3117 /** sets up the subproblem using the solution to the master problem */
3119  SCIP_BENDERS* benders, /**< Benders' decomposition */
3120  SCIP_SET* set, /**< global SCIP settings */
3121  SCIP_SOL* sol, /**< primal CIP solution */
3122  int probnumber /**< the subproblem number */
3123  )
3124 {
3125  SCIP* subproblem;
3126  SCIP_VAR** vars;
3127  SCIP_VAR* mastervar;
3128  SCIP_Real solval;
3129  int nvars;
3130  int i;
3131 
3132  assert(benders != NULL);
3133  assert(set != NULL);
3134  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
3135 
3136  /* changing all of the master problem variable to continuous. */
3137  SCIP_CALL( SCIPbendersChgMastervarsToCont(benders, set, probnumber) );
3138 
3139  subproblem = SCIPbendersSubproblem(benders, probnumber);
3140 
3141  /* if the Benders' decomposition subproblem is an LP, then probing mode must be started.
3142  * If the subproblem is a MIP, the problem must be initialised, put into SCIP_STAGE_SOLVING to be able to change the
3143  * variable bounds. The probing mode is entered once the variable bounds are set.
3144  * In the MIP case, the transformed problem is freed after each subproblem solve round. */
3145  if( SCIPbendersSubproblemIsConvex(benders, probnumber) )
3146  {
3147  SCIP_CALL( SCIPstartProbing(subproblem) );
3148  }
3149  else
3150  {
3151  SCIP_Bool success;
3152 
3153  SCIP_CALL( initialiseSubproblem(benders, set, probnumber, &success) );
3154 
3155  if( !success )
3156  {
3157  /* set the flag to indicate that the subproblems have been set up */
3158  SCIPbendersSetSubproblemIsSetup(benders, probnumber, FALSE);
3159 
3160  return SCIP_OKAY;
3161  }
3162  }
3163 
3164  vars = SCIPgetVars(subproblem);
3165  nvars = SCIPgetNVars(subproblem);
3166 
3167  /* looping over all variables in the subproblem to find those corresponding to the master problem variables. */
3168  /* TODO: It should be possible to store the pointers to the master variables to speed up the subproblem setup */
3169  for( i = 0; i < nvars; i++ )
3170  {
3171  SCIP_CALL( SCIPbendersGetVar(benders, set, vars[i], &mastervar, -1) );
3172 
3173  if( mastervar != NULL )
3174  {
3175  /* It is possible due to numerics that the solution value exceeds the upper or lower bounds. When this
3176  * happens, it causes an error in the LP solver as a result of inconsistent bounds. So the following statements
3177  * are used to ensure that the bounds are not exceeded when applying the fixings for the Benders'
3178  * decomposition subproblems
3179  */
3180  solval = SCIPgetSolVal(set->scip, sol, mastervar);
3181  if( solval > SCIPvarGetUbLocal(vars[i]) )
3182  solval = SCIPvarGetUbLocal(vars[i]);
3183  else if( solval < SCIPvarGetLbLocal(vars[i]) )
3184  solval = SCIPvarGetLbLocal(vars[i]);
3185 
3186  /* fixing the variable in the subproblem */
3187  if( !SCIPisEQ(subproblem, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
3188  {
3189  if( SCIPisGT(subproblem, solval, SCIPvarGetLbLocal(vars[i])) )
3190  {
3191  SCIP_CALL( SCIPchgVarLb(subproblem, vars[i], solval) );
3192  }
3193  if( SCIPisLT(subproblem, solval, SCIPvarGetUbLocal(vars[i])) )
3194  {
3195  SCIP_CALL( SCIPchgVarUb(subproblem, vars[i], solval) );
3196  }
3197  }
3198 
3199  assert(SCIPisEQ(subproblem, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])));
3200  }
3201  }
3202 
3203  /* if the subproblem is a MIP, the probing mode is entered after setting up the subproblem */
3204  if( !SCIPbendersSubproblemIsConvex(benders, probnumber) )
3205  {
3206  SCIP_CALL( SCIPstartProbing(subproblem) );
3207  }
3208 
3209  /* set the flag to indicate that the subproblems have been set up */
3210  SCIPbendersSetSubproblemIsSetup(benders, probnumber, TRUE);
3211 
3212  return SCIP_OKAY;
3213 }
3214 
3215 /** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving
3216  * methods. If the generic method is called, then the subproblem must be set up before calling this method. */
3218  SCIP_BENDERS* benders, /**< Benders' decomposition */
3219  SCIP_SET* set, /**< global SCIP settings */
3220  SCIP_SOL* sol, /**< primal CIP solution, can be NULL */
3221  int probnumber, /**< the subproblem number */
3222  SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
3223  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
3224  SCIP_Bool solvecip, /**< directly solve the CIP subproblem */
3225  SCIP_Real* objective /**< the objective function value of the subproblem, can be NULL */
3226  )
3227 {
3228  assert(benders != NULL);
3229  assert(set != NULL);
3230  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
3231 
3232  /* the subproblem must be set up before this function is called. */
3233  if( !SCIPbendersSubproblemIsSetup(benders, probnumber) && !SCIPbendersSubproblemIsIndependent(benders, probnumber) )
3234  {
3235  SCIPerrorMessage("Benders' decomposition subproblem %d must be set up before calling SCIPbendersSolveSubproblem(). Call SCIPsetupSubproblem() first.\n", probnumber);
3236  return SCIP_ERROR;
3237  }
3238 
3239  /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
3240  if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL)
3241  {
3242  SCIP_BENDERSSOLVELOOP solveloop;
3243  SCIP_RESULT result;
3244  SCIP_Real subobj;
3245 
3246  if( solvecip )
3247  solveloop = SCIP_BENDERSSOLVELOOP_USERCIP;
3248  else
3250 
3251  SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &subobj, &result) );
3252 
3253  if( objective != NULL )
3254  (*objective) = subobj;
3255  }
3256  else
3257  {
3258  SCIP* subproblem;
3259 
3260  subproblem = SCIPbendersSubproblem(benders, probnumber);
3261 
3262  /* solving the subproblem */
3263  if( solvecip && !SCIPbendersSubproblemIsConvex(benders, probnumber) )
3264  {
3265  SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, infeasible, type, solvecip) );
3266 
3267  if( objective != NULL )
3268  (*objective) = SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem));
3269  }
3270  else
3271  {
3272  SCIP_Bool success;
3273 
3274  /* if the subproblem is an LP, then it should have been initialised and in SCIP_STAGE_SOLVING.
3275  * in this case, the subproblem only needs to be put into probing mode. */
3276  if( SCIPbendersSubproblemIsConvex(benders, probnumber) )
3277  {
3278  /* if the subproblem is not in probing mode, then it must be put into that mode for the LP solve. */
3279  if( !SCIPinProbing(subproblem) )
3280  {
3281  SCIP_CALL( SCIPstartProbing(subproblem) );
3282  }
3283 
3284  success = TRUE;
3285  }
3286  else
3287  {
3288  SCIP_CALL( initialiseSubproblem(benders, set, probnumber, &success) );
3289  }
3290 
3291  /* if setting up the subproblem was successful */
3292  if( success )
3293  {
3294  SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, infeasible) );
3295 
3296  if( objective != NULL )
3297  (*objective) = SCIPgetSolOrigObj(subproblem, NULL);
3298  }
3299  else
3300  {
3301  if( objective != NULL )
3302  (*objective) = SCIPinfinity(subproblem);
3303  }
3304  }
3305  }
3306 
3307  return SCIP_OKAY;
3308 }
3309 
3310 /** copies the time and memory limit from the master problem to the subproblem */
3311 static
3313  SCIP* scip, /**< the SCIP data structure */
3314  SCIP* subproblem /**< the Benders' decomposition subproblem */
3315  )
3316 {
3317  SCIP_Real mastertimelimit;
3318  SCIP_Real subtimelimit;
3319  SCIP_Real maxsubtimelimit;
3320  SCIP_Real mastermemorylimit;
3321  SCIP_Real submemorylimit;
3322  SCIP_Real maxsubmemorylimit;
3323 
3324  assert(scip != NULL);
3325 
3326  /* setting the time limit for the Benders' decomposition subproblems. It is set to 102% of the remaining time. */
3327  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &mastertimelimit) );
3328  maxsubtimelimit = SCIPparamGetRealMax(SCIPgetParam(subproblem, "limits/time"));
3329  subtimelimit = (mastertimelimit - SCIPgetSolvingTime(scip)) * 1.02;
3330  subtimelimit = MIN(subtimelimit, maxsubtimelimit);
3331  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/time", MAX(0.0, subtimelimit)) );
3332 
3333  /* setting the memory limit for the Benders' decomposition subproblems. */
3334  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &mastermemorylimit) );
3335  maxsubmemorylimit = SCIPparamGetRealMax(SCIPgetParam(subproblem, "limits/memory"));
3336  submemorylimit = mastermemorylimit - (SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0;
3337  submemorylimit = MIN(submemorylimit, maxsubmemorylimit);
3338  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/memory", MAX(0.0, submemorylimit)) );
3339 
3340  return SCIP_OKAY;
3341 }
3342 
3343 /** stores the original parameters from the subproblem */
3344 static
3346  SCIP* subproblem, /**< the SCIP data structure */
3347  SCIP_SUBPROBPARAMS* origparams /**< the original subproblem parameters */
3348  )
3349 {
3350  assert(subproblem != NULL);
3351  assert(origparams != NULL);
3352 
3353  SCIP_CALL( SCIPgetRealParam(subproblem, "limits/memory", &origparams->limits_memory) );
3354  SCIP_CALL( SCIPgetRealParam(subproblem, "limits/time", &origparams->limits_time) );
3355  SCIP_CALL( SCIPgetBoolParam(subproblem, "conflict/enable", &origparams->conflict_enable) );
3356  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/disablecutoff", &origparams->lp_disablecutoff) );
3357  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/scaling", &origparams->lp_scaling) );
3358  SCIP_CALL( SCIPgetCharParam(subproblem, "lp/initalgorithm", &origparams->lp_initalg) );
3359  SCIP_CALL( SCIPgetCharParam(subproblem, "lp/resolvealgorithm", &origparams->lp_resolvealg) );
3360  SCIP_CALL( SCIPgetBoolParam(subproblem, "lp/alwaysgetduals", &origparams->lp_alwaysgetduals) );
3361  SCIP_CALL( SCIPgetBoolParam(subproblem, "misc/scaleobj", &origparams->misc_scaleobj) );
3362  SCIP_CALL( SCIPgetBoolParam(subproblem, "misc/catchctrlc", &origparams->misc_catchctrlc) );
3363  SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxrounds", &origparams->prop_maxrounds) );
3364  SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxroundsroot", &origparams->prop_maxroundsroot) );
3365  SCIP_CALL( SCIPgetIntParam(subproblem, "constraints/linear/propfreq", &origparams->cons_linear_propfreq) );
3366 
3367  return SCIP_OKAY;
3368 }
3369 
3370 /** sets the parameters for the subproblem */
3371 static
3373  SCIP* scip, /**< the SCIP data structure */
3374  SCIP* subproblem /**< the subproblem SCIP instance */
3375  )
3376 {
3377  assert(scip != NULL);
3378  assert(subproblem != NULL);
3379 
3380  /* copying memory and time limits */
3381  SCIP_CALL( copyMemoryAndTimeLimits(scip, subproblem) );
3382 
3383  /* Do we have to disable presolving? If yes, we have to store all presolving parameters. */
3385 
3386  /* Disabling heuristics so that the problem is not trivially solved */
3388 
3389  /* store parameters that are changed for the generation of the subproblem cuts */
3390  SCIP_CALL( SCIPsetParam(subproblem, "conflict/enable", FALSE) );
3391 
3392  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", 1) );
3393  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/scaling", 0) );
3394 
3395  SCIP_CALL( SCIPsetCharParam(subproblem, "lp/initalgorithm", 'd') );
3396  SCIP_CALL( SCIPsetCharParam(subproblem, "lp/resolvealgorithm", 'd') );
3397 
3398  SCIP_CALL( SCIPsetBoolParam(subproblem, "lp/alwaysgetduals", TRUE) );
3399  SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/scaleobj", FALSE) );
3400 
3401  /* do not abort subproblem on CTRL-C */
3402  SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/catchctrlc", FALSE) );
3403 
3404  SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3405 
3406  SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxrounds", 0) );
3407  SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", 0) );
3408 
3409  SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", -1) );
3410 
3411  return SCIP_OKAY;
3412 }
3413 
3414 /** resets the original parameters from the subproblem */
3415 static
3417  SCIP* subproblem, /**< the SCIP data structure */
3418  SCIP_SUBPROBPARAMS* origparams /**< the original subproblem parameters */
3419  )
3420 {
3421  assert(subproblem != NULL);
3422  assert(origparams != NULL);
3423 
3424  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/memory", origparams->limits_memory) );
3425  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/time", origparams->limits_time) );
3426  SCIP_CALL( SCIPsetBoolParam(subproblem, "conflict/enable", origparams->conflict_enable) );
3427  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", origparams->lp_disablecutoff) );
3428  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/scaling", origparams->lp_scaling) );
3429  SCIP_CALL( SCIPsetCharParam(subproblem, "lp/initalgorithm", origparams->lp_initalg) );
3430  SCIP_CALL( SCIPsetCharParam(subproblem, "lp/resolvealgorithm", origparams->lp_resolvealg) );
3431  SCIP_CALL( SCIPsetBoolParam(subproblem, "lp/alwaysgetduals", origparams->lp_alwaysgetduals) );
3432  SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/scaleobj", origparams->misc_scaleobj) );
3433  SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/catchctrlc", origparams->misc_catchctrlc) );
3434  SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxrounds", origparams->prop_maxrounds) );
3435  SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", origparams->prop_maxroundsroot) );
3436  SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", origparams->cons_linear_propfreq) );
3437 
3438  return SCIP_OKAY;
3439 }
3440 
3441 /** solves the LP of the Benders' decomposition subproblem
3442  *
3443  * This requires that the subproblem is in probing mode.
3444  */
3446  SCIP* scip, /**< the SCIP data structure */
3447  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
3448  int probnumber, /**< the subproblem number */
3449  SCIP_Bool* infeasible /**< a flag to indicate whether all subproblems are feasible */
3450  )
3451 {
3452  SCIP* subproblem;
3453  SCIP_SUBPROBPARAMS* origparams;
3454  SCIP_Bool lperror;
3455  SCIP_Bool cutoff;
3456 
3457  assert(benders != NULL);
3458  assert(infeasible != NULL);
3459  assert(SCIPbendersSubproblemIsSetup(benders, probnumber));
3460 
3461  (*infeasible) = FALSE;
3462 
3463  /* TODO: This should be solved just as an LP, so as a MIP. There is too much overhead with the MIP.
3464  * Need to change status check for checking the LP. */
3465  subproblem = SCIPbendersSubproblem(benders, probnumber);
3466 
3467  assert(SCIPisLPConstructed(subproblem));
3468  assert(SCIPinProbing(subproblem));
3469 
3470  /* allocating memory for the parameter storage */
3471  SCIP_CALL( SCIPallocBlockMemory(subproblem, &origparams) );
3472 
3473  /* store the original parameters of the subproblem */
3474  SCIP_CALL( storeOrigSubproblemParams(subproblem, origparams) );
3475 
3476  /* setting the subproblem parameters */
3477  SCIP_CALL( setSubproblemParams(scip, subproblem) );
3478 
3479  SCIP_CALL( SCIPsolveProbingLP(subproblem, -1, &lperror, &cutoff) );
3480 
3481  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_INFEASIBLE )
3482  (*infeasible) = TRUE;
3483  else if( SCIPgetLPSolstat(subproblem) != SCIP_LPSOLSTAT_OPTIMAL
3485  && SCIPgetLPSolstat(subproblem) != SCIP_LPSOLSTAT_NOTSOLVED
3486  && SCIPgetLPSolstat(subproblem) != SCIP_LPSOLSTAT_ERROR
3487  && SCIPgetLPSolstat(subproblem) != SCIP_LPSOLSTAT_TIMELIMIT )
3488  {
3489  SCIPerrorMessage("Invalid status: %d. Solving the LP relaxation of Benders' decomposition subproblem %d.\n",
3490  SCIPgetLPSolstat(subproblem), probnumber);
3491  SCIPABORT();
3492  }
3493 
3494  /* resetting the subproblem parameters */
3495  SCIP_CALL( resetOrigSubproblemParams(subproblem, origparams) );
3496 
3497  /* freeing the parameter storage */
3498  SCIPfreeBlockMemory(subproblem, &origparams);
3499 
3500  return SCIP_OKAY;
3501 }
3502 
3503 /** solves the Benders' decomposition subproblem */
3505  SCIP* scip, /**< the SCIP data structure */
3506  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
3507  int probnumber, /**< the subproblem number */
3508  SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
3509  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
3510  SCIP_Bool solvecip /**< directly solve the CIP subproblem */
3511  )
3512 {
3513  SCIP* subproblem;
3514  SCIP_SUBPROBPARAMS* origparams;
3515 
3516  assert(benders != NULL);
3517  assert(infeasible != NULL);
3518 
3519  (*infeasible) = FALSE;
3520 
3521  subproblem = SCIPbendersSubproblem(benders, probnumber);
3522 
3523  /* allocating memory for the parameter storage */
3524  SCIP_CALL( SCIPallocBlockMemory(subproblem, &origparams) );
3525 
3526  /* store the original parameters of the subproblem */
3527  SCIP_CALL( storeOrigSubproblemParams(subproblem, origparams) );
3528 
3529  /* If the solve has been stopped for the subproblem, then we need to restart it to complete the solve. The subproblem
3530  * is stopped when it is a MIP so that LP cuts and IP cuts can be generated. */
3531  if( SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING )
3532  {
3533  /* the subproblem should be in probing mode. Otherwise, the event handler did not work correctly */
3534  assert( SCIPinProbing(subproblem) );
3535 
3536  /* the probing mode needs to be stopped so that the MIP can be solved */
3537  SCIP_CALL( SCIPendProbing(subproblem) );
3538 
3539  /* the problem was interrupted in the event handler, so SCIP needs to be informed that the problem is to be restarted */
3540  SCIP_CALL( SCIPrestartSolve(subproblem) );
3541 
3542  /* if the solve type is for CHECK, then the FEASIBILITY emphasis setting is used. */
3543  if( type == SCIP_BENDERSENFOTYPE_CHECK )
3544  {
3546 
3547  /* the number of solution improvements is limited to try and prove feasibility quickly */
3548  /* NOTE: This should be a parameter */
3549  /* SCIP_CALL( SCIPsetIntParam(subproblem, "limits/bestsol", 5) ); */
3550  }
3551  }
3552  else if( solvecip )
3553  {
3554  /* if the MIP will be solved directly, then the probing mode needs to be skipped.
3555  * This is achieved by setting the solvecip flag in the event handler data to TRUE
3556  */
3557  SCIP_EVENTHDLR* eventhdlr;
3558  SCIP_EVENTHDLRDATA* eventhdlrdata;
3559 
3560  eventhdlr = SCIPfindEventhdlr(subproblem, MIPNODEFOCUS_EVENTHDLR_NAME);
3561  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
3562 
3563  eventhdlrdata->solvecip = TRUE;
3564  }
3565  else
3566  {
3567  /* if the problem is not in probing mode, then we need to solve the LP. That requires all methods that will
3568  * modify the structure of the problem need to be deactivated */
3569 
3570  /* setting the subproblem parameters */
3571  SCIP_CALL( setSubproblemParams(scip, subproblem) );
3572 
3573 #ifdef SCIP_MOREDEBUG
3574  SCIP_CALL( SCIPsetBoolParam(subproblem, "display/lpinfo", TRUE) );
3575 #endif
3576  }
3577 
3578 #ifdef SCIP_MOREDEBUG
3579  SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", (int)SCIP_VERBLEVEL_FULL) );
3580 #endif
3581 
3582  SCIP_CALL( SCIPsolve(subproblem) );
3583 
3584  if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
3585  (*infeasible) = TRUE;
3586  else if( SCIPgetStatus(subproblem) != SCIP_STATUS_OPTIMAL && SCIPgetStatus(subproblem) != SCIP_STATUS_UNBOUNDED
3588  && SCIPgetStatus(subproblem) != SCIP_STATUS_TIMELIMIT && SCIPgetStatus(subproblem) != SCIP_STATUS_MEMLIMIT )
3589  {
3590  SCIPerrorMessage("Invalid status: %d. Solving the CIP of Benders' decomposition subproblem %d.\n",
3591  SCIPgetStatus(subproblem), probnumber);
3592  SCIPABORT();
3593  }
3594 
3595  /* resetting the subproblem parameters */
3596  SCIP_CALL( resetOrigSubproblemParams(subproblem, origparams) );
3597 
3598  /* freeing the parameter storage */
3599  SCIPfreeBlockMemory(subproblem, &origparams);
3600 
3601  return SCIP_OKAY;
3602 }
3603 
3604 /** frees the subproblems */
3606  SCIP_BENDERS* benders, /**< Benders' decomposition */
3607  SCIP_SET* set, /**< global SCIP settings */
3608  int probnumber /**< the subproblem number */
3609  )
3610 {
3611  assert(benders != NULL);
3612  assert(benders->bendersfreesub != NULL
3613  || (benders->bendersfreesub == NULL && benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL));
3614  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
3615 
3616  if( benders->bendersfreesub != NULL )
3617  {
3618  SCIP_CALL( benders->bendersfreesub(set->scip, benders, probnumber) );
3619  }
3620  else
3621  {
3622  /* the subproblem is only freed if it is not independent */
3623  if( subproblemIsActive(benders, probnumber) )
3624  {
3625  SCIP* subproblem = SCIPbendersSubproblem(benders, probnumber);
3626 
3627  if( SCIPbendersSubproblemIsConvex(benders, probnumber) )
3628  {
3629  /* ending probing mode to reset the current node. The probing mode will be restarted at the next solve */
3630  if( SCIPinProbing(subproblem) )
3631  {
3632  SCIP_CALL( SCIPendProbing(subproblem) );
3633  }
3634  }
3635  else
3636  {
3637  /* if the subproblems were solved as part of an enforcement stage, then they will still be in probing mode. The
3638  * probing mode must first be finished and then the problem can be freed */
3639  if( SCIPgetStage(subproblem) >= SCIP_STAGE_TRANSFORMED && SCIPinProbing(subproblem) )
3640  {
3641  SCIP_CALL( SCIPendProbing(subproblem) );
3642  }
3643 
3644  SCIP_CALL( SCIPfreeTransform(subproblem) );
3645  }
3646  }
3647  }
3648 
3649  /* setting the setup flag for the subproblem to FALSE */
3650  SCIPbendersSetSubproblemIsSetup(benders, probnumber, FALSE);
3651  return SCIP_OKAY;
3652 }
3653 
3654 /** compares the subproblem objective value with the auxiliary variable value for optimality */
3656  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
3657  SCIP_SET* set, /**< global SCIP settings */
3658  SCIP_SOL* sol, /**< primal CIP solution */
3659  int probnumber, /**< the subproblem number */
3660  SCIP_Bool* optimal /**< flag to indicate whether the current subproblem is optimal for the master */
3661  )
3662 {
3663  SCIP_Real auxiliaryvarval;
3664  SCIP_Real soltol;
3665 
3666  assert(benders != NULL);
3667  assert(set != NULL);
3668  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
3669 
3670  (*optimal) = FALSE;
3671 
3672  auxiliaryvarval = SCIPbendersGetAuxiliaryVarVal(benders, set, sol, probnumber);
3673 
3674  SCIP_CALL( SCIPsetGetRealParam(set, "benders/solutiontol", &soltol) );
3675 
3676  SCIPsetDebugMsg(set, "Subproblem %d - Auxiliary Variable: %g Subproblem Objective: %g Reldiff: %g Soltol: %g\n",
3677  probnumber, auxiliaryvarval, SCIPbendersGetSubproblemObjval(benders, probnumber),
3678  SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval), soltol);
3679 
3680  if( SCIPrelDiff(SCIPbendersGetSubproblemObjval(benders, probnumber), auxiliaryvarval) < soltol )
3681  (*optimal) = TRUE;
3682 
3683  return SCIP_OKAY;
3684 }
3685 
3686 /** returns the value of the auxiliary variable value in a master problem solution */
3688  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
3689  SCIP_SET* set, /**< global SCIP settings */
3690  SCIP_SOL* sol, /**< primal CIP solution */
3691  int probnumber /**< the subproblem number */
3692  )
3693 {
3694  SCIP_VAR* auxiliaryvar;
3695 
3696  assert(benders != NULL);
3697  assert(set != NULL);
3698 
3699  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
3700  assert(auxiliaryvar != NULL);
3701 
3702  return SCIPgetSolVal(set->scip, sol, auxiliaryvar);
3703 }
3704 
3705 /** Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on
3706  * the auxiliary variable.
3707  */
3709  SCIP_BENDERS* benders, /**< Benders' decomposition */
3710  SCIP_SET* set, /**< global SCIP settings */
3711  int probnumber, /**< the subproblem to be evaluated */
3712  SCIP_Real* lowerbound, /**< the lowerbound for the subproblem */
3713  SCIP_Bool* infeasible /**< was the subproblem found to be infeasible? */
3714  )
3715 {
3716  SCIP* subproblem;
3717  SCIP_Real memorylimit;
3718  SCIP_Real timelimit;
3719  SCIP_Longint totalnodes;
3720  int disablecutoff;
3721  int verblevel;
3722  SCIP_Bool lperror;
3723  SCIP_Bool cutoff;
3724 
3725  assert(benders != NULL);
3726  assert(set != NULL);
3727 
3728  /* getting the subproblem to evaluate */
3729  subproblem = SCIPbendersSubproblem(benders, probnumber);
3730 
3731  (*lowerbound) = -SCIPinfinity(subproblem);
3732  (*infeasible) = FALSE;
3733 
3734  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Computing a lower bound for"
3735  " subproblem %d\n", probnumber);
3736 
3737  SCIP_CALL( SCIPgetIntParam(subproblem, "display/verblevel", &verblevel) );
3738  SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3739 #ifdef SCIP_MOREDEBUG
3740  SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", (int)SCIP_VERBLEVEL_HIGH) );
3741 #endif
3742 
3743  /* copying memory and time limits */
3744  SCIP_CALL( SCIPgetRealParam(subproblem, "limits/time", &timelimit) );
3745  SCIP_CALL( SCIPgetRealParam(subproblem, "limits/memory", &memorylimit) );
3746  SCIP_CALL( copyMemoryAndTimeLimits(set->scip, subproblem) );
3747 
3748  /* if the subproblem is independent, then the default SCIP settings are used. Otherwise, only the root node is solved
3749  * to compute a lower bound on the subproblem
3750  */
3751  SCIP_CALL( SCIPgetLongintParam(subproblem, "limits/totalnodes", &totalnodes) );
3752  SCIP_CALL( SCIPgetIntParam(subproblem, "lp/disablecutoff", &disablecutoff) );
3753  if( !SCIPbendersSubproblemIsIndependent(benders, probnumber) )
3754  {
3755  SCIP_CALL( SCIPsetLongintParam(subproblem, "limits/totalnodes", 1LL) );
3756  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", 1) );
3757  }
3758 
3759  /* if the subproblem not independent and is convex, then the probing LP is solved. Otherwise, the MIP is solved */
3760  if( SCIPbendersSubproblemIsConvex(benders, probnumber) )
3761  {
3762  assert(SCIPisLPConstructed(subproblem));
3763 
3764  SCIP_CALL( SCIPstartProbing(subproblem) );
3765  SCIP_CALL( SCIPsolveProbingLP(subproblem, -1, &lperror, &cutoff) );
3766 
3767  if( SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_INFEASIBLE )
3768  (*infeasible) = TRUE;
3769  }
3770  else
3771  {
3772  SCIP_EVENTHDLRDATA* eventhdlrdata;
3773 
3774  /* if the subproblem is not convex, then event handlers have been added to interrupt the solve. These must be
3775  * disabled
3776  */
3778  eventhdlrdata->solvecip = TRUE;
3779 
3780  SCIP_CALL( SCIPsolve(subproblem) );
3781 
3782  if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE )
3783  (*infeasible) = TRUE;
3784  }
3785 
3786  /* getting the lower bound value */
3787  if( !(*infeasible) )
3788  (*lowerbound) = SCIPgetDualbound(subproblem);
3789  else
3790  (*lowerbound) = -SCIPinfinity(subproblem);
3791 
3792  if( !SCIPbendersSubproblemIsIndependent(benders, probnumber) )
3793  {
3794  SCIP_CALL( SCIPsetLongintParam(subproblem, "limits/totalnodes", totalnodes) );
3795  SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", disablecutoff) );
3796  }
3797  SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", verblevel) );
3798  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/memory", memorylimit) );
3799  SCIP_CALL( SCIPsetRealParam(subproblem, "limits/time", timelimit) );
3800 
3801  /* the subproblem must be freed so that it is reset for the subsequent Benders' decomposition solves. If the
3802  * subproblems are independent, they are not freed. SCIPfreeBendersSubproblem must still be called, but in this
3803  * function the independent subproblems are not freed. However, they will still be freed at the end of the
3804  * solving process for the master problem.
3805  */
3806  SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, probnumber) );
3807 
3808  return SCIP_OKAY;
3809 }
3810 
3811 /** Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and
3812  * constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. The reason for
3813  * keeping the subproblem available is for when it is queried for solutions after the problem is solved.
3814  *
3815  * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that
3816  * it will not be solved in the subsequent subproblem solving loops.
3817  *
3818  * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem
3819  * is added as an underestimator constraint.
3820  */
3822  SCIP_BENDERS* benders, /**< Benders' decomposition */
3823  SCIP_SET* set, /**< global SCIP settings */
3824  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding
3825  * to the newly created master variables, or NULL */
3826  SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of subproblem constraints to the
3827  corresponding newly created constraints, or NULL */
3828  int probnumber /**< the number of the subproblem that will be merged into the master problem*/
3829  )
3830 {
3831  SCIP* subproblem;
3832  SCIP_HASHMAP* localvarmap;
3833  SCIP_HASHMAP* localconsmap;
3834  SCIP_VAR** vars;
3835  SCIP_VAR* auxiliaryvar;
3836  SCIP_CONS** conss;
3837  SCIP_CONS* objcons;
3838  int nvars;
3839  int nconss;
3840  int i;
3841  SCIP_Bool uselocalvarmap;
3842  SCIP_Bool uselocalconsmap;
3843  char varname[SCIP_MAXSTRLEN];
3844  char consname[SCIP_MAXSTRLEN];
3845  const char* origvarname;
3846 
3847  assert(benders != NULL);
3848  assert(set != NULL);
3849  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
3850 
3851  SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " Benders' decomposition: Infeasibility of subproblem %d can't "
3852  "be resolved. Subproblem %d is being merged into the master problem.\n", probnumber, probnumber);
3853 
3854  /* freeing the subproblem because it will be flagged as independent. Since the subproblem is flagged as independent,
3855  * it will no longer be solved or freed within the solving loop.
3856  */
3857  SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, probnumber) );
3858 
3859  subproblem = SCIPbendersSubproblem(benders, probnumber);
3860 
3861  uselocalvarmap = (varmap == NULL);
3862  uselocalconsmap = (consmap == NULL);
3863 
3864  if( uselocalvarmap )
3865  {
3866  /* create the variable mapping hash map */
3867  SCIP_CALL( SCIPhashmapCreate(&localvarmap, SCIPblkmem(set->scip), SCIPgetNVars(subproblem)) );
3868  }
3869  else
3870  localvarmap = varmap;
3871 
3872  if( uselocalconsmap )
3873  {
3874  /* create the constraint mapping hash map */
3875  SCIP_CALL( SCIPhashmapCreate(&localconsmap, SCIPblkmem(set->scip), SCIPgetNConss(subproblem)) );
3876  }
3877  else
3878  localconsmap = consmap;
3879 
3880  /* retrieving the subproblem variable to build a subproblem mapping */
3881  vars = SCIPgetVars(subproblem);
3882  nvars = SCIPgetNVars(subproblem);
3883 
3884  /* creating the objective function constraint that will be added to the master problem */
3885  /* setting the name of the transferred cut */
3886  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objectivecons_%d", probnumber );
3887  SCIP_CALL( SCIPcreateConsBasicLinear(set->scip, &objcons, consname, 0, NULL, NULL, -SCIPsetInfinity(set), 0.0) );
3888  SCIP_CALL( SCIPsetConsRemovable(set->scip, objcons, TRUE) );
3889 
3890  for( i = 0; i < nvars; i++ )
3891  {
3892  SCIP_VAR* mastervar = NULL;
3893  SCIP_Bool releasevar = FALSE;
3894 
3895  SCIP_CALL( SCIPgetBendersMasterVar(set->scip, benders, vars[i], &mastervar) );
3896 
3897  /* if the master problem variable is not NULL, then there is a corresponding variable in the master problem for
3898  * the given subproblem variable. In this case, the variable is added to the hashmap.
3899  */
3900  if( mastervar == NULL )
3901  {
3902  SCIP_VAR* origvar;
3903  SCIP_Real scalar;
3904  SCIP_Real constant;
3905 
3906  /* This is following the same process as in createVariableMappings. The original variable is used to map
3907  * between the subproblem and the master problem
3908  */
3909  origvar = vars[i];
3910  scalar = 1.0;
3911  constant = 0.0;
3912  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
3913 
3914  /* retrieving the var name */
3915  origvarname = SCIPvarGetName(origvar);
3916  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s", origvarname);
3917 
3918  /* creating and adding the variable to the Benders' decomposition master problem */
3919  SCIP_CALL( SCIPcreateVarBasic(set->scip, &mastervar, varname, SCIPvarGetLbOriginal(origvar),
3920  SCIPvarGetUbOriginal(origvar), 0.0, SCIPvarGetType(origvar)) );
3921 
3922  /* adding the variable to the master problem */
3923  SCIP_CALL( SCIPaddVar(set->scip, mastervar) );
3924 
3925  /* adds the variable to the objective function constraint */
3926  SCIP_CALL( SCIPaddCoefLinear(set->scip, objcons, mastervar, SCIPvarGetObj(origvar)) );
3927 
3928  /* the variable must be released */
3929  releasevar = TRUE;
3930  }
3931 
3932  /* creating the mapping betwen the subproblem var and the master var for the constraint copying */
3933  SCIP_CALL( SCIPhashmapInsert(localvarmap, vars[i], mastervar) );
3934 
3935  /* releasing the variable */
3936  if( releasevar )
3937  {
3938  SCIP_CALL( SCIPreleaseVar(set->scip, &mastervar) );
3939  }
3940  }
3941 
3942  /* getting the constraints from the subproblem that will be added to the master problem */
3943  conss = SCIPgetConss(subproblem);
3944  nconss = SCIPgetNConss(subproblem);
3945 
3946  /* getting a copy of all constraints and adding it to the master problem */
3947  for( i = 0; i < nconss; i++ )
3948  {
3949  SCIP_CONS* targetcons;
3950  SCIP_Bool initial;
3951  SCIP_Bool valid;
3952 
3953  /* NOTE: adding all subproblem constraints appears to cause an error when resolving the LP, which results in the
3954  * current incumbent being reported as optimal. To avoid this, only half of the subproblem constraints are added
3955  * the master problem. The remaining half are marked as lazy and are separated as required.
3956  */
3957  initial = (i < nconss/2);
3958 
3959  SCIP_CALL( SCIPgetConsCopy(subproblem, set->scip, conss[i], &targetcons, SCIPconsGetHdlr(conss[i]),
3960  localvarmap, localconsmap, NULL, initial, SCIPconsIsSeparated(conss[i]),
3961  SCIPconsIsEnforced(conss[i]), SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE,
3962  SCIPconsIsModifiable(conss[i]), SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]),
3963  FALSE, TRUE, &valid) );
3964  assert(SCIPconsIsInitial(conss[i]));
3965  assert(valid);
3966 
3967  SCIP_CALL( SCIPaddCons(set->scip, targetcons) );
3968 
3969  SCIP_CALL( SCIPreleaseCons(set->scip, &targetcons) );
3970  }
3971 
3972  /* freeing the hashmaps */
3973  if( uselocalvarmap )
3974  {
3975  /* free hash map */
3976  SCIPhashmapFree(&localvarmap);
3977  }
3978 
3979  if( uselocalconsmap )
3980  {
3981  /* free hash map */
3982  SCIPhashmapFree(&localconsmap);
3983  }
3984 
3985  /* adding the auxiliary variable to the objective constraint */
3986  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
3987  SCIP_CALL( SCIPaddCoefLinear(set->scip, objcons, auxiliaryvar, -1.0) );
3988 
3989  /* adding the objective function constraint to the master problem */
3990  SCIP_CALL( SCIPaddCons(set->scip, objcons) );
3991 
3992  SCIP_CALL( SCIPreleaseCons(set->scip, &objcons) );
3993 
3994  /* the merged subproblem is no longer solved. This is indicated by setting the subproblem as disabled. The
3995  * subproblem still exists, but it is not solved in the solving loop.
3996  */
3997  SCIPbendersSetSubproblemEnabled(benders, probnumber, FALSE);
3998 
3999  return SCIP_OKAY;
4000 }
4001 
4002 /** Returns the corresponding master or subproblem variable for the given variable.
4003  * This provides a call back for the variable mapping between the master and subproblems. */
4005  SCIP_BENDERS* benders, /**< Benders' decomposition */
4006  SCIP_SET* set, /**< global SCIP settings */
4007  SCIP_VAR* var, /**< the variable for which the corresponding variable is desired */
4008  SCIP_VAR** mappedvar, /**< the variable that is mapped to var */
4009  int probnumber /**< the problem number for the desired variable, -1 for the master problem */
4010  )
4011 {
4012  assert(benders != NULL);
4013  assert(set != NULL);
4014  assert(var != NULL);
4015  assert(mappedvar != NULL);
4016  assert(benders->bendersgetvar != NULL);
4017 
4018  (*mappedvar) = NULL;
4019 
4020  /* if the variable name matches the auxiliary variable, then the master variable is returned as NULL */
4021  if( strstr(SCIPvarGetName(var), AUXILIARYVAR_NAME) != NULL )
4022  return SCIP_OKAY;
4023 
4024  SCIP_CALL( benders->bendersgetvar(set->scip, benders, var, mappedvar, probnumber) );
4025 
4026  return SCIP_OKAY;
4027 }
4028 
4029 /** gets user data of Benders' decomposition */
4031  SCIP_BENDERS* benders /**< Benders' decomposition */
4032  )
4033 {
4034  assert(benders != NULL);
4035 
4036  return benders->bendersdata;
4037 }
4038 
4039 /** sets user data of Benders' decomposition; user has to free old data in advance! */
4041  SCIP_BENDERS* benders, /**< Benders' decomposition */
4042  SCIP_BENDERSDATA* bendersdata /**< new Benders' decomposition user data */
4043  )
4044 {
4045  assert(benders != NULL);
4046 
4047  benders->bendersdata = bendersdata;
4048 }
4049 
4050 /** sets copy callback of Benders' decomposition */
4052  SCIP_BENDERS* benders, /**< Benders' decomposition */
4053  SCIP_DECL_BENDERSCOPY ((*benderscopy)) /**< copy callback of Benders' decomposition */
4054  )
4055 {
4056  assert(benders != NULL);
4057 
4058  benders->benderscopy = benderscopy;
4059 }
4060 
4061 /** sets destructor callback of Benders' decomposition */
4063  SCIP_BENDERS* benders, /**< Benders' decomposition */
4064  SCIP_DECL_BENDERSFREE ((*bendersfree)) /**< destructor of Benders' decomposition */
4065  )
4066 {
4067  assert(benders != NULL);
4068 
4069  benders->bendersfree = bendersfree;
4070 }
4071 
4072 /** sets initialization callback of Benders' decomposition */
4074  SCIP_BENDERS* benders, /**< Benders' decomposition */
4075  SCIP_DECL_BENDERSINIT((*bendersinit)) /**< initialize the Benders' decomposition */
4076  )
4077 {
4078  assert(benders != NULL);
4079 
4080  benders->bendersinit = bendersinit;
4081 }
4082 
4083 /** sets deinitialization callback of Benders' decomposition */
4085  SCIP_BENDERS* benders, /**< Benders' decomposition */
4086  SCIP_DECL_BENDERSEXIT((*bendersexit)) /**< deinitialize the Benders' decomposition */
4087  )
4088 {
4089  assert(benders != NULL);
4090 
4091  benders->bendersexit = bendersexit;
4092 }
4093 
4094 /** sets presolving initialization callback of Benders' decomposition */
4096  SCIP_BENDERS* benders, /**< Benders' decomposition */
4097  SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< initialize presolving for Benders' decomposition */
4098  )
4099 {
4100  assert(benders != NULL);
4101 
4102  benders->bendersinitpre = bendersinitpre;
4103 }
4104 
4105 /** sets presolving deinitialization callback of Benders' decomposition */
4107  SCIP_BENDERS* benders, /**< Benders' decomposition */
4108  SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< deinitialize presolving for Benders' decomposition */
4109  )
4110 {
4111  assert(benders != NULL);
4112 
4113  benders->bendersexitpre = bendersexitpre;
4114 }
4115 
4116 /** sets solving process initialization callback of Benders' decomposition */
4118  SCIP_BENDERS* benders, /**< Benders' decomposition */
4119  SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization callback of Benders' decomposition */
4120  )
4121 {
4122  assert(benders != NULL);
4123 
4124  benders->bendersinitsol = bendersinitsol;
4125 }
4126 
4127 /** sets solving process deinitialization callback of Benders' decomposition */
4129  SCIP_BENDERS* benders, /**< Benders' decomposition */
4130  SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization callback of Benders' decomposition */
4131  )
4132 {
4133  assert(benders != NULL);
4134 
4135  benders->bendersexitsol = bendersexitsol;
4136 }
4137 
4138 /** sets the pre subproblem solve callback of Benders' decomposition */
4140  SCIP_BENDERS* benders, /**< Benders' decomposition */
4141  SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< called prior to the subproblem solving loop */
4142  )
4143 {
4144  assert(benders != NULL);
4145 
4146  benders->benderspresubsolve = benderspresubsolve;
4147 }
4148 
4149 /** sets convex solve callback of Benders' decomposition */
4151  SCIP_BENDERS* benders, /**< Benders' decomposition */
4152  SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))/**< solving method for the convex Benders' decomposition subproblem */
4153  )
4154 {
4155  assert(benders != NULL);
4156 
4157  benders->benderssolvesubconvex = benderssolvesubconvex;
4158 }
4159 
4160 /** sets solve callback of Benders' decomposition */
4162  SCIP_BENDERS* benders, /**< Benders' decomposition */
4163  SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))/**< solving method for a Benders' decomposition subproblem */
4164  )
4165 {
4166  assert(benders != NULL);
4167 
4168  benders->benderssolvesub = benderssolvesub;
4169 }
4170 
4171 /** sets post-solve callback of Benders' decomposition */
4173  SCIP_BENDERS* benders, /**< Benders' decomposition */
4174  SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization callback of Benders' decomposition */
4175  )
4176 {
4177  assert(benders != NULL);
4178 
4179  benders->benderspostsolve = benderspostsolve;
4180 }
4181 
4182 /** sets free subproblem callback of Benders' decomposition */
4184  SCIP_BENDERS* benders, /**< Benders' decomposition */
4185  SCIP_DECL_BENDERSFREESUB((*bendersfreesub))/**< the freeing callback for the subproblem */
4186  )
4187 {
4188  assert(benders != NULL);
4189 
4190  benders->bendersfreesub = bendersfreesub;
4191 }
4192 
4193 /** gets name of Benders' decomposition */
4195  SCIP_BENDERS* benders /**< Benders' decomposition */
4196  )
4197 {
4198  assert(benders != NULL);
4199 
4200  return benders->name;
4201 }
4202 
4203 /** gets description of Benders' decomposition */
4205  SCIP_BENDERS* benders /**< Benders' decomposition */
4206  )
4207 {
4208  assert(benders != NULL);
4209 
4210  return benders->desc;
4211 }
4212 
4213 /** gets priority of Benders' decomposition */
4215  SCIP_BENDERS* benders /**< Benders' decomposition */
4216  )
4217 {
4218  assert(benders != NULL);
4219 
4220  return benders->priority;
4221 }
4222 
4223 /** sets priority of Benders' decomposition */
4225  SCIP_BENDERS* benders, /**< Benders' decomposition */
4226  SCIP_SET* set, /**< global SCIP settings */
4227  int priority /**< new priority of the Benders' decomposition */
4228  )
4229 {
4230  assert(benders != NULL);
4231  assert(set != NULL);
4232 
4233  benders->priority = priority;
4234  set->benderssorted = FALSE;
4235 }
4236 
4237 /** gets the number of subproblems for the Benders' decomposition */
4239  SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
4240  )
4241 {
4242  assert(benders != NULL);
4243 
4244  return benders->nsubproblems;
4245 }
4246 
4247 /** returns the SCIP instance for a given subproblem */
4249  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
4250  int probnumber /**< the subproblem number */
4251  )
4252 {
4253  assert(benders != NULL);
4254  assert(probnumber >= 0 && probnumber < benders->nsubproblems);
4255 
4256  return benders->subproblems[probnumber];
4257 }
4258 
4259 /** gets the number of times, the Benders' decomposition was called and tried to find a variable with negative reduced costs */
4261  SCIP_BENDERS* benders /**< Benders' decomposition */
4262  )
4263 {
4264  assert(benders != NULL);
4265 
4266  return benders->ncalls;
4267 }
4268 
4269 /** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
4271  SCIP_BENDERS* benders /**< Benders' decomposition */
4272  )
4273 {
4274  assert(benders != NULL);
4275 
4276  return benders->ncutsfound;
4277 }
4278 
4279 /** gets time in seconds used in this Benders' decomposition for setting up for next stages */
4281  SCIP_BENDERS* benders /**< Benders' decomposition */
4282  )
4283 {
4284  assert(benders != NULL);
4285 
4286  return SCIPclockGetTime(benders->setuptime);
4287 }
4288 
4289 /** gets time in seconds used in this Benders' decomposition */
4291  SCIP_BENDERS* benders /**< Benders' decomposition */
4292  )
4293 {
4294  assert(benders != NULL);
4295 
4296  return SCIPclockGetTime(benders->bendersclock);
4297 }
4298 
4299 /** enables or disables all clocks of the Benders' decomposition, depending on the value of the flag */
4301  SCIP_BENDERS* benders, /**< the Benders' decomposition for which all clocks should be enabled or disabled */
4302  SCIP_Bool enable /**< should the clocks of the Benders' decomposition be enabled? */
4303  )
4304 {
4305  assert(benders != NULL);
4306 
4307  SCIPclockEnableOrDisable(benders->setuptime, enable);
4308  SCIPclockEnableOrDisable(benders->bendersclock, enable);
4309 }
4310 
4311 /** is Benders' decomposition initialized? */
4313  SCIP_BENDERS* benders /**< Benders' decomposition */
4314  )
4315 {
4316  assert(benders != NULL);
4317 
4318  return benders->initialized;
4319 }
4320 
4321 /** Are Benders' cuts generated from the LP solutions? */
4323  SCIP_BENDERS* benders /**< Benders' decomposition */
4324  )
4325 {
4326  assert(benders != NULL);
4327 
4328  return benders->cutlp;
4329 }
4330 
4331 /** Are Benders' cuts generated from the pseudo solutions? */
4333  SCIP_BENDERS* benders /**< Benders' decomposition */
4334  )
4335 {
4336  assert(benders != NULL);
4337 
4338  return benders->cutpseudo;
4339 }
4340 
4341 /** Are Benders' cuts generated from the relaxation solutions? */
4343  SCIP_BENDERS* benders /**< Benders' decomposition */
4344  )
4345 {
4346  assert(benders != NULL);
4347 
4348  return benders->cutrelax;
4349 }
4350 
4351 /** should this Benders' use the auxiliary variables from the highest priority Benders' */
4353  SCIP_BENDERS* benders /**< Benders' decomposition */
4354  )
4355 {
4356  assert(benders != NULL);
4357 
4358  return benders->shareauxvars;
4359 }
4360 
4361 /** adds a subproblem to the Benders' decomposition data */
4363  SCIP_BENDERS* benders, /**< Benders' decomposition */
4364  SCIP* subproblem /**< subproblem to be added to the data storage */
4365  )
4366 {
4367  assert(benders != NULL);
4368  assert(subproblem != NULL);
4369  assert(benders->subproblems != NULL);
4370  assert(benders->naddedsubprobs + 1 <= benders->nsubproblems);
4371 
4372  benders->subproblems[benders->naddedsubprobs] = subproblem;
4373 
4374  benders->naddedsubprobs++;
4375 
4376  return SCIP_OKAY;
4377 }
4378 
4379 /** removes the subproblems from the Benders' decomposition data */
4381  SCIP_BENDERS* benders /**< Benders' decomposition */
4382  )
4383 {
4384  assert(benders != NULL);
4385  assert(benders->subproblems != NULL);
4386 
4387  BMSclearMemoryArray(&benders->subproblems, benders->naddedsubprobs);
4388  benders->naddedsubprobs = 0;
4389 }
4390 
4391 /** returns the auxiliary variable for the given subproblem */
4393  SCIP_BENDERS* benders, /**< Benders' decomposition */
4394  int probnumber /**< the subproblem number */
4395  )
4396 {
4397  assert(benders != NULL);
4398  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4399 
4400  return benders->auxiliaryvars[probnumber];
4401 }
4402 
4403 /** returns all auxiliary variables */
4405  SCIP_BENDERS* benders /**< Benders' decomposition */
4406  )
4407 {
4408  assert(benders != NULL);
4409 
4410  return benders->auxiliaryvars;
4411 }
4412 
4413 /** stores the objective function value of the subproblem for use in cut generation */
4415  SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
4416  int probnumber, /**< the subproblem number */
4417  SCIP_Real objval /**< the objective function value for the subproblem */
4418  )
4419 {
4420  assert(benders != NULL);
4421  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4422 
4423  /* updating the best objval */
4424  if( objval < benders->bestsubprobobjval[probnumber] )
4425  benders->bestsubprobobjval[probnumber] = objval;
4426 
4427  benders->subprobobjval[probnumber] = objval;
4428 }
4429 
4430 /** returns the objective function value of the subproblem for use in cut generation */
4432  SCIP_BENDERS* benders, /**< Benders' decomposition */
4433  int probnumber /**< the subproblem number */
4434  )
4435 {
4436  assert(benders != NULL);
4437  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4438 
4439  return benders->subprobobjval[probnumber];
4440 }
4441 
4442 /** sets the flag indicating whether a subproblem is convex
4443  *
4444  * It is possible that this can change during the solving process. One example is when the three-phase method is
4445  * employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
4446  * reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
4447  * constraints to the subproblems.
4448  */
4450  SCIP_BENDERS* benders, /**< Benders' decomposition */
4451  int probnumber, /**< the subproblem number */
4452  SCIP_Bool isconvex /**< flag to indicate whether the subproblem is convex */
4453  )
4454 {
4455  assert(benders != NULL);
4456  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4457 
4458  if( isconvex && !benders->subprobisconvex[probnumber] )
4459  benders->nconvexsubprobs++;
4460  else if( !isconvex && benders->subprobisconvex[probnumber] )
4461  benders->nconvexsubprobs--;
4462 
4463  benders->subprobisconvex[probnumber] = isconvex;
4464 
4465  assert(benders->nconvexsubprobs >= 0 && benders->nconvexsubprobs <= benders->nsubproblems);
4466 }
4467 
4468 /** returns whether the subproblem is convex
4469  *
4470  * This means that the dual solution can be used to generate cuts.
4471  */
4473  SCIP_BENDERS* benders, /**< Benders' decomposition */
4474  int probnumber /**< the subproblem number */
4475  )
4476 {
4477  assert(benders != NULL);
4478  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4479 
4480  return benders->subprobisconvex[probnumber];
4481 }
4482 
4483 /** returns the number of subproblems that are convex */
4485  SCIP_BENDERS* benders /**< Benders' decomposition */
4486  )
4487 {
4488  assert(benders != NULL);
4489 
4490  return benders->nconvexsubprobs;
4491 }
4492 
4493 /** changes all of the master problem variables in the given subproblem to continuous. */
4495  SCIP_BENDERS* benders, /**< Benders' decomposition */
4496  SCIP_SET* set, /**< global SCIP settings */
4497  int probnumber /**< the subproblem number */
4498  )
4499 {
4500  SCIP* subproblem;
4501  SCIP_VAR** vars;
4502  int nbinvars;
4503  int nintvars;
4504  int nimplvars;
4505  int chgvarscount;
4506  int origintvars;
4507  int i;
4508  SCIP_Bool infeasible;
4509 
4510  assert(benders != NULL);
4511  assert(set != NULL);
4512  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4513 
4514  subproblem = SCIPbendersSubproblem(benders, probnumber);
4515  assert(subproblem != NULL);
4516 
4517  /* only set the master problem variable to continuous if they have not already been changed. */
4518  if( !SCIPbendersGetMastervarsCont(benders, probnumber) )
4519  {
4520  SCIP_VAR* mastervar;
4521 
4522  /* retrieving the variable data */
4523  SCIP_CALL( SCIPgetVarsData(subproblem, &vars, NULL, &nbinvars, &nintvars, &nimplvars, NULL) );
4524 
4525  origintvars = nbinvars + nintvars + nimplvars;
4526 
4527  chgvarscount = 0;
4528 
4529  /* looping over all integer variables to change the master variables to continuous */
4530  i = 0;
4531  while( i < nbinvars + nintvars + nimplvars )
4532  {
4533  SCIP_CALL( SCIPbendersGetVar(benders, set, vars[i], &mastervar, -1) );
4534 
4535  if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS && mastervar != NULL )
4536  {
4537  /* changing the type of the subproblem variable corresponding to mastervar to CONTINUOUS */
4538  SCIP_CALL( SCIPchgVarType(subproblem, vars[i], SCIP_VARTYPE_CONTINUOUS, &infeasible) );
4539 
4540  assert(!infeasible);
4541 
4542  chgvarscount++;
4543  SCIP_CALL( SCIPgetVarsData(subproblem, NULL, NULL, &nbinvars, &nintvars, &nimplvars, NULL) );
4544  }
4545  else
4546  i++;
4547  }
4548 
4549  /* if all of the integer variables have been changed to continuous, then the subproblem must now be an LP. In this
4550  * case, the subproblem is initialised and then put into probing mode */
4551  if( chgvarscount > 0 && chgvarscount == origintvars )
4552  {
4553  SCIP_CALL( initialiseLPSubproblem(benders, set, probnumber) );
4554  SCIPbendersSetSubproblemIsConvex(benders, probnumber, TRUE);
4555  }
4556 
4557  SCIP_CALL( SCIPbendersSetMastervarsCont(benders, probnumber, TRUE) );
4558  }
4559 
4560  return SCIP_OKAY;
4561 }
4562 
4563 /** sets the subproblem setup flag */
4565  SCIP_BENDERS* benders, /**< Benders' decomposition */
4566  int probnumber, /**< the subproblem number */
4567  SCIP_Bool issetup /**< flag to indicate whether the subproblem has been setup */
4568  )
4569 {
4570  assert(benders != NULL);
4571  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4572 
4573  benders->subprobsetup[probnumber] = issetup;
4574 }
4575 
4576 /** returns the subproblem setup flag */
4578  SCIP_BENDERS* benders, /**< Benders' decomposition */
4579  int probnumber /**< the subproblem number */
4580  )
4581 {
4582  assert(benders != NULL);
4583  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4584 
4585  return benders->subprobsetup[probnumber];
4586 }
4587 
4588 /** sets the independent subproblem flag */
4590  SCIP_BENDERS* benders, /**< Benders' decomposition */
4591  int probnumber, /**< the subproblem number */
4592  SCIP_Bool isindep /**< flag to indicate whether the subproblem is independent */
4593  )
4594 {
4595  assert(benders != NULL);
4596  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4597 
4598  /* if the user has defined solving or freeing functions, then it is not possible to declare a subproblem as
4599  * independent. This is because declaring a subproblem as independent changes the solving loop, so it would change
4600  * the expected behaviour of the user defined plugin. If a user calls this function, then an error will be returned.
4601  */
4602  if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL || benders->bendersfreesub != NULL )
4603  {
4604  SCIPerrorMessage("The user has defined either bendersSolvesubconvex%d, bendersSolvesub%d or bendersFreesub%s. "
4605  "Thus, it is not possible to declare the independence of a subproblem.\n", benders->name, benders->name,
4606  benders->name);
4607  SCIPABORT();
4608  }
4609  else
4610  {
4611  SCIP_Bool activesubprob;
4612 
4613  /* if the active status of the subproblem changes, then we must update the activesubprobs counter */
4614  activesubprob = subproblemIsActive(benders, probnumber);
4615 
4616  benders->indepsubprob[probnumber] = isindep;
4617 
4618  /* updating the activesubprobs counter */
4619  if( activesubprob && !subproblemIsActive(benders, probnumber) )
4620  benders->nactivesubprobs--;
4621  else if( !activesubprob && subproblemIsActive(benders, probnumber) )
4622  benders->nactivesubprobs++;
4623 
4624  assert(benders->nactivesubprobs >= 0 && benders->nactivesubprobs <= SCIPbendersGetNSubproblems(benders));
4625  }
4626 }
4627 
4628 /** returns whether the subproblem is independent */
4630  SCIP_BENDERS* benders, /**< Benders' decomposition */
4631  int probnumber /**< the subproblem number */
4632  )
4633 {
4634  assert(benders != NULL);
4635  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4636 
4637  return benders->indepsubprob[probnumber];
4638 }
4639 
4640 /** Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master
4641  * problem.
4642  */
4644  SCIP_BENDERS* benders, /**< Benders' decomposition */
4645  int probnumber, /**< the subproblem number */
4646  SCIP_Bool enabled /**< flag to indicate whether the subproblem is enabled */
4647  )
4648 {
4649  SCIP_Bool activesubprob;
4650 
4651  assert(benders != NULL);
4652  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4653 
4654  /* if the active status of the subproblem changes, then we must update the activesubprobs counter */
4655  activesubprob = subproblemIsActive(benders, probnumber);
4656 
4657  benders->subprobenabled[probnumber] = enabled;
4658 
4659  /* updating the activesubprobs counter */
4660  if( activesubprob && !subproblemIsActive(benders, probnumber) )
4661  benders->nactivesubprobs--;
4662  else if( !activesubprob && subproblemIsActive(benders, probnumber) )
4663  benders->nactivesubprobs++;
4664 
4665  assert(benders->nactivesubprobs >= 0 && benders->nactivesubprobs <= SCIPbendersGetNSubproblems(benders));
4666 }
4667 
4668 /** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
4670  SCIP_BENDERS* benders, /**< Benders' decomposition */
4671  int probnumber /**< the subproblem number */
4672  )
4673 {
4674  assert(benders != NULL);
4675  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4676 
4677  return benders->subprobenabled[probnumber];
4678 }
4679 
4680 /** sets a flag to indicate whether the master variables are all set to continuous */
4682  SCIP_BENDERS* benders, /**< Benders' decomposition */
4683  int probnumber, /**< the subproblem number */
4684  SCIP_Bool arecont /**< flag to indicate whether the master problem variables are continuous */
4685  )
4686 {
4687  assert(benders != NULL);
4688  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4689 
4690  /* if the master variables were all continuous and now are not, then the subproblem must exit probing mode and be
4691  * changed to non-LP subproblem */
4692  if( benders->mastervarscont[probnumber] && !arecont )
4693  {
4694  if( SCIPinProbing(SCIPbendersSubproblem(benders, probnumber)) )
4695  {
4696  SCIP_CALL( SCIPendProbing(SCIPbendersSubproblem(benders, probnumber)) );
4697  }
4698 
4699  SCIPbendersSetSubproblemIsConvex(benders, probnumber, FALSE);
4700  }
4701 
4702  benders->mastervarscont[probnumber] = arecont;
4703 
4704  return SCIP_OKAY;
4705 }
4706 
4707 /** returns whether the master variables are all set to continuous */
4709  SCIP_BENDERS* benders, /**< Benders' decomposition */
4710  int probnumber /**< the subproblem number */
4711  )
4712 {
4713  assert(benders != NULL);
4714  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4715 
4716  return benders->mastervarscont[probnumber];
4717 }
4718 
4719 /** returns the number of cuts that have been transferred from sub SCIPs to the master SCIP */
4721  SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
4722  )
4723 {
4724  assert(benders != NULL);
4725 
4726  return benders->ntransferred;
4727 }
4728 
4729 /** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
4730  * then no update occurs.
4731  */
4733  SCIP_BENDERS* benders, /**< Benders' decomposition */
4734  int probnumber, /**< the subproblem number */
4735  SCIP_Real lowerbound /**< the lower bound */
4736  )
4737 {
4738  assert(benders != NULL);
4739  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4740 
4741  if( lowerbound > benders->subproblowerbound[probnumber] )
4742  benders->subproblowerbound[probnumber] = lowerbound;
4743  else
4744  {
4745  SCIPdebugMessage("The lowerbound %g for subproblem %d is less than the currently stored lower bound %g\n",
4746  lowerbound, probnumber, benders->subproblowerbound[probnumber]);
4747  }
4748 }
4749 
4750 /** returns the stored lower bound for the given subproblem */
4752  SCIP_BENDERS* benders, /**< Benders' decomposition */
4753  int probnumber /**< the subproblem number */
4754  )
4755 {
4756  assert(benders != NULL);
4757  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4758 
4759  return benders->subproblowerbound[probnumber];
4760 }
4761 
4762 /** sets the sorted flags in the Benders' decomposition */
4764  SCIP_BENDERS* benders, /**< Benders' decomposition structure */
4765  SCIP_Bool sorted /**< the value to set the sorted flag to */
4766  )
4767 {
4768  assert(benders != NULL);
4769 
4770  benders->benderscutssorted = sorted;
4771  benders->benderscutsnamessorted = sorted;
4772 }
4773 
4774 /** inserts a Benders' cut into the Benders' cuts list */
4776  SCIP_BENDERS* benders, /**< Benders' decomposition structure */
4777  SCIP_SET* set, /**< global SCIP settings */
4778  SCIP_BENDERSCUT* benderscut /**< Benders' cut */
4779  )
4780 {
4781  assert(benders != NULL);
4782  assert(benderscut != NULL);
4783 
4784  if( benders->nbenderscuts >= benders->benderscutssize )
4785  {
4786  benders->benderscutssize = SCIPsetCalcMemGrowSize(set, benders->nbenderscuts+1);
4788  }
4789  assert(benders->nbenderscuts < benders->benderscutssize);
4790 
4791  benders->benderscuts[benders->nbenderscuts] = benderscut;
4792  benders->nbenderscuts++;
4793  benders->benderscutssorted = FALSE;
4794 
4795  return SCIP_OKAY;
4796 }
4797 
4798 /** returns the Benders' cut of the given name, or NULL if not existing */
4800  SCIP_BENDERS* benders, /**< Benders' decomposition */
4801  const char* name /**< name of Benderscut' decomposition */
4802  )
4803 {
4804  int i;
4805 
4806  assert(benders != NULL);
4807  assert(name != NULL);
4808 
4809  for( i = 0; i < benders->nbenderscuts; i++ )
4810  {
4811  if( strcmp(SCIPbenderscutGetName(benders->benderscuts[i]), name) == 0 )
4812  return benders->benderscuts[i];
4813  }
4814 
4815  return NULL;
4816 }
4817 
4818 /** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
4819  * the array
4820  */
4822  SCIP_BENDERS* benders /**< Benders' decomposition */
4823  )
4824 {
4825  assert(benders != NULL);
4826 
4827  if( !benders->benderscutssorted )
4828  {
4829  SCIPsortPtr((void**)benders->benderscuts, SCIPbenderscutComp, benders->nbenderscuts);
4830  benders->benderscutssorted = TRUE;
4831  benders->benderscutsnamessorted = FALSE;
4832  }
4833 
4834  return benders->benderscuts;
4835 }
4836 
4837 /** returns the number of currently available Benders' cuts */
4839  SCIP_BENDERS* benders /**< Benders' decomposition */
4840  )
4841 {
4842  assert(benders != NULL);
4843 
4844  return benders->nbenderscuts;
4845 }
4846 
4847 /** sets the priority of a Benders' decomposition */
4849  SCIP_BENDERS* benders, /**< Benders' decomposition */
4850  SCIP_BENDERSCUT* benderscut, /**< Benders' cut */
4851  int priority /**< new priority of the Benders' decomposition */
4852  )
4853 {
4854  assert(benders != NULL);
4855  assert(benderscut != NULL);
4856 
4857  benderscut->priority = priority;
4858  benders->benderscutssorted = FALSE;
4859 
4860  return SCIP_OKAY;
4861 }
4862 
4863 /** sorts Benders' decomposition cuts by priorities */
4865  SCIP_BENDERS* benders /**< Benders' decomposition */
4866  )
4867 {
4868  assert(benders != NULL);
4869 
4870  if( !benders->benderscutssorted )
4871  {
4872  SCIPsortPtr((void**)benders->benderscuts, SCIPbenderscutComp, benders->nbenderscuts);
4873  benders->benderscutssorted = TRUE;
4874  benders->benderscutsnamessorted = FALSE;
4875  }
4876 }
4877 
4878 /** sorts Benders' decomposition cuts by name */
4880  SCIP_BENDERS* benders /**< Benders' decomposition */
4881  )
4882 {
4883  assert(benders != NULL);
4884 
4885  if( !benders->benderscutsnamessorted )
4886  {
4887  SCIPsortPtr((void**)benders->benderscuts, SCIPbenderscutCompName, benders->nbenderscuts);
4888  benders->benderscutssorted = FALSE;
4889  benders->benderscutsnamessorted = TRUE;
4890  }
4891 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPbenderscutExec(SCIP_BENDERSCUT *benderscut, SCIP_SET *set, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)
Definition: benderscut.c:343
int SCIPbendersGetNBenderscuts(SCIP_BENDERS *benders)
Definition: benders.c:4838
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
#define SCIP_DECL_BENDERSCREATESUB(x)
Definition: type_benders.h:170
#define UPPERBOUND_EVENTHDLR_DESC
Definition: benders.c:65
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:398
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:213
static SCIP_DECL_EVENTEXIT(eventExitBendersNodefocus)
Definition: benders.c:241
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3172
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5953
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:489
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:436
SCIP_Bool benders_copybenders
Definition: struct_set.h:439
#define NULL
Definition: def.h:239
static SCIP_RETCODE updateAuxiliaryVarLowerbound(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_RESULT *result)
Definition: benders.c:1943
SCIP_RETCODE SCIPbendersIncludeBenderscut(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSCUT *benderscut)
Definition: benders.c:4775
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4431
void SCIPbendersDeactivate(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1891
void SCIPsetBendersPriority(SCIP *scip, SCIP_BENDERS *benders, int priority)
Definition: scip_benders.c:633
SCIP_RETCODE SCIPsetEventhdlrInitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINITSOL((*eventinitsol)))
Definition: scip_event.c:260
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:130
SCIP_RETCODE SCIPbendersSolveSubproblemLP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Bool *infeasible)
Definition: benders.c:3445
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_BENDERSDATA * bendersdata
SCIP_HASHMAP * mastervarsmap
#define SCIP_DECL_BENDERSINITSOL(x)
Definition: type_benders.h:130
SCIP_RETCODE SCIPbendersSetupSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber)
Definition: benders.c:3118
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecBendersNodefocus)
Definition: benders.c:193
#define SCIP_DECL_BENDERSFREE(x)
Definition: type_benders.h:82
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:703
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:661
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
#define SCIP_MAXSTRLEN
Definition: def.h:260
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:4194
SCIP_RETCODE SCIPbendersSolveSubproblemCIP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Bool *infeasible, SCIP_BENDERSENFOTYPE type, SCIP_Bool solvecip)
Definition: benders.c:3504
SCIP_RETCODE SCIPsetEventhdlrExitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXITSOL((*eventexitsol)))
Definition: scip_event.c:274
SCIP_Bool SCIPbendersIsInitialized(SCIP_BENDERS *benders)
Definition: benders.c:4312
internal methods for clocks and timing issues
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:103
#define SCIP_DECL_BENDERSINITPRE(x)
Definition: type_benders.h:111
SCIP_RETCODE SCIPsetParam(SCIP *scip, const char *name, void *value)
Definition: scip_param.c:475
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXIT((*eventexit)))
Definition: scip_event.c:246
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1602
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16790
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:76
void SCIPbendersSetSolvesub(SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)))
Definition: benders.c:4161
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:172
#define NODESOLVED_EVENTHDLR_DESC
Definition: benders.c:68
static SCIP_RETCODE solveBendersSubproblems(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool checkint, int *nchecked, int *nverified, SCIP_Bool **subprobsolved, SCIP_BENDERSSUBSTATUS **substatus, SCIP_Bool *infeasible, SCIP_Bool *optimal, SCIP_Bool *stopped)
Definition: benders.c:2041
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:138
#define SCIP_DEFAULT_CUTSASCONSS
Definition: benders.c:46
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:5813
#define SCIP_DECL_BENDERSGETVAR(x)
Definition: type_benders.h:339
SCIP_Bool cutsasconss
static SCIP_RETCODE updateSubproblemLowerbound(SCIP *masterprob, SCIP_BENDERS *benders)
Definition: benders.c:455
static int numSubproblemsToCheck(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_BENDERSENFOTYPE type)
Definition: benders.c:2010
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:350
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:996
void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:4040
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16869
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPbendersExit(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1552
static SCIP_Bool subproblemIsActive(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:2024
SCIP_RETCODE SCIPbendersCopyInclude(SCIP_BENDERS *benders, SCIP_SET *sourceset, SCIP_SET *targetset, SCIP_HASHMAP *varmap, SCIP_Bool *valid)
Definition: benders.c:777
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPbendersExitpre(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_STAT *stat)
Definition: benders.c:1713
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10325
internal methods for Benders&#39; decomposition
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:280
SCIP_CLOCK * bendersclock
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:4404
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
SCIP_Real * bestsubprobobjval
static SCIP_RETCODE initsolEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTTYPE eventtype)
Definition: benders.c:103
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
#define SCIP_EVENTTYPE_NODEFOCUSED
Definition: type_event.h:77
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:1022
SCIP_Bool * subprobenabled
SCIP_Bool SCIPbendersGetMastervarsCont(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4708
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5503
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
void SCIPbendersRemoveSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:4380
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:105
SCIP_Bool benderscutssorted
void SCIPbendersSetFree(SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREE((*bendersfree)))
Definition: benders.c:4062
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
#define SCIP_DECL_BENDERSINIT(x)
Definition: type_benders.h:91
void SCIPbendersSetExitpre(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)))
Definition: benders.c:4106
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:302
SCIP_RETCODE SCIPbenderscutCopyInclude(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SET *set)
Definition: benderscut.c:78
static SCIP_RETCODE addAuxiliaryVariablesToMaster(SCIP *scip, SCIP_BENDERS *benders)
Definition: benders.c:579
const char * SCIPbendersGetDesc(SCIP_BENDERS *benders)
Definition: benders.c:4204
SCIP_Bool * indepsubprob
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3140
SCIP_Bool updateauxvarbound
internal methods for handling parameter settings
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4613
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_lp.c:182
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:250
static SCIP_RETCODE executeUserDefinedSolvesub(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool *infeasible, SCIP_Real *objective, SCIP_RESULT *result)
Definition: benders.c:2875
SCIP_RETCODE SCIPbendersCheckSubproblemOptimality(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: benders.c:3655
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define BMSfreeMemory(ptr)
Definition: memory.h:127
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
void SCIPbendersSetInit(SCIP_BENDERS *benders, SCIP_DECL_BENDERSINIT((*bendersinit)))
Definition: benders.c:4073
void SCIPbendersSetExit(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXIT((*bendersexit)))
Definition: benders.c:4084
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:694
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:739
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
#define SCIPdebugMsg
Definition: scip_message.h:88
void SCIPbendersSetPostsolve(SCIP_BENDERS *benders, SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)))
Definition: benders.c:4172
SCIP_Real SCIPsetCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6151
SCIP_RETCODE SCIPbenderscutGetAddedCuts(SCIP_BENDERSCUT *benderscut, SCIP_ROW ***addedcuts, int *naddedcuts)
Definition: benderscut.c:598
#define MIPNODEFOCUS_EVENTHDLR_NAME
Definition: benders.c:61
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool subprobscreated
internal methods for LP management
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:540
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
datastructures for Benders&#39; decomposition cuts techniques
#define BENDERS_MAXPSEUDOSOLS
Definition: benders.c:52
SCIP * scip
Definition: struct_set.h:64
static SCIP_RETCODE resetOrigSubproblemParams(SCIP *subproblem, SCIP_SUBPROBPARAMS *origparams)
Definition: benders.c:3416
void SCIPbendersSetFreesub(SCIP_BENDERS *benders, SCIP_DECL_BENDERSFREESUB((*bendersfreesub)))
Definition: benders.c:4183
SCIP_RETCODE SCIPbendersAddSubproblem(SCIP_BENDERS *benders, SCIP *subproblem)
Definition: benders.c:4362
SCIP ** subproblems
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:334
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:159
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2737
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8072
SCIP_Real * subprobobjval
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition: benders.c:4260
#define SCIP_DECL_BENDERSFREESUB(x)
Definition: type_benders.h:323
SCIP_Bool lnscheck
void SCIPbendersSetSolvesubconvex(SCIP_BENDERS *benders, SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)))
Definition: benders.c:4150
int SCIPbendersGetNTransferredCuts(SCIP_BENDERS *benders)
Definition: benders.c:4720
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1488
static SCIP_RETCODE createSubproblems(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1133
void SCIPbendersSortBenderscutsName(SCIP_BENDERS *benders)
Definition: benders.c:4879
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
SCIP_RETCODE SCIPbendersInitsol(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1739
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:129
static SCIP_RETCODE createMasterVarMapping(SCIP_BENDERS *benders, SCIP_SET *sourceset, SCIP_HASHMAP *varmap)
Definition: benders.c:737
internal methods for storing and manipulating the main problem
SCIP_RETCODE SCIPbendersFreeSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:3605
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
Definition: var.c:17289
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3143
SCIP * sourcescip
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:218
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3151
static SCIP_RETCODE copyMemoryAndTimeLimits(SCIP *scip, SCIP *subproblem)
Definition: benders.c:3312
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE exitsolEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTTYPE eventtype)
Definition: benders.c:123
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:199
SCIP_RETCODE SCIPbenderscutFree(SCIP_BENDERSCUT **benderscut, SCIP_SET *set)
Definition: benderscut.c:167
#define SCIP_DECL_BENDERSEXIT(x)
Definition: type_benders.h:100
#define SCIP_DECL_BENDERSSOLVESUB(x)
Definition: type_benders.h:265
void SCIPbendersSetExitsol(SCIP_BENDERS *benders, SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)))
Definition: benders.c:4128
SCIP_Real SCIPvarGetUbOriginal(SCIP_VAR *var)
Definition: var.c:17309
SCIP_Real SCIPgetDualbound(SCIP *scip)
static SCIP_RETCODE freeEventhandler(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
Definition: benders.c:167
SCIP_Bool * subprobisconvex
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:520
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:519
void SCIPbendersSetPriority(SCIP_BENDERS *benders, SCIP_SET *set, int priority)
Definition: benders.c:4224
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
static SCIP_RETCODE initialiseLPSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:1095
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4703
SCIP_RETCODE SCIPbendersSolveSubproblem(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, int probnumber, SCIP_Bool *infeasible, SCIP_BENDERSENFOTYPE type, SCIP_Bool solvecip, SCIP_Real *objective)
Definition: benders.c:3217
static SCIP_RETCODE initEventhandlerData(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: benders.c:85
SCIP_RETCODE SCIPbendersExitsol(SCIP_BENDERS *benders, SCIP_SET *set)
Definition: benders.c:1772
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition: benders.c:4030
#define SCIP_DEFAULT_UPDATEAUXVARBOUND
Definition: benders.c:50
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:315
static SCIP_RETCODE generateBendersCuts(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_BENDERSSOLVELOOP solveloop, SCIP_Bool checkint, int nchecked, SCIP_Bool *subprobsolved, SCIP_BENDERSSUBSTATUS *substatus, int **mergecands, int *npriomergecands, int *nmergecands, int *nsolveloops)
Definition: benders.c:2305
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:322
SCIP_Bool transfercuts
SCIP_Bool benderscutsnamessorted
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1540
SCIP_BENDERSCUT * SCIPfindBenderscut(SCIP_BENDERS *benders, const char *name)
Definition: benders.c:4799
#define AUXILIARYVAR_NAME
Definition: benders.c:55
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
SCIP_PARAM * SCIPgetParam(SCIP *scip, const char *name)
Definition: scip_param.c:306
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:63
SCIP_RETCODE SCIPbendersSetMastervarsCont(SCIP_BENDERS *benders, int probnumber, SCIP_Bool arecont)
Definition: benders.c:4681
static SCIP_DECL_EVENTEXITSOL(eventExitsolBendersNodefocus)
Definition: benders.c:228
void SCIPbendersEnableOrDisableClocks(SCIP_BENDERS *benders, SCIP_Bool enable)
Definition: benders.c:4300
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:866
#define SCIP_DECL_BENDERSSOLVESUBCONVEX(x)
Definition: type_benders.h:232
SCIP_RETCODE SCIPbendersExec(SCIP_BENDERS *benders, SCIP_SET *set, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: benders.c:2505
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16879
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
internal methods for storing priced variables
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2879
void SCIPbendersSetSubproblemObjval(SCIP_BENDERS *benders, int probnumber, SCIP_Real objval)
Definition: benders.c:4414
SCIP_RETCODE SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
Definition: scip_param.c:360
void SCIPbendersSetInitsol(SCIP_BENDERS *benders, SCIP_DECL_BENDERSINITSOL((*bendersinitsol)))
Definition: benders.c:4117
SCIP_Bool shareauxvars
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6395
SCIP_RETCODE SCIPbendersCreate(SCIP_BENDERS **benders, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, SCIP_Bool cutlp, SCIP_Bool cutpseudo, SCIP_Bool cutrelax, SCIP_Bool shareauxvars, SCIP_DECL_BENDERSCOPY((*benderscopy)), SCIP_DECL_BENDERSFREE((*bendersfree)), SCIP_DECL_BENDERSINIT((*bendersinit)), SCIP_DECL_BENDERSEXIT((*bendersexit)), SCIP_DECL_BENDERSINITPRE((*bendersinitpre)), SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)), SCIP_DECL_BENDERSINITSOL((*bendersinitsol)), SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)), SCIP_DECL_BENDERSGETVAR((*bendersgetvar)), SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)), SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)), SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)), SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)), SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)), SCIP_DECL_BENDERSFREESUB((*bendersfreesub)), SCIP_BENDERSDATA *bendersdata)
Definition: benders.c:835
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16815
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:125
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:160
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1350
SCIP_RETCODE SCIPbendersChgMastervarsToCont(SCIP_BENDERS *benders, SCIP_SET *set, int probnumber)
Definition: benders.c:4494
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4450
#define SCIP_DEFAULT_LNSMAXDEPTH
Definition: benders.c:48
#define SCIP_DECL_BENDERSCOPY(x)
Definition: type_benders.h:74