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