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