1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
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
97   	SCIP_RETCODE createBenderscutData(
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
126  	void updateSubproblemCutConstant(
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
158  	SCIP_RETCODE computeStandardIntegerOptCut(
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
283  	SCIP_RETCODE addAuxiliaryVariableToCut(
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
317  	SCIP_RETCODE generateAndApplyBendersIntegerCuts(
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 */
588  	   if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders))
589  	      && (!SCIPbendersMasterIsNonlinear(benders)
590  	         || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) )
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 */
617  	SCIP_RETCODE SCIPincludeBenderscutInt(
618  	   SCIP*                 scip,               /**< SCIP data structure */
619  	   SCIP_BENDERS*         benders             /**< Benders' decomposition */
620  	   )
621  	{
622  	   SCIP_BENDERSCUTDATA* benderscutdata;
623  	   SCIP_BENDERSCUT* benderscut;
624  	   char paramname[SCIP_MAXSTRLEN];
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 */
635  	   SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC,
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",
647  	      SCIPbendersGetName(benders), BENDERSCUT_NAME);
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",
654  	      SCIPbendersGetName(benders), BENDERSCUT_NAME);
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  	}
661