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