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_mutation.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LNS heuristic that tries to randomly mutate the incumbent solution
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/heuristics.h"
35   	#include "scip/heur_mutation.h"
36   	#include "scip/pub_heur.h"
37   	#include "scip/pub_message.h"
38   	#include "scip/pub_misc.h"
39   	#include "scip/pub_sol.h"
40   	#include "scip/pub_var.h"
41   	#include "scip/scip_branch.h"
42   	#include "scip/scip_cons.h"
43   	#include "scip/scip_copy.h"
44   	#include "scip/scip_general.h"
45   	#include "scip/scip_heur.h"
46   	#include "scip/scip_mem.h"
47   	#include "scip/scip_message.h"
48   	#include "scip/scip_nodesel.h"
49   	#include "scip/scip_numerics.h"
50   	#include "scip/scip_param.h"
51   	#include "scip/scip_prob.h"
52   	#include "scip/scip_randnumgen.h"
53   	#include "scip/scip_sol.h"
54   	#include "scip/scip_solve.h"
55   	#include "scip/scip_solvingstats.h"
56   	#include <string.h>
57   	
58   	#define HEUR_NAME             "mutation"
59   	#define HEUR_DESC             "mutation heuristic randomly fixing variables"
60   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
61   	#define HEUR_PRIORITY         -1103010
62   	#define HEUR_FREQ             -1
63   	#define HEUR_FREQOFS          8
64   	#define HEUR_MAXDEPTH         -1
65   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
66   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
67   	
68   	#define DEFAULT_NODESOFS      500            /**< number of nodes added to the contingent of the total nodes          */
69   	#define DEFAULT_MAXNODES      5000           /**< maximum number of nodes to regard in the subproblem                 */
70   	#define DEFAULT_MINIMPROVE    0.01           /**< factor by which Mutation should at least improve the incumbent      */
71   	#define DEFAULT_MINNODES      500            /**< minimum number of nodes to regard in the subproblem                 */
72   	#define DEFAULT_MINFIXINGRATE 0.8            /**< minimum percentage of integer variables that have to be fixed       */
73   	#define DEFAULT_NODESQUOT     0.1            /**< subproblem nodes in relation to nodes of the original problem       */
74   	#define DEFAULT_NWAITINGNODES 200            /**< number of nodes without incumbent change that heuristic should wait */
75   	#define DEFAULT_USELPROWS     FALSE          /**< should subproblem be created out of the rows in the LP rows,
76   	                                              *   otherwise, the copy constructors of the constraints handlers are used */
77   	#define DEFAULT_COPYCUTS      TRUE           /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
78   	                                              *   cutpool of the original scip be copied to constraints of the subscip */
79   	#define DEFAULT_BESTSOLLIMIT   -1            /**< limit on number of improving incumbent solutions in sub-CIP            */
80   	#define DEFAULT_USEUCT         FALSE         /**< should uct node selection be used at the beginning of the search?     */
81   	#define DEFAULT_RANDSEED       19            /**< initial random seed */
82   	/*
83   	 * Data structures
84   	 */
85   	
86   	/** primal heuristic data */
87   	struct SCIP_HeurData
88   	{
89   	   int                   nodesofs;           /**< number of nodes added to the contingent of the total nodes          */
90   	   int                   maxnodes;           /**< maximum number of nodes to regard in the subproblem                 */
91   	   int                   minnodes;           /**< minimum number of nodes to regard in the subproblem                 */
92   	   SCIP_Real             minfixingrate;      /**< minimum percentage of integer variables that have to be fixed       */
93   	   int                   nwaitingnodes;      /**< number of nodes without incumbent change that heuristic should wait */
94   	   SCIP_Real             minimprove;         /**< factor by which Mutation should at least improve the incumbent      */
95   	   SCIP_Longint          usednodes;          /**< nodes already used by Mutation in earlier calls                     */
96   	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem       */
97   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator                              */
98   	   SCIP_Bool             uselprows;          /**< should subproblem be created out of the rows in the LP rows?        */
99   	   SCIP_Bool             copycuts;           /**< if uselprows == FALSE, should all active cuts from cutpool be copied
100  	                                              *   to constraints in subproblem?
101  	                                              */
102  	   int                   bestsollimit;       /**< limit on number of improving incumbent solutions in sub-CIP            */
103  	   SCIP_Bool             useuct;             /**< should uct node selection be used at the beginning of the search?  */
104  	};
105  	
106  	
107  	/*
108  	 * Local methods
109  	 */
110  	
111  	/** determine variables and values which should be fixed in the mutation subproblem */
112  	static
113  	SCIP_RETCODE determineVariableFixings(
114  	   SCIP*                 scip,               /**< original SCIP data structure                                  */
115  	   SCIP_VAR**            fixedvars,          /**< array to store the variables that should be fixed in the subproblem */
116  	   SCIP_Real*            fixedvals,          /**< array to store the fixing values to fix variables in the subproblem */
117  	   int*                  nfixedvars,         /**< pointer to store the number of variables that should be fixed */
118  	   SCIP_Real             minfixingrate,      /**< percentage of integer variables that have to be fixed         */
119  	   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator                                       */
120  	   SCIP_Bool*            success             /**< used to store whether the creation of the subproblem worked   */
121  	   )
122  	{
123  	   SCIP_VAR** vars;                          /* original scip variables                    */
124  	   SCIP_SOL* sol;                            /* pool of solutions                          */
125  	
126  	   int nvars;
127  	   int nbinvars;
128  	   int nintvars;
129  	   int ndiscretevars;
130  	   int i;
131  	
132  	   assert(fixedvars != NULL);
133  	   assert(fixedvals != NULL);
134  	
135  	   /* get required data of the original problem */
136  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
137  	   sol = SCIPgetBestSol(scip);
138  	   assert(sol != NULL);
139  	
140  	   /* compute the number of variables that should be fixed in the subproblem */
141  	   *nfixedvars = (int)(minfixingrate * (nbinvars + nintvars));
142  	
143  	   /* avoid the two corner cases that no or all discrete variables should be fixed */
144  	   if( *nfixedvars == 0 || *nfixedvars == nbinvars + nintvars )
145  	   {
146  	      *success = FALSE;
147  	      return SCIP_OKAY;
148  	   }
149  	   assert(*nfixedvars < nbinvars + nintvars);
150  	
151  	   ndiscretevars = nbinvars + nintvars;
152  	   /* copy the binary and integer variables into fixedvars */
153  	   BMScopyMemoryArray(fixedvars, vars, ndiscretevars);
154  	
155  	   /* shuffle the array randomly */
156  	   SCIPrandomPermuteArray(randnumgen, (void **)fixedvars, 0, nbinvars + nintvars);
157  	
158  	   *success = TRUE;
159  	   /* store the fixing values for the subset of variables that should be fixed */
160  	   for( i = 0; i < *nfixedvars; ++i )
161  	   {
162  	      /* fix all randomly marked variables */
163  	      SCIP_Real solval;
164  	      SCIP_Real lb;
165  	      SCIP_Real ub;
166  	
167  	      solval = SCIPgetSolVal(scip, sol, fixedvars[i]);
168  	      lb = SCIPvarGetLbGlobal(fixedvars[i]);
169  	      ub = SCIPvarGetUbGlobal(fixedvars[i]);
170  	      assert(SCIPisLE(scip, lb, ub));
171  	
172  	      /* due to dual reductions, it may happen that the solution value is not in
173  	            the variable's domain anymore */
174  	      if( SCIPisLT(scip, solval, lb) )
175  	         solval = lb;
176  	      else if( SCIPisGT(scip, solval, ub) )
177  	         solval = ub;
178  	
179  	      /* we cannot fix to infinite solution values, better break in this case */
180  	      if( SCIPisInfinity(scip, REALABS(solval)) )
181  	      {
182  	         *success = FALSE;
183  	         break;
184  	      }
185  	
186  	      /* store the possibly adjusted solution value as fixing value */
187  	      fixedvals[i] = solval;
188  	   }
189  	
190  	   return SCIP_OKAY;
191  	}
192  	
193  	/** setup and solve mutation sub-SCIP */
194  	static
195  	SCIP_RETCODE setupAndSolveSubscipMutation(
196  	   SCIP*                 scip,               /**< SCIP data structure */
197  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
198  	   SCIP_HEUR*            heur,               /**< mutation heuristic */
199  	   SCIP_VAR**            fixedvars,          /**< array to store the variables that should be fixed in the subproblem */
200  	   SCIP_Real*            fixedvals,          /**< array to store the fixing values to fix variables in the subproblem */
201  	   int                   nfixedvars,         /**< the number of variables that should be fixed */
202  	   SCIP_Longint          nsubnodes,          /**< node limit for the subproblem */
203  	   SCIP_RESULT*          result              /**< pointer to store the result */
204  	   )
205  	{
206  	   SCIP_VAR** subvars;                       /* subproblem's variables                              */
207  	   SCIP_VAR** vars;                          /* original problem's variables                        */
208  	   SCIP_HASHMAP* varmapfw;                   /* mapping of SCIP variables to sub-SCIP variables */
209  	   SCIP_HEURDATA* heurdata;
210  	   SCIP_Real cutoff;                         /* objective cutoff for the subproblem                 */
211  	   SCIP_Real upperbound;
212  	   int nvars;                                /* number of original problem's variables              */
213  	   int i;
214  	   SCIP_Bool success;
215  	
216  	   assert(scip != NULL);
217  	   assert(subscip != NULL);
218  	   assert(heur != NULL);
219  	   assert(fixedvars != NULL);
220  	   assert(fixedvals != NULL);
221  	
222  	   heurdata = SCIPheurGetData(heur);
223  	   assert(heurdata != NULL);
224  	
225  	   vars = SCIPgetVars(scip);
226  	   nvars = SCIPgetNVars(scip);
227  	
228  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
229  	
230  	   /* create the variable mapping hash map */
231  	   SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
232  	
233  	   /* create a problem copy as sub SCIP */
234  	   SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "mutation", fixedvars, fixedvals, nfixedvars,
235  	         heurdata->uselprows, heurdata->copycuts, &success, NULL) );
236  	
237  	   for( i = 0; i < nvars; i++ )
238  	      subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
239  	
240  	   /* free hash map */
241  	   SCIPhashmapFree(&varmapfw);
242  	
243  	   /* do not abort subproblem on CTRL-C */
244  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
245  	
246  	#ifdef SCIP_DEBUG
247  	   /* for debugging, enable full output */
248  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
249  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
250  	#else
251  	   /* disable statistic timing inside sub SCIP and output to console */
252  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
253  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
254  	#endif
255  	
256  	   /* set limits for the subproblem */
257  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
258  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
259  	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
260  	
261  	   /* forbid recursive call of heuristics and separators solving subMIPs */
262  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
263  	
264  	   /* disable cutting plane separation */
265  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
266  	
267  	   /* disable expensive presolving */
268  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
269  	
270  	   /* use best estimate node selection */
271  	   if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
272  	   {
273  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
274  	   }
275  	
276  	   /* activate uct node selection at the top of the tree */
277  	   if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
278  	   {
279  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
280  	   }
281  	
282  	   /* use inference branching */
283  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
284  	   {
285  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
286  	   }
287  	
288  	   /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
289  	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
290  	   {
291  	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
292  	   }
293  	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
294  	   {
295  	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
296  	   }
297  	   if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
298  	   {
299  	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
300  	   }
301  	
302  	   /* speed up sub-SCIP by not checking dual LP feasibility */
303  	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
304  	
305  	   /* add an objective cutoff */
306  	   assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
307  	
308  	   upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
309  	   if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
310  	   {
311  	      cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
312  	                     + heurdata->minimprove * SCIPgetLowerbound(scip);
313  	   }
314  	   else
315  	   {
316  	      if( SCIPgetUpperbound(scip) >= 0 )
317  	         cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
318  	      else
319  	         cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
320  	   }
321  	   cutoff = MIN(upperbound, cutoff);
322  	   SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
323  	
324  	   /* solve the subproblem
325  	    *
326  	    * Errors in solving the subproblem should not kill the overall solving process
327  	    * Hence, the return code is caught but only in debug mode, SCIP will stop.
328  	    */
329  	   SCIPdebugMsg(scip, "Solve Mutation subMIP\n");
330  	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
331  	
332  	   /* transfer variable statistics from sub-SCIP */
333  	   SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
334  	
335  	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
336  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
337  	
338  	   heurdata->usednodes += SCIPgetNNodes(subscip);
339  	
340  	   /* check, whether a solution was found;
341  	    * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
342  	    */
343  	   SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
344  	   if( success )
345  	      *result = SCIP_FOUNDSOL;
346  	
347  	   /* free subproblem */
348  	   SCIPfreeBufferArray(scip, &subvars);
349  	
350  	   return SCIP_OKAY;
351  	}
352  	
353  	
354  	/*
355  	 * Callback methods of primal heuristic
356  	 */
357  	
358  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
359  	static
360  	SCIP_DECL_HEURCOPY(heurCopyMutation)
361  	{  /*lint --e{715}*/
362  	   assert(scip != NULL);
363  	   assert(heur != NULL);
364  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
365  	
366  	   /* call inclusion method of primal heuristic */
367  	   SCIP_CALL( SCIPincludeHeurMutation(scip) );
368  	
369  	   return SCIP_OKAY;
370  	}
371  	
372  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
373  	static
374  	SCIP_DECL_HEURFREE(heurFreeMutation)
375  	{  /*lint --e{715}*/
376  	   SCIP_HEURDATA* heurdata;
377  	
378  	   assert(heur != NULL);
379  	   assert(scip != NULL);
380  	
381  	   /* get heuristic data */
382  	   heurdata = SCIPheurGetData(heur);
383  	   assert(heurdata != NULL);
384  	
385  	   /* free heuristic data */
386  	   SCIPfreeBlockMemory(scip, &heurdata);
387  	   SCIPheurSetData(heur, NULL);
388  	
389  	   return SCIP_OKAY;
390  	}
391  	
392  	/** initialization method of primal heuristic (called after problem was transformed) */
393  	static
394  	SCIP_DECL_HEURINIT(heurInitMutation)
395  	{  /*lint --e{715}*/
396  	   SCIP_HEURDATA* heurdata;
397  	
398  	   assert(heur != NULL);
399  	   assert(scip != NULL);
400  	
401  	   /* get heuristic's data */
402  	   heurdata = SCIPheurGetData(heur);
403  	   assert(heurdata != NULL);
404  	
405  	   /* initialize data */
406  	   heurdata->usednodes = 0;
407  	
408  	   /* create random number generator */
409  	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
410  	         DEFAULT_RANDSEED, TRUE) );
411  	
412  	   return SCIP_OKAY;
413  	}
414  	
415  	/** deinitialization method of primal heuristic */
416  	static
417  	SCIP_DECL_HEUREXIT(heurExitMutation)
418  	{  /*lint --e{715}*/
419  	   SCIP_HEURDATA* heurdata;
420  	
421  	   assert(heur != NULL);
422  	   assert(scip != NULL);
423  	
424  	   /* get heuristic data */
425  	   heurdata = SCIPheurGetData(heur);
426  	   assert(heurdata != NULL);
427  	
428  	   /* free random number generator */
429  	   SCIPfreeRandom(scip, &heurdata->randnumgen);
430  	
431  	   return SCIP_OKAY;
432  	}
433  	
434  	/** execution method of primal heuristic */
435  	static
436  	SCIP_DECL_HEUREXEC(heurExecMutation)
437  	{  /*lint --e{715}*/
438  	   SCIP_Longint maxnnodes;
439  	   SCIP_Longint nsubnodes;                   /* node limit for the subproblem                       */
440  	
441  	   SCIP_HEURDATA* heurdata;                  /* heuristic's data                                    */
442  	   SCIP* subscip;                            /* the subproblem created by mutation                  */
443  	   SCIP_VAR** fixedvars;                     /* array to store variables that should be fixed in the subproblem */
444  	   SCIP_Real* fixedvals;                     /* array to store fixing values for the variables */
445  	
446  	   SCIP_Real maxnnodesr;
447  	
448  	   int nfixedvars;
449  	   int nbinvars;
450  	   int nintvars;
451  	
452  	   SCIP_Bool success;
453  	
454  	   SCIP_RETCODE retcode;
455  	
456  	   assert( heur != NULL );
457  	   assert( scip != NULL );
458  	   assert( result != NULL );
459  	
460  	   /* get heuristic's data */
461  	   heurdata = SCIPheurGetData(heur);
462  	   assert(heurdata != NULL);
463  	
464  	   *result = SCIP_DELAYED;
465  	
466  	   /* only call heuristic, if feasible solution is available */
467  	   if( SCIPgetNSols(scip) <= 0 )
468  	      return SCIP_OKAY;
469  	
470  	   /* only call heuristic, if the best solution comes from transformed problem */
471  	   assert(SCIPgetBestSol(scip) != NULL);
472  	   if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
473  	      return SCIP_OKAY;
474  	
475  	   /* only call heuristic, if enough nodes were processed since last incumbent */
476  	   if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip))  < heurdata->nwaitingnodes)
477  	      return SCIP_OKAY;
478  	
479  	   *result = SCIP_DIDNOTRUN;
480  	
481  	   SCIP_CALL( SCIPgetVarsData(scip, NULL, NULL, &nbinvars, &nintvars, NULL, NULL) );
482  	
483  	   /* only call heuristic, if discrete variables are present */
484  	   if( nbinvars + nintvars == 0 )
485  	      return SCIP_OKAY;
486  	
487  	   /* calculate the maximal number of branching nodes until heuristic is aborted */
488  	   maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
489  	
490  	   /* reward mutation if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
491  	   maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0);
492  	   maxnnodes = (SCIP_Longint) maxnnodesr - 100 * SCIPheurGetNCalls(heur);
493  	   maxnnodes += heurdata->nodesofs;
494  	
495  	   /* determine the node limit for the current process */
496  	   nsubnodes = maxnnodes - heurdata->usednodes;
497  	   nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
498  	
499  	   /* check whether we have enough nodes left to call subproblem solving */
500  	   if( nsubnodes < heurdata->minnodes )
501  	       return SCIP_OKAY;
502  	
503  	   if( SCIPisStopped(scip) )
504  	      return SCIP_OKAY;
505  	
506  	   /* check whether there is enough time and memory left */
507  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
508  	
509  	   if( !success )
510  	      return SCIP_OKAY;
511  	
512  	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
513  	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
514  	
515  	   /* determine variables that should be fixed in the mutation subproblem */
516  	   SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata->minfixingrate, heurdata->randnumgen, &success) );
517  	
518  	   /* terminate if it is not possible to create the subproblem */
519  	   if( !success )
520  	   {
521  	      SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
522  	      goto TERMINATE;
523  	   }
524  	
525  	   *result = SCIP_DIDNOTFIND;
526  	
527  	   /* initializing the subproblem */
528  	   SCIP_CALL( SCIPcreate(&subscip) );
529  	
530  	   /* setup and solve the subproblem and catch the return code */
531  	   retcode = setupAndSolveSubscipMutation(scip, subscip, heur, fixedvars, fixedvals, nfixedvars, nsubnodes, result);
532  	
533  	   /* free the subscip in any case */
534  	   SCIP_CALL( SCIPfree(&subscip) );
535  	   SCIP_CALL( retcode );
536  	
537  	   /* free storage for subproblem fixings */
538  	 TERMINATE:
539  	   SCIPfreeBufferArray(scip, &fixedvals);
540  	   SCIPfreeBufferArray(scip, &fixedvars);
541  	
542  	   return SCIP_OKAY;
543  	}
544  	
545  	/*
546  	 * primal heuristic specific interface methods
547  	 */
548  	
549  	/** creates the mutation primal heuristic and includes it in SCIP */
550  	SCIP_RETCODE SCIPincludeHeurMutation(
551  	   SCIP*                 scip                /**< SCIP data structure */
552  	   )
553  	{
554  	   SCIP_HEURDATA* heurdata;
555  	   SCIP_HEUR* heur;
556  	
557  	   /* create Mutation primal heuristic data */
558  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
559  	
560  	   /* include primal heuristic */
561  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
562  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
563  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMutation, heurdata) );
564  	
565  	   assert(heur != NULL);
566  	
567  	   /* set non-NULL pointers to callback methods */
568  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMutation) );
569  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMutation) );
570  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMutation) );
571  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMutation) );
572  	
573  	   /* add mutation primal heuristic parameters */
574  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
575  	         "number of nodes added to the contingent of the total nodes",
576  	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
577  	
578  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
579  	         "maximum number of nodes to regard in the subproblem",
580  	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
581  	
582  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
583  	         "minimum number of nodes required to start the subproblem",
584  	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
585  	
586  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
587  	         "number of nodes without incumbent change that heuristic should wait",
588  	         &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
589  	
590  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
591  	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
592  	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
593  	
594  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
595  	         "percentage of integer variables that have to be fixed",
596  	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
597  	
598  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
599  	         "factor by which " HEUR_NAME " should at least improve the incumbent",
600  	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
601  	
602  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
603  	         "should subproblem be created out of the rows in the LP rows?",
604  	         &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
605  	
606  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
607  	         "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
608  	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
609  	
610  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
611  	         "limit on number of improving incumbent solutions in sub-CIP",
612  	         &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
613  	
614  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
615  	         "should uct node selection be used at the beginning of the search?",
616  	         &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
617  	
618  	   return SCIP_OKAY;
619  	}
620