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