Scippy

SCIP

Solving Constraint Integer Programs

benderscut_int.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-2022 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 benderscut_int.c
17  * @ingroup OTHER_CFILES
18  * @brief Generates a Laporte and Louveaux Benders' decomposition integer cut
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/benderscut_int.h"
25 #include "scip/cons_linear.h"
26 #include "scip/pub_benderscut.h"
27 #include "scip/pub_benders.h"
28 #include "scip/pub_lp.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_paramset.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_benders.h"
34 #include "scip/scip_cons.h"
35 #include "scip/scip_cut.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_lp.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_numerics.h"
41 #include "scip/scip_param.h"
42 #include "scip/scip_prob.h"
43 #include "scip/scip_sol.h"
44 #include <string.h>
45 
46 #define BENDERSCUT_NAME "integer"
47 #define BENDERSCUT_DESC "Laporte and Louveaux Benders' decomposition integer cut"
48 #define BENDERSCUT_PRIORITY 0
49 #define BENDERSCUT_LPCUT FALSE
50 
51 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
52 #define SCIP_DEFAULT_CUTCONSTANT -10000.0
53 
54 /*
55  * Data structures
56  */
57 
58 /** Benders' decomposition cuts data */
59 struct SCIP_BenderscutData
60 {
61  SCIP_BENDERS* benders; /**< the Benders' decomposition data structure */
62  SCIP_Real cutconstant; /**< the constant for computing the integer cuts */
63  SCIP_Real* subprobconstant; /**< the constant for each subproblem used for computing the integer cuts */
64  SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
65  SCIP_Bool* firstcut; /**< flag to indicate that the first cut needs to be generated. */
66  int nsubproblems; /**< the number of subproblems for the Benders' decomposition */
67 };
68 
69 /** method to call, when the priority of a Benders' decomposition was changed */
70 static
71 SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
72 { /*lint --e{715}*/
73  SCIP_BENDERSCUTDATA* benderscutdata;
74  int i;
75 
76  benderscutdata = (SCIP_BENDERSCUTDATA*)SCIPparamGetData(param);
77  assert(benderscutdata != NULL);
78 
79  for( i = 0; i < benderscutdata->nsubproblems; i++ )
80  benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
81 
82  return SCIP_OKAY;
83 }
84 
85 
86 /** creates the Benders' decomposition cut data */
87 static
89  SCIP* scip, /**< the SCIP data structure */
90  SCIP_BENDERSCUTDATA* benderscutdata /**< the Benders' cut data */
91  )
92 {
93  int i;
94 
95  assert(scip != NULL);
96  assert(benderscutdata != NULL);
97 
98  /* allocating the memory for the subproblem constants */
99  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems) );
100  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems) );
101 
102  for( i = 0; i < benderscutdata->nsubproblems; i++ )
103  {
104  benderscutdata->subprobconstant[i] = benderscutdata->cutconstant;
105  benderscutdata->firstcut[i] = TRUE;
106  }
107 
108  return SCIP_OKAY;
109 }
110 
111 /*
112  * Local methods
113  */
114 
115 /** updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable */
116 static
118  SCIP* masterprob, /**< the SCIP instance of the master problem */
119  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
120  SCIP_BENDERSCUTDATA* benderscutdata, /**< the Benders' decomposition cut data */
121  int probnumber /**< the index for the subproblem */
122  )
123 {
124  SCIP_VAR* auxiliaryvar;
125 
126  assert(masterprob != NULL);
127  assert(benders != NULL);
128  assert(benderscutdata != NULL);
129 
130  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
131 
132  /* checking if the subproblem lower bound has been updated. If it is has changed, then firstcut is set to TRUE.
133  * Otherwise, the constant remains the same.
134  */
135  if( SCIPisGT(masterprob, SCIPbendersGetSubproblemLowerbound(benders, probnumber),
136  benderscutdata->subprobconstant[probnumber]) )
137  {
138  benderscutdata->subprobconstant[probnumber] = SCIPbendersGetSubproblemLowerbound(benders, probnumber);
139  benderscutdata->firstcut[probnumber] = TRUE;
140  }
141 
142  /* updating the cut constant if the auxiliary variable global lower bound is greater than the current constant */
143  if( SCIPisGT(masterprob, SCIPvarGetLbGlobal(auxiliaryvar), benderscutdata->subprobconstant[probnumber]) )
144  benderscutdata->subprobconstant[probnumber] = SCIPvarGetLbGlobal(auxiliaryvar);
145 }
146 
147 /** computes a standard Benders' optimality cut from the dual solutions of the LP */
148 static
150  SCIP* masterprob, /**< the SCIP instance of the master problem */
151  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
152  SCIP_SOL* sol, /**< primal CIP solution */
153  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
154  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
155  SCIP_Real cutconstant, /**< the constant value in the integer optimality cut */
156  int probnumber, /**< the number of the pricing problem */
157  SCIP_Bool addcut, /**< indicates whether a cut is created instead of a constraint */
158  SCIP_Bool* success /**< was the cut generation successful? */
159  )
160 {
161  SCIP_VAR** vars;
162  int nvars;
163  SCIP_Real subprobobj; /* the objective function value of the subproblem */
164  SCIP_Real lhs; /* the left hand side of the cut */
165  int i;
166  SCIPdebug( SCIP* subproblem; )
167 
168 #ifndef NDEBUG
169  SCIP_Real verifyobj = 0;
170 #endif
171 
172  assert(masterprob != NULL);
173  assert(benders != NULL);
174  assert(cons != NULL || addcut);
175  assert(row != NULL || !addcut);
176 
177  (*success) = FALSE;
178 
179  /* getting the best solution from the subproblem */
180 
181  subprobobj = SCIPbendersGetSubproblemObjval(benders, probnumber);
182 
183  SCIPdebug( subproblem = SCIPbendersSubproblem(benders, probnumber); )
184  SCIPdebug( SCIPdebugMsg(masterprob, "Subproblem %d - Objective Value: Stored - %g Orig Obj - %g Cut constant - %g\n",
185  probnumber, SCIPbendersGetSubproblemObjval(benders, probnumber), SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem),
186  cutconstant); )
187 
188  nvars = SCIPgetNVars(masterprob);
189  vars = SCIPgetVars(masterprob);
190 
191  /* adding the subproblem objective function value to the lhs */
192  if( addcut )
193  lhs = SCIProwGetLhs(row);
194  else
195  lhs = SCIPgetLhsLinear(masterprob, cons);
196 
197  /* looping over all master problem variables to update the coefficients in the computed cut. */
198  for( i = 0; i < nvars; i++ )
199  {
200  SCIP_VAR* subprobvar;
201  SCIP_Real coef;
202 
203  SCIP_CALL( SCIPgetBendersSubproblemVar(masterprob, benders, vars[i], &subprobvar, probnumber) );
204 
205  /* if there is a corresponding subproblem variable, then the variable will not be NULL. */
206  if( subprobvar != NULL )
207  {
208  /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */
209  if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) )
210  {
211  coef = -(subprobobj - cutconstant);
212  lhs -= (subprobobj - cutconstant);
213  }
214  else
215  coef = (subprobobj - cutconstant);
216 
217  /* adding the variable to the cut. The coefficient is the subproblem objective value */
218  if( addcut )
219  {
220  SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) );
221  }
222  else
223  {
224  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) );
225  }
226  }
227  }
228 
229  lhs += subprobobj;
230 
231  /* if the bound becomes infinite, then the cut generation terminates. */
232  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
233  {
234  (*success) = FALSE;
235  SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
236  return SCIP_OKAY;
237  }
238 
239  /* Update the lhs of the cut */
240  if( addcut )
241  {
242  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
243  }
244  else
245  {
246  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
247  }
248 
249 #ifndef NDEBUG
250  if( addcut )
251  lhs = SCIProwGetLhs(row);
252  else
253  lhs = SCIPgetLhsLinear(masterprob, cons);
254  verifyobj += lhs;
255 
256  if( addcut )
257  verifyobj -= SCIPgetRowSolActivity(masterprob, row, sol);
258  else
259  verifyobj -= SCIPgetActivityLinear(masterprob, cons, sol);
260 #endif
261 
262  assert(SCIPisFeasEQ(masterprob, verifyobj, subprobobj));
263 
264  (*success) = TRUE;
265 
266  return SCIP_OKAY;
267 }
268 
269 
270 /** adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
271  * auxiliary variable is first created and added to the master problem.
272  */
273 static
275  SCIP* masterprob, /**< the SCIP instance of the master problem */
276  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
277  SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */
278  SCIP_ROW* row, /**< the row for the generated cut, can be NULL */
279  int probnumber, /**< the number of the pricing problem */
280  SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */
281  )
282 {
283  SCIP_VAR* auxiliaryvar;
284 
285  assert(masterprob != NULL);
286  assert(benders != NULL);
287  assert(cons != NULL || addcut);
288  assert(row != NULL || !addcut);
289 
290  auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber);
291 
292  /* adding the auxiliary variable to the generated cut */
293  if( addcut )
294  {
295  SCIP_CALL( SCIPaddVarToRow(masterprob, row, auxiliaryvar, 1.0) );
296  }
297  else
298  {
299  SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, auxiliaryvar, 1.0) );
300  }
301 
302  return SCIP_OKAY;
303 }
304 
305 
306 /** generates and applies Benders' cuts */
307 static
309  SCIP* masterprob, /**< the SCIP instance of the master problem */
310  SCIP_BENDERS* benders, /**< the benders' decomposition */
311  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
312  SCIP_SOL* sol, /**< primal CIP solution */
313  int probnumber, /**< the number of the pricing problem */
314  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
315  SCIP_RESULT* result, /**< the result from solving the subproblems */
316  SCIP_Bool initcons /**< is this function called to generate the initial constraint */
317  )
318 {
319  SCIP_BENDERSCUTDATA* benderscutdata;
320  SCIP_CONSHDLR* consbenders;
321  SCIP_CONS* cons;
322  SCIP_ROW* row;
323  char cutname[SCIP_MAXSTRLEN];
324  SCIP_Bool optimal;
325  SCIP_Bool addcut;
326  SCIP_Bool success;
327 
328  assert(masterprob != NULL);
329  assert(benders != NULL);
330  assert(benderscut != NULL);
331  assert(result != NULL);
332 
333  row = NULL;
334  cons = NULL;
335 
336  success = FALSE;
337 
338  /* retrieving the Benders' cut data */
339  benderscutdata = SCIPbenderscutGetData(benderscut);
340 
341  /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be added
342  * to the master problem.
343  */
344  if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE )
345  addcut = FALSE;
346  else
347  addcut = benderscutdata->addcuts;
348 
349  /* retrieving the Benders' decomposition constraint handler */
350  consbenders = SCIPfindConshdlr(masterprob, "benders");
351 
352  /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
353  * objective value of the subproblem
354  */
355  optimal = FALSE;
356  SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) );
357 
358  if( optimal )
359  {
360  (*result) = SCIP_FEASIBLE;
361  SCIPdebugMsg(masterprob, "No <%s> cut added. Current Master Problem Obj: %g\n", BENDERSCUT_NAME,
362  SCIPgetSolOrigObj(masterprob, NULL)*(int)SCIPgetObjsense(masterprob));
363  return SCIP_OKAY;
364  }
365 
366  /* checking whether the subproblem constant is less than the auxiliary variable global lower bound */
367  updateSubproblemCutConstant(masterprob, benders, benderscutdata, probnumber);
368 
369  /* if no integer cuts have been previously generated and the bound on the auxiliary variable is -infinity,
370  * then an initial lower bounding cut is added
371  */
372  if( benderscutdata->firstcut[probnumber]
373  && SCIPisInfinity(masterprob, -SCIPvarGetLbGlobal(SCIPbendersGetAuxiliaryVar(benders, probnumber))) )
374  {
375  benderscutdata->firstcut[probnumber] = FALSE;
376  SCIP_CALL( generateAndApplyBendersIntegerCuts(masterprob, benders, benderscut, sol, probnumber, type, result,
377  TRUE) );
378  }
379 
380  /* setting the name of the generated cut */
381  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "integeroptcut_%d_%" SCIP_LONGINT_FORMAT, probnumber,
382  SCIPbenderscutGetNFound(benderscut) );
383 
384  /* creating an empty row or constraint for the Benders' cut */
385  if( addcut )
386  {
387  SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE,
388  FALSE, TRUE) );
389  }
390  else
391  {
392  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
393  SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) );
394  SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) );
395  }
396 
397  if( initcons )
398  {
399  SCIP_Real lhs;
400 
401  /* adding the subproblem objective function value to the lhs */
402  if( addcut )
403  lhs = SCIProwGetLhs(row);
404  else
405  lhs = SCIPgetLhsLinear(masterprob, cons);
406 
407  lhs += benderscutdata->subprobconstant[probnumber];
408 
409  /* if the bound becomes infinite, then the cut generation terminates. */
410  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) )
411  {
412  success = FALSE;
413  SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n");
414  }
415 
416  /* Update the lhs of the cut */
417  if( addcut )
418  {
419  SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) );
420  }
421  else
422  {
423  SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) );
424  }
425  }
426  else
427  {
428  /* computing the coefficients of the optimality cut */
429  SCIP_CALL( computeStandardIntegerOptCut(masterprob, benders, sol, cons, row,
430  benderscutdata->subprobconstant[probnumber], probnumber, addcut, &success) );
431  }
432 
433  /* if success is FALSE, then there was an error in generating the integer optimality cut. No cut will be added to
434  * the master problem. Otherwise, the constraint is added to the master problem.
435  */
436  if( !success )
437  {
438  (*result) = SCIP_DIDNOTFIND;
439  SCIPdebugMsg(masterprob, "Error in generating Benders' integer optimality cut for problem %d.\n", probnumber);
440  }
441  else
442  {
443  /* adding the auxiliary variable to the optimality cut */
444  SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, cons, row, probnumber, addcut) );
445 
446  /* adding the constraint to the master problem */
447  if( addcut )
448  {
449  SCIP_Bool infeasible;
450 
451  if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX )
452  {
453  SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
454  assert(!infeasible);
455  }
456  else
457  {
458  assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO);
459  SCIP_CALL( SCIPaddPoolCut(masterprob, row) );
460  }
461 
462 #ifdef SCIP_DEBUG
463  SCIP_CALL( SCIPprintRow(masterprob, row, NULL) );
464  SCIPinfoMessage(masterprob, NULL, ";\n");
465 #endif
466 
467  (*result) = SCIP_SEPARATED;
468  }
469  else
470  {
471  SCIP_CALL( SCIPaddCons(masterprob, cons) );
472 
473  SCIPdebugPrintCons(masterprob, cons, NULL);
474 
475  (*result) = SCIP_CONSADDED;
476  }
477  }
478 
479  if( addcut )
480  {
481  /* release the row */
482  SCIP_CALL( SCIPreleaseRow(masterprob, &row) );
483  }
484  else
485  {
486  /* release the constraint */
487  SCIP_CALL( SCIPreleaseCons(masterprob, &cons) );
488  }
489 
490  return SCIP_OKAY;
491 }
492 
493 /*
494  * Callback methods of Benders' decomposition cuts
495  */
496 
497 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
498 static
499 SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
500 { /*lint --e{715}*/
501  SCIP_BENDERSCUTDATA* benderscutdata;
502 
503  assert( benderscut != NULL );
504  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
505 
506  /* free Benders' cut data */
507  benderscutdata = SCIPbenderscutGetData(benderscut);
508  assert( benderscutdata != NULL );
509 
510  SCIPfreeBlockMemory(scip, &benderscutdata);
511 
512  SCIPbenderscutSetData(benderscut, NULL);
513 
514  return SCIP_OKAY;
515 }
516 
517 
518 /** initialization method of Benders' decomposition cuts (called after problem was transformed) */
519 static
520 SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
521 { /*lint --e{715}*/
522  SCIP_BENDERSCUTDATA* benderscutdata;
523 
524  assert( benderscut != NULL );
525  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
526 
527  /* free Benders' cut data */
528  benderscutdata = SCIPbenderscutGetData(benderscut);
529  assert( benderscutdata != NULL );
530 
531  benderscutdata->nsubproblems = SCIPbendersGetNSubproblems(benderscutdata->benders);
532  SCIP_CALL( createBenderscutData(scip, benderscutdata) );
533 
534  return SCIP_OKAY;
535 }
536 
537 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */
538 static
539 SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
540 { /*lint --e{715}*/
541  SCIP_BENDERSCUTDATA* benderscutdata;
542 
543  assert( benderscut != NULL );
544  assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 );
545 
546  /* free Benders' cut data */
547  benderscutdata = SCIPbenderscutGetData(benderscut);
548  assert( benderscutdata != NULL );
549 
550  SCIPfreeBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems);
551  SCIPfreeBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems);
552 
553  return SCIP_OKAY;
554 }
555 
556 /** execution method of Benders' decomposition cuts */
557 static
558 SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)
559 { /*lint --e{715}*/
560  SCIP* subproblem;
561 
562  assert(scip != NULL);
563  assert(benders != NULL);
564  assert(benderscut != NULL);
565  assert(result != NULL);
566 
567  subproblem = SCIPbendersSubproblem(benders, probnumber);
568 
569  if( subproblem == NULL )
570  {
571  SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
572  probnumber, BENDERSCUT_NAME);
573 
574  (*result) = SCIP_DIDNOTRUN;
575  return SCIP_OKAY;
576  }
577 
578  /* it is only possible to generate the Laporte and Louveaux cuts for pure binary master problems */
580  && (!SCIPbendersMasterIsNonlinear(benders)
582  {
583  SCIPinfoMessage(scip, NULL, "The integer optimality cuts can only be applied to problems with a "
584  "pure binary master problem. The integer optimality cuts will be disabled.\n");
585 
586  SCIPbenderscutSetEnabled(benderscut, FALSE);
587 
588  return SCIP_OKAY;
589  }
590 
591  /* the integer subproblem could terminate early if the auxiliary variable value is much greater than the optimal
592  * solution. As such, it is only necessary to generate a cut if the subproblem is OPTIMAL */
593  if( SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL )
594  {
595  /* generating a cut for a given subproblem */
596  SCIP_CALL( generateAndApplyBendersIntegerCuts(scip, benders, benderscut, sol, probnumber, type, result, FALSE) );
597  }
598 
599  return SCIP_OKAY;
600 }
601 
602 
603 /*
604  * Benders' decomposition cuts specific interface methods
605  */
606 
607 /** creates the int Benders' decomposition cuts and includes it in SCIP */
609  SCIP* scip, /**< SCIP data structure */
610  SCIP_BENDERS* benders /**< Benders' decomposition */
611  )
612 {
613  SCIP_BENDERSCUTDATA* benderscutdata;
614  SCIP_BENDERSCUT* benderscut;
616 
617  assert(benders != NULL);
618 
619  /* create int Benders' decomposition cuts data */
620  SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
621  benderscutdata->benders = benders;
622 
623  benderscut = NULL;
624 
625  /* include Benders' decomposition cuts */
627  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecInt, benderscutdata) );
628 
629  assert(benderscut != NULL);
630 
631  /* set non fundamental callbacks via setter functions */
632  SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeInt) );
633  SCIP_CALL( SCIPsetBenderscutInit(scip, benderscut, benderscutInitInt) );
634  SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitInt) );
635 
636  /* add int Benders' decomposition cuts parameters */
637  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/cutsconstant",
639  SCIP_CALL( SCIPaddRealParam(scip, paramname,
640  "the constant term of the integer Benders' cuts.",
641  &benderscutdata->cutconstant, FALSE, SCIP_DEFAULT_CUTCONSTANT, -SCIPinfinity(scip), SCIPinfinity(scip),
642  paramChgdBenderscutintConstant, (SCIP_PARAMDATA*)benderscutdata) );
643 
644  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
646  SCIP_CALL( SCIPaddBoolParam(scip, paramname,
647  "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
648  &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
649 
650  return SCIP_OKAY;
651 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
Generates a Laporte and Louveaux Benders&#39; decomposition integer cut.
SCIP_RETCODE SCIPincludeBenderscutInt(SCIP *scip, SCIP_BENDERS *benders)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:483
SCIP_RETCODE SCIPincludeBenderscutBasic(SCIP *scip, SCIP_BENDERS *benders, SCIP_BENDERSCUT **benderscutptr, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6170
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static SCIP_RETCODE generateAndApplyBendersIntegerCuts(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result, SCIP_Bool initcons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
static SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt)
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:394
static SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant)
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:670
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_MAXSTRLEN
Definition: def.h:293
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition: benders.c:5895
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
#define BENDERSCUT_NAME
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:78
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition: benderscut.c:404
static SCIP_RETCODE createBenderscutData(SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17225
#define FALSE
Definition: def.h:87
public methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
static void updateSubproblemCutConstant(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUTDATA *benderscutdata, int probnumber)
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define BENDERSCUT_PRIORITY
#define BENDERSCUT_DESC
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
SCIP_RETCODE SCIPgetBendersSubproblemVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar, int probnumber)
Definition: scip_benders.c:687
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition: benders.c:6408
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:534
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
#define BENDERSCUT_LPCUT
public methods for numerical tolerances
public methods for handling parameter settings
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip_cons.c:1411
void SCIPbenderscutSetEnabled(SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)
Definition: benderscut.c:584
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
static SCIP_RETCODE computeStandardIntegerOptCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Real cutconstant, int probnumber, SCIP_Bool addcut, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip_cons.c:1386
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPsetBenderscutExit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)))
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
public methods for constraint handler plugins and constraints
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
static SCIP_DECL_BENDERSCUTINIT(benderscutInitInt)
static const char * paramname[]
Definition: lpi_msk.c:5021
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
public methods for LP management
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1574
public methods for cuts and aggregation rows
#define SCIP_DEFAULT_ADDCUTS
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:5949
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2129
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
Definition: scip_benders.c:883
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5939
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
public methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPsetBenderscutInit(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTINIT((*benderscutinit)))
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
general public methods
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6703
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
#define SCIP_Real
Definition: def.h:177
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut, SCIP_DECL_BENDERSCUTFREE((*benderscutfree)))
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1224
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
static SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt)
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
#define SCIP_DEFAULT_CUTCONSTANT
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6131
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
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