Scippy

SCIP

Solving Constraint Integer Programs

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