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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_benders.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for Benders' decomposition
19  * @author Stephen J. Maher
20  *
21  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
22  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
23  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
24  * respect to the subproblem constraints.
25  *
26  * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
27  * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
28  * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
29  * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
30  *
31  * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
32  * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
33  * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
34  * decomposition algorithm.
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include <assert.h>
40 #include <string.h>
41 
42 #include "scip/scip.h"
43 #include "scip/cons_benders.h"
44 #include "scip/heur_trysol.h"
45 #include "scip/heuristics.h"
46 
47 
48 /* fundamental constraint handler properties */
49 #define CONSHDLR_NAME "benders"
50 #define CONSHDLR_DESC "constraint handler to execute Benders' Decomposition"
51 #define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
52 #define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
53 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
54  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
55 #define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
56 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
57 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
58 
59 
60 #define DEFAULT_CHECKEDSOLSSIZE 20 /**< initial size of the checked sols array */
61 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */
62 
63 /*
64  * Data structures
65  */
66 
67 /** constraint handler data */
68 struct SCIP_ConshdlrData
69 {
70  int* checkedsols; /**< an array of solutions that this constraint has already checked */
71  int ncheckedsols; /**< the number of checked solutions */
72  int checkedsolssize; /**< the size of the checked solutions array */
73  SCIP_Bool active; /**< is the constraint handler active? */
74 };
75 
76 /*
77  * Local methods
78  */
79 
80 /** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */
81 static
83  SCIP* scip, /**< the SCIP instance */
84  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
85  SCIP_SOL* sol, /**< primal CIP solution */
86  SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */
87  )
88 {
89  SCIP_CONSHDLRDATA* conshdlrdata;
90  SCIP_SOL* newsol;
91  SCIP_HEUR* heurtrysol;
92  SCIP_BENDERS** benders;
93  SCIP_VAR** auxiliaryvars;
94  int nactivebenders;
95  int nsubproblems;
96  int i;
97  int j;
98  SCIP_Bool success = TRUE;
99 
100  /* don't propose new solutions if not in presolve or solving */
102  return SCIP_OKAY;
103 
104  conshdlrdata = SCIPconshdlrGetData(conshdlr);
105  assert(conshdlrdata != NULL);
106 
107  benders = SCIPgetBenders(scip);
108  nactivebenders = SCIPgetNActiveBenders(scip);
109 
110  /* if the solution is NULL, then we create the solution from the LP sol */
111  if( sol != NULL )
112  {
113  assert(type == SCIP_BENDERSENFOTYPE_CHECK);
114  SCIP_CALL( SCIPcreateSolCopy(scip, &newsol, sol) );
115  }
116  else
117  {
118  switch( type )
119  {
121  SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
122  break;
124  SCIP_CALL( SCIPcreatePseudoSol(scip, &newsol, NULL) );
125  break;
127  SCIP_CALL( SCIPcreateRelaxSol(scip, &newsol, NULL) );
128  break;
129  default:
130  SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
131  break;
132  } /*lint !e788*/
133  }
134  SCIP_CALL( SCIPunlinkSol(scip, newsol) );
135 
136  /* looping through all Benders' decompositions to construct the new solution */
137  for( i = 0; i < nactivebenders; i++ )
138  {
139  /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */
140  auxiliaryvars = SCIPbendersGetAuxiliaryVars(benders[i]);
141  nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
142 
143  /* setting the auxiliary variable in the new solution */
144  for( j = 0; j < nsubproblems; j++ )
145  {
146  SCIP_Real objval;
147 
148  objval = SCIPbendersGetSubproblemObjval(benders[i], j);
149 
150  if( SCIPvarGetStatus(auxiliaryvars[j]) == SCIP_VARSTATUS_FIXED
151  && !SCIPisEQ(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
152  {
153  success = FALSE;
154  break;
155  }
156  else if( SCIPisLT(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
157  {
158  SCIP_CALL( SCIPsetSolVal(scip, newsol, auxiliaryvars[j], objval) );
159  }
160  }
161 
162  if( !success )
163  break;
164  }
165 
166  /* if setting the variable values was successful, then we try to add the solution */
167  if( success ) /*lint !e774*/
168  {
169  /* checking the size of the checkedsols array and extending it is there is not enough memory */
170  assert(conshdlrdata->ncheckedsols <= conshdlrdata->checkedsolssize);
171  if( conshdlrdata->ncheckedsols + 1 > conshdlrdata->checkedsolssize )
172  {
173  int newsize;
174 
175  newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->ncheckedsols + 1);
176  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) );
177  conshdlrdata->checkedsolssize = newsize;
178  }
179  assert(conshdlrdata->ncheckedsols + 1 <= conshdlrdata->checkedsolssize);
180 
181  /* recording the solution number to avoid checking the solution again */
182  conshdlrdata->checkedsols[conshdlrdata->ncheckedsols] = SCIPsolGetIndex(newsol);
183  conshdlrdata->ncheckedsols++;
184 
185  /* getting the try solution heuristic */
186  heurtrysol = SCIPfindHeur(scip, "trysol");
187 
188  /* passing the new solution to the trysol heuristic */
189  SCIP_CALL( SCIPcheckSol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
190  if ( success )
191  {
192  SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, newsol) );
193  SCIPdebugMsg(scip, "Creating solution was successful.\n");
194  }
195  else
196  {
197  /* the solution might not be feasible, because of additional constraints */
198  SCIPdebugMsg(scip, "Creating solution was not successful.\n");
199  }
200  }
201 
202  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
203 
204  return SCIP_OKAY;
205 }
206 
207 /** checks the Benders' decomposition auxiliary variables for unboundedness. */
208 static
210  SCIP* scip, /**< the SCIP data structure */
211  SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
212  SCIP_SOL* sol /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
213  )
214 {
215  int nsubproblems;
216  SCIP_Bool unbounded = FALSE;
217  int i;
218 
219  assert(scip != NULL);
220  assert(benders != NULL);
221 
222  nsubproblems = SCIPbendersGetNSubproblems(benders);
223 
224  /* checking the auxiliary variable values for unboundedness */
225  for( i = 0; i < nsubproblems; i++ )
226  {
227  if( SCIPisInfinity(scip, SCIPgetBendersAuxiliaryVarVal(scip, benders, sol, i))
228  || SCIPisInfinity(scip, -SCIPgetBendersAuxiliaryVarVal(scip, benders, sol, i)) )
229  {
230  unbounded = TRUE;
231  break;
232  }
233  }
234 
235  return unbounded;
236 }
237 
238 /** enforces Benders' constraints for given solution
239  *
240  * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
241  * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
242  * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
243  * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
244  * integer feasible.
245  *
246  * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
247  * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
248  * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
249  * solution feasibility.
250  */
252  SCIP* scip, /**< the SCIP instance */
253  SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
254  SCIP_CONSHDLR* conshdlr, /**< the constraint handler */
255  SCIP_RESULT* result, /**< the result of the enforcement */
256  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
257  SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */
258  )
259 {
260  SCIP_BENDERS** benders;
261  SCIP_Bool infeasible;
262  SCIP_Bool auxviol;
263  int nactivebenders;
264  int i;
265 
266  assert(scip != NULL);
267  assert(conshdlr != NULL);
268  assert(result != NULL);
269 
270  (*result) = SCIP_FEASIBLE;
271  infeasible = FALSE;
272  auxviol = FALSE;
273 
274  benders = SCIPgetBenders(scip);
275  nactivebenders = SCIPgetNActiveBenders(scip);
276 
277  for( i = 0; i < nactivebenders; i++ )
278  {
279  switch( type )
280  {
282  if( SCIPbendersCutLP(benders[i]) )
283  {
284  SCIP_Bool unbounded = FALSE;
285 
286  /* if the solution is unbounded, then it may not be possible to generate any Benders' decomposition
287  * cuts. If the unboundedness is from the auxiliary variables, then cuts are required. Otherwise, if
288  * the unboundedness comes from original variables, then the unboundedness needs to be handled by other
289  * constraint handlers or the problem is reported as unbounded
290  * */
292  {
293  if( !unboundedAuxiliaryVariables(scip, benders[i], NULL) )
294  {
295  (*result) = SCIP_FEASIBLE;
296  auxviol = FALSE;
297  unbounded = TRUE;
298  }
299  }
300 
301  if( !unbounded )
302  {
303  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
304  }
305  }
306  break;
308  if( SCIPbendersCutRelaxation(benders[i]) )
309  {
310  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) );
311  }
312  break;
314  if( SCIPbendersCutPseudo(benders[i]) )
315  {
316  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
317  }
318  break;
320  SCIPwarningMessage(scip, "The conscheck callback is not supported\n");
321  break;
322  default:
323  break;
324  } /*lint !e788*/
325 
326  /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that
327  * infeasibility of the original problem has been proven or a constraint has been added. If the result
328  * SCIP_DIDNOTRUN is returned, then the next decomposition is checked */
329  if( (*result) != SCIP_FEASIBLE && (*result) != SCIP_DIDNOTRUN )
330  break;
331  }
332 
333  /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */
334  if( checkint )
335  {
336  /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
337  * still need to be updated. This is done by constructing a valid solution. */
338  if( (*result) == SCIP_FEASIBLE && auxviol )
339  {
340  SCIP_CALL( constructValidSolution(scip, conshdlr, sol, type) );
341 
342  (*result) = SCIP_INFEASIBLE;
343  }
344  }
345 
346  /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
347  * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
348  * solution is feasible.
349  */
350  if( (*result) == SCIP_DIDNOTRUN )
351  (*result) = SCIP_FEASIBLE;
352 
353  return SCIP_OKAY;
354 }
355 
356 /*
357  * Callback methods of constraint handler
358  */
359 
360 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
361 static
362 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
363 { /*lint --e{715}*/
364  assert(scip != NULL);
365 
367 
368  *valid = TRUE;
369 
370  return SCIP_OKAY;
371 }
372 
373 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
374 static
375 SCIP_DECL_CONSFREE(consFreeBenders)
376 { /*lint --e{715}*/
377  SCIP_CONSHDLRDATA* conshdlrdata;
378 
379  assert(scip != NULL);
380  assert(conshdlr != NULL);
381 
382  conshdlrdata = SCIPconshdlrGetData(conshdlr);
383  assert(conshdlrdata != NULL);
384 
385  /* freeing the constraint handler data */
386  SCIPfreeMemory(scip, &conshdlrdata);
387 
388  return SCIP_OKAY;
389 }
390 
391 
392 /** initialization method of constraint handler (called after problem was transformed) */
393 static
394 SCIP_DECL_CONSINIT(consInitBenders)
395 { /*lint --e{715}*/
396  SCIP_CONSHDLRDATA* conshdlrdata;
397 
398  assert(scip != NULL);
399  assert(conshdlr != NULL);
400 
401  conshdlrdata = SCIPconshdlrGetData(conshdlr);
402 
403  conshdlrdata->checkedsolssize = DEFAULT_CHECKEDSOLSSIZE;
404  conshdlrdata->ncheckedsols = 0;
405 
406  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) );
407 
408  return SCIP_OKAY;
409 }
410 
411 
412 /** deinitialization method of constraint handler (called before transformed problem is freed) */
413 static
414 SCIP_DECL_CONSEXIT(consExitBenders)
415 { /*lint --e{715}*/
416  SCIP_CONSHDLRDATA* conshdlrdata;
417 
418  assert(scip != NULL);
419  assert(conshdlr != NULL);
420 
421  conshdlrdata = SCIPconshdlrGetData(conshdlr);
422  assert(conshdlrdata != NULL);
423 
424  /* freeing the checked sols array */
425  SCIPfreeBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize);
426 
427  return SCIP_OKAY;
428 }
429 
430 
431 
432 /** constraint enforcing method of constraint handler for LP solutions */
433 static
434 SCIP_DECL_CONSENFOLP(consEnfolpBenders)
435 { /*lint --e{715}*/
436  SCIP_CONSHDLRDATA* conshdlrdata;
437 
438  assert(scip != NULL);
439  assert(conshdlr != NULL);
440 
441  conshdlrdata = SCIPconshdlrGetData(conshdlr);
442  assert(conshdlrdata != NULL);
443 
444  if( conshdlrdata->active )
445  {
447  }
448  else
449  (*result) = SCIP_FEASIBLE;
450 
451  return SCIP_OKAY;
452 }
453 
454 
455 /** constraint enforcing method of constraint handler for relaxation solutions */
456 static
457 SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
458 { /*lint --e{715}*/
459  SCIP_CONSHDLRDATA* conshdlrdata;
460 
461  assert(scip != NULL);
462  assert(conshdlr != NULL);
463 
464  conshdlrdata = SCIPconshdlrGetData(conshdlr);
465  assert(conshdlrdata != NULL);
466 
467  if( conshdlrdata->active )
468  {
470  }
471  else
472  (*result) = SCIP_FEASIBLE;
473 
474  return SCIP_OKAY;
475 }
476 
477 
478 /** constraint enforcing method of constraint handler for pseudo solutions */
479 static
480 SCIP_DECL_CONSENFOPS(consEnfopsBenders)
481 { /*lint --e{715}*/
482  SCIP_CONSHDLRDATA* conshdlrdata;
483 
484  assert(scip != NULL);
485  assert(conshdlr != NULL);
486 
487  conshdlrdata = SCIPconshdlrGetData(conshdlr);
488  assert(conshdlrdata != NULL);
489 
490  if( conshdlrdata->active )
491  {
493  }
494  else
495  (*result) = SCIP_FEASIBLE;
496 
497  return SCIP_OKAY;
498 }
499 
500 
501 /** feasibility check method of constraint handler for integral solutions
502  *
503  * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is
504  * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not
505  * possible to simply update the auxiliary variable values, so a new solution is created.
506  */
507 static
508 SCIP_DECL_CONSCHECK(consCheckBenders)
509 { /*lint --e{715}*/
510  SCIP_CONSHDLRDATA* conshdlrdata;
511  SCIP_BENDERS** benders;
512  int nactivebenders;
513  int solindex;
514  int i;
515  SCIP_Bool performcheck;
516  SCIP_Bool infeasible;
517  SCIP_Bool auxviol;
518 
519  assert(scip != NULL);
520  assert(conshdlr != NULL);
521  assert(result != NULL);
522 
523  (*result) = SCIP_FEASIBLE;
524  performcheck = TRUE;
525  infeasible = FALSE;
526  auxviol = FALSE;
527 
528  conshdlrdata = SCIPconshdlrGetData(conshdlr);
529 
530  /* if the constraint handler is active, then the check must be performed. */
531  if( conshdlrdata->active )
532  {
533  benders = SCIPgetBenders(scip);
534  nactivebenders = SCIPgetNActiveBenders(scip);
535 
536  /* checking if the solution was constructed by this constraint handler */
537  solindex = SCIPsolGetIndex(sol);
538  for( i = 0; i < conshdlrdata->ncheckedsols; i++ )
539  {
540  if( conshdlrdata->checkedsols[i] == solindex )
541  {
542  conshdlrdata->checkedsols[0] = conshdlrdata->checkedsols[conshdlrdata->ncheckedsols - 1];
543  conshdlrdata->ncheckedsols--;
544 
545  performcheck = FALSE;
546  break;
547  }
548  }
549 
550  /* if the solution has not been checked before, then we must perform the check */
551  if( performcheck && nactivebenders > 0 )
552  {
553  for( i = 0; i < nactivebenders; i++ )
554  {
555  SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol,
557 
558  /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or
559  * infeasibility is proven. So if the result is not SCIP_FEASIBLE, then the loop is exited */
560  if( (*result) != SCIP_FEASIBLE )
561  break;
562  }
563 
564  /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
565  * still need to be updated. This is done by constructing a valid solution. */
566  if( (*result) == SCIP_FEASIBLE )
567  {
568  if( auxviol )
569  {
570  if( !SCIPsolIsOriginal(sol) )
571  {
573  }
574 
575  if( printreason )
576  SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n");
577 
578  (*result) = SCIP_INFEASIBLE;
579  }
580  }
581 
582  /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
583  * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
584  * solution is feasible.
585  */
586  if( (*result) == SCIP_DIDNOTRUN )
587  (*result) = SCIP_FEASIBLE;
588  }
589  }
590 
591  return SCIP_OKAY;
592 }
593 
594 
595 /** the presolving method for the Benders' decomposition constraint handler
596  *
597  * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the
598  * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are
599  * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the
600  * computed bounds would be identical.
601  */
602 static
603 SCIP_DECL_CONSPRESOL(consPresolBenders)
604 { /*lint --e{715}*/
605  SCIP_CONSHDLRDATA* conshdlrdata;
606  SCIP_BENDERS** benders;
607  int nactivebenders;
608  int nsubproblems;
609  int i;
610  int j;
611 
612  assert(scip != NULL);
613  assert(conshdlr != NULL);
614 
615  (*result) = SCIP_DIDNOTFIND;
616 
617  /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving
618  * step is not performed.
619  */
620  if( SCIPgetSubscipDepth(scip) > 0 )
621  {
622  (*result) = SCIP_DIDNOTRUN;
623  return SCIP_OKAY;
624  }
625 
626  conshdlrdata = SCIPconshdlrGetData(conshdlr);
627  assert(conshdlrdata != NULL);
628 
629  /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */
630  if( conshdlrdata->active )
631  {
632  benders = SCIPgetBenders(scip);
633  nactivebenders = SCIPgetNActiveBenders(scip);
634 
635  /* need to compute the lower bound for all active Benders' decompositions */
636  for( i = 0; i < nactivebenders; i++ )
637  {
638  nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
639 
640  for( j = 0; j < nsubproblems; j++ )
641  {
642  SCIP_VAR* auxiliaryvar;
643  SCIP_Real lowerbound;
644  SCIP_Bool infeasible;
645 
646  infeasible = FALSE;
647 
648  /* computing the lower bound of the subproblem by solving it without any variable fixings */
649  SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) );
650 
651  if( infeasible )
652  {
653  (*result) = SCIP_CUTOFF;
654  break;
655  }
656 
657  /* retrieving the auxiliary variable */
658  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders[i], j);
659 
660  /* only update the lower bound if it is greater than the current lower bound */
661  if( SCIPisGT(scip, lowerbound, SCIPvarGetLbLocal(auxiliaryvar)) )
662  {
663  SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
664  /* updating the lower bound of the auxiliary variable */
665  SCIP_CALL( SCIPchgVarLb(scip, auxiliaryvar, lowerbound) );
666 
667  (*nchgbds)++;
668  (*result) = SCIP_SUCCESS;
669  }
670 
671  /* stores the lower bound for the subproblem */
672  SCIPbendersUpdateSubproblemLowerbound(benders[i], j, lowerbound);
673  }
674 
675  if( (*result) == SCIP_CUTOFF )
676  break;
677  }
678  }
679 
680  return SCIP_OKAY;
681 }
682 
683 /** variable rounding lock method of constraint handler
684  * The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition
685  * constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock.
686  * The master problem variables require locks in both directions because the coefficients in all potential Benders'
687  * cuts are not known in general.
688  */
689 static
690 SCIP_DECL_CONSLOCK(consLockBenders)
691 { /*lint --e{715}*/
692  SCIP_CONSHDLRDATA* conshdlrdata;
693  SCIP_BENDERS** benders;
694  SCIP_VAR** vars;
695  int nactivebenders;
696  int nsubproblems;
697  int nvars;
698  int i;
699  int j;
700 
701  assert(scip != NULL);
702  assert(conshdlr != NULL);
703  assert(locktype == SCIP_LOCKTYPE_MODEL);
704 
705  conshdlrdata = SCIPconshdlrGetData(conshdlr);
706  assert(conshdlrdata != NULL);
707 
708  /* the locks should only be added if the Benders' decomposition constraint handler has been activated */
709  if( conshdlrdata->active )
710  {
711  benders = SCIPgetBenders(scip);
712  nactivebenders = SCIPgetNActiveBenders(scip);
713 
714  /* retrieving the master problem variables */
715  SCIP_CALL( SCIPgetOrigVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
716 
717  /* need to compute the lower bound for all active Benders' decompositions */
718  for( i = 0; i < nactivebenders; i++ )
719  {
720  nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
721 
722  /* if the auxiliary variable exists, then we need to add a down lock. Initially, a down lock is added to all
723  * auxiliary variables during creating. This is because the creation of auxiliary variable occurs after
724  * CONS_LOCK is called. The inclusion of the auxiliary variables in this function is to cover the case if locks
725  * are added or removed after presolving.
726  */
727  for( j = 0; j < nsubproblems; j++ )
728  {
729  SCIP_VAR* auxvar;
730 
731  auxvar = SCIPbendersGetAuxiliaryVar(benders[i], j);
732 
733  if( auxvar != NULL )
734  {
735  SCIP_CALL( SCIPaddVarLocksType(scip, auxvar, locktype, nlockspos, nlocksneg) );
736  }
737  }
738 
739  /* adding up and down locks for all master problem variables. Since the locks for all constraint handlers
740  * without constraints, no auxiliary variables have been added. As such, all variables are master variables.
741  */
742  for( j = 0; j < nvars; j++ )
743  {
744  SCIP_CALL( SCIPaddVarLocksType(scip, vars[j], locktype, (nlockspos + nlocksneg)*nsubproblems,
745  (nlockspos + nlocksneg)*nsubproblems) );
746  }
747  }
748  }
749 
750  return SCIP_OKAY;
751 }
752 
753 
754 /*
755  * constraint specific interface methods
756  */
757 
758 /** creates the handler for Benders' decomposition and includes it in SCIP */
760  SCIP* scip /**< SCIP data structure */
761  )
762 {
763  SCIP_CONSHDLRDATA* conshdlrdata;
764  SCIP_CONSHDLR* conshdlr;
765 
766  /* create benders constraint handler data */
767  conshdlrdata = NULL;
768 
769  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
770 
771  conshdlr = NULL;
772 
773  /* include constraint handler */
776  consEnfolpBenders, consEnfopsBenders, consCheckBenders, consLockBenders,
777  conshdlrdata) );
778  assert(conshdlr != NULL);
779 
780  /* set non-fundamental callbacks via specific setter functions */
781  SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitBenders) );
782  SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitBenders) );
783  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenders, NULL) );
784  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenders) );
785  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenders) );
786  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBenders, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
787 
788  /* add Benders' decomposition constraint handler parameters */
790  "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition constraint handler active?",
791  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
792 
793  return SCIP_OKAY;
794 }
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:49
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6132
constraint handler for Benders&#39; decomposition
#define CONSHDLR_PRESOLTIMING
Definition: cons_benders.c:57
#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:1213
#define CONSHDLR_ENFOPRIORITY
Definition: cons_benders.c:51
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6685
SCIP_BENDERS ** SCIPgetBenders(SCIP *scip)
Definition: scip_benders.c:499
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:166
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4263
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition: benders.c:6064
SCIP_EXPORT SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2521
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
#define DEFAULT_CHECKEDSOLSSIZE
Definition: cons_benders.c:61
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5940
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
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:509
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:48
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6171
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17131
#define DEFAULT_ACTIVE
Definition: cons_benders.c:62
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:525
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:381
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:922
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6074
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1182
#define SCIPdebugMsg
Definition: scip_message.h:69
static SCIP_DECL_CONSINIT(consInitBenders)
Definition: cons_benders.c:395
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:425
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
#define CONSHDLR_NEEDSCONS
Definition: cons_benders.c:58
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:284
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition: benders.c:6054
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:405
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4677
static SCIP_DECL_CONSENFOLP(consEnfolpBenders)
Definition: cons_benders.c:435
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:458
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:613
static SCIP_DECL_CONSPRESOL(consPresolBenders)
Definition: cons_benders.c:604
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:252
static SCIP_DECL_CONSEXIT(consExitBenders)
Definition: cons_benders.c:415
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:585
static SCIP_DECL_CONSLOCK(consLockBenders)
Definition: cons_benders.c:691
#define CONSHDLR_MAXPREROUNDS
Definition: cons_benders.c:56
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
#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:332
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:452
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:91
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
Definition: cons_benders.c:83
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:362
int SCIPgetNActiveBenders(SCIP *scip)
Definition: scip_benders.c:523
static SCIP_DECL_CONSFREE(consFreeBenders)
Definition: cons_benders.c:376
SCIP_EXPORT int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
#define CONSHDLR_CHECKPRIORITY
Definition: cons_benders.c:52
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:950
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
#define CONSHDLR_EAGERFREQ
Definition: cons_benders.c:53
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:363
#define SCIP_Real
Definition: def.h:163
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6144
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:55
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
Definition: cons_benders.c:210
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2548
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:3440
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2351
SCIP callable library.
static SCIP_DECL_CONSENFOPS(consEnfopsBenders)
Definition: cons_benders.c:481
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:760
#define CONSHDLR_DESC
Definition: cons_benders.c:50