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   heur_crossover.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  crossover primal heuristic
28   	 * @author Timo Berthold
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/heur_crossover.h"
35   	#include "scip/heuristics.h"
36   	#include "scip/pub_event.h"
37   	#include "scip/pub_heur.h"
38   	#include "scip/pub_message.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/pub_sol.h"
41   	#include "scip/pub_var.h"
42   	#include "scip/scip_branch.h"
43   	#include "scip/scip_cons.h"
44   	#include "scip/scip_copy.h"
45   	#include "scip/scip_event.h"
46   	#include "scip/scip_general.h"
47   	#include "scip/scip_heur.h"
48   	#include "scip/scip_mem.h"
49   	#include "scip/scip_message.h"
50   	#include "scip/scip_nodesel.h"
51   	#include "scip/scip_numerics.h"
52   	#include "scip/scip_param.h"
53   	#include "scip/scip_prob.h"
54   	#include "scip/scip_randnumgen.h"
55   	#include "scip/scip_sol.h"
56   	#include "scip/scip_solve.h"
57   	#include "scip/scip_solvingstats.h"
58   	#include "scip/scip_tree.h"
59   	#include "scip/scip_var.h"
60   	#include <string.h>
61   	
62   	#define HEUR_NAME             "crossover"
63   	#define HEUR_DESC             "LNS heuristic that fixes all variables that are identic in a couple of solutions"
64   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
65   	#define HEUR_PRIORITY         -1104000
66   	#define HEUR_FREQ             30
67   	#define HEUR_FREQOFS          0
68   	#define HEUR_MAXDEPTH         -1
69   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
70   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
71   	
72   	#define DEFAULT_MAXNODES      5000LL         /* maximum number of nodes to regard in the subproblem                   */
73   	#define DEFAULT_MINIMPROVE    0.01           /* factor by which Crossover should at least improve the incumbent       */
74   	#define DEFAULT_MINNODES      50LL           /* minimum number of nodes to regard in the subproblem                   */
75   	#define DEFAULT_MINFIXINGRATE 0.666          /* minimum percentage of integer variables that have to be fixed         */
76   	#define DEFAULT_NODESOFS      500LL          /* number of nodes added to the contingent of the total nodes            */
77   	#define DEFAULT_NODESQUOT     0.1            /* subproblem nodes in relation to nodes of the original problem         */
78   	#define DEFAULT_LPLIMFAC      2.0            /* factor by which the limit on the number of LP depends on the node limit */
79   	#define DEFAULT_NUSEDSOLS     3              /* number of solutions that will be taken into account                   */
80   	#define DEFAULT_NWAITINGNODES 200LL          /* number of nodes without incumbent change heuristic should wait        */
81   	#define DEFAULT_RANDOMIZATION TRUE           /* should the choice which sols to take be randomized?                   */
82   	#define DEFAULT_DONTWAITATROOT FALSE         /* should the nwaitingnodes parameter be ignored at the root node?       */
83   	#define DEFAULT_USELPROWS     FALSE          /* should subproblem be created out of the rows in the LP rows,
84   	                                              * otherwise, the copy constructors of the constraints handlers are used */
85   	#define DEFAULT_COPYCUTS      TRUE           /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
86   	                                              * cutpool of the original scip be copied to constraints of the subscip
87   	                                              */
88   	#define DEFAULT_PERMUTE       FALSE          /* should the subproblem be permuted to increase diversification?        */
89   	#define HASHSIZE_SOLS         500            /* size of hash table for solution tuples in crossover heuristic         */
90   	#define DEFAULT_BESTSOLLIMIT   -1            /* limit on number of improving incumbent solutions in sub-CIP           */
91   	#define DEFAULT_USEUCT        FALSE          /* should uct node selection be used at the beginning of the search?     */
92   	#define DEFAULT_RANDSEED         7           /* initial random seed                                                   */
93   	
94   	/* event handler properties */
95   	#define EVENTHDLR_NAME         "Crossover"
96   	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
97   	
98   	/*
99   	 * Data structures
100  	 */
101  	
102  	typedef struct SolTuple SOLTUPLE;
103  	
104  	/** primal heuristic data */
105  	struct SCIP_HeurData
106  	{
107  	   SCIP_SOL*             prevlastsol;        /**< worst solution taken into account during the previous run         */
108  	   SCIP_SOL*             prevbestsol;        /**< best solution during the previous run                             */
109  	   int                   prevnsols;          /**< number of all solutions during the previous run                   */
110  	
111  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem               */
112  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem               */
113  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes        */
114  	   SCIP_Longint          usednodes;          /**< nodes already used by crossover in earlier calls                  */
115  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem     */
116  	
117  	   int                   nusedsols;          /**< number of solutions that will be taken into account               */
118  	   SCIP_Longint          nwaitingnodes;      /**< number of nodes without incumbent change heuristic should wait    */
119  	   unsigned int          nfailures;          /**< number of failures since last successful call                     */
120  	   SCIP_Longint          nextnodenumber;     /**< number of nodes at which crossover should be called the next time */
121  	   SCIP_Real             minfixingrate;      /**< minimum percentage of integer variables that have to be fixed     */
122  	   SCIP_Real             minimprove;         /**< factor by which Crossover should at least improve the incumbent   */
123  	   SCIP_Real             nodelimit;          /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
124  	   SCIP_Real             lplimfac;           /**< factor by which the limit on the number of LP depends on the node limit */
125  	   SCIP_Bool             randomization;      /**< should the choice which sols to take be randomized?               */
126  	   SCIP_Bool             dontwaitatroot;     /**< should the nwaitingnodes parameter be ignored at the root node?   */
127  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator                                           */
128  	   SCIP_HASHTABLE*       hashtable;          /**< hashtable used to store the solution tuples already used          */
129  	   SOLTUPLE*             lasttuple;          /**< last tuple of solutions created by crossover                      */
130  	   SCIP_Bool             uselprows;          /**< should subproblem be created out of the rows in the LP rows?      */
131  	   SCIP_Bool             copycuts;           /**< if uselprows == FALSE, should all active cuts from cutpool be copied
132  	                                              *   to constraints in subproblem?                                     */
133  	   SCIP_Bool             permute;            /**< should the subproblem be permuted to increase diversification?    */
134  	   int                   bestsollimit;       /**< limit on number of improving incumbent solutions in sub-CIP       */
135  	   SCIP_Bool             useuct;             /**< should uct node selection be used at the beginning of the search?  */
136  	};
137  	
138  	/** n-tuple of solutions and their hashkey */
139  	struct SolTuple
140  	{
141  	   int*                  indices;            /**< sorted array of solution indices                                 */
142  	   int                   size;               /**< size of the array (should be heurdata->nusedsols)                */
143  	   unsigned int          key;                /**< hashkey of the tuple                                             */
144  	   SOLTUPLE*             prev;               /**< previous solution tuple created                                  */
145  	};
146  	
147  	
148  	/*
149  	 * Local methods
150  	 */
151  	
152  	/** gets the hash key of a solution tuple */
153  	static
154  	SCIP_DECL_HASHGETKEY(hashGetKeySols)
155  	{  /*lint --e{715}*/
156  	   return elem;
157  	}
158  	
159  	
160  	/** returns TRUE iff both solution tuples are identical */
161  	static
162  	SCIP_DECL_HASHKEYEQ(hashKeyEqSols)
163  	{  /*lint --e{715}*/
164  	   int i;
165  	   int size;
166  	
167  	   int* indices1;
168  	   int* indices2;
169  	
170  	   indices1 = ((SOLTUPLE*)key1)->indices;
171  	   indices2 = ((SOLTUPLE*)key2)->indices;
172  	
173  	   /* there should be two nonempty arrays of the same size */
174  	   assert(indices1 != NULL);
175  	   assert(indices2 != NULL);
176  	   assert(((SOLTUPLE*)key1)->size == ((SOLTUPLE*)key2)->size);
177  	
178  	   size = ((SOLTUPLE*)key1)->size;
179  	
180  	   /* compare arrays by components, return TRUE, iff equal */
181  	   for( i = 0; i < size; i++ )
182  	   {
183  	      if( indices1[i] != indices2[i] )
184  	         return FALSE;
185  	   }
186  	
187  	   return TRUE;
188  	}
189  	
190  	
191  	/** returns hashkey of a solution tuple */
192  	static
193  	SCIP_DECL_HASHKEYVAL(hashKeyValSols)
194  	{  /*lint --e{715}*/
195  	   return ((SOLTUPLE*)key)->key;
196  	}
197  	
198  	
199  	/** calculates a hash key for a given tuple of solution indices */
200  	static
201  	unsigned int calculateHashKey(
202  	   int*                  indices,            /**< indices of solutions */
203  	   int                   size                /**< number of solutions */
204  	   )
205  	{
206  	   int i;
207  	   unsigned int hashkey;
208  	
209  	   /* hashkey should be (x1+1) * (x2+1) * ... * (xn+1) + x1 + x2 + ... + xn */
210  	   hashkey = 1;
211  	   for( i = 0; i < size; i++ )
212  	      hashkey *= (unsigned) indices[i] + 1;
213  	   for( i = 0; i < size; i++ )
214  	      hashkey += (unsigned) indices[i];
215  	
216  	   return hashkey;
217  	}
218  	
219  	
220  	/** insertion sort for a small int array */
221  	static void sortArray(
222  	   int*                  a,                  /**< array to be sorted */
223  	   int                   size                /**< size of array */
224  	   )
225  	{
226  	   int i;
227  	   int j;
228  	   int tmp;
229  	
230  	   /* simple insertion sort algorithm */
231  	   for( i = 1; i < size; i++ )
232  	   {
233  	      tmp = a[i];
234  	      j = i-1;
235  	      while( j >= 0 && a[j] > tmp )
236  	      {
237  	         a[j+1] = a[j]; /*lint !e679*/
238  	         j = j-1;
239  	      }
240  	      a[j+1] = tmp; /*lint !e679*/
241  	   }
242  	}
243  	
244  	
245  	/** creates a new tuple of solutions */
246  	static
247  	SCIP_RETCODE createSolTuple(
248  	   SCIP*                 scip,               /**< original SCIP data structure */
249  	   SOLTUPLE**            elem,               /**< tuple of solutions which should be created */
250  	   int*                  indices,            /**< indices of solutions */
251  	   int                   size,               /**< number of solutions */
252  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
253  	   )
254  	{
255  	   /* memory allocation */
256  	   SCIP_CALL( SCIPallocBlockMemory(scip, elem) );
257  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*elem)->indices, size) );
258  	   BMScopyMemoryArray((*elem)->indices, indices, size);
259  	
260  	   /* data input */
261  	   sortArray(indices,size);
262  	   (*elem)->size = size;
263  	   (*elem)->key = calculateHashKey((*elem)->indices, (*elem)->size);
264  	   (*elem)->prev = heurdata->lasttuple;
265  	
266  	   /* update heurdata */
267  	   heurdata->lasttuple = *elem;
268  	   return SCIP_OKAY;
269  	}
270  	
271  	
272  	/** checks whether the new solution was found at the same node by the same heuristic as an already selected one */
273  	static
274  	SCIP_Bool solHasNewSource(
275  	   SCIP_SOL**            sols,               /**< feasible SCIP solutions */
276  	   int*                  selection,          /**< pool of solutions crossover uses */
277  	   int                   selectionsize,      /**< size of solution pool */
278  	   int                   newsol              /**< candidate solution */
279  	   )
280  	{
281  	   int i;
282  	
283  	   for( i = 0; i < selectionsize; i++ )
284  	   {
285  	      if( SCIPsolGetHeur(sols[selection[i]]) == SCIPsolGetHeur(sols[newsol])
286  	         && SCIPsolGetNodenum(sols[selection[i]]) == SCIPsolGetNodenum(sols[newsol]) )
287  	         return FALSE;
288  	   }
289  	
290  	   return TRUE;
291  	}
292  	
293  	/** randomly selects the solutions crossover will use from the pool of all solutions found so far */
294  	static
295  	SCIP_RETCODE selectSolsRandomized(
296  	   SCIP*                 scip,               /**< original SCIP data structure */
297  	   int*                  selection,          /**< pool of solutions crossover uses  */
298  	   SCIP_HEURDATA*        heurdata,           /**< primal heuristic data */
299  	   SCIP_Bool*            success             /**< pointer to store whether the process was successful */
300  	   )
301  	{
302  	   int i;
303  	   int j;
304  	   int lastsol;          /* the worst solution possible to choose */
305  	   int nusedsols;        /* number of solutions which will be chosen */
306  	
307  	   SOLTUPLE* elem;
308  	   SCIP_SOL** sols;
309  	
310  	   assert( success != NULL );
311  	
312  	   /* initialization */
313  	   nusedsols = heurdata->nusedsols;
314  	   lastsol = SCIPgetNSols(scip);
315  	   sols = SCIPgetSols(scip);
316  	   assert(nusedsols < lastsol);
317  	
318  	   i = 0;
319  	   *success = FALSE;
320  	
321  	   /* perform at maximum 10 restarts and stop as soon as a new set of solutions is found */
322  	   while( !*success && i < 10 )
323  	   {
324  	      SCIP_Bool validtuple;
325  	
326  	      validtuple = TRUE;
327  	      for( j = 0; j < nusedsols && validtuple; j++ )
328  	      {
329  	         int k;
330  	         k = SCIPrandomGetInt(heurdata->randnumgen, nusedsols-j-1, lastsol-1);
331  	
332  	         /* ensure that the solution does not have a similar source as the others */
333  	         while( k >= nusedsols-j-1 && !solHasNewSource(sols, selection, j, k) )
334  	            k--;
335  	
336  	         validtuple = (k >= nusedsols-j-1);
337  	         selection[j] = k;
338  	         lastsol = k;
339  	      }
340  	
341  	      if( validtuple )
342  	      {
343  	         /* creates an object ready to be inserted into the hashtable */
344  	         SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
345  	
346  	         /* check whether the randomized set is already in the hashtable, if not, insert it */
347  	         if( !SCIPhashtableExists(heurdata->hashtable, elem) )
348  	         {
349  	            SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
350  	            *success = TRUE;
351  	         }
352  	      }
353  	      i++;
354  	   }
355  	
356  	   return SCIP_OKAY;
357  	}
358  	
359  	
360  	/** determines the fixings for the CROSSOVER subproblem and checks whether enough fixings were found */
361  	static
362  	SCIP_RETCODE fixVariables(
363  	   SCIP*                 scip,               /**< original SCIP data structure */
364  	   SCIP_VAR**            fixedvars,          /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
365  	   SCIP_Real*            fixedvals,          /**< array to store solution values for variable fixing */
366  	   int*                  nfixedvars,         /**< pointer to store the number of fixed variables */
367  	   int                   fixedvarssize,      /**< size of the arrays to store fixing variables */
368  	   int*                  selection,          /**< pool of solutions crossover will use */
369  	   SCIP_HEURDATA*        heurdata,           /**< primal heuristic data */
370  	   SCIP_Bool*            success             /**< pointer to store whether the problem was created successfully */
371  	   )
372  	{
373  	   SCIP_VAR** vars;                          /* original scip variables                */
374  	   SCIP_SOL** sols;                          /* pool of solutions                      */
375  	   SCIP_Real fixingrate;                     /* percentage of variables that are fixed */
376  	
377  	   int nvars;
378  	   int nbinvars;
379  	   int nintvars;
380  	
381  	   int i;
382  	   int j;
383  	
384  	   sols = SCIPgetSols(scip);
385  	   assert(sols != NULL);
386  	   assert(fixedvars != NULL);
387  	   assert(fixedvals != NULL);
388  	
389  	   /* get required data of the original problem */
390  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
391  	   assert(fixedvarssize >= nbinvars + nintvars);
392  	
393  	   *nfixedvars = 0;
394  	
395  	   /* go through discrete variables and collect potential fixings */
396  	   for( i = 0; i < nbinvars + nintvars; i++ )
397  	   {
398  	      SCIP_Real solval;
399  	      SCIP_Bool fixable;
400  	
401  	      fixable = TRUE;
402  	      solval = SCIPgetSolVal(scip, sols[selection[0]], vars[i]);
403  	
404  	      /* check, whether variable's value is identical for each selected solution */
405  	      for( j = 1; j < heurdata->nusedsols; j++ )
406  	      {
407  	         SCIP_Real varsolval;
408  	         varsolval = SCIPgetSolVal(scip, sols[selection[j]], vars[i]);
409  	         if( REALABS(solval - varsolval) > 0.5 )
410  	         {
411  	            fixable = FALSE;
412  	            break;
413  	         }
414  	      }
415  	
416  	      /* original solval can be outside transformed global bounds */
417  	      fixable = fixable && SCIPvarGetLbGlobal(vars[i]) <= solval && solval <= SCIPvarGetUbGlobal(vars[i]);
418  	
419  	      /* if solutions' values are equal, variable should be fixed in the subproblem */
420  	      if( fixable )
421  	      {
422  	         fixedvars[(*nfixedvars)] = vars[i];
423  	         fixedvals[(*nfixedvars)] = solval;
424  	         (*nfixedvars)++;
425  	      }
426  	   }
427  	
428  	   fixingrate = (SCIP_Real)(*nfixedvars) / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
429  	
430  	   /* if all variables would be fixed or amount of fixed variables is insufficient,
431  	    * skip subproblem creation and abort immediately
432  	    */
433  	   *success = (*nfixedvars) < nbinvars + nintvars && fixingrate >= heurdata->minfixingrate;
434  	
435  	   return SCIP_OKAY;
436  	}
437  	
438  	/** creates a subproblem for subscip by fixing a number of variables */
439  	static
440  	SCIP_RETCODE determineVariableFixings(
441  	   SCIP*                 scip,               /**< original SCIP data structure */
442  	   SCIP_VAR**            fixedvars,          /**< array to store source SCIP variables whose copies should be fixed in the sub-SCIP */
443  	   SCIP_Real*            fixedvals,          /**< array to store solution values for variable fixing */
444  	   int*                  nfixedvars,         /**< pointer to store the number of fixed variables */
445  	   int                   fixedvarssize,      /**< size of the arrays to store fixing variables */
446  	   int*                  selection,          /**< pool of solutions crossover will use */
447  	   SCIP_HEURDATA*        heurdata,           /**< primal heuristic data */
448  	   SCIP_Bool*            success             /**< pointer to store whether the problem was created successfully */
449  	   )
450  	{
451  	   SCIP_SOL** sols;                         /* array of all solutions found so far         */
452  	   int nsols;                               /* number of all solutions found so far        */
453  	   int nusedsols;                           /* number of solutions to use in crossover     */
454  	   int i;
455  	
456  	   /* get solutions' data */
457  	   nsols = SCIPgetNSols(scip);
458  	   sols = SCIPgetSols(scip);
459  	   nusedsols = heurdata->nusedsols;
460  	
461  	   assert(nusedsols > 1);
462  	   assert(nsols >= nusedsols);
463  	
464  	   /* use nusedsols best solutions if randomization is deactivated or there are only nusedsols solutions at hand
465  	    * or a good new solution was found since last call */
466  	   if( !heurdata->randomization || nsols == nusedsols || heurdata->prevlastsol != sols[nusedsols-1] )
467  	   {
468  	      SOLTUPLE* elem;
469  	      SCIP_HEUR* solheur;
470  	      SCIP_Longint solnodenum;
471  	      SCIP_Bool allsame;
472  	
473  	      for( i = 0; i < nusedsols; i++ )
474  	         selection[i] = i;
475  	      SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
476  	
477  	      solheur = SCIPsolGetHeur(sols[0]);
478  	      solnodenum = SCIPsolGetNodenum(sols[0]);
479  	      allsame = TRUE;
480  	
481  	      /* check, whether all solutions have been found by the same heuristic at the same node; in this case we do not run
482  	       * crossover, since it would probably just optimize over the same space as the other heuristic
483  	       */
484  	      for( i = 1; i < nusedsols; i++ )
485  	      {
486  	         if( SCIPsolGetHeur(sols[i]) != solheur || SCIPsolGetNodenum(sols[i]) != solnodenum )
487  	            allsame = FALSE;
488  	      }
489  	      *success = !allsame && !SCIPhashtableExists(heurdata->hashtable, elem);
490  	
491  	      /* check, whether solution tuple has already been tried */
492  	      if( !SCIPhashtableExists(heurdata->hashtable, elem) )
493  	      {
494  	         SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
495  	      }
496  	
497  	      /* if solution tuple has already been tried, randomization is allowed and enough solutions are at hand, try
498  	       * to randomize another tuple. E.g., this can happen if the last crossover solution was among the best ones */
499  	      if( !(*success) && heurdata->randomization && nsols > nusedsols )
500  	      {
501  	         SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) );
502  	      }
503  	   }
504  	   /* otherwise randomize the set of solutions */
505  	   else
506  	   {
507  	      SCIP_CALL( selectSolsRandomized(scip, selection, heurdata, success) );
508  	   }
509  	
510  	   /* no acceptable solution tuple could be created */
511  	   if( !(*success) )
512  	      return SCIP_OKAY;
513  	
514  	   /* set up the variables of the subproblem */
515  	   SCIP_CALL( fixVariables(scip, fixedvars, fixedvals, nfixedvars, fixedvarssize, selection, heurdata, success) );
516  	
517  	   return SCIP_OKAY;
518  	}
519  	
520  	/** updates heurdata after a run of crossover */
521  	static
522  	void updateFailureStatistic(
523  	   SCIP*                 scip,               /**< original SCIP data structure */
524  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
525  	   )
526  	{
527  	   /* increase number of failures, calculate next node at which crossover should be called and update actual solutions */
528  	   heurdata->nfailures++;
529  	   heurdata->nextnodenumber = (heurdata->nfailures <= 25
530  	      ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
531  	      : SCIP_LONGINT_MAX);
532  	}
533  	
534  	/* ---------------- Callback methods of event handler ---------------- */
535  	
536  	/* exec the event handler
537  	 *
538  	 * we interrupt the solution process
539  	 */
540  	static
541  	SCIP_DECL_EVENTEXEC(eventExecCrossover)
542  	{
543  	   SCIP_HEURDATA* heurdata;
544  	
545  	   assert(eventhdlr != NULL);
546  	   assert(eventdata != NULL);
547  	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
548  	   assert(event != NULL);
549  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
550  	
551  	   heurdata = (SCIP_HEURDATA*)eventdata;
552  	   assert(heurdata != NULL);
553  	
554  	   /* interrupt solution process of sub-SCIP */
555  	   if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
556  	   {
557  	      SCIPdebugMsg(scip, "interrupt after  %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip));
558  	      SCIP_CALL( SCIPinterruptSolve(scip) );
559  	   }
560  	
561  	   return SCIP_OKAY;
562  	}
563  	
564  	/*
565  	 * Callback methods of primal heuristic
566  	 */
567  	
568  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
569  	static
570  	SCIP_DECL_HEURCOPY(heurCopyCrossover)
571  	{  /*lint --e{715}*/
572  	   assert(scip != NULL);
573  	   assert(heur != NULL);
574  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
575  	
576  	   /* call inclusion method of primal heuristic */
577  	   SCIP_CALL( SCIPincludeHeurCrossover(scip) );
578  	
579  	   return SCIP_OKAY;
580  	}
581  	
582  	/** setup and solve the subproblem and catch the return code */
583  	static
584  	SCIP_RETCODE setupAndSolveSubscipCrossover(
585  	   SCIP*                 scip,               /**< SCIP data structure */
586  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
587  	   SCIP_HEUR*            heur,               /**< mutation heuristic */
588  	   SCIP_HEURDATA*        heurdata,           /**< heuristics data */
589  	   SCIP_VAR**            vars,               /**< SCIP variables */
590  	   SCIP_VAR**            fixedvars,          /**< array to store the variables that should be fixed in the subproblem */
591  	   SCIP_Real*            fixedvals,          /**< array to store the fixing values to fix variables in the subproblem */
592  	   SCIP_Longint          nstallnodes,        /**< node limit for the subproblem */
593  	   SCIP_RESULT*          result,             /**< pointer to store the result */
594  	   int*                  selection,          /**< pool of solutions crossover uses */
595  	   int                   nvars,              /**< number of original problem's variables */
596  	   int                   nfixedvars,         /**< the number of variables that should be fixed */
597  	   int                   nusedsols           /**< number of solutions which will be chosen */
598  	   )
599  	{
600  	   SCIP_EVENTHDLR* eventhdlr;                /* event handler for LP events                     */
601  	   SCIP_HASHMAP* varmapfw;                   /* mapping of SCIP variables to sub-SCIP variables */
602  	   SCIP_VAR** subvars;                       /* subproblem's variables                          */
603  	   SCIP_Real cutoff;                         /* objective cutoff for the subproblem             */
604  	   SCIP_Real upperbound;
605  	   SCIP_Bool success;
606  	   int i;
607  	
608  	   assert(scip != NULL);
609  	   assert(subscip != NULL);
610  	   assert(heur != NULL);
611  	   assert(heurdata != NULL);
612  	
613  	   /* create the variable mapping hash map */
614  	   SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
615  	   success = FALSE;
616  	
617  	   /* create a copy of the transformed problem to be used by the heuristic */
618  	   SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "crossover", fixedvars, fixedvals, nfixedvars,
619  	         heurdata->uselprows, heurdata->copycuts, &success, NULL) );
620  	
621  	   eventhdlr = NULL;
622  	   /* create event handler for LP events */
623  	   SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCrossover, NULL) );
624  	   if( eventhdlr == NULL )
625  	   {
626  	      SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
627  	      return SCIP_PLUGINNOTFOUND;
628  	   }
629  	
630  	   /* store copied variables in the order in which they appear in the main SCIP */
631  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
632  	   for( i = 0; i < nvars; i++ )
633  	     subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
634  	
635  	   /* free hash map */
636  	   SCIPhashmapFree(&varmapfw);
637  	
638  	   /* do not abort subproblem on CTRL-C */
639  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
640  	
641  	#ifdef SCIP_DEBUG
642  	   /* for debugging, enable full output */
643  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
644  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
645  	#else
646  	   /* disable statistic timing inside sub SCIP and output to console */
647  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
648  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
649  	#endif
650  	
651  	   /* check whether there is enough time and memory left */
652  	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
653  	
654  	   /* set limits for the subproblem */
655  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
656  	   heurdata->nodelimit = nstallnodes;
657  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nstallnodes) );
658  	
659  	   /* forbid recursive call of heuristics and separators solving subMIPs */
660  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
661  	
662  	   /* disable cutting plane separation */
663  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
664  	
665  	   /* disable expensive presolving */
666  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
667  	
668  	   /* use best estimate node selection */
669  	   if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
670  	   {
671  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
672  	   }
673  	
674  	   /* activate uct node selection at the top of the tree */
675  	   if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
676  	   {
677  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
678  	   }
679  	
680  	   /* use inference branching */
681  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
682  	   {
683  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
684  	   }
685  	
686  	   /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
687  	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
688  	   {
689  	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
690  	   }
691  	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
692  	   {
693  	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
694  	   }
695  	   if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
696  	   {
697  	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
698  	   }
699  	
700  	   /* speed up sub-SCIP by not checking dual LP feasibility */
701  	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
702  	
703  	   /* add an objective cutoff */
704  	   assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
705  	
706  	   upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
707  	   if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
708  	   {
709  	      cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
710  	   }
711  	   else
712  	   {
713  	      if( SCIPgetUpperbound ( scip ) >= 0 )
714  	         cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
715  	      else
716  	         cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
717  	   }
718  	   cutoff = MIN(upperbound, cutoff );
719  	   SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
720  	
721  	   /* permute the subproblem to increase diversification */
722  	   if( heurdata->permute )
723  	   {
724  	      SCIP_CALL( SCIPpermuteProb(subscip, SCIPinitializeRandomSeed(scip, (unsigned) SCIPheurGetNCalls(heur)), TRUE, TRUE, TRUE, TRUE, TRUE) );
725  	   }
726  	
727  	   /* catch LP events of sub-SCIP */
728  	   SCIP_CALL( SCIPtransformProb(subscip) );
729  	   SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
730  	
731  	   /* this code can be enabled whenever the subproblem should be written out */
732  	#ifdef SCIP_DISABLED_CODE
733  	   SCIPdebug( SCIP_CALL( SCIPwriteOrigProblem(subscip, "crossoverprob.cip", "cip", FALSE) ) );
734  	#endif
735  	   /* solve the subproblem */
736  	   SCIPdebugMsg(scip, "Solve Crossover subMIP\n");
737  	
738  	   /* Errors in solving the subproblem should not kill the overall solving process.
739  	    * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
740  	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
741  	
742  	   /* drop LP events of sub-SCIP */
743  	   SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
744  	
745  	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
746  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
747  	
748  	   heurdata->usednodes += SCIPgetNNodes(subscip);
749  	
750  	   /* merge histories of the subscip-variables to the SCIP variables. */
751  	   SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
752  	   SCIPdebugMsg(scip, "Transferring variable histories complete\n");
753  	
754  	   /* check, whether a solution was found */
755  	   if( SCIPgetNSols(subscip) > 0 )
756  	   {
757  	      int solindex;                             /* index of the solution created by crossover          */
758  	
759  	      /* check, whether a solution was found;
760  	       * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
761  	      success = FALSE;
762  	      solindex = -1;
763  	      SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, &solindex) );
764  	
765  	      if( success )
766  	      {
767  	         int tmp;
768  	
769  	         assert(solindex != -1);
770  	
771  	         *result = SCIP_FOUNDSOL;
772  	
773  	         /* insert all crossings of the new solution and (nusedsols-1) of its parents into the hashtable
774  	          * in order to avoid incest ;)
775  	          */
776  	         for( i = 0; i < nusedsols; i++ )
777  	         {
778  	            SOLTUPLE* elem;
779  	            tmp = selection[i];
780  	            selection[i] = solindex;
781  	
782  	            SCIP_CALL( createSolTuple(scip, &elem, selection, nusedsols, heurdata) );
783  	            SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
784  	            selection[i] = tmp;
785  	         }
786  	
787  	         /* if solution was among the best ones, crossover should not be called until another good solution was found */
788  	         if( !heurdata->randomization )
789  	         {
790  	            heurdata->prevbestsol = SCIPgetBestSol(scip);
791  	            heurdata->prevlastsol = SCIPgetSols(scip)[heurdata->nusedsols-1];
792  	         }
793  	      }
794  	
795  	      /* if solution is not better than incumbent or could not be added to problem => run is counted as a failure */
796  	      if( !success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) )
797  	         updateFailureStatistic(scip, heurdata);
798  	   }
799  	   else
800  	   {
801  	      /* if no new solution was found, run was a failure */
802  	      updateFailureStatistic(scip, heurdata);
803  	   }
804  	
805  	   SCIPfreeBufferArray(scip, &subvars);
806  	
807  	   return SCIP_OKAY;
808  	}
809  	
810  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
811  	static
812  	SCIP_DECL_HEURFREE(heurFreeCrossover)
813  	{  /*lint --e{715}*/
814  	   SCIP_HEURDATA* heurdata;
815  	
816  	   assert(heur != NULL);
817  	   assert(scip != NULL);
818  	
819  	   /* get heuristic data */
820  	   heurdata = SCIPheurGetData(heur);
821  	   assert(heurdata != NULL);
822  	
823  	   /* free heuristic data */
824  	   SCIPfreeBlockMemory(scip, &heurdata);
825  	   SCIPheurSetData(heur, NULL);
826  	
827  	   return SCIP_OKAY;
828  	}
829  	
830  	/** initialization method of primal heuristic (called after problem was transformed) */
831  	static
832  	SCIP_DECL_HEURINIT(heurInitCrossover)
833  	{  /*lint --e{715}*/
834  	   SCIP_HEURDATA* heurdata;
835  	
836  	   assert(heur != NULL);
837  	   assert(scip != NULL);
838  	
839  	   /* get heuristic's data */
840  	   heurdata = SCIPheurGetData(heur);
841  	   assert(heurdata != NULL);
842  	
843  	   /* initialize data */
844  	   heurdata->usednodes = 0;
845  	   heurdata->prevlastsol = NULL;
846  	   heurdata->prevbestsol = NULL;
847  	   heurdata->lasttuple = NULL;
848  	   heurdata->nfailures = 0;
849  	   heurdata->prevnsols = 0;
850  	   heurdata->nextnodenumber = 0;
851  	
852  	   /* create random number generator */
853  	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
854  	
855  	   /* initialize hash table */
856  	   SCIP_CALL( SCIPhashtableCreate(&heurdata->hashtable, SCIPblkmem(scip), HASHSIZE_SOLS,
857  	         hashGetKeySols, hashKeyEqSols, hashKeyValSols, NULL) );
858  	   assert(heurdata->hashtable != NULL);
859  	
860  	   return SCIP_OKAY;
861  	}
862  	
863  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
864  	static
865  	SCIP_DECL_HEUREXIT(heurExitCrossover)
866  	{  /*lint --e{715}*/
867  	   SCIP_HEURDATA* heurdata;
868  	   SOLTUPLE* soltuple;
869  	
870  	   assert(heur != NULL);
871  	   assert(scip != NULL);
872  	
873  	   /* get heuristic data */
874  	   heurdata = SCIPheurGetData(heur);
875  	   assert(heurdata != NULL);
876  	   soltuple = heurdata->lasttuple;
877  	
878  	   /* free all soltuples iteratively */
879  	   while( soltuple != NULL )
880  	   {
881  	      SOLTUPLE* tmp;
882  	      tmp = soltuple->prev;
883  	      SCIPfreeBlockMemoryArray(scip, &soltuple->indices, soltuple->size);
884  	      SCIPfreeBlockMemory(scip, &soltuple);
885  	      soltuple = tmp;
886  	   }
887  	
888  	   /* free random number generator */
889  	   SCIPfreeRandom(scip, &heurdata->randnumgen);
890  	
891  	   /* free hash table */
892  	   assert(heurdata->hashtable != NULL);
893  	   SCIPhashtableFree(&heurdata->hashtable);
894  	
895  	   return SCIP_OKAY;
896  	}
897  	
898  	/** execution method of primal heuristic */
899  	static
900  	SCIP_DECL_HEUREXEC(heurExecCrossover)
901  	{  /*lint --e{715}*/
902  	   SCIP* subscip;                            /* the subproblem created by crossover                 */
903  	   SCIP_HEURDATA* heurdata;                  /* primal heuristic data                               */
904  	   SCIP_VAR** vars;                          /* original problem's variables                        */
905  	   SCIP_VAR** fixedvars;
906  	   SCIP_SOL** sols;
907  	   SCIP_RETCODE retcode;
908  	   SCIP_Longint nstallnodes;                 /* node limit for the subproblem                       */
909  	   SCIP_Bool success;
910  	   SCIP_Real* fixedvals;
911  	   int* selection;                           /* pool of solutions crossover uses                    */
912  	   int nvars;                                /* number of original problem's variables              */
913  	   int nbinvars;
914  	   int nintvars;
915  	   int nusedsols;
916  	   int nfixedvars;
917  	
918  	   assert(heur != NULL);
919  	   assert(scip != NULL);
920  	   assert(result != NULL);
921  	
922  	   /* get heuristic's data */
923  	   heurdata = SCIPheurGetData(heur);
924  	   assert(heurdata != NULL);
925  	   nusedsols = heurdata->nusedsols;
926  	
927  	   *result = SCIP_DELAYED;
928  	
929  	   /* only call heuristic, if enough solutions are at hand */
930  	   if( SCIPgetNSols(scip) < nusedsols  )
931  	      return SCIP_OKAY;
932  	
933  	   sols = SCIPgetSols(scip);
934  	   assert(sols != NULL);
935  	
936  	   /* if one good solution was found, heuristic should not be delayed any longer */
937  	   if( sols[nusedsols-1] != heurdata->prevlastsol )
938  	   {
939  	      heurdata->nextnodenumber = SCIPgetNNodes(scip);
940  	      if( sols[0] != heurdata->prevbestsol )
941  	         heurdata->nfailures = 0;
942  	   }
943  	   /* in nonrandomized mode: only recall heuristic, if at least one new good solution was found in the meantime */
944  	   else if( !heurdata->randomization )
945  	      return SCIP_OKAY;
946  	
947  	   /* if heuristic should be delayed, wait until certain number of nodes is reached */
948  	   if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
949  	      return SCIP_OKAY;
950  	
951  	   /* only call heuristic, if enough nodes were processed since last incumbent */
952  	   if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes
953  	      && (SCIPgetDepth(scip) > 0 || !heurdata->dontwaitatroot) )
954  	      return SCIP_OKAY;
955  	
956  	   *result = SCIP_DIDNOTRUN;
957  	
958  	   /* calculate the maximal number of branching nodes until heuristic is aborted */
959  	   nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
960  	
961  	   /* reward Crossover if it succeeded often */
962  	   nstallnodes = (SCIP_Longint)
963  	      (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
964  	
965  	   /* count the setup costs for the sub-MIP as 100 nodes */
966  	   nstallnodes -= 100 * SCIPheurGetNCalls(heur);
967  	   nstallnodes += heurdata->nodesofs;
968  	
969  	   /* determine the node limit for the current process */
970  	   nstallnodes -= heurdata->usednodes;
971  	   nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
972  	
973  	   /* check whether we have enough nodes left to call subproblem solving */
974  	   if( nstallnodes < heurdata->minnodes )
975  	      return SCIP_OKAY;
976  	
977  	   /* consider time and memory limits of the main SCIP */
978  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
979  	
980  	   if( !success )
981  	      return SCIP_OKAY;
982  	
983  	   if( SCIPisStopped(scip) )
984  	     return SCIP_OKAY;
985  	
986  	   /* get variable information */
987  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
988  	   assert(nvars > 0);
989  	
990  	   /* check whether discrete variables are available */
991  	   if( nbinvars == 0 && nintvars == 0 )
992  	      return SCIP_OKAY;
993  	
994  	   /* allocate necessary buffer storage for selection of variable fixings */
995  	   SCIP_CALL( SCIPallocBufferArray(scip, &selection, nusedsols) );
996  	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
997  	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
998  	
999  	   success = FALSE;
1000 	   nfixedvars = 0;
1001 	   /* determine fixings of variables with same value in a certain set of solutions */
1002 	   SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, selection, heurdata, &success) );
1003 	
1004 	   heurdata->prevbestsol = SCIPgetBestSol(scip);
1005 	   heurdata->prevlastsol = sols[heurdata->nusedsols-1];
1006 	
1007 	   /* if creation of sub-SCIP was aborted (e.g. due to number of fixings), free sub-SCIP and abort */
1008 	   if( !success )
1009 	   {
1010 	      /* this run will be counted as a failure since no new solution tuple could be generated or the neighborhood of the
1011 	       * solution was not fruitful in the sense that it was too big
1012 	       */
1013 	      updateFailureStatistic(scip, heurdata);
1014 	
1015 	      goto TERMINATE;
1016 	   }
1017 	
1018 	   *result = SCIP_DIDNOTFIND;
1019 	   /* initializing the subproblem */
1020 	   SCIP_CALL( SCIPcreate(&subscip) );
1021 	
1022 	   /* setup and solve the subproblem and catch the return code */
1023 	   retcode = setupAndSolveSubscipCrossover(scip, subscip, heur, heurdata, vars,
1024 	               fixedvars, fixedvals, nstallnodes, result, selection, nvars, nfixedvars, nusedsols);
1025 	
1026 	   /* free the subscip in any case */
1027 	   SCIP_CALL( SCIPfree(&subscip) );
1028 	   SCIP_CALL( retcode );
1029 	
1030 	TERMINATE:
1031 	   /* free buffer storage for variable fixings */
1032 	   SCIPfreeBufferArray(scip, &fixedvals);
1033 	   SCIPfreeBufferArray(scip, &fixedvars);
1034 	   SCIPfreeBufferArray(scip, &selection);
1035 	
1036 	   return SCIP_OKAY;
1037 	}
1038 	
1039 	/*
1040 	 * primal heuristic specific interface methods
1041 	 */
1042 	
1043 	/** creates the crossover primal heuristic and includes it in SCIP */
1044 	SCIP_RETCODE SCIPincludeHeurCrossover(
1045 	   SCIP*                 scip                /**< SCIP data structure */
1046 	   )
1047 	{
1048 	   SCIP_HEURDATA* heurdata;
1049 	   SCIP_HEUR* heur;
1050 	
1051 	   /* create Crossover primal heuristic data */
1052 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1053 	
1054 	   /* include primal heuristic */
1055 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1056 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1057 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCrossover, heurdata) );
1058 	
1059 	   assert(heur != NULL);
1060 	
1061 	   /* set non-NULL pointers to callback methods */
1062 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCrossover) );
1063 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCrossover) );
1064 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCrossover) );
1065 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCrossover) );
1066 	
1067 	   /* add crossover primal heuristic parameters */
1068 	
1069 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1070 	         "number of nodes added to the contingent of the total nodes",
1071 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1072 	
1073 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1074 	         "maximum number of nodes to regard in the subproblem",
1075 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1076 	
1077 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1078 	         "minimum number of nodes required to start the subproblem",
1079 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1080 	
1081 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nusedsols",
1082 	         "number of solutions to be taken into account",
1083 	         &heurdata->nusedsols, FALSE, DEFAULT_NUSEDSOLS, 2, INT_MAX, NULL, NULL) );
1084 	
1085 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
1086 	         "number of nodes without incumbent change that heuristic should wait",
1087 	         &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1088 	
1089 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1090 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1091 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1092 	
1093 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1094 	         "minimum percentage of integer variables that have to be fixed",
1095 	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1096 	
1097 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1098 	         "factor by which Crossover should at least improve the incumbent",
1099 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1100 	
1101 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1102 	         "factor by which the limit on the number of LP depends on the node limit",
1103 	         &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1104 	
1105 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/randomization",
1106 	         "should the choice which sols to take be randomized?",
1107 	         &heurdata->randomization, TRUE, DEFAULT_RANDOMIZATION, NULL, NULL) );
1108 	
1109 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dontwaitatroot",
1110 	         "should the nwaitingnodes parameter be ignored at the root node?",
1111 	         &heurdata->dontwaitatroot, TRUE, DEFAULT_DONTWAITATROOT, NULL, NULL) );
1112 	
1113 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1114 	         "should subproblem be created out of the rows in the LP rows?",
1115 	         &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1116 	
1117 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1118 	         "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1119 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1120 	
1121 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/permute",
1122 	         "should the subproblem be permuted to increase diversification?",
1123 	         &heurdata->permute, TRUE, DEFAULT_PERMUTE, NULL, NULL) );
1124 	
1125 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
1126 	         "limit on number of improving incumbent solutions in sub-CIP",
1127 	         &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
1128 	
1129 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
1130 	         "should uct node selection be used at the beginning of the search?",
1131 	         &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
1132 	   return SCIP_OKAY;
1133 	}
1134