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