Scippy

SCIP

Solving Constraint Integer Programs

heur_mutation.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_mutation.c
17  * @brief LNS heuristic that tries to randomly mutate the incumbent solution
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include "scip/scip.h"
26 #include "scip/scipdefplugins.h"
27 #include "scip/cons_linear.h"
28 #include "scip/heur_mutation.h"
29 #include "scip/pub_misc.h"
30 
31 #define HEUR_NAME "mutation"
32 #define HEUR_DESC "mutation heuristic randomly fixing variables"
33 #define HEUR_DISPCHAR 'M'
34 #define HEUR_PRIORITY -1103000
35 #define HEUR_FREQ -1
36 #define HEUR_FREQOFS 8
37 #define HEUR_MAXDEPTH -1
38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
39 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
40 
41 #define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */
42 #define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */
43 #define DEFAULT_MINIMPROVE 0.01 /* factor by which Mutation should at least improve the incumbent */
44 #define DEFAULT_MINNODES 500 /* minimum number of nodes to regard in the subproblem */
45 #define DEFAULT_MINFIXINGRATE 0.8 /* minimum percentage of integer variables that have to be fixed */
46 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
47 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
48 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
49  * otherwise, the copy constructors of the constraints handlers are used */
50 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
51  * cutpool of the original scip be copied to constraints of the subscip */
52 #define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */
53 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
54 #define DEFAULT_RANDSEED 19 /* initial random seed */
55 /*
56  * Data structures
57  */
58 
59 /** primal heuristic data */
60 struct SCIP_HeurData
61 {
62  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
63  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
64  int minnodes; /**< minimum number of nodes to regard in the subproblem */
65  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
66  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
67  SCIP_Real minimprove; /**< factor by which Mutation should at least improve the incumbent */
68  SCIP_Longint usednodes; /**< nodes already used by Mutation in earlier calls */
69  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
70  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
71  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
72  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
73  * to constraints in subproblem?
74  */
75  int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
76  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
77 };
78 
79 
80 /*
81  * Local methods
82  */
83 
84 /** determine variables and values which should be fixed in the mutation subproblem */
85 static
87  SCIP* scip, /**< original SCIP data structure */
88  SCIP_VAR** fixedvars, /**< array to store the variables that should be fixed in the subproblem */
89  SCIP_Real* fixedvals, /**< array to store the fixing values to fix variables in the subproblem */
90  int* nfixedvars, /**< pointer to store the number of variables that should be fixed */
91  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
92  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
93  SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */
94  )
95 {
96  SCIP_VAR** vars; /* original scip variables */
97  SCIP_SOL* sol; /* pool of solutions */
98 
99  int nvars;
100  int nbinvars;
101  int nintvars;
102  int ndiscretevars;
103  int i;
104 
105  assert(fixedvars != NULL);
106  assert(fixedvals != NULL);
107 
108  /* get required data of the original problem */
109  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
110  sol = SCIPgetBestSol(scip);
111  assert(sol != NULL);
112 
113  /* compute the number of variables that should be fixed in the subproblem */
114  *nfixedvars = (int)(minfixingrate * (nbinvars + nintvars));
115 
116  /* avoid the two corner cases that no or all discrete variables should be fixed */
117  if( *nfixedvars == 0 || *nfixedvars == nbinvars + nintvars )
118  {
119  *success = FALSE;
120  return SCIP_OKAY;
121  }
122  assert(*nfixedvars < nbinvars + nintvars);
123 
124  ndiscretevars = nbinvars + nintvars;
125  /* copy the binary and integer variables into fixedvars */
126  BMScopyMemoryArray(fixedvars, vars, ndiscretevars);
127 
128  /* shuffle the array randomly */
129  SCIPrandomPermuteArray(randnumgen, (void **)fixedvars, 0, nbinvars + nintvars);
130 
131  *success = TRUE;
132  /* store the fixing values for the subset of variables that should be fixed */
133  for( i = 0; i < *nfixedvars; ++i )
134  {
135  /* fix all randomly marked variables */
136  SCIP_Real solval;
137  SCIP_Real lb;
138  SCIP_Real ub;
139 
140  solval = SCIPgetSolVal(scip, sol, fixedvars[i]);
141  lb = SCIPvarGetLbGlobal(fixedvars[i]);
142  ub = SCIPvarGetUbGlobal(fixedvars[i]);
143  assert(SCIPisLE(scip, lb, ub));
144 
145  /* due to dual reductions, it may happen that the solution value is not in
146  the variable's domain anymore */
147  if( SCIPisLT(scip, solval, lb) )
148  solval = lb;
149  else if( SCIPisGT(scip, solval, ub) )
150  solval = ub;
151 
152  /* we cannot fix to infinite solution values, better break in this case */
153  if( SCIPisInfinity(scip, REALABS(solval)) )
154  {
155  *success = FALSE;
156  break;
157  }
158 
159  /* store the possibly adjusted solution value as fixing value */
160  fixedvals[i] = solval;
161  }
162 
163  return SCIP_OKAY;
164 }
165 
166 /** creates a new solution for the original problem by copying the solution of the subproblem */
167 static
169  SCIP* scip, /**< original SCIP data structure */
170  SCIP* subscip, /**< SCIP structure of the subproblem */
171  SCIP_VAR** subvars, /**< the variables of the subproblem */
172  SCIP_HEUR* heur, /**< mutation heuristic structure */
173  SCIP_SOL* subsol, /**< solution of the subproblem */
174  SCIP_Bool* success /**< used to store whether new solution was found or not */
175  )
176 {
177  SCIP_VAR** vars; /* the original problem's variables */
178  int nvars;
179  SCIP_Real* subsolvals; /* solution values of the subproblem */
180  SCIP_SOL* newsol; /* solution to be created for the original problem */
181 
182  assert(scip != NULL);
183  assert(subscip != NULL);
184  assert(subvars != NULL);
185  assert(subsol != NULL);
186 
187  /* get variables' data */
188  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
189  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
190  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
191  */
192  assert(nvars <= SCIPgetNOrigVars(subscip));
193 
194  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
195 
196  /* copy the solution */
197  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
198 
199  /* create new solution for the original problem */
200  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
201  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
202 
203  /* try to add new solution to scip and free it immediately */
204  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
205 
206  SCIPfreeBufferArray(scip, &subsolvals);
207 
208  return SCIP_OKAY;
209 }
210 
211 
212 /*
213  * Callback methods of primal heuristic
214  */
215 
216 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
217 static
218 SCIP_DECL_HEURCOPY(heurCopyMutation)
219 { /*lint --e{715}*/
220  assert(scip != NULL);
221  assert(heur != NULL);
222  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
223 
224  /* call inclusion method of primal heuristic */
226 
227  return SCIP_OKAY;
228 }
229 
230 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
231 static
232 SCIP_DECL_HEURFREE(heurFreeMutation)
233 { /*lint --e{715}*/
234  SCIP_HEURDATA* heurdata;
235 
236  assert(heur != NULL);
237  assert(scip != NULL);
238 
239  /* get heuristic data */
240  heurdata = SCIPheurGetData(heur);
241  assert(heurdata != NULL);
242 
243  /* free heuristic data */
244  SCIPfreeBlockMemory(scip, &heurdata);
245  SCIPheurSetData(heur, NULL);
246 
247  return SCIP_OKAY;
248 }
249 
250 /** initialization method of primal heuristic (called after problem was transformed) */
251 static
252 SCIP_DECL_HEURINIT(heurInitMutation)
253 { /*lint --e{715}*/
254  SCIP_HEURDATA* heurdata;
255 
256  assert(heur != NULL);
257  assert(scip != NULL);
258 
259  /* get heuristic's data */
260  heurdata = SCIPheurGetData(heur);
261  assert(heurdata != NULL);
262 
263  /* initialize data */
264  heurdata->usednodes = 0;
265 
266  /* create random number generator */
267  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
269 
270  return SCIP_OKAY;
271 }
272 
273 /** deinitialization method of primal heuristic */
274 static
275 SCIP_DECL_HEUREXIT(heurExitMutation)
276 { /*lint --e{715}*/
277  SCIP_HEURDATA* heurdata;
278 
279  assert(heur != NULL);
280  assert(scip != NULL);
281 
282  /* get heuristic data */
283  heurdata = SCIPheurGetData(heur);
284  assert(heurdata != NULL);
285 
286  /* free random number generator */
287  SCIPrandomFree(&heurdata->randnumgen);
288 
289  return SCIP_OKAY;
290 }
291 
292 
293 /** execution method of primal heuristic */
294 static
295 SCIP_DECL_HEUREXEC(heurExecMutation)
296 { /*lint --e{715}*/
297  SCIP_Longint maxnnodes;
298  SCIP_Longint nsubnodes; /* node limit for the subproblem */
299 
300  SCIP_HEURDATA* heurdata; /* heuristic's data */
301  SCIP* subscip; /* the subproblem created by mutation */
302  SCIP_VAR** vars; /* original problem's variables */
303  SCIP_VAR** fixedvars; /* array to store variables that should be fixed in the subproblem */
304  SCIP_Real* fixedvals; /* array to store fixing values for the variables */
305  SCIP_VAR** subvars; /* subproblem's variables */
306  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
307 
308  SCIP_Real cutoff; /* objective cutoff for the subproblem */
309  SCIP_Real maxnnodesr;
310  SCIP_Real upperbound;
311 
312  int nfixedvars;
313  int nbinvars;
314  int nintvars;
315  int nvars; /* number of original problem's variables */
316  int i;
317 
318  SCIP_Bool success;
319 
320  SCIP_RETCODE retcode;
321 
322  assert( heur != NULL );
323  assert( scip != NULL );
324  assert( result != NULL );
325 
326  /* get heuristic's data */
327  heurdata = SCIPheurGetData(heur);
328  assert(heurdata != NULL);
329 
330  *result = SCIP_DELAYED;
331 
332  /* only call heuristic, if feasible solution is available */
333  if( SCIPgetNSols(scip) <= 0 )
334  return SCIP_OKAY;
335 
336  /* only call heuristic, if the best solution comes from transformed problem */
337  assert(SCIPgetBestSol(scip) != NULL);
339  return SCIP_OKAY;
340 
341  /* only call heuristic, if enough nodes were processed since last incumbent */
342  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes)
343  return SCIP_OKAY;
344 
345  *result = SCIP_DIDNOTRUN;
346 
347  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
348 
349  /* only call heuristic, if discrete variables are present */
350  if( nbinvars + nintvars == 0 )
351  return SCIP_OKAY;
352 
353  /* calculate the maximal number of branching nodes until heuristic is aborted */
354  maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
355 
356  /* reward mutation if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
357  maxnnodesr *= 1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0);
358  maxnnodes = (SCIP_Longint) maxnnodesr - 100 * SCIPheurGetNCalls(heur);
359  maxnnodes += heurdata->nodesofs;
360 
361  /* determine the node limit for the current process */
362  nsubnodes = maxnnodes - heurdata->usednodes;
363  nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
364 
365  /* check whether we have enough nodes left to call subproblem solving */
366  if( nsubnodes < heurdata->minnodes )
367  return SCIP_OKAY;
368 
369  if( SCIPisStopped(scip) )
370  return SCIP_OKAY;
371 
372  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
373  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
374 
375  /* determine variables that should be fixed in the mutation subproblem */
376  SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata->minfixingrate, heurdata->randnumgen, &success) );
377 
378  /* terminate if it is not possible to create the subproblem */
379  if( !success )
380  {
381  SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
382  goto TERMINATE;
383  }
384 
385  /* check whether there is enough time and memory left */
386  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
387 
388  if( !success )
389  goto TERMINATE;
390 
391  *result = SCIP_DIDNOTFIND;
392 
393  /* initializing the subproblem */
394  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
395  SCIP_CALL( SCIPcreate(&subscip) );
396 
397  /* create the variable mapping hash map */
398  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
399 
400  /* create a problem copy as sub SCIP */
401  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "mutation", fixedvars, fixedvals, nfixedvars,
402  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
403 
404  for( i = 0; i < nvars; i++ )
405  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
406 
407  /* free hash map */
408  SCIPhashmapFree(&varmapfw);
409 
410  /* do not abort subproblem on CTRL-C */
411  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
412 
413 #ifdef SCIP_DEBUG
414  /* for debugging, enable full output */
415  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
416  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
417 #else
418  /* disable statistic timing inside sub SCIP and output to console */
419  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
420  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
421 #endif
422 
423  /* set limits for the subproblem */
424  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
425  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
426  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
427 
428  /* forbid recursive call of heuristics and separators solving subMIPs */
429  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
430 
431  /* disable cutting plane separation */
433 
434  /* disable expensive presolving */
436 
437  /* use best estimate node selection */
438  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
439  {
440  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
441  }
442 
443  /* activate uct node selection at the top of the tree */
444  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
445  {
446  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
447  }
448 
449  /* use inference branching */
450  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
451  {
452  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
453  }
454 
455  /* enable conflict analysis and restrict conflict pool */
456  if( !SCIPisParamFixed(subscip, "conflict/enable") )
457  {
458  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
459  }
460  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
461  {
462  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
463  }
464 
465  /* speed up sub-SCIP by not checking dual LP feasibility */
466  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
467 
468  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
469  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
470  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
471  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
472  * made for the original SCIP
473  */
474  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
475  {
476  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
477  }
478 
479  /* add an objective cutoff */
481 
482  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
483  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
484  {
485  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
486  + heurdata->minimprove * SCIPgetLowerbound(scip);
487  }
488  else
489  {
490  if( SCIPgetUpperbound(scip) >= 0 )
491  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
492  else
493  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
494  }
495  cutoff = MIN(upperbound, cutoff);
496  SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
497 
498  /* solve the subproblem */
499  SCIPdebugMsg(scip, "Solve Mutation subMIP\n");
500  retcode = SCIPsolve(subscip);
501 
502  /* Errors in solving the subproblem should not kill the overall solving process
503  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
504  */
505  if( retcode != SCIP_OKAY )
506  {
507  SCIPwarningMessage(scip, "Error while solving subproblem in Mutation heuristic; sub-SCIP terminated with code <%d>\n",retcode);
508  SCIPABORT();
509  }
510  else
511  {
512  /* transfer variable statistics from sub-SCIP */
513  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
514  }
515 
516  /* print solving statistics of subproblem if we are in SCIP's debug mode */
518 
519  heurdata->usednodes += SCIPgetNNodes(subscip);
520 
521  /* check, whether a solution was found */
522  if( SCIPgetNSols(subscip) > 0 )
523  {
524  SCIP_SOL** subsols;
525  int nsubsols;
526 
527  /* check, whether a solution was found;
528  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
529  */
530  nsubsols = SCIPgetNSols(subscip);
531  subsols = SCIPgetSols(subscip);
532  success = FALSE;
533  for( i = 0; i < nsubsols && !success; ++i )
534  {
535  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
536  }
537  if( success )
538  *result = SCIP_FOUNDSOL;
539  }
540 
541  /* free subproblem */
542  SCIPfreeBufferArray(scip, &subvars);
543  SCIP_CALL( SCIPfree(&subscip) );
544  /* free storage for subproblem fixings */
545  TERMINATE:
546  SCIPfreeBufferArray(scip, &fixedvals);
547  SCIPfreeBufferArray(scip, &fixedvars);
548 
549  return SCIP_OKAY;
550 }
551 
552 /*
553  * primal heuristic specific interface methods
554  */
555 
556 /** creates the mutation primal heuristic and includes it in SCIP */
558  SCIP* scip /**< SCIP data structure */
559  )
560 {
561  SCIP_HEURDATA* heurdata;
562  SCIP_HEUR* heur;
563 
564  /* create Mutation primal heuristic data */
565  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
566 
567  /* include primal heuristic */
568  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
570  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMutation, heurdata) );
571 
572  assert(heur != NULL);
573 
574  /* set non-NULL pointers to callback methods */
575  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyMutation) );
576  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeMutation) );
577  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitMutation) );
578  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitMutation) );
579 
580  /* add mutation primal heuristic parameters */
581  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
582  "number of nodes added to the contingent of the total nodes",
583  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
584 
585  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
586  "maximum number of nodes to regard in the subproblem",
587  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
588 
589  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
590  "minimum number of nodes required to start the subproblem",
591  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
592 
593  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
594  "number of nodes without incumbent change that heuristic should wait",
595  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
596 
597  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
598  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
599  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
600 
601  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
602  "percentage of integer variables that have to be fixed",
603  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
604 
605  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
606  "factor by which " HEUR_NAME " should at least improve the incumbent",
607  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
608 
609  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
610  "should subproblem be created out of the rows in the LP rows?",
611  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
612 
613  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
614  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
615  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
616 
617  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
618  "limit on number of improving incumbent solutions in sub-CIP",
619  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
620 
621  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
622  "should uct node selection be used at the beginning of the search?",
623  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
624 
625 
626  return SCIP_OKAY;
627 }
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
#define DEFAULT_COPYCUTS
Definition: heur_mutation.c:50
static SCIP_DECL_HEURCOPY(heurCopyMutation)
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
static SCIP_DECL_HEUREXIT(heurExitMutation)
SCIP_RETCODE SCIPincludeHeurMutation(SCIP *scip)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5130
static SCIP_DECL_HEURFREE(heurFreeMutation)
#define DEFAULT_NWAITINGNODES
Definition: heur_mutation.c:47
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6576
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12120
#define DEFAULT_MINNODES
Definition: heur_mutation.c:44
#define DEFAULT_RANDSEED
Definition: heur_mutation.c:54
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39108
#define FALSE
Definition: def.h:64
#define HEUR_DISPCHAR
Definition: heur_mutation.c:33
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4164
#define TRUE
Definition: def.h:63
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:8794
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MINFIXINGRATE
Definition: heur_mutation.c:45
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5104
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8034
#define HEUR_NAME
Definition: heur_mutation.c:31
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44659
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
static SCIP_DECL_HEUREXEC(heurExecMutation)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4373
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38219
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4602
#define DEFAULT_NODESQUOT
Definition: heur_mutation.c:46
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip.c:2420
LNS heuristic that tries to randomly mutate the incumbent solution.
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:169
#define DEFAULT_MAXNODES
Definition: heur_mutation.c:42
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
#define DEFAULT_MINIMPROVE
Definition: heur_mutation.c:43
#define HEUR_MAXDEPTH
Definition: heur_mutation.c:37
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
#define HEUR_USESSUBSCIP
Definition: heur_mutation.c:39
#define HEUR_PRIORITY
Definition: heur_mutation.c:34
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11114
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40070
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:93
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
#define DEFAULT_USELPROWS
Definition: heur_mutation.c:48
#define HEUR_FREQOFS
Definition: heur_mutation.c:36
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
#define HEUR_DESC
Definition: heur_mutation.c:32
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8907
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:899
#define HEUR_TIMING
Definition: heur_mutation.c:38
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define HEUR_FREQ
Definition: heur_mutation.c:35
static SCIP_DECL_HEURINIT(heurInitMutation)
#define SCIP_Longint
Definition: def.h:130
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4128
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38084
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
#define DEFAULT_BESTSOLLIMIT
Definition: heur_mutation.c:52
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45494
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42699
#define DEFAULT_USEUCT
Definition: heur_mutation.c:53
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
#define SCIPABORT()
Definition: def.h:288
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
default SCIP plugins
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5055
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
#define DEFAULT_NODESOFS
Definition: heur_mutation.c:41
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38483
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, SCIP_Real minfixingrate, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool *success)
Definition: heur_mutation.c:86