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