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_components.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for handling independent components
28   	 * @author Gerald Gamrath
29   	 *
30   	 * This constraint handler looks for independent components.
31   	 */
32   	/*#define DETAILED_OUTPUT*/
33   	/*#define SCIP_DEBUG*/
34   	/*#define SCIP_MORE_DEBUG*/
35   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36   	
37   	#include "blockmemshell/memory.h"
38   	#include "scip/cons_components.h"
39   	#include "scip/debug.h"
40   	#include "scip/pub_cons.h"
41   	#include "scip/pub_heur.h"
42   	#include "scip/pub_message.h"
43   	#include "scip/pub_misc.h"
44   	#include "scip/pub_misc_sort.h"
45   	#include "scip/pub_sol.h"
46   	#include "scip/pub_tree.h"
47   	#include "scip/pub_var.h"
48   	#include "scip/scip_cons.h"
49   	#include "scip/scip_copy.h"
50   	#include "scip/scip_datastructures.h"
51   	#include "scip/scip_general.h"
52   	#include "scip/scip_heur.h"
53   	#include "scip/scip_mem.h"
54   	#include "scip/scip_message.h"
55   	#include "scip/scip_numerics.h"
56   	#include "scip/scip_param.h"
57   	#include "scip/scip_pricer.h"
58   	#include "scip/scip_prob.h"
59   	#include "scip/scip_probing.h"
60   	#include "scip/scip_sol.h"
61   	#include "scip/scip_solve.h"
62   	#include "scip/scip_solvingstats.h"
63   	#include "scip/scip_timing.h"
64   	#include "scip/scip_tree.h"
65   	#include "scip/scip_var.h"
66   	#include <string.h>
67   	
68   	#define CONSHDLR_NAME          "components"
69   	#define CONSHDLR_DESC          "independent components constraint handler"
70   	#define CONSHDLR_ENFOPRIORITY         0 /**< priority of the constraint handler for constraint enforcing */
71   	#define CONSHDLR_CHECKPRIORITY -9999999 /**< priority of the constraint handler for checking feasibility */
72   	#define CONSHDLR_EAGERFREQ           -1 /**< frequency for using all instead of only the useful constraints in separation,
73   	                                         *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
74   	#define CONSHDLR_NEEDSCONS        FALSE /**< should the constraint handler be skipped, if no constraints are available? */
75   	
76   	#define CONSHDLR_PROPFREQ             1 /**< frequency for propagating domains; zero means only preprocessing propagation */
77   	#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
78   	#define CONSHDLR_DELAYPROP         TRUE /**< should propagation method be delayed, if other propagators found reductions? */
79   	
80   	#define CONSHDLR_PRESOLTIMING    SCIP_PRESOLTIMING_FINAL  /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
81   	#define CONSHDLR_PROP_TIMING     SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/
82   	
83   	#define DEFAULT_MAXDEPTH             -1      /**< maximum depth of a node to run components detection (-1: disable component detection during solving) */
84   	#define DEFAULT_MAXINTVARS          500      /**< maximum number of integer (or binary) variables to solve a subproblem directly in presolving (-1: no solving) */
85   	#define DEFAULT_MINSIZE              50      /**< minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound */
86   	#define DEFAULT_MINRELSIZE          0.1      /**< minimum relative size (in terms of variables) to solve a component individually during branch-and-bound */
87   	#define DEFAULT_NODELIMIT       10000LL      /**< maximum number of nodes to be solved in subproblems during presolving */
88   	#define DEFAULT_INTFACTOR           1.0      /**< the weight of an integer variable compared to binary variables */
89   	#define DEFAULT_FEASTOLFACTOR       1.0      /**< default value for parameter to increase the feasibility tolerance in all sub-SCIPs */
90   	
91   	/*
92   	 * Data structures
93   	 */
94   	
95   	/** data related to one problem (see below) */
96   	typedef struct Problem PROBLEM;
97   	
98   	/** data related to one component */
99   	typedef struct Component
100  	{
101  	   PROBLEM*              problem;            /**< the problem this component belongs to */
102  	   SCIP*                 subscip;            /**< sub-SCIP representing the component */
103  	   SCIP_SOL*             workingsol;         /**< working solution for transferring solutions into the sub-SCIP */
104  	   SCIP_VAR**            vars;               /**< variables belonging to this component (in complete problem) */
105  	   SCIP_VAR**            subvars;            /**< variables belonging to this component (in subscip) */
106  	   SCIP_VAR**            fixedvars;          /**< variables in the original SCIP which were copied while copying the component's
107  	                                              *   constraints, but do not count to the subvars, because they were locally fixed */
108  	   SCIP_VAR**            fixedsubvars;       /**< variables in the sub-SCIP which were copied while copying the component's
109  	                                              *   constraints, but do not count to the subvars, because they were locally fixed */
110  	   SCIP_Real             fixedvarsobjsum;    /**< objective contribution of all locally fixed variables */
111  	   SCIP_Real             lastdualbound;      /**< dual bound after last optimization call for this component */
112  	   SCIP_Real             lastprimalbound;    /**< primal bound after last optimization call for this component */
113  	   SCIP_STATUS           laststatus;         /**< solution status of last optimization call for the sub-SCIP of this component */
114  	   SCIP_Bool             solved;             /**< was this component solved already? */
115  	   int                   ncalls;             /**< number of optimization calls for this component */
116  	   int                   lastsolindex;       /**< index of best solution after last optimization call for this component */
117  	   int                   lastbestsolindex;   /**< index of last best solution transferred to this component from the main problem */
118  	   int                   nvars;              /**< number of variables belonging to this component */
119  	   int                   nfixedvars;         /**< number of fixed variables copied during constraint copying */
120  	   int                   fixedvarssize;      /**< size of fixedvars and fixedsubvars arrays */
121  	   int                   number;             /**< component number */
122  	} COMPONENT;
123  	
124  	/** data related to one problem
125  	 *  (corresponding to one node in the branch-and-bound tree and consisting of multiple components)
126  	 */
127  	struct Problem
128  	{
129  	   SCIP*                 scip;               /**< the SCIP instance this problem belongs to */
130  	   COMPONENT*            components;         /**< independent components into which the problem can be divided */
131  	   SCIP_PQUEUE*          compqueue;          /**< priority queue for components */
132  	   SCIP_SOL*             bestsol;            /**< best solution found so far for the problem */
133  	   char*                 name;               /**< name of the problem */
134  	   SCIP_Real             fixedvarsobjsum;    /**< objective contribution of all locally fixed variables */
135  	   SCIP_Real             lowerbound;         /**< lower bound of the problem */
136  	   int                   ncomponents;        /**< number of independent components into which the problem can be divided */
137  	   int                   componentssize;     /**< size of components array */
138  	   int                   nfeascomps;         /**< number of components for which a feasible solution was found */
139  	   int                   nsolvedcomps;       /**< number of components solved to optimality */
140  	   int                   nlowerboundinf;     /**< number of components with lower bound equal to -infinity */
141  	};
142  	
143  	
144  	/** constraint handler data */
145  	struct SCIP_ConshdlrData
146  	{
147  	   SCIP_Longint          nodelimit;          /**< maximum number of nodes to be solved in subproblems */
148  	   SCIP_Real             intfactor;          /**< the weight of an integer variable compared to binary variables */
149  	   SCIP_Real             feastolfactor;      /**< parameter to increase the feasibility tolerance in all sub-SCIPs */
150  	   int                   maxintvars;         /**< maximum number of integer (or binary) variables to solve a subproblem
151  	                                              *   directly (-1: no solving) */
152  	   int                   maxdepth;           /**< maximum depth of a node to run components detection (-1: disable
153  	                                              *   component detection during solving) */
154  	   int                   minsize;            /**< minimum absolute size (in terms of variables) to solve a component
155  	                                              *   individually during branch-and-bound */
156  	   SCIP_Real             minrelsize;         /**< minimum relative size (in terms of variables) to solve a component
157  	                                              *   individually during branch-and-bound */
158  	   int                   subscipdepth;       /**< depth offset of the current (sub-)problem compared to the original
159  	                                              *   problem */
160  	};
161  	
162  	
163  	/** comparison method for sorting components */
164  	static
165  	SCIP_DECL_SORTPTRCOMP(componentSort)
166  	{
167  	   SCIP* scip;
168  	   COMPONENT* comp1;
169  	   COMPONENT* comp2;
170  	   SCIP_Real gap1;
171  	   SCIP_Real gap2;
172  	
173  	   assert(elem1 != NULL);
174  	   assert(elem2 != NULL);
175  	
176  	   comp1 = (COMPONENT*)elem1;
177  	   comp2 = (COMPONENT*)elem2;
178  	
179  	   if( comp1->ncalls == 0 )
180  	      if( comp2->ncalls == 0 )
181  	         return comp1->number - comp2->number;
182  	      else
183  	         return -1;
184  	   else if( comp2->ncalls == 0 )
185  	      return 1;
186  	
187  	   /* the main sorting criterion is the absolute gap; however, we devide it by the number of solving calls for this
188  	    * component to diversify the search if one component does not improve
189  	    * @todo investigate other sorting criteria
190  	    */
191  	   gap1 = SQR(comp1->lastprimalbound - comp1->lastdualbound) / comp1->ncalls;
192  	   gap2 = SQR(comp2->lastprimalbound - comp2->lastdualbound) / comp2->ncalls;
193  	
194  	   assert(comp1->problem != NULL);
195  	   assert(comp1->problem == comp2->problem);
196  	   assert(comp1->problem->scip == comp2->problem->scip);
197  	
198  	   scip = comp1->problem->scip;
199  	   assert(scip != NULL);
200  	
201  	   if( SCIPisFeasGT(scip, gap1, gap2) )
202  	      return -1;
203  	   else if( SCIPisFeasLT(scip, gap1, gap2) )
204  	      return +1;
205  	   else
206  	      return comp1->number - comp2->number;
207  	}
208  	
209  	/** returns minimum size of components to be solved individually during the branch-and-bound search */
210  	static
211  	int getMinsize(
212  	   SCIP*                 scip,               /**< main SCIP data structure */
213  	   SCIP_CONSHDLRDATA*    conshdlrdata        /**< constraint handler data */
214  	   )
215  	{
216  	   int minsize;
217  	
218  	   assert(conshdlrdata != NULL);
219  	
220  	   minsize = (int)(conshdlrdata->minrelsize * SCIPgetNVars(scip));
221  	   minsize = MAX(minsize, conshdlrdata->minsize);
222  	
223  	   return minsize;
224  	}
225  	
226  	/** initialize component structure */
227  	static
228  	SCIP_RETCODE initComponent(
229  	   PROBLEM*              problem             /**< subproblem structure */
230  	   )
231  	{
232  	   COMPONENT* component;
233  	   SCIP* scip;
234  	
235  	   assert(problem != NULL);
236  	   assert(problem->ncomponents < problem->componentssize);
237  	
238  	   scip = problem->scip;
239  	   assert(scip != NULL);
240  	
241  	   component = &problem->components[problem->ncomponents];
242  	
243  	   component->problem = problem;
244  	   component->subscip = NULL;
245  	   component->workingsol = NULL;
246  	   component->vars = NULL;
247  	   component->subvars = NULL;
248  	   component->fixedvars = NULL;
249  	   component->fixedsubvars = NULL;
250  	   component->fixedvarsobjsum = 0.0;
251  	   component->lastdualbound = -SCIPinfinity(scip);
252  	   component->lastprimalbound = SCIPinfinity(scip);
253  	   component->laststatus = SCIP_STATUS_UNKNOWN;
254  	   component->solved = FALSE;
255  	   component->ncalls = 0;
256  	   component->lastsolindex = -1;
257  	   component->lastbestsolindex = -1;
258  	   component->nvars = 0;
259  	   component->nfixedvars = 0;
260  	   component->fixedvarssize = 0;
261  	   component->number = problem->ncomponents;
262  	
263  	   ++problem->ncomponents;
264  	
265  	   return SCIP_OKAY;
266  	}
267  	
268  	/** free component structure */
269  	static
270  	SCIP_RETCODE freeComponent(
271  	   COMPONENT*            component           /**< pointer to component structure */
272  	   )
273  	{
274  	   PROBLEM* problem;
275  	   SCIP* scip;
276  	
277  	   assert(component != NULL);
278  	
279  	   problem = component->problem;
280  	   assert(problem != NULL);
281  	
282  	   scip = problem->scip;
283  	   assert(scip != NULL);
284  	
285  	   SCIPdebugMsg(scip, "freeing component %d of problem <%s>\n", component->number, component->problem->name);
286  	
287  	   assert((component->vars != NULL) == (component->subvars != NULL));
288  	   if( component->vars != NULL )
289  	   {
290  	      SCIPfreeBlockMemoryArray(scip, &component->vars, component->nvars);
291  	      SCIPfreeBlockMemoryArray(scip, &component->subvars, component->nvars);
292  	   }
293  	
294  	   assert((component->fixedvars != NULL) == (component->fixedsubvars != NULL));
295  	   if( component->fixedvars != NULL )
296  	   {
297  	      SCIPfreeBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize);
298  	      SCIPfreeBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize);
299  	   }
300  	
301  	   /* free sub-SCIP belonging to this component and the working solution */
302  	   if( component->subscip != NULL )
303  	   {
304  	      if( component->workingsol != NULL )
305  	      {
306  	         SCIP_CALL( SCIPfreeSol(component->subscip, &component->workingsol) );
307  	      }
308  	
309  	      SCIP_CALL( SCIPfree(&component->subscip) );
310  	   }
311  	
312  	   return SCIP_OKAY;
313  	}
314  	
315  	
316  	/** create the working solution for a given component, store fixed variables and the corresponding objective offset */
317  	static
318  	SCIP_RETCODE componentSetupWorkingSol(
319  	   COMPONENT*            component,          /**< component structure */
320  	   SCIP_HASHMAP*         varmap              /**< variable hashmap */
321  	   )
322  	{
323  	   SCIP* subscip;
324  	
325  	   assert(component != NULL);
326  	
327  	   subscip = component->subscip;
328  	   assert(subscip != NULL);
329  	   assert(SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM);
330  	
331  	   /* the solution should live in the primal, not the origprimal, of the sub-SCIP, so we need to transform it first */
332  	   SCIP_CALL( SCIPtransformProb(subscip) );
333  	   SCIP_CALL( SCIPcreateOrigSol(subscip, &(component->workingsol), NULL) );
334  	
335  	   /* the number of variables was increased by copying the constraints */
336  	   if( SCIPgetNOrigVars(subscip) > component->nvars )
337  	   {
338  	      PROBLEM* problem;
339  	      SCIP* scip;
340  	      SCIP_VAR** sourcevars;
341  	      SCIP_VAR* subvar;
342  	      int nsourcevars;
343  	      int nnewvars;
344  	      int idx = 0;
345  	      int nvars;
346  	      int v;
347  	
348  	      problem = component->problem;
349  	      assert(problem != NULL);
350  	
351  	      scip = problem->scip;
352  	      assert(scip != NULL);
353  	
354  	      sourcevars = SCIPgetVars(scip);
355  	      nsourcevars = SCIPgetNVars(scip);
356  	      nnewvars = SCIPgetNOrigVars(subscip);
357  	      nvars = component->nvars;
358  	
359  	      component->fixedvarssize = nnewvars - nvars;
360  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize) );
361  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize) );
362  	
363  	      for( v = 0; v < nsourcevars; ++v )
364  	      {
365  	         subvar = (SCIP_VAR*)SCIPhashmapGetImage(varmap, sourcevars[v]);
366  	         if( subvar != NULL && SCIPvarGetIndex(subvar) >= nvars )
367  	         {
368  	            /* the variable is either locally fixed or could be an inactive variable present in a constraint
369  	             * for which an aggregation constraint linking it to the active variable was created in the subscip
370  	             */
371  	            assert(SCIPisZero(subscip, SCIPvarGetObj(subvar)) ||
372  	               SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)));
373  	
374  	            /* variable is gloablly fixed in sub-SCIP, so it was locally fixed in the main-SCIP */
375  	            if( SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)) )
376  	            {
377  	               assert(SCIPisEQ(scip, SCIPvarGetLbLocal(sourcevars[v]), SCIPvarGetUbLocal(sourcevars[v])));
378  	
379  	               component->fixedvarsobjsum += SCIPvarGetLbGlobal(subvar) * SCIPvarGetObj(subvar);
380  	               component->fixedvars[idx] = sourcevars[v];
381  	               component->fixedsubvars[idx] = subvar;
382  	               ++idx;
383  	
384  	               SCIP_CALL( SCIPsetSolVal(subscip, component->workingsol, subvar, SCIPvarGetLbGlobal(subvar)) );
385  	            }
386  	            /* inactive variable */
387  	            else
388  	            {
389  	               assert(SCIPisZero(subscip, SCIPvarGetObj(subvar)));
390  	            }
391  	         }
392  	         else
393  	         {
394  	            assert(subvar == NULL || SCIPisLT(scip, SCIPvarGetLbGlobal(sourcevars[v]), SCIPvarGetUbGlobal(sourcevars[v])));
395  	            assert(subvar == NULL || SCIPisLT(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)));
396  	         }
397  	      }
398  	      component->nfixedvars = idx;
399  	      assert(component->nfixedvars <= component->fixedvarssize);
400  	      SCIPdebugMsg(scip, "%d locally fixed variables have been copied, objective contribution: %g\n",
401  	         component->nfixedvars, component->fixedvarsobjsum);
402  	   }
403  	
404  	   /* set up debug solution */
405  	#ifdef WITH_DEBUG_SOLUTION
406  	   if( SCIPdebugSolIsEnabled(component->problem->scip) )
407  	   {
408  	      PROBLEM* problem;
409  	      SCIP* scip;
410  	      SCIP_Bool isvalid = FALSE;
411  	
412  	      problem = component->problem;
413  	      assert(problem != NULL);
414  	
415  	      scip = problem->scip;
416  	      assert(scip != NULL);
417  	
418  	      SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) );
419  	
420  	      if( isvalid )
421  	      {
422  	         SCIP_Real val;
423  	         int i;
424  	
425  	         SCIPdebugSolEnable(component->subscip);
426  	
427  	         for( i = 0; i < component->nvars; ++i )
428  	         {
429  	            if( component->subvars[i] != NULL )
430  	            {
431  	               SCIP_CALL( SCIPdebugGetSolVal(scip, component->vars[i], &val) );
432  	               SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->subvars[i], val) );
433  	            }
434  	         }
435  	         for( i = 0; i < component->nfixedvars; ++i )
436  	         {
437  	            if( component->fixedsubvars[i] != NULL )
438  	            {
439  	               SCIP_CALL( SCIPdebugGetSolVal(scip, component->fixedvars[i], &val) );
440  	               SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->fixedsubvars[i], val) );
441  	            }
442  	         }
443  	      }
444  	   }
445  	#endif
446  	
447  	   return SCIP_OKAY;
448  	}
449  	
450  	/** create a sub-SCIP for the given variables and constraints */
451  	static
452  	SCIP_RETCODE createSubscip(
453  	   SCIP*                 scip,               /**< main SCIP data structure */
454  	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
455  	   SCIP**                subscip             /**< pointer to store created sub-SCIP */
456  	   )
457  	{
458  	   SCIP_Bool success;
459  	
460  	   assert(conshdlrdata != NULL);
461  	
462  	   /* create a new SCIP instance */
463  	   SCIP_CALL( SCIPcreate(subscip) );
464  	
465  	   /* copy plugins, we omit pricers (because we do not run if there are active pricers) and dialogs */
466  	#ifdef SCIP_MORE_DEBUG /* we print statistics later, so we need to copy statistics tables */
467  	   SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
468  	         TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, &success) );
469  	#else
470  	   SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE,
471  	         TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
472  	#endif
473  	
474  	   /* the plugins were successfully copied */
475  	   if( success )
476  	   {
477  	      SCIP_CONSHDLR* newconshdlr;
478  	      SCIP_CONSHDLRDATA* newconshdlrdata;
479  	#ifdef WITH_DEBUG_SOLUTION
480  	      SCIP_Bool isvalid = FALSE;
481  	#endif
482  	
483  	      /* copy parameter settings */
484  	      SCIP_CALL( SCIPcopyParamSettings(scip, *subscip) );
485  	
486  	      /* some general settings should not be fixed */
487  	      assert(!SCIPisParamFixed(*subscip, "limits/solutions"));
488  	      assert(!SCIPisParamFixed(*subscip, "limits/bestsol"));
489  	      assert(!SCIPisParamFixed(*subscip, "misc/usevartable"));
490  	      assert(!SCIPisParamFixed(*subscip, "misc/useconstable"));
491  	      assert(!SCIPisParamFixed(*subscip, "numerics/feastol"));
492  	      assert(!SCIPisParamFixed(*subscip, "misc/usesmalltables"));
493  	
494  	      /* disable solution limits */
495  	      SCIP_CALL( SCIPsetIntParam(*subscip, "limits/solutions", -1) );
496  	      SCIP_CALL( SCIPsetIntParam(*subscip, "limits/bestsol", -1) );
497  	
498  	      /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree,
499  	       * hash tables are needed for installing the debug solution
500  	       */
501  	#ifdef WITH_DEBUG_SOLUTION
502  	      SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) );
503  	      if( !isvalid && SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
504  	#endif
505  	      {
506  	         SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) );
507  	         SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) );
508  	      }
509  	
510  	      /* disable presolving */
511  	      SCIP_CALL( SCIPsetPresolving(*subscip, SCIP_PARAMSETTING_OFF, TRUE) );
512  	
513  	      /* disable component presolving and fix the parameter */
514  	      SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) );
515  	      SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") );
516  	
517  	      /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */
518  	      newconshdlr = SCIPfindConshdlr(*subscip, CONSHDLR_NAME);
519  	      assert(newconshdlr != NULL);
520  	
521  	      newconshdlrdata = SCIPconshdlrGetData(newconshdlr);
522  	      assert(newconshdlrdata != NULL);
523  	      newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip);
524  	
525  	      /* disable output, unless in extended debug mode */
526  	#ifndef SCIP_MORE_DEBUG
527  	      SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
528  	#endif
529  	   }
530  	   else
531  	   {
532  	      SCIP_CALL( SCIPfree(subscip) );
533  	      *subscip = NULL;
534  	   }
535  	
536  	   return SCIP_OKAY;
537  	}
538  	
539  	/** copies the given variables and constraints to the given sub-SCIP */
540  	static
541  	SCIP_RETCODE copyToSubscip(
542  	   SCIP*                 scip,               /**< source SCIP */
543  	   SCIP*                 subscip,            /**< target SCIP */
544  	   const char*           name,               /**< name for copied problem */
545  	   SCIP_VAR**            vars,               /**< array of variables to copy */
546  	   SCIP_VAR**            subvars,            /**< array to fill with copied vars */
547  	   SCIP_CONS**           conss,              /**< constraint to copy */
548  	   SCIP_HASHMAP*         varmap,             /**< hashmap used for the copy process of variables */
549  	   SCIP_HASHMAP*         consmap,            /**< hashmap used for the copy process of constraints */
550  	   int                   nvars,              /**< number of variables to copy */
551  	   int                   nconss,             /**< number of constraints to copy */
552  	   SCIP_Bool*            success             /**< pointer to store whether copying was successful */
553  	   )
554  	{
555  	   SCIP_CONS* newcons;
556  	   int i;
557  	
558  	   assert(scip != NULL);
559  	   assert(subscip != NULL);
560  	   assert(vars != NULL);
561  	   assert(subvars != NULL);
562  	   assert(conss != NULL);
563  	   assert(varmap != NULL);
564  	   assert(consmap != NULL);
565  	   assert(success != NULL);
566  	
567  	   *success = TRUE;
568  	
569  	   /* create problem in sub-SCIP */
570  	   SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
571  	
572  	   /* copy variables */
573  	   for( i = 0; i < nvars; ++i )
574  	   {
575  	      SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) );
576  	
577  	      /* abort if variable was not successfully copied */
578  	      if( !(*success) )
579  	         return SCIP_OKAY;
580  	   }
581  	
582  	   /* copy constraints */
583  	   for( i = 0; i < nconss; ++i )
584  	   {
585  	      assert(!SCIPconsIsModifiable(conss[i]));
586  	
587  	      /* copy the constraint */
588  	      SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
589  	            SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
590  	            SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
591  	            SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
592  	
593  	      /* abort if constraint was not successfully copied */
594  	      if( !(*success) )
595  	         return SCIP_OKAY;
596  	
597  	      SCIP_CALL( SCIPaddCons(subscip, newcons) );
598  	      SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
599  	   }
600  	
601  	   return SCIP_OKAY;
602  	}
603  	
604  	/** create the sub-SCIP for a given component */
605  	static
606  	SCIP_RETCODE componentCreateSubscip(
607  	   COMPONENT*            component,          /**< component structure */
608  	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
609  	   SCIP_HASHMAP*         varmap,             /**< variable hashmap used to improve performance */
610  	   SCIP_HASHMAP*         consmap,            /**< constraint hashmap used to improve performance */
611  	   SCIP_CONS**           conss,              /**< constraints contained in this component */
612  	   int                   nconss,             /**< number of constraints contained in this component */
613  	   SCIP_Bool*            success             /**< pointer to store whether the copying process was successful */
614  	   )
615  	{
616  	   char name[SCIP_MAXSTRLEN];
617  	   PROBLEM* problem;
618  	   SCIP* scip;
619  	   int minsize;
620  	
621  	   assert(component != NULL);
622  	   assert(consmap != NULL);
623  	   assert(conss != NULL);
624  	   assert(success != NULL);
625  	   assert(component->nvars > 0);
626  	
627  	   problem = component->problem;
628  	   assert(problem != NULL);
629  	
630  	   scip = problem->scip;
631  	   assert(scip != NULL);
632  	
633  	   (*success) = TRUE;
634  	
635  	   SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) );
636  	
637  	   if( component->subscip != NULL )
638  	   {
639  	      /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */
640  	      minsize = getMinsize(scip, conshdlrdata);
641  	
642  	      SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) );
643  	
644  	      /* get name of the original problem and add "comp_nr" */
645  	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number);
646  	
647  	      SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars,
648  	            conss, varmap, consmap, component->nvars, nconss, success) );
649  	
650  	      if( !(*success) )
651  	      {
652  	         SCIP_CALL( SCIPfree(&component->subscip) );
653  	         component->subscip = NULL;
654  	      }
655  	   }
656  	   else
657  	      (*success) = FALSE;
658  	
659  	   return SCIP_OKAY;
660  	}
661  	
662  	/** solve a given sub-SCIP up to the given limits */
663  	static
664  	SCIP_RETCODE solveSubscip(
665  	   SCIP*                 scip,               /**< main SCIP */
666  	   SCIP*                 subscip,            /**< sub-SCIP to solve */
667  	   SCIP_Longint          nodelimit,          /**< node limit */
668  	   SCIP_Real             gaplimit            /**< gap limit */
669  	   )
670  	{
671  	   SCIP_Real timelimit;
672  	   SCIP_Real memorylimit;
673  	   SCIP_Bool avoidmemout;
674  	
675  	   assert(scip != NULL);
676  	   assert(subscip != NULL);
677  	
678  	   /* set time limit */
679  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
680  	   if( !SCIPisInfinity(scip, timelimit) )
681  	   {
682  	      timelimit -= SCIPgetSolvingTime(scip);
683  	      timelimit += SCIPgetSolvingTime(subscip);
684  	   }
685  	
686  	   /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
687  	   /* @todo count memory of other components */
688  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
689  	   if( !SCIPisInfinity(scip, memorylimit) )
690  	   {
691  	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
692  	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
693  	   }
694  	
695  	   /* check if mem limit needs to be avoided */
696  	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
697  	
698  	   /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == TRUE)
699  	    * to create a copy of SCIP, including external memory usage */
700  	   if( avoidmemout && memorylimit <= 0.0 )
701  	   {
702  	      SCIPdebugMessage("--> not solved (not enough memory left)\n");
703  	      return SCIP_OKAY;
704  	   }
705  	   else if( timelimit <= 0.0 )
706  	   {
707  	      SCIPdebugMessage("--> not solved (not enough time left)\n");
708  	      return SCIP_OKAY;
709  	   }
710  	
711  	   /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the
712  	    * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP
713  	    */
714  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
715  	
716  	   /* set time and memory limit for the subproblem */
717  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
718  	
719  	   /* only set soft time limit if it exists */
720  	   if( SCIPgetParam(scip, "limits/softtime") != NULL )
721  	   {
722  	      SCIP_Real softtimelimit;
723  	
724  	       /* set soft time limit, if specified in main SCIP and if it exists */
725  	      SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) );
726  	      if( softtimelimit > -0.5 )
727  	      {
728  	         softtimelimit -= SCIPgetSolvingTime(scip);
729  	         softtimelimit += SCIPgetSolvingTime(subscip);
730  	         softtimelimit = MAX(softtimelimit, 0.0);
731  	      }
732  	
733  	      SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) );
734  	   }
735  	
736  	   /* set gap limit */
737  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) );
738  	
739  	   /* set node limit */
740  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
741  	
742  	   /* solve the subproblem */
743  	   SCIP_CALL( SCIPsolve(subscip) );
744  	
745  	#ifdef SCIP_MORE_DEBUG
746  	   SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) );
747  	   SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
748  	#endif
749  	
750  	   return SCIP_OKAY;
751  	}
752  	
753  	/** solve a connected component during presolving and evaluate the result */
754  	static
755  	SCIP_RETCODE solveAndEvalSubscip(
756  	   SCIP*                 scip,               /**< SCIP main data structure */
757  	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< the components constraint handler data */
758  	   SCIP*                 subscip,            /**< sub-SCIP to be solved */
759  	   SCIP_VAR**            vars,               /**< array of variables copied to this component */
760  	   SCIP_VAR**            subvars,            /**< array of sub-SCIP variables corresponding to the vars array */
761  	   SCIP_CONS**           conss,              /**< array of constraints copied to this component */
762  	   int                   nvars,              /**< number of variables copied to this component */
763  	   int                   nconss,             /**< number of constraints copied to this component */
764  	   int*                  ndeletedconss,      /**< pointer to store the number of deleted constraints */
765  	   int*                  nfixedvars,         /**< pointer to store the number of fixed variables */
766  	   int*                  ntightenedbounds,   /**< pointer to store the number of bound tightenings */
767  	   SCIP_RESULT*          result,             /**< pointer to store the result of the component solving */
768  	   SCIP_Bool*            solved              /**< pointer to store if the problem was solved to optimality */
769  	   )
770  	{
771  	   int i;
772  	
773  	   assert(scip != NULL);
774  	   assert(conshdlrdata != NULL);
775  	   assert(subscip != NULL);
776  	   assert(vars != NULL);
777  	   assert(conss != NULL);
778  	   assert(ndeletedconss != NULL);
779  	   assert(nfixedvars != NULL);
780  	   assert(ntightenedbounds != NULL);
781  	   assert(result != NULL);
782  	
783  	   *solved  = FALSE;
784  	
785  	   SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) );
786  	
787  	   if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
788  	   {
789  	      SCIP_SOL* sol;
790  	      SCIP_VAR* var;
791  	      SCIP_VAR* subvar;
792  	      SCIP_Real* fixvals;
793  	      SCIP_Bool feasible;
794  	      SCIP_Bool infeasible;
795  	      SCIP_Bool fixed;
796  	
797  	      sol = SCIPgetBestSol(subscip);
798  	
799  	#ifdef SCIP_DEBUG
800  	      SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
801  	#else
802  	      SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, FALSE, FALSE) );
803  	#endif
804  	
805  	      SCIPdebugMessage("--> solved to optimality: time=%.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not");
806  	
807  	      SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) );
808  	
809  	      if( feasible )
810  	      {
811  	         SCIP_Real glb;
812  	         SCIP_Real gub;
813  	
814  	         /* get values of variables in the optimal solution */
815  	         for( i = 0; i < nvars; ++i )
816  	         {
817  	            var = vars[i];
818  	            subvar = subvars[i];
819  	
820  	            /* get global bounds */
821  	            glb = SCIPvarGetLbGlobal(var);
822  	            gub = SCIPvarGetUbGlobal(var);
823  	
824  	            if( subvar != NULL )
825  	            {
826  	               /* get solution value from optimal solution of the sub-SCIP */
827  	               fixvals[i] = SCIPgetSolVal(subscip, sol, subvar);
828  	
829  	               assert(SCIPisFeasLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
830  	               assert(SCIPisFeasGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
831  	
832  	               /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to
833  	                * change the bounds of the variables by fixing them, the old bounds must not be violated by more than
834  	                * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution
835  	                * has to be checked again
836  	                */
837  	               if( SCIPisGT(scip, fixvals[i], gub) )
838  	               {
839  	                  SCIPdebugMessage("variable <%s> fixval: %f violates global upperbound: %f\n",
840  	                     SCIPvarGetName(var), fixvals[i], gub);
841  	                  fixvals[i] = gub;
842  	                  feasible = FALSE;
843  	               }
844  	               else if( SCIPisLT(scip, fixvals[i], glb) )
845  	               {
846  	                  SCIPdebugMessage("variable <%s> fixval: %f violates global lowerbound: %f\n",
847  	                     SCIPvarGetName(var), fixvals[i], glb);
848  	                  fixvals[i] = glb;
849  	                  feasible = FALSE;
850  	               }
851  	               assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(var)));
852  	               assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(var)));
853  	            }
854  	            else
855  	            {
856  	               /* the variable was not copied, so it was cancelled out of constraints during copying;
857  	                * thus, the variable is not constrained and we fix it to its best bound
858  	                */
859  	               if( SCIPisPositive(scip, SCIPvarGetObj(var)) )
860  	                  fixvals[i] = glb;
861  	               else if( SCIPisNegative(scip, SCIPvarGetObj(var)) )
862  	                  fixvals[i] = gub;
863  	               else
864  	               {
865  	                  fixvals[i] = 0.0;
866  	                  fixvals[i] = MIN(fixvals[i], gub);
867  	                  fixvals[i] = MAX(fixvals[i], glb);
868  	               }
869  	            }
870  	         }
871  	
872  	         /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon,
873  	          * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check
874  	          * solution again in the original space (changing the values might now introduce infeasibilities of constraints)
875  	          */
876  	         if( !feasible )
877  	         {
878  	            SCIP_Real origobj;
879  	
880  	            SCIPdebugMessage("solution violates bounds by more than epsilon, check the corrected solution...\n");
881  	
882  	            origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
883  	
884  	            SCIP_CALL( SCIPfreeTransform(subscip) );
885  	
886  	            SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) );
887  	
888  	            /* set solution values of variables */
889  	            for( i = 0; i < nvars; ++i )
890  	            {
891  	               if( subvars[i] != NULL )
892  	               {
893  	                  SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) );
894  	               }
895  	            }
896  	
897  	            /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */
898  	            SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &feasible) );
899  	
900  	#ifndef NDEBUG
901  	            /* in debug mode, we additionally check integrality and bounds */
902  	            if( feasible )
903  	            {
904  	               SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, TRUE, TRUE, FALSE, &feasible) );
905  	               assert(feasible);
906  	            }
907  	#endif
908  	
909  	            SCIPdebugMessage("--> corrected solution is%s feasible\n", feasible ? "" : " not");
910  	
911  	            if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) )
912  	            {
913  	               SCIPdebugMessage("--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n",
914  	                  origobj, SCIPsolGetOrigObj(sol));
915  	
916  	               feasible = FALSE;
917  	            }
918  	
919  	            SCIP_CALL( SCIPfreeSol(subscip, &sol) );
920  	         }
921  	
922  	         /* if the solution is feasible, fix variables and delete constraints of the component */
923  	         if( feasible )
924  	         {
925  	            /* fix variables */
926  	            for( i = 0; i < nvars; ++i )
927  	            {
928  	               assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(vars[i])));
929  	               assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(vars[i])));
930  	               assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbGlobal(vars[i])));
931  	               assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbGlobal(vars[i])));
932  	
933  	               SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) );
934  	               SCIPvarMarkDeleteGlobalStructures(vars[i]);
935  	               assert(!infeasible);
936  	               assert(fixed);
937  	               (*nfixedvars)++;
938  	            }
939  	
940  	            /* delete constraints */
941  	            for( i = 0; i < nconss; ++i )
942  	            {
943  	               SCIP_CALL( SCIPdelCons(scip, conss[i]) );
944  	               (*ndeletedconss)++;
945  	            }
946  	
947  	            *result = SCIP_SUCCESS;
948  	            *solved = TRUE;
949  	         }
950  	      }
951  	
952  	      SCIPfreeBufferArray(scip, &fixvals);
953  	   }
954  	   else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE )
955  	   {
956  	      *result = SCIP_CUTOFF;
957  	   }
958  	   else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD )
959  	   {
960  	      /* TODO: store unbounded ray in original SCIP data structure */
961  	      *result = SCIP_UNBOUNDED;
962  	   }
963  	   else
964  	   {
965  	      SCIPdebugMessage("--> solving interrupted (status=%d, time=%.2f)\n",
966  	         SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip));
967  	
968  	      /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the
969  	       * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to
970  	       * the original problem without also transferring the possibly suboptimal solution (which is currently not
971  	       * possible)
972  	       */
973  	      if( SCIPgetNSols(subscip) == 0 )
974  	      {
975  	         SCIP_Bool infeasible;
976  	         SCIP_Bool tightened;
977  	         int ntightened;
978  	
979  	         ntightened = 0;
980  	
981  	         for( i = 0; i < nvars; ++i )
982  	         {
983  	            if( subvars[i] == NULL )
984  	               continue;
985  	
986  	            SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE,
987  	                  &infeasible, &tightened) );
988  	            assert(!infeasible);
989  	            if( tightened )
990  	               ntightened++;
991  	
992  	            SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE,
993  	                  &infeasible, &tightened) );
994  	            assert(!infeasible);
995  	            if( tightened )
996  	               ntightened++;
997  	         }
998  	
999  	         *result = SCIP_SUCCESS;
1000 	
1001 	         *ntightenedbounds += ntightened;
1002 	
1003 	         SCIPdebugMessage("--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened);
1004 	      }
1005 	   }
1006 	
1007 	   return SCIP_OKAY;
1008 	}
1009 	
1010 	/** (continues) solving a connected component */
1011 	static
1012 	SCIP_RETCODE solveComponent(
1013 	   COMPONENT*            component,          /**< component structure */
1014 	   SCIP_Bool             lastcomponent,      /**< is this the last component to be solved? */
1015 	   SCIP_RESULT*          result              /**< pointer to store the result of the solving process */
1016 	   )
1017 	{
1018 	   PROBLEM* problem;
1019 	   SCIP* scip;
1020 	   SCIP* subscip;
1021 	   SCIP_SOL* bestsol;
1022 	   SCIP_Longint nodelimit;
1023 	   SCIP_Longint lastnnodes;
1024 	   SCIP_Real gaplimit;
1025 	   SCIP_STATUS status;
1026 	
1027 	   assert(component != NULL);
1028 	
1029 	   problem = component->problem;
1030 	   assert(problem != NULL);
1031 	
1032 	   scip = problem->scip;
1033 	   assert(scip != NULL);
1034 	
1035 	   subscip = component->subscip;
1036 	   assert(subscip != NULL);
1037 	
1038 	   *result = SCIP_DIDNOTRUN;
1039 	
1040 	   SCIPdebugMessage("solve component <%s> (ncalls=%d, absgap=%.9g)\n",
1041 	      SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1042 	
1043 	   bestsol = SCIPgetBestSol(scip);
1044 	
1045 	   /* update best solution of component */
1046 	   if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex )
1047 	   {
1048 	      SCIP_SOL* compsol = component->workingsol;
1049 	      SCIP_VAR** vars = component->vars;
1050 	      SCIP_VAR** subvars = component->subvars;
1051 	      int nvars = component->nvars;
1052 	      int v;
1053 	
1054 	      component->lastbestsolindex = SCIPsolGetIndex(bestsol);
1055 	
1056 	      /* set solution values of component variables */
1057 	      for( v = 0; v < nvars; ++v )
1058 	      {
1059 	         if( subvars[v] != NULL )
1060 	         {
1061 	            SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) );
1062 	         }
1063 	      }
1064 	#ifndef NDEBUG
1065 	      for( v = 0; v < component->nfixedvars; ++v )
1066 	      {
1067 	         if( component->fixedsubvars[v] != NULL )
1068 	            assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]),
1069 	               SCIPvarGetLbGlobal(component->fixedsubvars[v])));
1070 	      }
1071 	#endif
1072 	
1073 	      if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM
1074 	         || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) )
1075 	      {
1076 	         SCIP_Bool feasible;
1077 	
1078 	         SCIPdebugMessage("checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n",
1079 	            SCIPgetProbName(subscip), problem->name,
1080 	            SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip),
1081 	            SCIPgetSolOrigObj(subscip, compsol));
1082 	
1083 	         SCIP_CALL( SCIPcheckSolOrig(subscip, compsol, &feasible, FALSE, FALSE) );
1084 	         if( feasible )
1085 	         {
1086 	            SCIPdebugMessage("... feasible, adding solution.\n");
1087 	
1088 	            SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) );
1089 	         }
1090 	
1091 	         /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting
1092 	          * variables are different and might not allow for a better solution in this component, but still for far
1093 	          * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound
1094 	          * of the problem reduced by the dual bounds of the other components
1095 	          */
1096 	         if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1
1097 	               && SCIPisInfinity(scip, -component->lastdualbound)) )
1098 	         {
1099 	            SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol);
1100 	
1101 	            assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound));
1102 	
1103 	            newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum;
1104 	
1105 	            if( problem->nlowerboundinf == 0 )
1106 	               newcutoffbound += component->lastdualbound;
1107 	
1108 	            if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) )
1109 	            {
1110 	               SCIPdebugMessage("update cutoff bound to %16.9g\n", newcutoffbound);
1111 	
1112 	               SCIP_CALL( SCIPupdateCutoffbound(subscip, newcutoffbound) );
1113 	            }
1114 	         }
1115 	      }
1116 	   }
1117 	
1118 	   assert(component->laststatus != SCIP_STATUS_OPTIMAL);
1119 	
1120 	   SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n",
1121 	      SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound);
1122 	
1123 	   if( component->ncalls == 0 )
1124 	   {
1125 	      nodelimit = 1LL;
1126 	      gaplimit = 0.0;
1127 	
1128 	      lastnnodes = 0;
1129 	   }
1130 	   else
1131 	   {
1132 	      SCIP_Longint mainnodelimit;
1133 	
1134 	      lastnnodes = SCIPgetNNodes(component->subscip);
1135 	
1136 	      SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) );
1137 	
1138 	      nodelimit = 2 * lastnnodes;
1139 	      nodelimit = MAX(nodelimit, 10LL);
1140 	
1141 	      if( mainnodelimit != -1 )
1142 	      {
1143 	         assert(mainnodelimit >= lastnnodes);
1144 	         nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes);
1145 	      }
1146 	
1147 	      /* set a gap limit of half the current gap (at most 10%) */
1148 	      if( SCIPgetGap(component->subscip) < 0.2 )
1149 	         gaplimit = 0.5 * SCIPgetGap(component->subscip);
1150 	      else
1151 	         gaplimit = 0.1;
1152 	
1153 	      if( lastcomponent )
1154 	         gaplimit = 0.0;
1155 	   }
1156 	
1157 	   SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) );
1158 	
1159 	   SCIPaddNNodes(scip, SCIPgetNNodes(subscip) - lastnnodes);
1160 	
1161 	   SCIP_CALL( SCIPprintDisplayLine(scip, NULL, SCIP_VERBLEVEL_NORMAL, TRUE) );
1162 	
1163 	   status = SCIPgetStatus(subscip);
1164 	
1165 	   component->laststatus = status;
1166 	   ++component->ncalls;
1167 	
1168 	   SCIPdebugMsg(scip, "--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n",
1169 	      status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip),
1170 	      SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip));
1171 	
1172 	   *result = SCIP_SUCCESS;
1173 	
1174 	   switch( status )
1175 	   {
1176 	   case SCIP_STATUS_OPTIMAL:
1177 	      component->solved = TRUE;
1178 	      break;
1179 	   case SCIP_STATUS_INFEASIBLE:
1180 	      component->solved = TRUE;
1181 	
1182 	      /* the problem is really infeasible */
1183 	      if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) )
1184 	      {
1185 	         *result = SCIP_CUTOFF;
1186 	      }
1187 	      /* the cutoff bound was reached; no solution better than the cutoff bound exists */
1188 	      else
1189 	      {
1190 	         *result = SCIP_SUCCESS;
1191 	         component->laststatus = SCIP_STATUS_OPTIMAL;
1192 	         assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip)));
1193 	      }
1194 	      break;
1195 	   case SCIP_STATUS_UNBOUNDED:
1196 	   case SCIP_STATUS_INFORUNBD:
1197 	      /* TODO: store unbounded ray in original SCIP data structure */
1198 	      *result = SCIP_UNBOUNDED;
1199 	      component->solved = TRUE;
1200 	      break;
1201 	   case SCIP_STATUS_USERINTERRUPT:
1202 	      SCIP_CALL( SCIPinterruptSolve(scip) );
1203 	      break;
1204 	   case SCIP_STATUS_TERMINATE:
1205 	   case SCIP_STATUS_UNKNOWN:
1206 	   case SCIP_STATUS_NODELIMIT:
1207 	   case SCIP_STATUS_TOTALNODELIMIT:
1208 	   case SCIP_STATUS_STALLNODELIMIT:
1209 	   case SCIP_STATUS_TIMELIMIT:
1210 	   case SCIP_STATUS_MEMLIMIT:
1211 	   case SCIP_STATUS_GAPLIMIT:
1212 	   case SCIP_STATUS_SOLLIMIT:
1213 	   case SCIP_STATUS_BESTSOLLIMIT:
1214 	   case SCIP_STATUS_RESTARTLIMIT:
1215 	   default:
1216 	      break;
1217 	   }
1218 	
1219 	   /* evaluate call */
1220 	   if( *result == SCIP_SUCCESS )
1221 	   {
1222 	      SCIP_SOL* sol = SCIPgetBestSol(subscip);
1223 	      SCIP_VAR* var;
1224 	      SCIP_VAR* subvar;
1225 	      SCIP_Real newdualbound;
1226 	      int v;
1227 	
1228 	      /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */
1229 	      newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum;
1230 	
1231 	      /* update dual bound of problem */
1232 	      if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) )
1233 	      {
1234 	         assert(!SCIPisInfinity(scip, -newdualbound));
1235 	
1236 	         /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */
1237 	         if( SCIPisInfinity(scip, -component->lastdualbound) )
1238 	         {
1239 	            --problem->nlowerboundinf;
1240 	            problem->lowerbound += newdualbound;
1241 	         }
1242 	         /* increase problem dual bound by dual bound delta */
1243 	         else
1244 	         {
1245 	            problem->lowerbound += (newdualbound - component->lastdualbound);
1246 	         }
1247 	
1248 	         /* update problem dual bound if all problem components have a finite dual bound */
1249 	         if( problem->nlowerboundinf == 0 )
1250 	         {
1251 	            SCIPdebugMessage("component <%s>: dual bound increased from %16.9g to %16.9g, new dual bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1252 	               SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name,
1253 	               SCIPretransformObj(scip, problem->lowerbound),
1254 	               problem->nfeascomps == problem->ncomponents ?
1255 	               (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1256 	               MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1257 	               : SCIPinfinity(scip),
1258 	               problem->nfeascomps == problem->ncomponents ?
1259 	               SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1260 	            SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) );
1261 	         }
1262 	
1263 	         /* store dual bound of this call */
1264 	         component->lastdualbound = newdualbound;
1265 	      }
1266 	
1267 	      /* update primal solution of problem */
1268 	      if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) )
1269 	      {
1270 	         component->lastsolindex = SCIPsolGetIndex(sol);
1271 	
1272 	         if( SCIPsolGetHeur(sol) != NULL )
1273 	            SCIPsolSetHeur(problem->bestsol, SCIPfindHeur(scip, SCIPheurGetName(SCIPsolGetHeur(sol))));
1274 	         else
1275 	            SCIPsolSetHeur(problem->bestsol, NULL);
1276 	
1277 	         /* increase counter for feasible problems if no solution was known before */
1278 	         if( SCIPisInfinity(scip, component->lastprimalbound) )
1279 	            ++(problem->nfeascomps);
1280 	
1281 	         /* update working best solution in problem */
1282 	         for( v = 0; v < component->nvars; ++v )
1283 	         {
1284 	            var = component->vars[v];
1285 	            subvar = component->subvars[v];
1286 	            assert(var != NULL);
1287 	            assert(SCIPvarIsActive(var));
1288 	
1289 	            if( subvar == NULL )
1290 	               continue;
1291 	
1292 	            SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) );
1293 	         }
1294 	
1295 	         /* if we have a feasible solution for each component, add the working solution to the main problem */
1296 	         if( problem->nfeascomps == problem->ncomponents )
1297 	         {
1298 	            SCIP_Bool feasible;
1299 	#ifdef SCIP_MORE_DEBUG
1300 	            SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) );
1301 	            assert(feasible);
1302 	#endif
1303 	            SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) );
1304 	
1305 	            SCIPdebugMessage("component <%s>: primal bound decreased from %16.9g to %16.9g, new primal bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n",
1306 	               SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name,
1307 	               SCIPgetSolOrigObj(scip, problem->bestsol),
1308 	               problem->nfeascomps == problem->ncomponents ?
1309 	               (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) /
1310 	               MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/
1311 	               : SCIPinfinity(scip),
1312 	               problem->nfeascomps == problem->ncomponents ?
1313 	               SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip));
1314 	         }
1315 	
1316 	         /* store primal bound of this call */
1317 	         component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum;
1318 	      }
1319 	
1320 	      /* if the component was solved to optimality, we increase the respective counter and free the subscip */
1321 	      if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE ||
1322 	            component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD )
1323 	      {
1324 	         ++(problem->nsolvedcomps);
1325 	         component->solved = TRUE;
1326 	
1327 	         /* free working solution and component */
1328 	         SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) );
1329 	
1330 	         SCIP_CALL( SCIPfree(&subscip) );
1331 	         component->subscip = NULL;
1332 	      }
1333 	   }
1334 	
1335 	   return SCIP_OKAY;
1336 	}
1337 	
1338 	/** initialize subproblem structure */
1339 	static
1340 	SCIP_RETCODE initProblem(
1341 	   SCIP*                 scip,               /**< SCIP data structure */
1342 	   PROBLEM**             problem,            /**< pointer to subproblem structure */
1343 	   SCIP_Real             fixedvarsobjsum,    /**< objective contribution of all locally fixed variables */
1344 	   int                   ncomponents         /**< number of independent components */
1345 	   )
1346 	{
1347 	   char name[SCIP_MAXSTRLEN];
1348 	   SCIP_VAR** vars;
1349 	   int nvars;
1350 	   int v;
1351 	
1352 	   assert(scip != NULL);
1353 	   assert(problem != NULL);
1354 	
1355 	   vars = SCIPgetVars(scip);
1356 	   nvars = SCIPgetNVars(scip);
1357 	
1358 	   SCIP_CALL( SCIPallocBlockMemory(scip, problem) );
1359 	   assert(*problem != NULL);
1360 	
1361 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) );
1362 	
1363 	   /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be
1364 	    * resized
1365 	    */
1366 	   SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort, NULL) );
1367 	
1368 	   (*problem)->scip = scip;
1369 	   (*problem)->lowerbound = fixedvarsobjsum;
1370 	   (*problem)->fixedvarsobjsum = fixedvarsobjsum;
1371 	   (*problem)->ncomponents = 0;
1372 	   (*problem)->componentssize = ncomponents;
1373 	   (*problem)->nlowerboundinf = ncomponents;
1374 	   (*problem)->nfeascomps = 0;
1375 	   (*problem)->nsolvedcomps = 0;
1376 	
1377 	   if( SCIPgetDepth(scip) == 0 )
1378 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
1379 	   else
1380 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_node_%" SCIP_LONGINT_FORMAT, SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1381 	
1382 	   SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) );
1383 	
1384 	   SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) );
1385 	
1386 	   for( v = 0; v < nvars; v++ )
1387 	   {
1388 	      if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1389 	      {
1390 	         SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v],
1391 	               (SCIPvarGetUbLocal(vars[v]) + SCIPvarGetLbLocal(vars[v]))/2) );
1392 	      }
1393 	   }
1394 	
1395 	   SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
1396 	
1397 	   return SCIP_OKAY;
1398 	}
1399 	
1400 	/** free subproblem structure */
1401 	static
1402 	SCIP_RETCODE freeProblem(
1403 	   PROBLEM**             problem             /**< pointer to problem to free */
1404 	   )
1405 	{
1406 	   SCIP* scip;
1407 	   int c;
1408 	
1409 	   assert(problem != NULL);
1410 	   assert(*problem != NULL);
1411 	
1412 	   scip = (*problem)->scip;
1413 	   assert(scip != NULL);
1414 	
1415 	   /* free best solution */
1416 	   if( (*problem)->bestsol != NULL )
1417 	   {
1418 	      SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) );
1419 	   }
1420 	
1421 	   /* free all components */
1422 	   for( c = (*problem)->ncomponents - 1; c >= 0; --c )
1423 	   {
1424 	      SCIP_CALL( freeComponent(&(*problem)->components[c]) );
1425 	   }
1426 	   if( (*problem)->components != NULL )
1427 	   {
1428 	      SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize);
1429 	   }
1430 	
1431 	   /* free priority queue */
1432 	   SCIPpqueueFree(&(*problem)->compqueue);
1433 	
1434 	   /* free problem name */
1435 	   SCIPfreeMemoryArray(scip, &(*problem)->name);
1436 	
1437 	   /* free PROBLEM struct and set the pointer to NULL */
1438 	   SCIPfreeBlockMemory(scip, problem);
1439 	   *problem = NULL;
1440 	
1441 	   return SCIP_OKAY;
1442 	}
1443 	
1444 	/** creates and captures a components constraint */
1445 	static
1446 	SCIP_RETCODE createConsComponents(
1447 	   SCIP*                 scip,               /**< SCIP data structure */
1448 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
1449 	   const char*           name,               /**< name of constraint */
1450 	   PROBLEM*              problem             /**< problem to be stored in the constraint */
1451 	   )
1452 	{
1453 	   SCIP_CONSHDLR* conshdlr;
1454 	
1455 	   /* find the samediff constraint handler */
1456 	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
1457 	   if( conshdlr == NULL )
1458 	   {
1459 	      SCIPerrorMessage("components constraint handler not found\n");
1460 	      return SCIP_PLUGINNOTFOUND;
1461 	   }
1462 	
1463 	   /* create constraint */
1464 	   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem,
1465 	         FALSE, FALSE, FALSE, FALSE, TRUE,
1466 	         TRUE, FALSE, FALSE, FALSE, TRUE) );
1467 	
1468 	   return SCIP_OKAY;
1469 	}
1470 	
1471 	
1472 	/** sort the components by size and sort vars and conss arrays by component numbers */
1473 	static
1474 	SCIP_RETCODE sortComponents(
1475 	   SCIP*                 scip,               /**< SCIP data structure */
1476 	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
1477 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1478 	   SCIP_CONS**           conss,              /**< constraints */
1479 	   SCIP_VAR**            vars,               /**< variables */
1480 	   int*                  varcomponent,       /**< component numbers for the variables */
1481 	   int*                  conscomponent,      /**< array to store component numbers for the constraints */
1482 	   int                   nconss,             /**< number of constraints */
1483 	   int                   nvars,              /**< number of variables */
1484 	   int*                  firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */
1485 	   int*                  ncompsminsize,      /**< pointer to store the number of components not exceeding the minimum size */
1486 	   int*                  ncompsmaxsize       /**< pointer to store the number of components not exceeding the maximum size */
1487 	   )
1488 	{
1489 	   SCIP_Real* compsize;
1490 	   int* permu;
1491 	   int ncomponents;
1492 	   int nbinvars;
1493 	   int nintvars;
1494 	   int ndiscvars;
1495 	   int ncontvars;
1496 	   int minsize;
1497 	   int v;
1498 	   int c;
1499 	
1500 	   assert(scip != NULL);
1501 	   assert(conshdlrdata != NULL);
1502 	   assert(digraph != NULL);
1503 	   assert(conss != NULL);
1504 	   assert(vars != NULL);
1505 	   assert(firstvaridxpercons != NULL);
1506 	
1507 	   /* compute minimum size of components to solve individually */
1508 	   minsize = getMinsize(scip, conshdlrdata);
1509 	
1510 	   ncomponents = SCIPdigraphGetNComponents(digraph);
1511 	   *ncompsminsize = 0;
1512 	   *ncompsmaxsize = 0;
1513 	
1514 	   /* We want to sort the components in increasing complexity (number of discrete variables,
1515 	    * integer weighted with factor intfactor, continuous used as tie-breaker).
1516 	    * Therefore, we now get the variables for each component, count the different variable types
1517 	    * and compute a size as described above. Then, we rename the components
1518 	    * such that for i < j, component i has no higher complexity than component j.
1519 	    */
1520 	   SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) );
1521 	   SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) );
1522 	
1523 	   /* get number of variables in the components */
1524 	   for( c = 0; c < ncomponents; ++c )
1525 	   {
1526 	      int* cvars;
1527 	      int ncvars;
1528 	
1529 	      SCIPdigraphGetComponent(digraph, c, &cvars, &ncvars);
1530 	      permu[c] = c;
1531 	      nbinvars = 0;
1532 	      nintvars = 0;
1533 	
1534 	      for( v = 0; v < ncvars; ++v )
1535 	      {
1536 	         /* check whether variable is of binary or integer type */
1537 	         if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY )
1538 	            nbinvars++;
1539 	         else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER )
1540 	            nintvars++;
1541 	      }
1542 	      ncontvars = ncvars - nintvars - nbinvars;
1543 	      ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars);
1544 	      compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars));
1545 	
1546 	      /* component fulfills the maxsize requirement */
1547 	      if( ndiscvars <= conshdlrdata->maxintvars )
1548 	         ++(*ncompsmaxsize);
1549 	
1550 	      /* component fulfills the minsize requirement */
1551 	      if( ncvars >= minsize )
1552 	         ++(*ncompsminsize);
1553 	   }
1554 	
1555 	   /* get permutation of component numbers such that the size of the components is increasing */
1556 	   SCIPsortRealInt(compsize, permu, ncomponents);
1557 	
1558 	   /* now, we need the reverse direction, i.e., for each component number, we store its new number
1559 	    * such that the components are sorted; for this, we abuse the conscomponent array
1560 	    */
1561 	   for( c = 0; c < ncomponents; ++c )
1562 	      conscomponent[permu[c]] = c;
1563 	
1564 	   /* for each variable, replace the old component number by the new one */
1565 	   for( c = 0; c < nvars; ++c )
1566 	      varcomponent[c] = conscomponent[varcomponent[c]];
1567 	
1568 	   SCIPfreeBufferArray(scip, &permu);
1569 	   SCIPfreeBufferArray(scip, &compsize);
1570 	
1571 	   /* do the mapping from calculated components per variable to corresponding
1572 	    * constraints and sort the component-arrays for faster finding the
1573 	    * actual variables and constraints belonging to one component
1574 	    */
1575 	   for( c = 0; c < nconss; c++ )
1576 	      conscomponent[c] = (firstvaridxpercons[c] == -1 ? -1 : varcomponent[firstvaridxpercons[c]]);
1577 	
1578 	   SCIPsortIntPtr(varcomponent, (void**)vars, nvars);
1579 	   SCIPsortIntPtr(conscomponent, (void**)conss, nconss);
1580 	
1581 	   return SCIP_OKAY;
1582 	}
1583 	
1584 	
1585 	
1586 	/** create PROBLEM structure for the current node and split it into components */
1587 	static
1588 	SCIP_RETCODE createAndSplitProblem(
1589 	   SCIP*                 scip,               /**< SCIP data structure */
1590 	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
1591 	   SCIP_Real             fixedvarsobjsum,    /**< objective contribution of all locally fixed variables */
1592 	   SCIP_VAR**            sortedvars,         /**< array of unfixed variables sorted by components */
1593 	   SCIP_CONS**           sortedconss,        /**< array of (checked) constraints sorted by components */
1594 	   int*                  compstartsvars,     /**< start points of components in sortedvars array */
1595 	   int*                  compstartsconss,    /**< start points of components in sortedconss array */
1596 	   int                   ncomponents,        /**< number of components */
1597 	   PROBLEM**             problem             /**< pointer to store problem structure */
1598 	   )
1599 	{
1600 	   COMPONENT* component;
1601 	   SCIP_HASHMAP* consmap;
1602 	   SCIP_HASHMAP* varmap;
1603 	   SCIP_VAR** compvars;
1604 	   SCIP_CONS** compconss;
1605 	   SCIP_Bool success = TRUE;
1606 	   int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents];
1607 	   int ncompconss;
1608 	   int comp;
1609 	
1610 	   /* init subproblem data structure */
1611 	   SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) );
1612 	   assert((*problem)->components != NULL);
1613 	
1614 	   /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
1615 	   SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) );
1616 	
1617 	   /* loop over all components */
1618 	   for( comp = 0; comp < ncomponents; comp++ )
1619 	   {
1620 	      SCIP_CALL( initComponent(*problem) );
1621 	      assert((*problem)->ncomponents == comp+1);
1622 	
1623 	      component = &(*problem)->components[comp];
1624 	
1625 	      /* get component variables and store them in component structure */
1626 	      compvars = &(sortedvars[compstartsvars[comp]]);
1627 	      component->nvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
1628 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &component->vars, compvars, component->nvars) );
1629 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->subvars, component->nvars) );
1630 	      SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) );
1631 	
1632 	      /* get component constraints */
1633 	      compconss = &(sortedconss[compstartsconss[comp]]);
1634 	      ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
1635 	
1636 	#ifdef DETAILED_OUTPUT
1637 	      /* print details about the component including its size */
1638 	      if( component->nvars > 1 && ncompconss > 1 )
1639 	      {
1640 	         int nbinvars = 0;
1641 	         int nintvars = 0;
1642 	         int ncontvars = 0;
1643 	         int i;
1644 	
1645 	         for( i = 0; i < component->nvars; ++i )
1646 	         {
1647 	            if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
1648 	               ++nbinvars;
1649 	            else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
1650 	               ++nintvars;
1651 	            else
1652 	               ++ncontvars;
1653 	         }
1654 	         SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n",
1655 	            comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth,
1656 	            component->nvars, nbinvars, nintvars, ncontvars, ncompconss);
1657 	      }
1658 	#endif
1659 	      assert(ncompconss > 0 || component->nvars == 1);
1660 	
1661 	      SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n",
1662 	         component->number, (*problem)->name, component->nvars, ncompconss);
1663 	
1664 	#ifndef NDEBUG
1665 	      {
1666 	         int i;
1667 	         for( i = 0; i < component->nvars; ++i )
1668 	            assert(SCIPvarIsActive(component->vars[i]));
1669 	      }
1670 	#endif
1671 	
1672 	      /* build subscip for component */
1673 	      SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) );
1674 	
1675 	      if( success )
1676 	      {
1677 	         SCIP_CALL( componentSetupWorkingSol(component, varmap) );
1678 	
1679 	         /* add component to the priority queue of the problem structure */
1680 	         SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) );
1681 	      }
1682 	
1683 	      SCIPhashmapFree(&varmap);
1684 	
1685 	      if( !success )
1686 	         break;
1687 	   }
1688 	
1689 	   SCIPhashmapFree(&consmap);
1690 	
1691 	   if( !success )
1692 	   {
1693 	      /* free subproblem data structure since not all component could be copied */
1694 	      SCIP_CALL( freeProblem(problem) );
1695 	   }
1696 	
1697 	   return SCIP_OKAY;
1698 	}
1699 	
1700 	/** continue solving a problem  */
1701 	static
1702 	SCIP_RETCODE solveProblem(
1703 	   PROBLEM*              problem,            /**< problem structure */
1704 	   SCIP_RESULT*          result              /**< result pointer for the problem solve */
1705 	   )
1706 	{
1707 	   COMPONENT* component;
1708 	   SCIP_RESULT subscipresult;
1709 	
1710 	   assert(problem != NULL);
1711 	
1712 	   *result = SCIP_SUCCESS;
1713 	
1714 	   component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue);
1715 	
1716 	   /* continue solving the component */
1717 	   SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) );
1718 	
1719 	   /* if infeasibility or unboundedness was detected, return this */
1720 	   if( subscipresult == SCIP_CUTOFF || subscipresult == SCIP_UNBOUNDED )
1721 	   {
1722 	      *result = subscipresult;
1723 	   }
1724 	   /* the component was not solved to optimality, so we need to re-insert it in the components queue */
1725 	   else if( !component->solved )
1726 	   {
1727 	      SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) );
1728 	      *result = SCIP_DELAYNODE;
1729 	   }
1730 	   /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */
1731 	   else if( SCIPpqueueNElems(problem->compqueue) == 0 )
1732 	      *result = SCIP_CUTOFF;
1733 	   /* there are some unsolved components left, so we delay this node */
1734 	   else
1735 	      *result = SCIP_DELAYNODE;
1736 	
1737 	   return SCIP_OKAY;
1738 	}
1739 	
1740 	/*
1741 	 * Local methods
1742 	 */
1743 	
1744 	/** loop over constraints, get active variables and fill directed graph */
1745 	static
1746 	SCIP_RETCODE fillDigraph(
1747 	   SCIP*                 scip,               /**< SCIP data structure */
1748 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1749 	   SCIP_CONS**           conss,              /**< constraints */
1750 	   int                   nconss,             /**< number of constraints */
1751 	   int*                  unfixedvarpos,      /**< mapping from variable problem index to unfixed var index */
1752 	   int                   nunfixedvars,       /**< number of unfixed variables */
1753 	   int*                  firstvaridxpercons, /**< array to store for each constraint the index in the local vars array
1754 	                                              *   of the first variable of the constraint */
1755 	   SCIP_Bool*            success             /**< flag indicating successful directed graph filling */
1756 	   )
1757 	{
1758 	   SCIP_VAR** consvars;
1759 	   int requiredsize;
1760 	   int nconsvars;
1761 	   int nvars;
1762 	   int idx1;
1763 	   int idx2;
1764 	   int c;
1765 	   int v;
1766 	
1767 	   assert(scip != NULL);
1768 	   assert(digraph != NULL);
1769 	   assert(conss != NULL);
1770 	   assert(firstvaridxpercons != NULL);
1771 	   assert(success != NULL);
1772 	
1773 	   *success = TRUE;
1774 	
1775 	   nconsvars = 0;
1776 	   requiredsize = 0;
1777 	   nvars = SCIPgetNVars(scip);
1778 	
1779 	   /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */
1780 	   SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
1781 	
1782 	   for( c = 0; c < nconss; ++c )
1783 	   {
1784 	      /* check for reached timelimit */
1785 	      if( (c % 1000 == 0) && SCIPisStopped(scip) )
1786 	      {
1787 	         *success = FALSE;
1788 	         break;
1789 	      }
1790 	
1791 	      /* get number of variables for this constraint */
1792 	      SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) );
1793 	
1794 	      if( !(*success) )
1795 	         break;
1796 	
1797 	      /* reallocate consvars array, if needed */
1798 	      if( nconsvars > nvars )
1799 	      {
1800 	         nvars = nconsvars;
1801 	         SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, nvars) );
1802 	      }
1803 	
1804 	#ifndef NDEBUG
1805 	      /* clearing variables array to check for consistency */
1806 	      if( nconsvars == nvars )
1807 	      {
1808 		 BMSclearMemoryArray(consvars, nconsvars);
1809 	      }
1810 	      else
1811 	      {
1812 		 assert(nconsvars < nvars);
1813 		 BMSclearMemoryArray(consvars, nconsvars + 1);
1814 	      }
1815 	#endif
1816 	
1817 	      /* get variables for this constraint */
1818 	      SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) );
1819 	
1820 	      if( !(*success) )
1821 	      {
1822 	#ifndef NDEBUG
1823 		 /* it looks strange if returning the number of variables was successful but not returning the variables */
1824 		 SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c]));
1825 	#endif
1826 	         break;
1827 	      }
1828 	
1829 	#ifndef NDEBUG
1830 	      /* check if returned variables are consistent with the number of variables that were returned */
1831 	      for( v = nconsvars - 1; v >= 0; --v )
1832 		 assert(consvars[v] != NULL);
1833 	      if( nconsvars < nvars )
1834 		 assert(consvars[nconsvars] == NULL);
1835 	#endif
1836 	
1837 	      /* transform given variables to active variables */
1838 	      SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) );
1839 	      assert(requiredsize <= nvars);
1840 	
1841 	      firstvaridxpercons[c] = -1;
1842 	
1843 	      /* store the index of the first unfixed variable and add edges to the directed graph */
1844 	      if( nconsvars > 0 )
1845 	      {
1846 	         v = 0;
1847 	         idx1 = -1;
1848 	
1849 	         /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */
1850 	         while( idx1 == -1 && v < nconsvars )
1851 	         {
1852 	            idx1 = SCIPvarGetProbindex(consvars[v]);
1853 	            assert(idx1 >= 0);
1854 	            idx1 = unfixedvarpos[idx1];
1855 	            assert(idx1 < nunfixedvars);
1856 	            ++v;
1857 	         }
1858 	
1859 	         if( idx1 >= 0 )
1860 	         {
1861 	            /* save index of the first variable for later component assignment */
1862 	            firstvaridxpercons[c] = idx1;
1863 	
1864 	            /* create sparse directed graph; sparse means to add only those edges necessary for component calculation,
1865 	             * i.e., add edges from the first variable to all others
1866 	             */
1867 	            for(; v < nconsvars; ++v )
1868 	            {
1869 	               idx2 = SCIPvarGetProbindex(consvars[v]);
1870 	               assert(idx2 >= 0);
1871 	               idx2 = unfixedvarpos[idx2];
1872 	               assert(idx2 < nunfixedvars);
1873 	
1874 	               /* variable is fixed */
1875 	               if( idx2 < 0 )
1876 	                  continue;
1877 	
1878 	               /* we add only one directed edge, because the other direction is automatically added for component computation */
1879 	               SCIP_CALL( SCIPdigraphAddArc(digraph, idx1, idx2, NULL) );
1880 	            }
1881 	         }
1882 	      }
1883 	   }
1884 	
1885 	   SCIPfreeBufferArray(scip, &consvars);
1886 	
1887 	   return SCIP_OKAY;
1888 	}
1889 	
1890 	/** search for components in the problem */
1891 	static
1892 	SCIP_RETCODE findComponents(
1893 	   SCIP*                 scip,               /**< SCIP main data structure */
1894 	   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< the components constraint handler data */
1895 	   SCIP_Real*            fixedvarsobjsum,    /**< objective contribution of all locally fixed variables, or NULL if
1896 	                                              *   fixed variables should not be disregarded */
1897 	   SCIP_VAR**            sortedvars,         /**< array to store variables sorted by components, should have enough size
1898 	                                              *   for all variables */
1899 	   SCIP_CONS**           sortedconss,        /**< array to store (checked) constraints sorted by components, should have
1900 	                                              *   enough size for all constraints */
1901 	   int*                  compstartsvars,     /**< start points of components in sortedvars array */
1902 	   int*                  compstartsconss,    /**< start points of components in sortedconss array */
1903 	   int*                  nsortedvars,        /**< pointer to store the number of variables belonging to any component */
1904 	   int*                  nsortedconss,       /**< pointer to store the number of (checked) constraints in components */
1905 	   int*                  ncomponents,        /**< pointer to store the number of components */
1906 	   int*                  ncompsminsize,      /**< pointer to store the number of components not exceeding the minimum size */
1907 	   int*                  ncompsmaxsize       /**< pointer to store the number of components not exceeding the maximum size */
1908 	
1909 	   )
1910 	{
1911 	   SCIP_CONS** tmpconss;
1912 	   SCIP_VAR** vars;
1913 	   SCIP_Bool success;
1914 	   int ntmpconss;
1915 	   int nvars;
1916 	   int c;
1917 	
1918 	   assert(scip != NULL);
1919 	   assert(conshdlrdata != NULL);
1920 	   assert(sortedvars != NULL);
1921 	   assert(sortedconss != NULL);
1922 	   assert(compstartsvars != NULL);
1923 	   assert(compstartsconss != NULL);
1924 	   assert(nsortedvars != NULL);
1925 	   assert(nsortedconss != NULL);
1926 	   assert(ncomponents != NULL);
1927 	   assert(ncompsminsize != NULL);
1928 	   assert(ncompsmaxsize != NULL);
1929 	
1930 	   vars = SCIPgetVars(scip);
1931 	   nvars = SCIPgetNVars(scip);
1932 	
1933 	   if( fixedvarsobjsum != NULL )
1934 	      *fixedvarsobjsum = 0.0;
1935 	
1936 	   *ncomponents = 0;
1937 	   *ncompsminsize = 0;
1938 	   *ncompsmaxsize = 0;
1939 	
1940 	   /* collect checked constraints for component detection */
1941 	   ntmpconss = SCIPgetNConss(scip);
1942 	   tmpconss = SCIPgetConss(scip);
1943 	   (*nsortedconss) = 0;
1944 	   for( c = 0; c < ntmpconss; c++ )
1945 	   {
1946 	      sortedconss[(*nsortedconss)] = tmpconss[c];
1947 	      (*nsortedconss)++;
1948 	   }
1949 	
1950 	   if( nvars > 1 && *nsortedconss > 1 )
1951 	   {
1952 	      int* unfixedvarpos;
1953 	      int* firstvaridxpercons;
1954 	      int* varlocks;
1955 	      int nunfixedvars = 0;
1956 	      int v;
1957 	
1958 	      /* arrays for storing the first variable in each constraint (for later component assignment), the number of
1959 	       * variable locks, and the positions in the sortedvars array for all unfixed variables
1960 	       */
1961 	      SCIP_CALL( SCIPallocBufferArray(scip, &firstvaridxpercons, *nsortedconss) );
1962 	      SCIP_CALL( SCIPallocBufferArray(scip, &varlocks, nvars) );
1963 	      SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvarpos, nvars) );
1964 	
1965 	      /* count number of varlocks for each variable (up + down locks) and multiply it by 2;
1966 	       * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph
1967 	       * to be safe, we double this value
1968 	       */
1969 	      for( v = 0; v < nvars; ++v )
1970 	      {
1971 	         /* variable is not fixed or we do not want to disregard fixed variables */
1972 	         if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1973 	         {
1974 	            assert(nunfixedvars <= v);
1975 	            sortedvars[nunfixedvars] = vars[v];
1976 	            varlocks[nunfixedvars] = 4 * (SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL)
1977 	               + SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL));
1978 	            unfixedvarpos[v] = nunfixedvars;
1979 	            ++nunfixedvars;
1980 	         }
1981 	         /* variable is fixed; update the objective sum of all fixed variables */
1982 	         else
1983 	         {
1984 	            unfixedvarpos[v] = -1;
1985 	            (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]);
1986 	         }
1987 	      }
1988 	      *nsortedvars = nunfixedvars;
1989 	
1990 	      if( nunfixedvars > 0 )
1991 	      {
1992 	         SCIP_DIGRAPH* digraph;
1993 	
1994 	         /* create and fill directed graph */
1995 	         SCIP_CALL( SCIPcreateDigraph(scip, &digraph, nunfixedvars) );
1996 	         SCIP_CALL( SCIPdigraphSetSizes(digraph, varlocks) );
1997 	         SCIP_CALL( fillDigraph(scip, digraph, sortedconss, *nsortedconss, unfixedvarpos, nunfixedvars, firstvaridxpercons, &success) );
1998 	
1999 	         if( success )
2000 	         {
2001 	            int* varcomponent;
2002 	            int* conscomponent;
2003 	
2004 	            SCIP_CALL( SCIPallocBufferArray(scip, &varcomponent, nunfixedvars) );
2005 	            SCIP_CALL( SCIPallocBufferArray(scip, &conscomponent, MAX(nunfixedvars,*nsortedconss)) );
2006 	
2007 	            /* compute independent components */
2008 	            SCIP_CALL( SCIPdigraphComputeUndirectedComponents(digraph, 1, varcomponent, ncomponents) );
2009 	
2010 	            if( *ncomponents > 1 )
2011 	            {
2012 	               int nconss = *nsortedconss;
2013 	               int i;
2014 	
2015 	               nvars = *nsortedvars;
2016 	
2017 	               SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
2018 	                  "cons components found %d undirected components at node %lld, depth %d (%d)\n",
2019 	                  *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2020 	
2021 	               /* sort components by size and sort variables and constraints by component number */
2022 	               SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars,
2023 	                     firstvaridxpercons, ncompsminsize, ncompsmaxsize) );
2024 	
2025 	               /* determine start indices of components in sortedvars and sortedconss array */
2026 	               i = 0;
2027 	
2028 	               while( i < nconss && conscomponent[i] == -1 )
2029 	                  ++i;
2030 	
2031 	               for( c = 0; c < *ncomponents + 1; ++c )
2032 	               {
2033 	                  assert(i == nconss || conscomponent[i] >= c);
2034 	
2035 	                  compstartsconss[c] = i;
2036 	
2037 	                  while( i < nconss && conscomponent[i] == c )
2038 	                     ++i;
2039 	               }
2040 	
2041 	               for( c = 0, i = 0; c < *ncomponents + 1; ++c )
2042 	               {
2043 	                  assert(i == nvars || varcomponent[i] >= c);
2044 	
2045 	                  compstartsvars[c] = i;
2046 	
2047 	                  while( i < nvars && varcomponent[i] == c )
2048 	                     ++i;
2049 	               }
2050 	
2051 	#ifndef NDEBUG
2052 	               for( c = 0; c < *ncomponents; ++c )
2053 	               {
2054 	                  for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i )
2055 	                     assert(conscomponent[i] == c);
2056 	                  for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i )
2057 	                     assert(varcomponent[i] == c);
2058 	               }
2059 	#endif
2060 	            }
2061 	
2062 	            SCIPfreeBufferArray(scip, &conscomponent);
2063 	            SCIPfreeBufferArray(scip, &varcomponent);
2064 	         }
2065 	
2066 	         SCIPdigraphFree(&digraph);
2067 	      }
2068 	
2069 	      SCIPfreeBufferArray(scip, &unfixedvarpos);
2070 	      SCIPfreeBufferArray(scip, &varlocks);
2071 	      SCIPfreeBufferArray(scip, &firstvaridxpercons);
2072 	   }
2073 	
2074 	   return SCIP_OKAY;
2075 	}
2076 	
2077 	
2078 	/*
2079 	 * Callback methods of constraint handler
2080 	 */
2081 	
2082 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2083 	static
2084 	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents)
2085 	{  /*lint --e{715}*/
2086 	   assert(scip != NULL);
2087 	   assert(conshdlr != NULL);
2088 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2089 	
2090 	   /* call inclusion method of constraint handler */
2091 	   SCIP_CALL( SCIPincludeConshdlrComponents(scip) );
2092 	
2093 	   *valid = TRUE;
2094 	
2095 	   return SCIP_OKAY;
2096 	}
2097 	
2098 	/** destructor of constraint handler to free user data (called when SCIP is exiting) */
2099 	static
2100 	SCIP_DECL_CONSFREE(conshdlrFreeComponents)
2101 	{  /*lint --e{715}*/
2102 	   SCIP_CONSHDLRDATA* conshdlrdata;
2103 	
2104 	   /* free constraint handler data */
2105 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
2106 	   assert(conshdlrdata != NULL);
2107 	
2108 	   SCIPfreeBlockMemory(scip, &conshdlrdata);
2109 	   SCIPconshdlrSetData(conshdlr, NULL);
2110 	
2111 	   return SCIP_OKAY;
2112 	}
2113 	
2114 	/** domain propagation method of constraint handler */
2115 	static
2116 	SCIP_DECL_CONSPROP(consPropComponents)
2117 	{  /*lint --e{715}*/
2118 	   PROBLEM* problem;
2119 	   SCIP_CONSHDLRDATA* conshdlrdata;
2120 	   SCIP_Longint nodelimit;
2121 	
2122 	   assert(conshdlr != NULL);
2123 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2124 	   assert(result != NULL);
2125 	   assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2126 	   assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2127 	
2128 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
2129 	   assert(conshdlrdata != NULL);
2130 	
2131 	   *result = SCIP_DIDNOTRUN;
2132 	
2133 	   /* do not try to detect independent components if the depth is too high */
2134 	   if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth
2135 	      && SCIPconshdlrGetNActiveConss(conshdlr) == 0 )
2136 	      return SCIP_OKAY;
2137 	
2138 	   /* don't run in probing or in repropagation */
2139 	   if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
2140 	      return SCIP_OKAY;
2141 	
2142 	   /* do not run, if not all variables are explicitly known */
2143 	   if( SCIPgetNActivePricers(scip) > 0 )
2144 	      return SCIP_OKAY;
2145 	
2146 	   /* we do not want to run, if there are no variables left */
2147 	   if( SCIPgetNVars(scip) == 0 )
2148 	      return SCIP_OKAY;
2149 	
2150 	   /* check for a reached timelimit */
2151 	   if( SCIPisStopped(scip) )
2152 	      return SCIP_OKAY;
2153 	
2154 	   /* the components constraint handler does kind of dual reductions */
2155 	   if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) )
2156 	      return SCIP_OKAY;
2157 	
2158 	   problem = NULL;
2159 	   *result = SCIP_DIDNOTFIND;
2160 	
2161 	   /* the current node already has a components constraint storing a problem split into individual components */
2162 	   if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 )
2163 	   {
2164 	      assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1);
2165 	
2166 	      problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]);
2167 	   }
2168 	   /* no components constraint at the current node, search for components */
2169 	   else
2170 	   {
2171 	      SCIP_Real fixedvarsobjsum;
2172 	      SCIP_VAR** sortedvars;
2173 	      SCIP_CONS** sortedconss;
2174 	      int* compstartsvars;
2175 	      int* compstartsconss;
2176 	      int nsortedvars;
2177 	      int nsortedconss;
2178 	      int ncomponents;
2179 	      int ncompsminsize;
2180 	      int ncompsmaxsize;
2181 	
2182 	      assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2183 	
2184 	      /* allocate memory for sorted components */
2185 	      SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2186 	      SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2187 	      SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2188 	      SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2189 	
2190 	      /* search for components */
2191 	      SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2192 	            compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2193 	
2194 	      if( ncompsminsize > 1 )
2195 	      {
2196 	         SCIP_CONS* cons;
2197 	
2198 	         SCIPdebugMsg(scip, "found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n",
2199 	            ncomponents, ncompsminsize, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip),
2200 	            SCIPgetDepth(scip) + conshdlrdata->subscipdepth);
2201 	
2202 	         /* if there are components with size smaller than the limit, we merge them with the smallest component */
2203 	         if( ncomponents > ncompsminsize )
2204 	         {
2205 	            int minsize;
2206 	            int size;
2207 	            int c;
2208 	            int m = 0;
2209 	
2210 	            /* compute minimum size of components to solve individually */
2211 	            minsize = getMinsize(scip, conshdlrdata);
2212 	
2213 	            for( c = 0; c < ncomponents; ++c )
2214 	            {
2215 	               size = compstartsvars[c+1] - compstartsvars[c];
2216 	
2217 	               if( size >= minsize )
2218 	               {
2219 	                  ++m;
2220 	                  compstartsvars[m] = compstartsvars[c+1];
2221 	                  compstartsconss[m] = compstartsconss[c+1];
2222 	               }
2223 	               /* the last component is too small */
2224 	               else if( c == ncomponents - 1 )
2225 	               {
2226 	                  assert(m == ncompsminsize);
2227 	                  compstartsvars[m] = compstartsvars[c+1];
2228 	                  compstartsconss[m] = compstartsconss[c+1];
2229 	               }
2230 	            }
2231 	            assert(m == ncompsminsize);
2232 	            assert(compstartsvars[m] == nsortedvars);
2233 	            assert(compstartsconss[m] == nsortedconss);
2234 	
2235 	            ncomponents = m;
2236 	         }
2237 	
2238 	         SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars,
2239 	               compstartsconss, ncomponents, &problem) );
2240 	
2241 	         /* if the problem is not NULL, copying worked fine */
2242 	         if( problem != NULL )
2243 	         {
2244 	            SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) );
2245 	            SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), cons, NULL) );
2246 	            SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2247 	         }
2248 	      }
2249 	
2250 	      SCIPfreeBufferArray(scip, &compstartsconss);
2251 	      SCIPfreeBufferArray(scip, &compstartsvars);
2252 	      SCIPfreeBufferArray(scip, &sortedconss);
2253 	      SCIPfreeBufferArray(scip, &sortedvars);
2254 	   }
2255 	
2256 	   /* (continue to) solve the problem
2257 	    *
2258 	    * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the
2259 	    * propagation is finished, the node is put back into the queue of open nodes and solving the components of the
2260 	    * problem will be continued when the node is focused and propagated the next time.
2261 	    * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached
2262 	    * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics
2263 	    * again and again
2264 	    */
2265 	   SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
2266 	   if( nodelimit == -1 )
2267 	      nodelimit = SCIP_LONGINT_MAX;
2268 	
2269 	   do
2270 	   {
2271 	      if( problem != NULL )
2272 	      {
2273 	         SCIP_CALL( solveProblem(problem, result) );
2274 	      }
2275 	   } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit);
2276 	
2277 	   return SCIP_OKAY;
2278 	}
2279 	
2280 	/** presolving method of constraint handler */
2281 	static
2282 	SCIP_DECL_CONSPRESOL(consPresolComponents)
2283 	{  /*lint --e{715}*/
2284 	   SCIP_CONSHDLRDATA* conshdlrdata;
2285 	   SCIP_VAR** sortedvars;
2286 	   SCIP_CONS** sortedconss;
2287 	   int* compstartsvars;
2288 	   int* compstartsconss;
2289 	   int nsortedvars;
2290 	   int nsortedconss;
2291 	   int ncomponents;
2292 	   int ncompsminsize;
2293 	   int ncompsmaxsize;
2294 	   int nvars;
2295 	
2296 	   assert(conshdlr != NULL);
2297 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2298 	   assert(result != NULL);
2299 	   assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0);
2300 	   assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1);
2301 	
2302 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
2303 	   assert(conshdlrdata != NULL);
2304 	
2305 	   *result = SCIP_DIDNOTRUN;
2306 	
2307 	   if( SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING || SCIPinProbing(scip) )
2308 	      return SCIP_OKAY;
2309 	
2310 	   /* do not run, if not all variables are explicitly known */
2311 	   if( SCIPgetNActivePricers(scip) > 0 )
2312 	      return SCIP_OKAY;
2313 	
2314 	   nvars = SCIPgetNVars(scip);
2315 	
2316 	   /* we do not want to run, if there are no variables left */
2317 	   if( nvars == 0 )
2318 	      return SCIP_OKAY;
2319 	
2320 	   /* only call the components presolving, if presolving would be stopped otherwise */
2321 	   if( !SCIPisPresolveFinished(scip) )
2322 	      return SCIP_OKAY;
2323 	
2324 	   /* the components constraint handler does kind of dual reductions */
2325 	   if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) )
2326 	      return SCIP_OKAY;
2327 	
2328 	   /* check for a reached timelimit */
2329 	   if( SCIPisStopped(scip) )
2330 	      return SCIP_OKAY;
2331 	
2332 	   *result = SCIP_DIDNOTFIND;
2333 	
2334 	   assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0);
2335 	
2336 	   /* allocate memory for sorted components */
2337 	   SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) );
2338 	   SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) );
2339 	   SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) );
2340 	   SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) );
2341 	
2342 	   /* search for components */
2343 	   SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars,
2344 	         compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) );
2345 	
2346 	   if( ncompsmaxsize > 0 )
2347 	   {
2348 	      char name[SCIP_MAXSTRLEN];
2349 	      SCIP* subscip;
2350 	      SCIP_HASHMAP* consmap;
2351 	      SCIP_HASHMAP* varmap;
2352 	      SCIP_VAR** compvars;
2353 	      SCIP_VAR** subvars;
2354 	      SCIP_CONS** compconss;
2355 	      SCIP_Bool success;
2356 	      SCIP_Bool solved;
2357 	      int nsolved = 0;
2358 	      int ncompvars;
2359 	      int ncompconss;
2360 	      int comp;
2361 	
2362 	      SCIPdebugMsg(scip, "found %d components (%d with small size) during presolving; overall problem size: %d vars (%d int, %d bin, %d cont), %d conss\n",
2363 	         ncomponents, ncompsmaxsize, SCIPgetNVars(scip), SCIPgetNBinVars(scip), SCIPgetNIntVars(scip), SCIPgetNContVars(scip) + SCIPgetNImplVars(scip), SCIPgetNConss(scip));
2364 	
2365 	      /* build subscip */
2366 	      SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2367 	
2368 	      if( subscip == NULL )
2369 	         goto TERMINATE;
2370 	
2371 	      SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) );
2372 	      SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) );
2373 	
2374 	      /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
2375 	      SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nsortedconss) );
2376 	
2377 	      SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) );
2378 	
2379 	      /* loop over all components */
2380 	      for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ )
2381 	      {
2382 	#ifdef WITH_DEBUG_SOLUTION
2383 	         if( SCIPgetStage(subscip) > SCIP_STAGE_INIT )
2384 	         {
2385 	            SCIP_CALL( SCIPfree(&subscip) );
2386 	            SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) );
2387 	         }
2388 	#endif
2389 	         /* get component variables */
2390 	         compvars = &(sortedvars[compstartsvars[comp]]);
2391 	         ncompvars = compstartsvars[comp + 1 ] - compstartsvars[comp];
2392 	
2393 	         /* get component constraints */
2394 	         compconss = &(sortedconss[compstartsconss[comp]]);
2395 	         ncompconss = compstartsconss[comp + 1] - compstartsconss[comp];
2396 	
2397 	         /* if we have an unlocked variable, let duality fixing do the job! */
2398 	         if( ncompconss == 0 )
2399 	         {
2400 	            assert(ncompvars == 1);
2401 	            continue;
2402 	         }
2403 	
2404 	         SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), ncompvars) );
2405 	#ifdef DETAILED_OUTPUT
2406 	         {
2407 	            int nbinvars = 0;
2408 	            int nintvars = 0;
2409 	            int ncontvars = 0;
2410 	            int i;
2411 	
2412 	            for( i = 0; i < ncompvars; ++i )
2413 	            {
2414 	               if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY )
2415 	                  ++nbinvars;
2416 	               else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER )
2417 	                  ++nintvars;
2418 	               else
2419 	                  ++ncontvars;
2420 	            }
2421 	            SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n",
2422 	               comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss);
2423 	         }
2424 	#endif
2425 	#ifndef NDEBUG
2426 	         {
2427 	            int i;
2428 	            for( i = 0; i < ncompvars; ++i )
2429 	               assert(SCIPvarIsActive(compvars[i]));
2430 	         }
2431 	#endif
2432 	
2433 	         /* get name of the original problem and add "comp_nr" */
2434 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp);
2435 	
2436 	         SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars,
2437 	               compconss, varmap, consmap, ncompvars, ncompconss, &success) );
2438 	
2439 	         if( !success )
2440 	         {
2441 	            SCIPhashmapFree(&varmap);
2442 	            continue;
2443 	         }
2444 	
2445 	            /* set up debug solution */
2446 	#ifdef WITH_DEBUG_SOLUTION
2447 	         if( SCIPdebugSolIsEnabled(scip) )
2448 	         {
2449 	            SCIP_SOL* debugsol;
2450 	            SCIP_Real val;
2451 	            int i;
2452 	
2453 	            SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
2454 	
2455 	            /* set solution values in the debug solution if it is available */
2456 	            if( debugsol != NULL )
2457 	            {
2458 	               SCIPdebugSolEnable(subscip);
2459 	
2460 	               for( i = 0; i < ncompvars; ++i )
2461 	               {
2462 	                  if( subvars[i] != NULL )
2463 	                  {
2464 	                     SCIP_CALL( SCIPdebugGetSolVal(scip, compvars[i], &val) );
2465 	                     SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) );
2466 	                  }
2467 	               }
2468 	            }
2469 	         }
2470 	#endif
2471 	
2472 	         /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */
2473 	         SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss,
2474 	               ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) );
2475 	
2476 	         /* free variable hash map */
2477 	         SCIPhashmapFree(&varmap);
2478 	
2479 	         if( solved )
2480 	            ++nsolved;
2481 	
2482 	         /* if the component is unbounded or infeasible, this holds for the complete problem as well */
2483 	         if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF )
2484 	            break;
2485 	         /* if there is only one component left, let's solve this in the main SCIP */
2486 	         else if( nsolved == ncomponents - 1 )
2487 	            break;
2488 	      }
2489 	
2490 	      SCIPfreeBufferArray(scip, &subvars);
2491 	      SCIPhashmapFree(&consmap);
2492 	
2493 	      SCIP_CALL( SCIPfree(&subscip) );
2494 	   }
2495 	
2496 	 TERMINATE:
2497 	   SCIPfreeBufferArray(scip, &compstartsconss);
2498 	   SCIPfreeBufferArray(scip, &compstartsvars);
2499 	   SCIPfreeBufferArray(scip, &sortedconss);
2500 	   SCIPfreeBufferArray(scip, &sortedvars);
2501 	
2502 	   return SCIP_OKAY;
2503 	}
2504 	
2505 	/** frees specific constraint data */
2506 	static
2507 	SCIP_DECL_CONSDELETE(consDeleteComponents)
2508 	{  /*lint --e{715}*/
2509 	   assert(conshdlr != NULL);
2510 	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2511 	   assert(consdata != NULL);
2512 	   assert(*consdata != NULL);
2513 	
2514 	   SCIP_CALL( freeProblem((PROBLEM**) consdata) );
2515 	
2516 	   return SCIP_OKAY;
2517 	}
2518 	
2519 	/** constraint enforcing method of constraint handler for relaxation solutions */
2520 	static
2521 	SCIP_DECL_CONSENFORELAX(consEnforelaxComponents)
2522 	{  /*lint --e{715}*/
2523 	   assert(result != NULL );
2524 	
2525 	   /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */
2526 	   *result = SCIP_FEASIBLE;
2527 	
2528 	   return SCIP_OKAY;
2529 	}
2530 	
2531 	/** variable rounding lock method of constraint handler */
2532 	static
2533 	SCIP_DECL_CONSLOCK(consLockComponents)
2534 	{  /*lint --e{715}*/
2535 	   return SCIP_OKAY;
2536 	}
2537 	
2538 	#ifndef NDEBUG
2539 	/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
2540 	static
2541 	SCIP_DECL_CONSINITSOL(consInitsolComponents)
2542 	{  /*lint --e{715}*/
2543 	   assert(nconss == 0);
2544 	
2545 	   return SCIP_OKAY;
2546 	}
2547 	#endif
2548 	
2549 	#define consEnfolpComponents NULL
2550 	#define consEnfopsComponents NULL
2551 	#define consCheckComponents NULL
2552 	
2553 	/** creates the components constraint handler and includes it in SCIP */
2554 	SCIP_RETCODE SCIPincludeConshdlrComponents(
2555 	   SCIP*                 scip                /**< SCIP data structure */
2556 	   )
2557 	{
2558 	   SCIP_CONSHDLRDATA* conshdlrdata;
2559 	   SCIP_CONSHDLR* conshdlr;
2560 	
2561 	   /* create components propagator data */
2562 	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2563 	   conshdlrdata->subscipdepth = 0;
2564 	
2565 	   /* include constraint handler */
2566 	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, CONSHDLR_ENFOPRIORITY,
2567 	         CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2568 	         consEnfolpComponents, consEnfopsComponents, consCheckComponents, consLockComponents,
2569 	         conshdlrdata) );
2570 	   assert(conshdlr != NULL);
2571 	
2572 	   SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropComponents,
2573 	         CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING));
2574 	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolComponents,
2575 	         CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING));
2576 	
2577 	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, conshdlrFreeComponents) );
2578 	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxComponents) );
2579 	#ifndef NDEBUG
2580 	   SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolComponents) );
2581 	#endif
2582 	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyComponents, NULL) );
2583 	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteComponents) );
2584 	
2585 	   SCIP_CALL( SCIPaddIntParam(scip,
2586 	         "constraints/" CONSHDLR_NAME "/maxdepth",
2587 	         "maximum depth of a node to run components detection (-1: disable component detection during solving)",
2588 	         &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
2589 	   SCIP_CALL( SCIPaddIntParam(scip,
2590 	         "constraints/" CONSHDLR_NAME "/maxintvars",
2591 	         "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)",
2592 	         &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) );
2593 	   SCIP_CALL( SCIPaddIntParam(scip,
2594 	         "constraints/" CONSHDLR_NAME "/minsize",
2595 	         "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound",
2596 	         &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) );
2597 	   SCIP_CALL( SCIPaddRealParam(scip,
2598 	         "constraints/" CONSHDLR_NAME "/minrelsize",
2599 	         "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound",
2600 	         &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) );
2601 	   SCIP_CALL( SCIPaddLongintParam(scip,
2602 	         "constraints/" CONSHDLR_NAME "/nodelimit",
2603 	         "maximum number of nodes to be solved in subproblems during presolving",
2604 	         &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
2605 	   SCIP_CALL( SCIPaddRealParam(scip,
2606 	         "constraints/" CONSHDLR_NAME "/intfactor",
2607 	         "the weight of an integer variable compared to binary variables",
2608 	         &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2609 	   SCIP_CALL( SCIPaddRealParam(scip,
2610 	         "constraints/" CONSHDLR_NAME "/feastolfactor",
2611 	         "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0",
2612 	         &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) );
2613 	
2614 	   return SCIP_OKAY;
2615 	}
2616