Scippy

SCIP

Solving Constraint Integer Programs

cons_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 cons_benders.c
17  * @brief constraint handler for Benders' decomposition
18  * @author Stephen J. Maher
19  *
20  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
21  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
22  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
23  * respect to the subproblem constraints.
24  *
25  * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
26  * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
27  * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
28  * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
29  *
30  * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
31  * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
32  * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
33  * decomposition algorithm.
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include <assert.h>
39 #include <string.h>
40 
41 #include "scip/scip.h"
42 #include "scip/cons_benders.h"
43 #include "scip/heur_trysol.h"
44 #include "scip/heuristics.h"
45 
46 
47 /* fundamental constraint handler properties */
48 #define CONSHDLR_NAME "benders"
49 #define CONSHDLR_DESC "constraint handler to execute Benders' Decomposition"
50 #define CONSHDLR_ENFOPRIORITY -1 /**< priority of the constraint handler for constraint enforcing */
51 #define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
52 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
53  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
54 #define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
55 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
56 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
57 
58 
59 #define DEFAULT_CHECKEDSOLSSIZE 20 /**< initial size of the checked sols array */
60 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */
61 
62 /*
63  * Data structures
64  */
65 
66 /** constraint handler data */
67 struct SCIP_ConshdlrData
68 {
69  int* checkedsols; /**< an array of solutions that this constraint has already checked */
70  int ncheckedsols; /**< the number of checked solutions */
71  int checkedsolssize; /**< the size of the checked solutions array */
72  SCIP_Bool active; /**< is the constraint handler active? */
73 };
74 
75 /*
76  * Local methods
77  */
78 
79 /** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */
80 static
82  SCIP* scip, /**< the SCIP instance */
83  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
84  SCIP_SOL* sol, /**< primal CIP solution */
85  SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */
86  )
87 {
88  SCIP_CONSHDLRDATA* conshdlrdata;
89  SCIP_SOL* newsol;
90  SCIP_HEUR* heurtrysol;
91  SCIP_BENDERS** benders;
92  SCIP_VAR** auxiliaryvars;
93  int nactivebenders;
94  int nsubproblems;
95  int i;
96  int j;
97  SCIP_Bool success;
98 
99  success = TRUE;
100 
101  /* don't propose new solutions if not in presolve or solving */
103  return SCIP_OKAY;
104 
105  conshdlrdata = SCIPconshdlrGetData(conshdlr);
106  assert(conshdlrdata != NULL);
107 
108  benders = SCIPgetBenders(scip);
109  nactivebenders = SCIPgetNActiveBenders(scip);
110 
111  /* if the solution is NULL, then we create the solution from the LP sol */
112  if( sol != NULL )
113  {
114  assert(type == SCIP_BENDERSENFOTYPE_CHECK);
115  SCIP_CALL( SCIPcreateSolCopy(scip, &newsol, sol) );
116  }
117  else
118  {
119  switch( type )
120  {
122  SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
123  break;
125  SCIP_CALL( SCIPcreatePseudoSol(scip, &newsol, NULL) );
126  break;
128  SCIP_CALL( SCIPcreateRelaxSol(scip, &newsol, NULL) );
129  break;
130  default:
131  SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
132  break;
133  } /*lint !e788*/
134  }
135  SCIP_CALL( SCIPunlinkSol(scip, newsol) );
136 
137  /* looping through all Benders' decompositions to construct the new solution */
138  for( i = 0; i < nactivebenders; i++ )
139  {
140  /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */
141  auxiliaryvars = SCIPbendersGetAuxiliaryVars(benders[i]);
142  nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
143 
144  /* setting the auxiliary variable in the new solution */
145  for( j = 0; j < nsubproblems; j++ )
146  {
147  SCIP_Real objval;
148 
149  objval = SCIPbendersGetSubproblemObjval(benders[i], j);
150 
151  if( SCIPvarGetStatus(auxiliaryvars[j]) == SCIP_VARSTATUS_FIXED
152  && !SCIPisEQ(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
153  {
154  success = FALSE;
155  break;
156  }
157  else if( SCIPisLT(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
158  {
159  SCIP_CALL( SCIPsetSolVal(scip, newsol, auxiliaryvars[j], objval) );
160  }
161  }
162 
163  if( !success )
164  break;
165  }
166 
167  /* if setting the variable values was successful, then we try to add the solution */
168  if( success )
169  {
170  /* checking the size of the checkedsols array and extending it is there is not enough memory */
171  assert(conshdlrdata->ncheckedsols <= conshdlrdata->checkedsolssize);
172  if( conshdlrdata->ncheckedsols + 1 > conshdlrdata->checkedsolssize )
173  {
174  int newsize;
175 
176  newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->ncheckedsols + 1);
177  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) );
178  conshdlrdata->checkedsolssize = newsize;
179  }
180  assert(conshdlrdata->ncheckedsols + 1 <= conshdlrdata->checkedsolssize);
181 
182  /* recording the solution number to avoid checking the solution again */
183  conshdlrdata->checkedsols[conshdlrdata->ncheckedsols] = SCIPsolGetIndex(newsol);
184  conshdlrdata->ncheckedsols++;
185 
186  /* getting the try solution heuristic */
187  heurtrysol = SCIPfindHeur(scip, "trysol");
188 
189  /* passing the new solution to the trysol heuristic */
190  SCIP_CALL( SCIPcheckSol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
191  if ( success )
192  {
193  SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, newsol) );
194  SCIPdebugMsg(scip, "Creating solution was successful.\n");
195  }
196  else
197  {
198  /* the solution might not be feasible, because of additional constraints */
199  SCIPdebugMsg(scip, "Creating solution was not successful.\n");
200  }
201  }
202 
203  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
204 
205  return SCIP_OKAY;
206 }
207 
208 /** enforces Benders' constraints for given solution
209  *
210  * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
211  * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
212  * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
213  * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
214  * integer feasible.
215  *
216  * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
217  * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
218  * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
219  * solution feasibility.
220  */
222  SCIP* scip, /**< the SCIP instance */
223  SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
224  SCIP_CONSHDLR* conshdlr, /**< the constraint handler */
225  SCIP_RESULT* result, /**< the result of the enforcement */
226  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
227  SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */
228  )
229 {
230  SCIP_BENDERS** benders;
231  SCIP_Bool infeasible;
232  SCIP_Bool auxviol;
233  int nactivebenders;
234  int i;
235 
236  assert(scip != NULL);
237  assert(conshdlr != NULL);
238  assert(result != NULL);
239 
240  (*result) = SCIP_FEASIBLE;
241  infeasible = FALSE;
242  auxviol = FALSE;
243 
244  benders = SCIPgetBenders(scip);
245  nactivebenders = SCIPgetNActiveBenders(scip);
246 
247  for( i = 0; i < nactivebenders; i++ )
248  {
249  switch( type )
250  {
252  if( SCIPbendersCutLP(benders[i]) )
253  {
254  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
255  }
256  break;
258  if( SCIPbendersCutRelaxation(benders[i]) )
259  {
260  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) );
261  }
262  break;
264  if( SCIPbendersCutPseudo(benders[i]) )
265  {
266  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
267  }
268  break;
270  SCIPwarningMessage(scip, "The conscheck callback is not supported\n");
271  break;
272  default:
273  break;
274  } /*lint !e788*/
275 
276  /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that
277  * infeasibility of the original problem has been proven or a constraint has been added. If the result
278  * SCIP_DIDNOTRUN is returned, then the next decomposition is checked */
279  if( (*result) != SCIP_FEASIBLE && (*result) != SCIP_DIDNOTRUN )
280  break;
281  }
282 
283  /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */
284  if( checkint )
285  {
286  /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
287  * still need to be updated. This is done by constructing a valid solution. */
288  if( (*result) == SCIP_FEASIBLE && auxviol )
289  {
290  SCIP_CALL( constructValidSolution(scip, conshdlr, sol, type) );
291 
292  (*result) = SCIP_INFEASIBLE;
293  }
294  }
295 
296  /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
297  * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
298  * solution is feasible.
299  */
300  if( (*result) == SCIP_DIDNOTRUN )
301  (*result) = SCIP_FEASIBLE;
302 
303  return SCIP_OKAY;
304 }
305 
306 /*
307  * Callback methods of constraint handler
308  */
309 
310 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
311 static
312 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
313 { /*lint --e{715}*/
314  assert(scip != NULL);
315 
317 
318  *valid = TRUE;
319 
320  return SCIP_OKAY;
321 }
322 
323 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
324 static
325 SCIP_DECL_CONSFREE(consFreeBenders)
326 { /*lint --e{715}*/
327  SCIP_CONSHDLRDATA* conshdlrdata;
328 
329  assert(scip != NULL);
330  assert(conshdlr != NULL);
331 
332  conshdlrdata = SCIPconshdlrGetData(conshdlr);
333  assert(conshdlrdata != NULL);
334 
335  /* freeing the constraint handler data */
336  SCIPfreeMemory(scip, &conshdlrdata);
337 
338  return SCIP_OKAY;
339 }
340 
341 
342 /** initialization method of constraint handler (called after problem was transformed) */
343 static
344 SCIP_DECL_CONSINIT(consInitBenders)
345 { /*lint --e{715}*/
346  SCIP_CONSHDLRDATA* conshdlrdata;
347 
348  assert(scip != NULL);
349  assert(conshdlr != NULL);
350 
351  conshdlrdata = SCIPconshdlrGetData(conshdlr);
352 
353  conshdlrdata->checkedsolssize = DEFAULT_CHECKEDSOLSSIZE;
354  conshdlrdata->ncheckedsols = 0;
355 
356  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) );
357 
358  return SCIP_OKAY;
359 }
360 
361 
362 /** deinitialization method of constraint handler (called before transformed problem is freed) */
363 static
364 SCIP_DECL_CONSEXIT(consExitBenders)
365 { /*lint --e{715}*/
366  SCIP_CONSHDLRDATA* conshdlrdata;
367 
368  assert(scip != NULL);
369  assert(conshdlr != NULL);
370 
371  conshdlrdata = SCIPconshdlrGetData(conshdlr);
372  assert(conshdlrdata != NULL);
373 
374  /* freeing the checked sols array */
375  SCIPfreeBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize);
376 
377  return SCIP_OKAY;
378 }
379 
380 
381 
382 /** constraint enforcing method of constraint handler for LP solutions */
383 static
384 SCIP_DECL_CONSENFOLP(consEnfolpBenders)
385 { /*lint --e{715}*/
386  SCIP_CONSHDLRDATA* conshdlrdata;
387 
388  assert(scip != NULL);
389  assert(conshdlr != NULL);
390 
391  conshdlrdata = SCIPconshdlrGetData(conshdlr);
392  assert(conshdlrdata != NULL);
393 
394  if( conshdlrdata->active )
395  {
397  }
398  else
399  (*result) = SCIP_FEASIBLE;
400 
401  return SCIP_OKAY;
402 }
403 
404 
405 /** constraint enforcing method of constraint handler for relaxation solutions */
406 static
407 SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
408 { /*lint --e{715}*/
409  SCIP_CONSHDLRDATA* conshdlrdata;
410 
411  assert(scip != NULL);
412  assert(conshdlr != NULL);
413 
414  conshdlrdata = SCIPconshdlrGetData(conshdlr);
415  assert(conshdlrdata != NULL);
416 
417  if( conshdlrdata->active )
418  {
420  }
421  else
422  (*result) = SCIP_FEASIBLE;
423 
424  return SCIP_OKAY;
425 }
426 
427 
428 /** constraint enforcing method of constraint handler for pseudo solutions */
429 static
430 SCIP_DECL_CONSENFOPS(consEnfopsBenders)
431 { /*lint --e{715}*/
432  SCIP_CONSHDLRDATA* conshdlrdata;
433 
434  assert(scip != NULL);
435  assert(conshdlr != NULL);
436 
437  conshdlrdata = SCIPconshdlrGetData(conshdlr);
438  assert(conshdlrdata != NULL);
439 
440  if( conshdlrdata->active )
441  {
443  }
444  else
445  (*result) = SCIP_FEASIBLE;
446 
447  return SCIP_OKAY;
448 }
449 
450 
451 /** feasibility check method of constraint handler for integral solutions
452  *
453  * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is
454  * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not
455  * possible to simply update the auxiliary variable values, so a new solution is created.
456  */
457 static
458 SCIP_DECL_CONSCHECK(consCheckBenders)
459 { /*lint --e{715}*/
460  SCIP_CONSHDLRDATA* conshdlrdata;
461  SCIP_BENDERS** benders;
462  int nactivebenders;
463  int solindex;
464  int i;
465  SCIP_Bool performcheck;
466  SCIP_Bool infeasible;
467  SCIP_Bool auxviol;
468 
469  assert(scip != NULL);
470  assert(conshdlr != NULL);
471  assert(result != NULL);
472 
473  (*result) = SCIP_FEASIBLE;
474  performcheck = TRUE;
475  infeasible = FALSE;
476  auxviol = FALSE;
477 
478  conshdlrdata = SCIPconshdlrGetData(conshdlr);
479 
480  /* if the constraint handler is active, then the check must be performed. */
481  if( conshdlrdata->active )
482  {
483  benders = SCIPgetBenders(scip);
484  nactivebenders = SCIPgetNActiveBenders(scip);
485 
486  /* checking if the solution was constructed by this constraint handler */
487  solindex = SCIPsolGetIndex(sol);
488  for( i = 0; i < conshdlrdata->ncheckedsols; i++ )
489  {
490  if( conshdlrdata->checkedsols[i] == solindex )
491  {
492  conshdlrdata->checkedsols[0] = conshdlrdata->checkedsols[conshdlrdata->ncheckedsols - 1];
493  conshdlrdata->ncheckedsols--;
494 
495  performcheck = FALSE;
496  break;
497  }
498  }
499 
500  /* if the solution has not been checked before, then we must perform the check */
501  if( performcheck && nactivebenders > 0 )
502  {
503  for( i = 0; i < nactivebenders; i++ )
504  {
505  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol,
507 
508  /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or
509  * infeasibility is proven. So if the result is not SCIP_FEASIBLE, then the loop is exited */
510  if( (*result) != SCIP_FEASIBLE )
511  break;
512  }
513 
514  /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
515  * still need to be updated. This is done by constructing a valid solution. */
516  if( (*result) == SCIP_FEASIBLE )
517  {
518  if( auxviol )
519  {
520  if( !SCIPsolIsOriginal(sol) )
521  {
523  }
524 
525  if( printreason )
526  SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n");
527 
528  (*result) = SCIP_INFEASIBLE;
529  }
530  }
531 
532  /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
533  * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
534  * solution is feasible.
535  */
536  if( (*result) == SCIP_DIDNOTRUN )
537  (*result) = SCIP_FEASIBLE;
538  }
539  }
540 
541  return SCIP_OKAY;
542 }
543 
544 
545 /** the presolving method for the Benders' decomposition constraint handler
546  *
547  * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the
548  * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are
549  * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the
550  * computed bounds would be identical.
551  */
552 static
553 SCIP_DECL_CONSPRESOL(consPresolBenders)
554 { /*lint --e{715}*/
555  SCIP_CONSHDLRDATA* conshdlrdata;
556  SCIP_BENDERS** benders;
557  int nactivebenders;
558  int nsubproblems;
559  int i;
560  int j;
561 
562  assert(scip != NULL);
563  assert(conshdlr != NULL);
564 
565  (*result) = SCIP_DIDNOTFIND;
566 
567  /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving
568  * step is not performed.
569  */
570  if( SCIPgetSubscipDepth(scip) > 0 )
571  {
572  (*result) = SCIP_DIDNOTRUN;
573  return SCIP_OKAY;
574  }
575 
576  conshdlrdata = SCIPconshdlrGetData(conshdlr);
577  assert(conshdlrdata != NULL);
578 
579  /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */
580  if( conshdlrdata->active )
581  {
582  benders = SCIPgetBenders(scip);
583  nactivebenders = SCIPgetNActiveBenders(scip);
584 
585  /* need to compute the lower bound for all active Benders' decompositions */
586  for( i = 0; i < nactivebenders; i++ )
587  {
588  nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
589 
590  for( j = 0; j < nsubproblems; j++ )
591  {
592  SCIP_VAR* auxiliaryvar;
593  SCIP_Real lowerbound;
594  SCIP_Bool infeasible;
595 
596  infeasible = FALSE;
597 
598  /* computing the lower bound of the subproblem by solving it without any variable fixings */
599  SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) );
600 
601  if( infeasible )
602  {
603  (*result) = SCIP_CUTOFF;
604  break;
605  }
606 
607  /* retrieving the auxiliary variable */
608  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders[i], j);
609 
610  /* only update the lower bound if it is greater than the current lower bound */
611  if( SCIPisGT(scip, lowerbound, SCIPvarGetLbLocal(auxiliaryvar)) )
612  {
613  SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
614  /* updating the lower bound of the auxiliary variable */
615  SCIP_CALL( SCIPchgVarLb(scip, auxiliaryvar, lowerbound) );
616 
617  (*nchgbds)++;
618  (*result) = SCIP_SUCCESS;
619  }
620 
621  /* stores the lower bound for the subproblem */
622  SCIPbendersUpdateSubproblemLowerbound(benders[i], j, lowerbound);
623  }
624 
625  if( (*result) == SCIP_CUTOFF )
626  break;
627  }
628  }
629 
630  return SCIP_OKAY;
631 }
632 
633 /** variable rounding lock method of constraint handler */
634 static
635 SCIP_DECL_CONSLOCK(consLockBenders)
636 { /*lint --e{715}*/
637  return SCIP_OKAY;
638 }
639 
640 
641 /*
642  * constraint specific interface methods
643  */
644 
645 /** creates the handler for Benders' decomposition and includes it in SCIP */
647  SCIP* scip /**< SCIP data structure */
648  )
649 {
650  SCIP_CONSHDLRDATA* conshdlrdata;
651  SCIP_CONSHDLR* conshdlr;
652 
653  /* create benders constraint handler data */
654  conshdlrdata = NULL;
655 
656  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
657 
658  conshdlr = NULL;
659 
660  /* include constraint handler */
663  consEnfolpBenders, consEnfopsBenders, consCheckBenders, consLockBenders,
664  conshdlrdata) );
665  assert(conshdlr != NULL);
666 
667  /* set non-fundamental callbacks via specific setter functions */
668  SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitBenders) );
669  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitBenders) );
670  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenders, NULL) );
671  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenders) );
672  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenders) );
673  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBenders, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
674 
675  /* add Benders' decomposition constraint handler parameters */
677  "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition constraint handler active?",
678  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
679 
680  return SCIP_OKAY;
681 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define CONSHDLR_NAME
Definition: cons_benders.c:48
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4409
constraint handler for Benders&#39; decomposition
#define NULL
Definition: def.h:253
#define CONSHDLR_PRESOLTIMING
Definition: cons_benders.c:56
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
primal heuristic that tries a given solution
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
#define CONSHDLR_ENFOPRIORITY
Definition: cons_benders.c:50
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:307
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:4749
SCIP_BENDERS ** SCIPgetBenders(SCIP *scip)
Definition: scip_benders.c:470
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:165
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition: benders.c:4349
SCIP_EXPORT SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2470
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:122
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define DEFAULT_CHECKEDSOLSSIZE
Definition: cons_benders.c:60
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:4255
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
methods commonly used by primal heuristics
static SCIP_DECL_CONSCHECK(consCheckBenders)
Definition: cons_benders.c:459
static GRAPHNODE ** active
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:47
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4448
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16857
#define DEFAULT_ACTIVE
Definition: cons_benders.c:61
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:524
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:380
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:4359
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1181
#define SCIPdebugMsg
Definition: scip_message.h:69
static SCIP_DECL_CONSINIT(consInitBenders)
Definition: cons_benders.c:345
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:356
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:248
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:424
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:907
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:609
#define CONSHDLR_NEEDSCONS
Definition: cons_benders.c:57
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:283
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition: benders.c:4339
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:404
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4614
static SCIP_DECL_CONSENFOLP(consEnfolpBenders)
Definition: cons_benders.c:385
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:408
SCIP_RETCODE SCIPsolveBendersSubproblems(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: scip_benders.c:584
static SCIP_DECL_CONSPRESOL(consPresolBenders)
Definition: cons_benders.c:554
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:222
static SCIP_DECL_CONSEXIT(consExitBenders)
Definition: cons_benders.c:365
#define SCIP_CALL(x)
Definition: def.h:365
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:584
static SCIP_DECL_CONSLOCK(consLockBenders)
Definition: cons_benders.c:636
#define CONSHDLR_MAXPREROUNDS
Definition: cons_benders.c:55
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:331
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:451
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:90
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
Definition: cons_benders.c:82
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:361
int SCIPgetNActiveBenders(SCIP *scip)
Definition: scip_benders.c:494
static SCIP_DECL_CONSFREE(consFreeBenders)
Definition: cons_benders.c:326
SCIP_EXPORT int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2584
#define CONSHDLR_CHECKPRIORITY
Definition: cons_benders.c:51
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
#define CONSHDLR_EAGERFREQ
Definition: cons_benders.c:52
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:313
#define SCIP_Real
Definition: def.h:164
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:4421
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2289
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3403
SCIP callable library.
static SCIP_DECL_CONSENFOPS(consEnfopsBenders)
Definition: cons_benders.c:431
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:647
#define CONSHDLR_DESC
Definition: cons_benders.c:49