Scippy

SCIP

Solving Constraint Integer Programs

heur.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur.c
17  * @brief methods for primal heuristics
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/def.h"
28 #include "scip/set.h"
29 #include "scip/clock.h"
30 #include "scip/paramset.h"
31 #include "scip/primal.h"
32 #include "scip/scip.h"
33 #include "scip/heur.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_misc.h"
36 #include "scip/misc.h"
37 
38 #include "scip/struct_heur.h"
39 
40 /** compares two heuristics w. r. to their delay positions and their priority */
41 SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
42 { /*lint --e{715}*/
43  SCIP_HEUR* heur1 = (SCIP_HEUR*)elem1;
44  SCIP_HEUR* heur2 = (SCIP_HEUR*)elem2;
45 
46  assert(heur1 != NULL);
47  assert(heur2 != NULL);
48 
49  if( heur1->delaypos == heur2->delaypos )
50  return heur2->priority - heur1->priority; /* prefer higher priorities */
51  else if( heur1->delaypos == -1 )
52  return +1; /* prefer delayed heuristics */
53  else if( heur2->delaypos == -1 )
54  return -1; /* prefer delayed heuristics */
55  else if( heur1->ncalls * heur1->freq > heur2->ncalls * heur2->freq )
56  return +1;
57  else if( heur1->ncalls * heur1->freq < heur2->ncalls * heur2->freq )
58  return -1;
59  else
60  return heur1->delaypos - heur2->delaypos; /* prefer lower delay positions */
61 }
62 
63 
64 /** comparison method for sorting heuristics w.r.t. to their name */
65 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName)
66 {
67  return strcmp(SCIPheurGetName((SCIP_HEUR*)elem1), SCIPheurGetName((SCIP_HEUR*)elem2));
68 }
69 
70 /** method to call, when the priority of a heuristic was changed */
71 static
72 SCIP_DECL_PARAMCHGD(paramChgdHeurPriority)
73 { /*lint --e{715}*/
74  SCIP_PARAMDATA* paramdata;
75 
76  paramdata = SCIPparamGetData(param);
77  assert(paramdata != NULL);
78 
79  /* use SCIPsetHeurPriority() to mark the heuristics unsorted */
80  SCIP_CALL( SCIPsetHeurPriority(scip, (SCIP_HEUR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
81 
82  return SCIP_OKAY;
83 }
84 
85 /* resets diving settings counters */
87  SCIP_DIVESET* diveset, /**< diveset to be reset */
88  SCIP_SET* set /**< global SCIP settings */
89  )
90 {
91  assert(diveset != NULL);
92  assert(diveset->randnumgen != NULL);
93 
94  diveset->nlpiterations = 0L;
95  diveset->totaldepth = 0L;
96  diveset->totalsoldepth = 0L;
97  diveset->totalnnodes = 0L;
98  diveset->totalnbacktracks = 0L;
99  diveset->minsoldepth = INT_MAX;
100  diveset->maxsoldepth = -1;
101  diveset->mindepth = INT_MAX;
102  diveset->maxdepth = -1;
103  diveset->nlps = 0;
104  diveset->nsolsfound = 0;
105  diveset->nbestsolsfound = 0;
106  diveset->ncalls = 0;
107  diveset->nsolcalls = 0;
108 
109  /* reset the random number generator */
110  SCIPrandomSetSeed(diveset->randnumgen, (unsigned int) SCIPsetInitializeRandomSeed(set, (int)(diveset->initialseed % INT_MAX)));
111 
112  return SCIP_OKAY;
113 }
114 
115 /** update diveset statistics and global diveset statistics */
117  SCIP_DIVESET* diveset, /**< diveset to be reset */
118  SCIP_STAT* stat, /**< global SCIP statistics */
119  int depth, /**< the depth reached this time */
120  int nprobingnodes, /**< the number of probing nodes explored this time */
121  int nbacktracks, /**< the number of backtracks during probing this time */
122  SCIP_Longint nsolsfound, /**< number of new solutions found this time */
123  SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */
124  SCIP_Bool leavesol /**< has the diving heuristic reached a feasible leaf */
125  )
126 {
127  assert(diveset != NULL);
128 
129  diveset->totaldepth += depth;
130  diveset->mindepth = MIN(diveset->mindepth, depth);
131  diveset->maxdepth = MAX(diveset->maxdepth, depth);
132  diveset->totalnnodes += nprobingnodes;
133  diveset->totalnbacktracks += nbacktracks;
134  diveset->ncalls++;
135 
136  /* update solution statistics only if a solution was found */
137  if( leavesol )
138  {
139  diveset->totalsoldepth += depth;
140  diveset->minsoldepth = MIN(diveset->minsoldepth, depth);
141  diveset->maxsoldepth = MAX(diveset->maxsoldepth, depth);
142  diveset->nsolcalls++;
143  }
144 
145  diveset->nsolsfound += nsolsfound;
146  diveset->nbestsolsfound += nbestsolsfound;
147 
148  stat->totaldivesetdepth += depth;
149  stat->ndivesetcalls++;
150 }
151 
152 /** append diveset to heuristic array of divesets */
153 static
155  SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */
156  SCIP_DIVESET* diveset /**< pointer to the freshly created diveset */
157  )
158 {
159  assert(heur != NULL);
160  assert(diveset != NULL);
161  assert(diveset->heur == NULL);
162 
163  diveset->heur = heur;
164 
165  if( heur->divesets == NULL )
166  {
167  assert(heur->ndivesets == 0);
169  }
170  else
171  {
172  assert(heur->ndivesets > 0);
173  SCIP_ALLOC( BMSreallocMemoryArray(&heur->divesets, heur->ndivesets + 1) ); /*lint !e776 I expect no overflow here */
174  }
175 
176  /* append diveset to the end of the array */
177  heur->divesets[heur->ndivesets] = diveset;
178  heur->ndivesets++;
179 
180  return SCIP_OKAY;
181 }
182 
183 /** create a set of diving heuristic settings */
185  SCIP_DIVESET** divesetptr, /**< pointer to the freshly created diveset */
186  SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */
187  const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */
188  SCIP_SET* set, /**< global SCIP settings */
189  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
190  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
191  SCIP_Real minreldepth, /**< minimal relative depth to start diving */
192  SCIP_Real maxreldepth, /**< maximal relative depth to start diving */
193  SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */
194  SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
195  * where diving is performed (0.0: no limit) */
196  SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
197  * where diving is performed (0.0: no limit) */
198  SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
199  SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
200  SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */
201  int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/
202  int maxlpiterofs, /**< additional number of allowed LP iterations */
203  unsigned int initialseed, /**< initial seed for random number generation */
204  SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */
205  SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but
206  * more general constraint handler diving variable selection? */
207  SCIP_DIVETYPE divetypemask, /**< bit mask that represents the supported dive types by this dive set */
208  SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)) /**< method for candidate score and rounding direction */
209  )
210 {
211  char paramname[SCIP_MAXSTRLEN];
212  const char* divesetname;
213  SCIP_DIVESET* diveset;
214 
215  assert(divesetptr != NULL);
216  assert(set != NULL);
217  assert(divesetgetscore != NULL);
218  assert(heur != NULL);
219  assert(blkmem != NULL);
220 
221  SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetptr) );
222  diveset = *divesetptr;
223 
224  /* allocate random number generator. Note that we must make explicit use of random seed initialization because
225  * we create the random number generator directly, not through the public SCIP API
226  */
227  diveset->initialseed = initialseed;
228 
229  /* simply use 0 as initial seed, the seed is reset in SCIPdivesetReset, anyway */
230  SCIP_CALL( SCIPrandomCreate(&diveset->randnumgen, blkmem, 0) );
231 
232  /* for convenience, the name gets inferred from the heuristic to which the diveset is added if no name is provided */
233  divesetname = (name == NULL ? SCIPheurGetName(heur) : name);
234  SCIP_ALLOC( BMSduplicateMemoryArray(&diveset->name, divesetname, strlen(divesetname)+1) );
235  diveset->heur = NULL;
236 
237  /* copy callbacks */
238  diveset->divesetgetscore = divesetgetscore;
239 
240  SCIP_CALL( heurAddDiveset(heur, diveset) );
241  diveset->sol = NULL;
242  diveset->divetypemask = divetypemask;
243 
244  SCIP_CALL( SCIPdivesetReset(diveset, set) );
245 
246  /* add collection of diving heuristic specific parameters */
247  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/minreldepth", diveset->name);
248  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
249  paramname, "minimal relative depth to start diving",
250  &diveset->minreldepth, TRUE, minreldepth, 0.0, 1.0, NULL, NULL) );
251 
252  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxreldepth", diveset->name);
253  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
254  "maximal relative depth to start diving",
255  &diveset->maxreldepth, TRUE, maxreldepth, 0.0, 1.0, NULL, NULL) );
256 
257  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterquot", diveset->name);
258  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
259  paramname,
260  "maximal fraction of diving LP iterations compared to node LP iterations",
261  &diveset->maxlpiterquot, FALSE, maxlpiterquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
262 
263  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterofs", diveset->name);
264  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
265  paramname,
266  "additional number of allowed LP iterations",
267  &diveset->maxlpiterofs, FALSE, maxlpiterofs, 0, INT_MAX, NULL, NULL) );
268 
269  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquot", diveset->name);
270  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
271  paramname,
272  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
273  &diveset->maxdiveubquot, TRUE, maxdiveubquot, 0.0, 1.0, NULL, NULL) );
274 
275  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquot", diveset->name);
276  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
277  paramname,
278  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
279  &diveset->maxdiveavgquot, TRUE, maxdiveavgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
280 
281  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquotnosol", diveset->name);
282  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
283  paramname,
284  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
285  &diveset->maxdiveubquotnosol, TRUE, maxdiveubquotnosol, 0.0, 1.0, NULL, NULL) );
286 
287  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquotnosol", diveset->name);
288  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
289  paramname,
290  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
291  &diveset->maxdiveavgquotnosol, TRUE, maxdiveavgquotnosol, 0.0, SCIP_REAL_MAX, NULL, NULL) );
292 
293  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/backtrack", diveset->name);
294  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
295  paramname,
296  "use one level of backtracking if infeasibility is encountered?",
297  &diveset->backtrack, FALSE, backtrack, NULL, NULL) );
298 
299  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpresolvedomchgquot", diveset->name);
300  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
301  "percentage of immediate domain changes during probing to trigger LP resolve",
302  &diveset->lpresolvedomchgquot, FALSE, lpresolvedomchgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
303 
304  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpsolvefreq", diveset->name);
305  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
306  paramname,
307  "LP solve frequency for diving heuristics (0: only after enough domain changes have been found)",
308  &diveset->lpsolvefreq, FALSE, lpsolvefreq, 0, INT_MAX,
309  NULL, NULL) );
310 
311  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/onlylpbranchcands", diveset->name);
312  SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
313  paramname,
314  "should only LP branching candidates be considered instead of the slower but "
315  "more general constraint handler diving variable selection?",
316  &diveset->onlylpbranchcands, FALSE, onlylpbranchcands, NULL, NULL) );
317 
318  return SCIP_OKAY;
319 }
320 
321 /** get the heuristic to which this diving setting belongs */
323  SCIP_DIVESET* diveset /**< diving settings */
324  )
325 {
326  return diveset->heur;
327 }
328 
329 /** get the working solution of this dive set */
331  SCIP_DIVESET* diveset /**< diving settings */
332  )
333 {
334  assert(diveset != NULL);
335 
336  return diveset->sol;
337 }
338 
339 /** set the working solution for this dive set */
341  SCIP_DIVESET* diveset, /**< diving settings */
342  SCIP_SOL* sol /**< new working solution for this dive set, or NULL */
343  )
344 {
345  assert(diveset != NULL);
346 
347  diveset->sol = sol;
348 }
349 
350 /** get the name of the dive set */
351 const char* SCIPdivesetGetName(
352  SCIP_DIVESET* diveset /**< diving settings */
353  )
354 {
355  assert(diveset != NULL);
356 
357  return diveset->name;
358 }
359 
360 /** get the minimum relative depth of the diving settings */
362  SCIP_DIVESET* diveset /**< diving settings */
363  )
364 {
365  return diveset->minreldepth;
366 }
367 
368 /** get the maximum relative depth of the diving settings */
370  SCIP_DIVESET* diveset /**< diving settings */
371  )
372 {
373  return diveset->maxreldepth;
374 }
375 
376 /** get the number of successful runs of the diving settings */
378  SCIP_DIVESET* diveset /**< diving settings */
379  )
380 {
381  return 10 * diveset->nbestsolsfound + diveset->nsolsfound;
382 }
383 
384 /** get the number of calls to this dive set */
386  SCIP_DIVESET* diveset /**< diving settings */
387  )
388 {
389  assert(diveset != NULL);
390 
391  return diveset->ncalls;
392 }
393 
394 /** get the number of calls successfully terminated at a feasible leaf node */
396  SCIP_DIVESET* diveset /**< diving settings */
397  )
398 {
399  assert(diveset != NULL);
400 
401  return diveset->nsolcalls;
402 }
403 
404 /** get the minimum depth reached by this dive set */
406  SCIP_DIVESET* diveset /**< diving settings */
407  )
408 {
409  assert(diveset != NULL);
410 
411  return diveset->mindepth;
412 }
413 
414 /** get the maximum depth reached by this dive set */
416  SCIP_DIVESET* diveset /**< diving settings */
417  )
418 {
419  assert(diveset != NULL);
420 
421  return diveset->maxdepth;
422 }
423 
424 /** get the average depth this dive set reached during execution */
426  SCIP_DIVESET* diveset /**< diving settings */
427  )
428 {
429  assert(diveset != NULL);
430 
431  return (diveset->ncalls == 0 ? 0.0 : diveset->totaldepth / (SCIP_Real)diveset->ncalls);
432 }
433 
434 /** get the minimum depth at which this dive set found a solution */
436  SCIP_DIVESET* diveset /**< diving settings */
437  )
438 {
439  assert(diveset != NULL);
440 
441  return diveset->minsoldepth;
442 }
443 
444 /** get the maximum depth at which this dive set found a solution */
446  SCIP_DIVESET* diveset /**< diving settings */
447  )
448 {
449  assert(diveset != NULL);
450 
451  return diveset->maxsoldepth;
452 }
453 
454 /** get the average depth at which this dive set found a solution */
456  SCIP_DIVESET* diveset /**< diving settings */
457  )
458 {
459  assert(diveset != NULL);
460 
461  return (diveset->nsolcalls == 0 ? 0.0 : diveset->totalsoldepth / (SCIP_Real)diveset->nsolcalls);
462 }
463 
464 /** get the total number of LP iterations used by this dive set */
466  SCIP_DIVESET* diveset /**< diving settings */
467  )
468 {
469  assert(diveset != NULL);
470 
471  return diveset->nlpiterations;
472 }
473 
474 /** get the total number of probing nodes used by this dive set */
476  SCIP_DIVESET* diveset /**< diving settings */
477  )
478 {
479  assert(diveset != NULL);
480 
481  return diveset->totalnnodes;
482 }
483 
484 /** get the total number of backtracks performed by this dive set */
486  SCIP_DIVESET* diveset /**< diving settings */
487  )
488 {
489  assert(diveset != NULL);
490 
491  return diveset->totalnbacktracks;
492 }
493 
494 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */
496  SCIP_DIVESET* diveset /**< diving settings */
497  )
498 {
499  assert(diveset != NULL);
500 
501  return diveset->nsolsfound;
502 }
503 
504 
505 /** get the maximum LP iterations quotient of the diving settings */
507  SCIP_DIVESET* diveset /**< diving settings */
508  )
509 {
510  return diveset->maxlpiterquot;
511 }
512 
513 /** get the maximum LP iterations offset of the diving settings */
515  SCIP_DIVESET* diveset /**< diving settings */
516  )
517 {
518  return diveset->maxlpiterofs;
519 }
520 
521 /** get the maximum upper bound quotient parameter of the diving settings if no solution is available */
523  SCIP_DIVESET* diveset /**< diving settings */
524  )
525 {
526  return diveset->maxdiveubquotnosol;
527 }
528 
529 /** get the average quotient parameter of the diving settings if no solution is available */
531  SCIP_DIVESET* diveset /**< diving settings */
532  )
533 {
534  return diveset->maxdiveavgquotnosol;
535 }
536 /** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */
538  SCIP_DIVESET* diveset /**< diving settings */
539  )
540 {
541  return diveset->maxdiveubquot;
542 }
543 
544 /** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */
546  SCIP_DIVESET* diveset /**< diving settings */
547  )
548 {
549  return diveset->maxdiveavgquot;
550 }
551 
552 /** should backtracking be applied? */
554  SCIP_DIVESET* diveset /**< diving settings */
555  )
556 {
557  return diveset->backtrack;
558 }
559 
560 /** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */
562  SCIP_DIVESET* diveset /**< diving settings */
563  )
564 {
565  assert(diveset != NULL);
566 
567  return diveset->lpsolvefreq;
568 }
569 
570 /** returns the random number generator of this \p diveset for tie-breaking */
572  SCIP_DIVESET* diveset /**< diving settings */
573  )
574 {
575  assert(diveset != NULL);
576  assert(diveset->randnumgen != NULL);
577 
578  return diveset->randnumgen;
579 }
580 
581 /** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/
583  SCIP_DIVESET* diveset /**< diving settings */
584  )
585 {
586  assert(diveset != NULL);
587 
588  return diveset->lpresolvedomchgquot;
589 }
590 
591 /** should only LP branching candidates be considered instead of the slower but
592  * more general constraint handler diving variable selection?
593  */
595  SCIP_DIVESET* diveset /**< diving settings */
596  )
597 {
598  assert(diveset != NULL);
599 
600  return diveset->onlylpbranchcands;
601 }
602 
603 /** returns TRUE if dive set supports diving of the specified type */
605  SCIP_DIVESET* diveset, /**< diving settings */
606  SCIP_DIVETYPE divetype /**< bit mask that represents the supported dive types by this dive set */
607  )
608 {
609  assert(diveset != NULL);
610 
611  return (divetype & diveset->divetypemask);
612 }
613 
614 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
616  SCIP_DIVESET* diveset, /**< diving settings */
617  SCIP_STAT* stat, /**< global SCIP statistics */
618  SCIP_Longint niterstoadd /**< additional number of LP iterations to be added */
619  )
620 {
621  diveset->nlpiterations += niterstoadd;
622  stat->ndivesetlpiterations += niterstoadd;
623  diveset->nlps++;
624  stat->ndivesetlps++;
625 }
626 
627 /** frees memory of a diveset */
628 static
630  SCIP_DIVESET** divesetptr, /**< general diving settings */
631  BMS_BLKMEM* blkmem /**< block memory for parameter settings */
632  )
633 {
634  SCIP_DIVESET* diveset = *divesetptr;
635 
636  assert(diveset != NULL);
637  assert(diveset->name != NULL);
638  assert(diveset->randnumgen != NULL);
639 
640  SCIPrandomFree(&diveset->randnumgen, blkmem);
641 
642  BMSfreeMemoryArray(&diveset->name);
643  BMSfreeBlockMemory(blkmem, divesetptr);
644 }
645 
646 /** get the candidate score and preferred rounding direction for a candidate variable */
648  SCIP_DIVESET* diveset, /**< general diving settings */
649  SCIP_SET* set, /**< SCIP settings */
650  SCIP_DIVETYPE divetype, /**< the type of diving that should be applied */
651  SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */
652  SCIP_Real divecandsol, /**< LP solution value of the candidate */
653  SCIP_Real divecandfrac, /**< fractionality of the candidate */
654  SCIP_Real* candscore, /**< pointer to store the candidate score */
655  SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */
656  )
657 {
658  assert(diveset->divesetgetscore != NULL);
659  assert(candscore != NULL);
660  assert(roundup != NULL);
661  assert(divecand != NULL);
662  assert(divetype & diveset->divetypemask);
663 
664  SCIP_CALL( diveset->divesetgetscore(set->scip, diveset, divetype, divecand, divecandsol, divecandfrac,
665  candscore, roundup) );
666 
667  return SCIP_OKAY;
668 }
669 
670 
671 
672 /** copies the given primal heuristic to a new scip */
674  SCIP_HEUR* heur, /**< primal heuristic */
675  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
676  )
677 {
678  assert(heur != NULL);
679  assert(set != NULL);
680  assert(set->scip != NULL);
681 
682  if( heur->heurcopy != NULL )
683  {
684  SCIPsetDebugMsg(set, "including heur %s in subscip %p\n", SCIPheurGetName(heur), (void*)set->scip);
685  SCIP_CALL( heur->heurcopy(set->scip, heur) );
686  }
687 
688  return SCIP_OKAY;
689 }
690 
691 /** creates a primal heuristic */
693  SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
694  SCIP_SET* set, /**< global SCIP settings */
695  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
696  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
697  const char* name, /**< name of primal heuristic */
698  const char* desc, /**< description of primal heuristic */
699  char dispchar, /**< display character of primal heuristic */
700  int priority, /**< priority of the primal heuristic */
701  int freq, /**< frequency for calling primal heuristic */
702  int freqofs, /**< frequency offset for calling primal heuristic */
703  int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
704  SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */
705  SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
706  SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
707  SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */
708  SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */
709  SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */
710  SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */
711  SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */
712  SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
713  SCIP_HEURDATA* heurdata /**< primal heuristic data */
714  )
715 {
716  char paramname[SCIP_MAXSTRLEN];
717  char paramdesc[SCIP_MAXSTRLEN];
718 
719  assert(heur != NULL);
720  assert(name != NULL);
721  assert(desc != NULL);
722  assert(freq >= -1);
723  assert(freqofs >= 0);
724  assert(heurexec != NULL);
725 
726  SCIP_ALLOC( BMSallocMemory(heur) );
727  SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->name, name, strlen(name)+1) );
728  SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->desc, desc, strlen(desc)+1) );
729  (*heur)->dispchar = dispchar;
730  (*heur)->priority = priority;
731  (*heur)->freq = freq;
732  (*heur)->freqofs = freqofs;
733  (*heur)->maxdepth = maxdepth;
734  (*heur)->delaypos = -1;
735  (*heur)->timingmask = timingmask;
736  (*heur)->usessubscip = usessubscip;
737  (*heur)->heurcopy = heurcopy;
738  (*heur)->heurfree = heurfree;
739  (*heur)->heurinit = heurinit;
740  (*heur)->heurexit = heurexit;
741  (*heur)->heurinitsol = heurinitsol;
742  (*heur)->heurexitsol = heurexitsol;
743  (*heur)->heurexec = heurexec;
744  (*heur)->heurdata = heurdata;
745  SCIP_CALL( SCIPclockCreate(&(*heur)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
746  SCIP_CALL( SCIPclockCreate(&(*heur)->heurclock, SCIP_CLOCKTYPE_DEFAULT) );
747  (*heur)->ncalls = 0;
748  (*heur)->nsolsfound = 0;
749  (*heur)->nbestsolsfound = 0;
750  (*heur)->initialized = FALSE;
751  (*heur)->divesets = NULL;
752  (*heur)->ndivesets = 0;
753 
754  /* add parameters */
755  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/priority", name);
756  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of heuristic <%s>", name);
757  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
758  &(*heur)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
759  paramChgdHeurPriority, (SCIP_PARAMDATA*)(*heur)) ); /*lint !e740*/
760  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freq", name);
761  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling primal heuristic <%s> (-1: never, 0: only at depth freqofs)", name);
762  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
763  &(*heur)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
764  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freqofs", name);
765  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency offset for calling primal heuristic <%s>", name);
766  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
767  &(*heur)->freqofs, FALSE, freqofs, 0, SCIP_MAXTREEDEPTH, NULL, NULL) );
768  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdepth", name);
769  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level to call primal heuristic <%s> (-1: no limit)", name);
770  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
771  &(*heur)->maxdepth, TRUE, maxdepth, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
772 
773  return SCIP_OKAY;
774 }
775 
776 /** calls destructor and frees memory of primal heuristic */
778  SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
779  SCIP_SET* set, /**< global SCIP settings */
780  BMS_BLKMEM* blkmem /**< block memory */
781  )
782 {
783  int d;
784  assert(heur != NULL);
785  assert(*heur != NULL);
786  assert(!(*heur)->initialized);
787  assert(set != NULL);
788  assert((*heur)->divesets != NULL || (*heur)->ndivesets == 0);
789 
790  /* call destructor of primal heuristic */
791  if( (*heur)->heurfree != NULL )
792  {
793  SCIP_CALL( (*heur)->heurfree(set->scip, *heur) );
794  }
795 
796  for( d = 0; d < (*heur)->ndivesets; ++d )
797  {
798  assert((*heur)->divesets[d] != NULL);
799  divesetFree(&((*heur)->divesets[d]), blkmem);
800  }
801  BMSfreeMemoryArrayNull(&(*heur)->divesets);
802  SCIPclockFree(&(*heur)->heurclock);
803  SCIPclockFree(&(*heur)->setuptime);
804  BMSfreeMemoryArray(&(*heur)->name);
805  BMSfreeMemoryArray(&(*heur)->desc);
806  BMSfreeMemory(heur);
807 
808  return SCIP_OKAY;
809 }
810 
811 /** initializes primal heuristic */
813  SCIP_HEUR* heur, /**< primal heuristic */
814  SCIP_SET* set /**< global SCIP settings */
815  )
816 {
817  int d;
818  assert(heur != NULL);
819  assert(set != NULL);
820 
821  if( heur->initialized )
822  {
823  SCIPerrorMessage("primal heuristic <%s> already initialized\n", heur->name);
824  return SCIP_INVALIDCALL;
825  }
826 
827  if( set->misc_resetstat )
828  {
829  SCIPclockReset(heur->setuptime);
830  SCIPclockReset(heur->heurclock);
831 
832  heur->delaypos = -1;
833  heur->ncalls = 0;
834  heur->nsolsfound = 0;
835  heur->nbestsolsfound = 0;
836  }
837 
838  if( heur->heurinit != NULL )
839  {
840  /* start timing */
841  SCIPclockStart(heur->setuptime, set);
842 
843  SCIP_CALL( heur->heurinit(set->scip, heur) );
844 
845  /* stop timing */
846  SCIPclockStop(heur->setuptime, set);
847  }
848 
849  /* reset dive sets */
850  for( d = 0; d < heur->ndivesets; ++d )
851  {
852  assert(heur->divesets[d] != NULL);
853  SCIP_CALL( SCIPdivesetReset(heur->divesets[d], set) );
854  }
855 
856  heur->initialized = TRUE;
857 
858  return SCIP_OKAY;
859 }
860 
861 /** calls exit method of primal heuristic */
863  SCIP_HEUR* heur, /**< primal heuristic */
864  SCIP_SET* set /**< global SCIP settings */
865  )
866 {
867  assert(heur != NULL);
868  assert(set != NULL);
869 
870  if( !heur->initialized )
871  {
872  SCIPerrorMessage("primal heuristic <%s> not initialized\n", heur->name);
873  return SCIP_INVALIDCALL;
874  }
875 
876  if( heur->heurexit != NULL )
877  {
878  /* start timing */
879  SCIPclockStart(heur->setuptime, set);
880 
881  SCIP_CALL( heur->heurexit(set->scip, heur) );
882 
883  /* stop timing */
884  SCIPclockStop(heur->setuptime, set);
885  }
886  heur->initialized = FALSE;
887 
888  return SCIP_OKAY;
889 }
890 
891 /** informs primal heuristic that the branch and bound process is being started */
893  SCIP_HEUR* heur, /**< primal heuristic */
894  SCIP_SET* set /**< global SCIP settings */
895  )
896 {
897  assert(heur != NULL);
898  assert(set != NULL);
899 
900  if( heur->delaypos != -1 )
901  {
902  heur->delaypos = -1;
903  set->heurssorted = FALSE;
904  }
905 
906  /* call solving process initialization method of primal heuristic */
907  if( heur->heurinitsol != NULL )
908  {
909  /* start timing */
910  SCIPclockStart(heur->setuptime, set);
911 
912  SCIP_CALL( heur->heurinitsol(set->scip, heur) );
913 
914  /* stop timing */
915  SCIPclockStop(heur->setuptime, set);
916  }
917 
918  return SCIP_OKAY;
919 }
920 
921 /** informs primal heuristic that the branch and bound process data is being freed */
923  SCIP_HEUR* heur, /**< primal heuristic */
924  SCIP_SET* set /**< global SCIP settings */
925  )
926 {
927  assert(heur != NULL);
928  assert(set != NULL);
929 
930  /* call solving process deinitialization method of primal heuristic */
931  if( heur->heurexitsol != NULL )
932  {
933  /* start timing */
934  SCIPclockStart(heur->setuptime, set);
935 
936  SCIP_CALL( heur->heurexitsol(set->scip, heur) );
937 
938  /* stop timing */
939  SCIPclockStop(heur->setuptime, set);
940  }
941 
942  return SCIP_OKAY;
943 }
944 
945 /** should the heuristic be executed at the given depth, frequency, timing, ... */
947  SCIP_HEUR* heur, /**< primal heuristic */
948  int depth, /**< depth of current node */
949  int lpstateforkdepth, /**< depth of the last node with solved LP */
950  SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
951  SCIP_Bool* delayed /**< pointer to store whether the heuristic should be delayed */
952  )
953 {
954  SCIP_Bool execute;
955 
958  {
959  /* heuristic may be executed before/during presolving. Do so, if it was not disabled by setting the frequency to -1 */
960  execute = heur->freq >= 0;
961  }
962  else if( (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0
963  && (heurtiming == SCIP_HEURTIMING_AFTERLPNODE || heurtiming == SCIP_HEURTIMING_AFTERLPPLUNGE) )
964  {
965  /* heuristic was skipped on intermediate pseudo nodes: check, if a node matching the execution frequency lies
966  * between the current node and the last LP node of the path
967  */
968  execute = (heur->freq > 0 && depth >= heur->freqofs
969  && ((depth + heur->freq - heur->freqofs) / heur->freq
970  != (lpstateforkdepth + heur->freq - heur->freqofs) / heur->freq));
971  }
972  else
973  {
974  /* heuristic may be executed on every node: check, if the current depth matches the execution frequency and offset */
975  execute = (heur->freq > 0 && depth >= heur->freqofs && (depth - heur->freqofs) % heur->freq == 0);
976  }
977 
978  /* if frequency is zero, execute heuristic only at the depth level of the frequency offset */
979  execute = execute || (depth == heur->freqofs && heur->freq == 0);
980 
981  /* compare current depth against heuristic's maximal depth level */
982  execute = execute && (heur->maxdepth == -1 || depth <= heur->maxdepth);
983 
984  /* if the heuristic was delayed, execute it anyway */
985  execute = execute || (heur->delaypos >= 0);
986 
987  /* if the heuristic should be called after plunging but not during plunging, delay it if we are in plunging */
988  if( execute
989  && ((heurtiming == SCIP_HEURTIMING_AFTERLPNODE
990  && (heur->timingmask & SCIP_HEURTIMING_AFTERLPNODE) == 0
991  && (heur->timingmask & SCIP_HEURTIMING_AFTERLPPLUNGE) > 0)
992  || (heurtiming == SCIP_HEURTIMING_AFTERPSEUDONODE
994  && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDOPLUNGE) > 0)) )
995  {
996  /* the heuristic should be delayed until plunging is finished */
997  execute = FALSE;
998  *delayed = TRUE;
999  }
1000 
1001  /* execute heuristic only if its timing mask fits the current point in the node solving process */
1002  execute = execute && (heur->timingmask & heurtiming) > 0;
1003 
1004  return execute;
1005 }
1006 
1007 /** calls execution method of primal heuristic */
1009  SCIP_HEUR* heur, /**< primal heuristic */
1010  SCIP_SET* set, /**< global SCIP settings */
1011  SCIP_PRIMAL* primal, /**< primal data */
1012  int depth, /**< depth of current node */
1013  int lpstateforkdepth, /**< depth of the last node with solved LP */
1014  SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
1015  SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
1016  int* ndelayedheurs, /**< pointer to count the number of delayed heuristics */
1017  SCIP_RESULT* result /**< pointer to store the result of the callback method */
1018  )
1019 {
1020  SCIP_Bool execute;
1021  SCIP_Bool delayed;
1022 
1023  assert(heur != NULL);
1024  assert(heur->heurexec != NULL);
1025  assert(heur->freq >= -1);
1026  assert(heur->freqofs >= 0);
1027  assert(heur->maxdepth >= -1);
1028  assert(set != NULL);
1029  assert(set->scip != NULL);
1030  assert(primal != NULL);
1031  assert(depth >= 0 || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP);
1032  assert(ndelayedheurs != NULL);
1033  assert(result != NULL);
1034 
1035  *result = SCIP_DIDNOTRUN;
1036 
1037  delayed = FALSE;
1038  execute = SCIPheurShouldBeExecuted(heur, depth, lpstateforkdepth, heurtiming, &delayed);
1039 
1040  if( delayed )
1041  {
1042  assert(!execute);
1043  *result = SCIP_DELAYED;
1044  }
1045 
1046  if( execute )
1047  {
1048  SCIP_Longint oldnsolsfound;
1049  SCIP_Longint oldnbestsolsfound;
1050 
1051  SCIPsetDebugMsg(set, "executing primal heuristic <%s> in depth %d (delaypos: %d)\n", heur->name, depth, heur->delaypos);
1052 
1053  oldnsolsfound = primal->nsolsfound;
1054  oldnbestsolsfound = primal->nbestsolsfound;
1055 
1056  /* start timing */
1057  SCIPclockStart(heur->heurclock, set);
1058 
1059  /* call external method */
1060  SCIP_CALL( heur->heurexec(set->scip, heur, heurtiming, nodeinfeasible, result) );
1061 
1062  /* stop timing */
1063  SCIPclockStop(heur->heurclock, set);
1064 
1065  /* evaluate result */
1066  if( *result != SCIP_FOUNDSOL
1067  && *result != SCIP_DIDNOTFIND
1068  && *result != SCIP_DIDNOTRUN
1069  && *result != SCIP_DELAYED
1070  && *result != SCIP_UNBOUNDED )
1071  {
1072  SCIPerrorMessage("execution method of primal heuristic <%s> returned invalid result <%d>\n",
1073  heur->name, *result);
1074  return SCIP_INVALIDRESULT;
1075  }
1076  if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
1077  heur->ncalls++;
1078  heur->nsolsfound += primal->nsolsfound - oldnsolsfound;
1079  heur->nbestsolsfound += primal->nbestsolsfound - oldnbestsolsfound;
1080 
1081  /* update delay position of heuristic */
1082  if( *result != SCIP_DELAYED && heur->delaypos != -1 )
1083  {
1084  heur->delaypos = -1;
1085  set->heurssorted = FALSE;
1086  }
1087  }
1088  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DELAYED || *result == SCIP_UNBOUNDED || heur->delaypos == -1);
1089 
1090  /* check if the heuristic was (still) delayed */
1091  if( *result == SCIP_DELAYED || heur->delaypos >= 0 )
1092  {
1093  SCIPsetDebugMsg(set, "delaying execution of primal heuristic <%s> in depth %d (delaypos: %d), heur was%s delayed before, had delaypos %d\n",
1094  heur->name, depth, *ndelayedheurs, heur->delaypos >= 0 ? "" : " not", heur->delaypos);
1095 
1096  /* mark the heuristic delayed */
1097  if( heur->delaypos != *ndelayedheurs )
1098  {
1099  heur->delaypos = *ndelayedheurs;
1100  set->heurssorted = FALSE;
1101  }
1102  (*ndelayedheurs)++;
1103  }
1104 
1105  return SCIP_OKAY;
1106 }
1107 
1108 /** gets user data of primal heuristic */
1110  SCIP_HEUR* heur /**< primal heuristic */
1111  )
1112 {
1113  assert(heur != NULL);
1114 
1115  return heur->heurdata;
1116 }
1117 
1118 /** sets user data of primal heuristic; user has to free old data in advance! */
1120  SCIP_HEUR* heur, /**< primal heuristic */
1121  SCIP_HEURDATA* heurdata /**< new primal heuristic user data */
1122  )
1123 {
1124  assert(heur != NULL);
1125 
1126  heur->heurdata = heurdata;
1127 }
1128 
1129 /* new callback setter methods */
1130 
1131 /** sets copy callback of primal heuristic */
1133  SCIP_HEUR* heur, /**< primal heuristic */
1134  SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
1135  )
1136 {
1137  assert(heur != NULL);
1138 
1139  heur->heurcopy = heurcopy;
1140 }
1141 
1142 /** sets destructor callback of primal heuristic */
1144  SCIP_HEUR* heur, /**< primal heuristic */
1145  SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */
1146  )
1147 {
1148  assert(heur != NULL);
1149 
1150  heur->heurfree = heurfree;
1151 }
1152 
1153 /** sets initialization callback of primal heuristic */
1155  SCIP_HEUR* heur, /**< primal heuristic */
1156  SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */
1157  )
1158 {
1159  assert(heur != NULL);
1160 
1161  heur->heurinit = heurinit;
1162 }
1163 
1164 /** sets deinitialization callback of primal heuristic */
1166  SCIP_HEUR* heur, /**< primal heuristic */
1167  SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */
1168  )
1169 {
1170  assert(heur != NULL);
1171 
1172  heur->heurexit = heurexit;
1173 }
1174 
1175 /** sets solving process initialization callback of primal heuristic */
1177  SCIP_HEUR* heur, /**< primal heuristic */
1178  SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization callback of primal heuristic */
1179  )
1180 {
1181  assert(heur != NULL);
1182 
1183  heur->heurinitsol = heurinitsol;
1184 }
1185 
1186 /** sets solving process deinitialization callback of primal heuristic */
1188  SCIP_HEUR* heur, /**< primal heuristic */
1189  SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization callback of primal heuristic */
1190  )
1191 {
1192  assert(heur != NULL);
1193 
1194  heur->heurexitsol = heurexitsol;
1195 }
1196 
1197 /** gets name of primal heuristic */
1198 const char* SCIPheurGetName(
1199  SCIP_HEUR* heur /**< primal heuristic */
1200  )
1201 {
1202  assert(heur != NULL);
1203 
1204  return heur->name;
1205 }
1206 
1207 /** gets description of primal heuristic */
1208 const char* SCIPheurGetDesc(
1209  SCIP_HEUR* heur /**< primal heuristic */
1210  )
1211 {
1212  assert(heur != NULL);
1213 
1214  return heur->desc;
1215 }
1216 
1217 /** gets display character of primal heuristic */
1219  SCIP_HEUR* heur /**< primal heuristic */
1220  )
1221 {
1222  assert(heur != NULL);
1223 
1224  return heur->dispchar;
1225 }
1226 
1227 /** returns the timing mask of the heuristic */
1229  SCIP_HEUR* heur /**< primal heuristic */
1230  )
1231 {
1232  assert(heur != NULL);
1233 
1234  return heur->timingmask;
1235 }
1236 
1237 /** sets new timing mask for heuristic */
1239  SCIP_HEUR* heur, /**< primal heuristic */
1240  SCIP_HEURTIMING timingmask /**< new timing mask of heuristic */
1241  )
1242 {
1243  assert(heur != NULL);
1244 
1245  heur->timingmask = timingmask;
1246 }
1247 
1248 /** does the heuristic use a secondary SCIP instance? */
1250  SCIP_HEUR* heur /**< primal heuristic */
1251  )
1252 {
1253  assert(heur != NULL);
1254 
1255  return heur->usessubscip;
1256 }
1257 
1258 /** gets priority of primal heuristic */
1260  SCIP_HEUR* heur /**< primal heuristic */
1261  )
1262 {
1263  assert(heur != NULL);
1264 
1265  return heur->priority;
1266 }
1267 
1268 /** sets priority of primal heuristic */
1270  SCIP_HEUR* heur, /**< primal heuristic */
1271  SCIP_SET* set, /**< global SCIP settings */
1272  int priority /**< new priority of the primal heuristic */
1273  )
1274 {
1275  assert(heur != NULL);
1276  assert(set != NULL);
1277 
1278  heur->priority = priority;
1279  set->heurssorted = FALSE;
1280 }
1281 
1282 /** gets frequency of primal heuristic */
1284  SCIP_HEUR* heur /**< primal heuristic */
1285  )
1286 {
1287  assert(heur != NULL);
1288 
1289  return heur->freq;
1290 }
1291 
1292 /** sets frequency of primal heuristic */
1294  SCIP_HEUR* heur, /**< primal heuristic */
1295  int freq /**< new frequency of heuristic */
1296  )
1297 {
1298  assert(heur != NULL);
1299 
1300  heur->freq = freq;
1301 }
1302 
1303 /** gets frequency offset of primal heuristic */
1305  SCIP_HEUR* heur /**< primal heuristic */
1306  )
1307 {
1308  assert(heur != NULL);
1309 
1310  return heur->freqofs;
1311 }
1312 
1313 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */
1315  SCIP_HEUR* heur /**< primal heuristic */
1316  )
1317 {
1318  assert(heur != NULL);
1319 
1320  return heur->maxdepth;
1321 }
1322 
1323 /** gets the number of times, the heuristic was called and tried to find a solution */
1325  SCIP_HEUR* heur /**< primal heuristic */
1326  )
1327 {
1328  assert(heur != NULL);
1329 
1330  return heur->ncalls;
1331 }
1332 
1333 /** gets the number of primal feasible solutions found by this heuristic */
1335  SCIP_HEUR* heur /**< primal heuristic */
1336  )
1337 {
1338  assert(heur != NULL);
1339 
1340  return heur->nsolsfound;
1341 }
1342 
1343 /** gets the number of new best primal feasible solutions found by this heuristic */
1345  SCIP_HEUR* heur /**< primal heuristic */
1346  )
1347 {
1348  assert(heur != NULL);
1349 
1350  return heur->nbestsolsfound;
1351 }
1352 
1353 /** is primal heuristic initialized? */
1355  SCIP_HEUR* heur /**< primal heuristic */
1356  )
1357 {
1358  assert(heur != NULL);
1359 
1360  return heur->initialized;
1361 }
1362 
1363 /** enables or disables all clocks of \p heur, depending on the value of the flag */
1365  SCIP_HEUR* heur, /**< the heuristic for which all clocks should be enabled or disabled */
1366  SCIP_Bool enable /**< should the clocks of the heuristic be enabled? */
1367  )
1368 {
1369  assert(heur != NULL);
1370 
1371  SCIPclockEnableOrDisable(heur->setuptime, enable);
1372  SCIPclockEnableOrDisable(heur->heurclock, enable);
1373 }
1374 
1375 /** gets time in seconds used in this heuristic for setting up for next stages */
1377  SCIP_HEUR* heur /**< primal heuristic */
1378  )
1379 {
1380  assert(heur != NULL);
1381 
1382  return SCIPclockGetTime(heur->setuptime);
1383 }
1384 
1385 /** gets time in seconds used in this heuristic */
1387  SCIP_HEUR* heur /**< primal heuristic */
1388  )
1389 {
1390  assert(heur != NULL);
1391 
1392  return SCIPclockGetTime(heur->heurclock);
1393 }
1394 
1395 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */
1397  SCIP_HEUR* heur /**< primal heuristic */
1398  )
1399 {
1400  assert(heur != NULL);
1401 
1402  return heur->divesets;
1403 }
1404 
1405 /** returns the number of divesets of this primal heuristic */
1407  SCIP_HEUR* heur /**< primal heuristic */
1408  )
1409 {
1410  assert(heur != NULL);
1411 
1412  return heur->ndivesets;
1413 }
1414 
1415 /** Perform breadth-first (BFS) search on the variable constraint graph.
1416  *
1417  * The result of the algorithm is that the \p distances array contains the correct distances for
1418  * every variable from the start variables. The distance of a variable can then be accessed through its
1419  * problem index (calling SCIPvarGetProbindex()).
1420  * Hence, The method assumes that the length of \p distances is at least
1421  * SCIPgetNVars().
1422  * Variables that are not connected through constraints to the start variables have a distance of -1.
1423  *
1424  * Limits can be provided to further restrict the breadth-first search. If a distance limit is given,
1425  * the search will be performed until the first variable at this distance is popped from the queue, i.e.,
1426  * all variables with a distance < maxdistance have been labeled by the search.
1427  * If a variable limit is given, the search stops after it completes the distance level at which
1428  * the limit was reached. Hence, more variables may be actually labeled.
1429  * The start variables are accounted for those variable limits.
1430  *
1431  * If no variable variable constraint graph is provided, the method will create one and free it at the end
1432  * This is useful for a single use of the variable constraint graph. For several consecutive uses,
1433  * it is advised to create a variable constraint graph via SCIPvariableGraphCreate().
1434  */
1436  SCIP* scip, /**< SCIP data structure */
1437  SCIP_VGRAPH* vargraph, /**< pointer to the variable graph, or NULL to let the function create a local graph */
1438  SCIP_VAR** startvars, /**< array of start variables to calculate distance from */
1439  int nstartvars, /**< number of starting variables, at least 1 */
1440  int* distances, /**< array to keep distance in vargraph from start variables for every variable */
1441  int maxdistance, /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */
1442  int maxvars, /**< maximum number of variables to compute distance for */
1443  int maxbinintvars /**< maximum number of binary or integer variables to compute distance for */
1444  )
1445 {
1446  SCIP_VAR** vars;
1447 
1448  int* queue;
1449  int nvars;
1450  int i;
1451  int currlvlidx;
1452  int nextlvlidx;
1453  int increment = 1;
1454  int currentdistance;
1455  int nbinintvarshit;
1456  int nvarshit;
1457  int nbinvars;
1458  int nintvars;
1459  int nbinintvars;
1460  SCIP_VAR** varbuffer;
1461  SCIP_Bool localvargraph;
1462 
1463  assert(scip != NULL);
1464  assert(startvars != NULL);
1465  assert(nstartvars >= 1);
1466  assert(distances != NULL);
1467  assert(maxdistance >= 0);
1468 
1469 
1470  /* get variable data */
1471  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1472  nbinintvars = nbinvars + nintvars;
1473 
1474  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nvars) );
1475  SCIP_CALL( SCIPallocClearBufferArray(scip, &varbuffer, nvars) );
1476 
1477  /* create a variable graph locally for this method, if none is provided */
1478  if( vargraph == NULL )
1479  {
1480  SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, FALSE, 1.0, NULL) );
1481  localvargraph = TRUE;
1482  }
1483  else
1484  localvargraph = FALSE;
1485 
1487 
1488  /* initialize distances to -1 */
1489  for( i = 0; i < nvars; ++i )
1490  {
1491  queue[i] = -1;
1492  distances[i] = -1;
1493  }
1494 
1495  nvarshit = 0;
1496  nbinintvarshit = 0;
1497  /* initialize distances for starting variables and add them to the queue */
1498  for( i = 0; i < nstartvars; ++i )
1499  {
1500  int probindex = SCIPvarGetProbindex(startvars[i]);
1501  assert(probindex >= 0);
1502  /* start variables have a distance of 0 */
1503  distances[probindex] = 0;
1504  queue[i] = probindex;
1505  nvarshit++;
1506 
1507  if( probindex < nbinintvars )
1508  nbinintvarshit++;
1509  }
1510  currlvlidx = 0;
1511  nextlvlidx = nvars - 1;
1512 
1513  /* loop over the queue and pop the next variable, starting with start variables */
1514  do
1515  {
1516  SCIP_VAR* currvar;
1517  int c;
1518  int varpos;
1519 
1520  currvar = vars[queue[currlvlidx]];
1521  varpos = SCIPvarGetProbindex(currvar);
1522  currentdistance = distances[varpos];
1523  assert(currentdistance >= 0);
1524 
1525  /* distances must only be computed up to maxdistance */
1526  assert(currentdistance <= maxdistance);
1527 
1528  /* check for termination because maximum distance has been reached */
1529  if( currentdistance == maxdistance )
1530  break;
1531 
1532  assert(varpos >= 0);
1533 
1534  /* loop over variable constraints and enqueue variables that were not visited yet */
1535  for( c = 0; c < vargraph->nvarconss[varpos]; ++c )
1536  {
1537  int nconsvars;
1538  int v;
1539  SCIP_Bool success;
1540  SCIP_CONS* cons = vargraph->varconss[varpos][c];
1541 
1542  /* check first if this constraint has already been visited */
1543  if( SCIPhashtableExists(vargraph->visitedconss, (void *)cons) )
1544  continue;
1545 
1546  /* request number of constraint variables */
1547  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1548 
1549  if( !success )
1550  continue;
1551 
1552  /* collect constraint variables in buffer */
1553  SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1554 
1555  if( !success )
1556  continue;
1557 
1558  /* collect previously unvisited variables of the constraint and enqueue them for breadth-first search */
1559  for( v = 0; v < nconsvars; ++v )
1560  {
1561  SCIP_VAR* nextvar = varbuffer[v];
1562  int nextvarpos;
1563  assert(nextvar != NULL);
1564  if( !SCIPvarIsActive(nextvar) )
1565  continue;
1566 
1567  nextvarpos = SCIPvarGetProbindex(nextvar);
1568  assert(nextvarpos >= 0);
1569 
1570  /* insert variables that were not considered yet into the next level queue */
1571  if( distances[nextvarpos] == -1 )
1572  {
1573  distances[nextvarpos] = currentdistance + 1;
1574  queue[nextlvlidx] = nextvarpos;
1575  nextlvlidx -= increment;
1576 
1577  nvarshit++;
1578  if( nextvarpos < nbinintvars )
1579  ++nbinintvarshit;
1580  }
1581  } /* end constraint variables loop */
1582 
1583  /* mark the constraint as visited */
1584  SCIP_CALL( SCIPhashtableInsert(vargraph->visitedconss, (void *)cons) );
1585 
1586  } /* end constraint loop */
1587 
1588  queue[currlvlidx] = -1;
1589  currlvlidx += increment;
1590 
1591  /* check if we need to swap current and next level index and reverse the increment */
1592  if( currlvlidx == nvars || currlvlidx == 0 || queue[currlvlidx] == -1 || currlvlidx == nextlvlidx )
1593  {
1594  /* break early if the distance has been determined for enough variables */
1595  if( nvarshit >= maxvars || nbinintvarshit >= maxbinintvars )
1596  break;
1597 
1598  /* increment knows whether we are currently looping upwards (all variables with odd distance) or downwards the
1599  * queue
1600  */
1601  if( increment == +1 )
1602  {
1603  currlvlidx = nvars - 1;
1604  nextlvlidx = 0;
1605  increment = -1;
1606  }
1607  else
1608  {
1609  currlvlidx = 0;
1610  nextlvlidx = nvars - 1;
1611  increment = +1;
1612  }
1613  }
1614  }
1615  while( queue[currlvlidx] != -1 && distances[queue[currlvlidx]] >= currentdistance );
1616 
1617  SCIPfreeBufferArray(scip, &varbuffer);
1618  SCIPfreeBufferArray(scip, &queue);
1619 
1620  /* free also the variable graph, if it wasn't provided by the caller */
1621  if( localvargraph )
1622  {
1623  SCIPvariableGraphFree(scip, &vargraph);
1624  }
1625 
1626  return SCIP_OKAY;
1627 }
1628 
1629 /* fills variable graph data structure
1630  *
1631  * loops over global problem constraints and creates a mapping from the variables to their respective constraints
1632  */
1633 static
1635  SCIP* scip, /**< SCIP data structure */
1636  SCIP_VGRAPH* vargraph, /**< variable graph data structure for breadth-first-search neighborhoods */
1637  SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be
1638  * ignored by connectivity graph? */
1639  SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */
1640  int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
1641  )
1642 {
1643  SCIP_CONS** conss;
1644  int nconss;
1645  int nvars;
1646  int c;
1647  int relaxlimit;
1648  SCIP_VAR** varbuffer;
1649 
1650  assert(scip != NULL);
1651  assert(vargraph != NULL);
1652 
1653  conss = SCIPgetConss(scip);
1654  nconss = SCIPgetNConss(scip);
1655 
1656  nvars = SCIPgetNVars(scip);
1657  SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, nvars) );
1658 
1659  if( nrelaxedconstraints != NULL )
1660  *nrelaxedconstraints = 0;
1661 
1662  relaxlimit = (int)(relaxdensity * nvars);
1663 
1664  for( c = 0; c < nconss; ++c )
1665  {
1666  int nconsvars;
1667  int v;
1668  SCIP_Bool success;
1669  SCIP_CONS* cons = conss[c];
1670 
1671  /* we only consider constraints that are checkable */
1672  if( !SCIPconsIsChecked(cons) )
1673  continue;
1674 
1675  /* request number of variables */
1676  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1677 
1678  if( !success )
1679  continue;
1680 
1681  /* relax constraints with density above the allowed number of free variables */
1682  if( relaxdenseconss && nconsvars >= relaxlimit )
1683  {
1684  if( nrelaxedconstraints != NULL )
1685  ++(*nrelaxedconstraints);
1686 
1687  continue;
1688  }
1689 
1690  /* collect constraint variables in buffer */
1691  SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1692 
1693  if( !success )
1694  continue;
1695 
1696  /* loop over constraint variables and add this constraint to them if they are active */
1697  for( v = 0; v < nconsvars; ++v )
1698  {
1699  int varpos = SCIPvarGetProbindex(varbuffer[v]);
1700 
1701  /* skip inactive variables */
1702  if( varpos == -1 )
1703  continue;
1704 
1705  /* ensure array size */
1706  if( vargraph->varconssize[varpos] == vargraph->nvarconss[varpos] )
1707  {
1708  int newmem = SCIPcalcMemGrowSize(scip, vargraph->nvarconss[varpos] + 1);
1709 
1710  assert(newmem > vargraph->varconssize[varpos]);
1711 
1712  if( vargraph->varconss[varpos] == NULL )
1713  {
1714  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vargraph->varconss[varpos], newmem) );
1715  }
1716  else
1717  {
1718  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &vargraph->varconss[varpos], vargraph->varconssize[varpos], newmem) ); /*lint !e866*/
1719  }
1720  vargraph->varconssize[varpos] = newmem;
1721  }
1722 
1723  assert(vargraph->nvarconss[varpos] < vargraph->varconssize[varpos]);
1724 
1725  /* add constraint to constraint array for this variable */
1726  vargraph->varconss[varpos][vargraph->nvarconss[varpos]] = cons;
1727  vargraph->nvarconss[varpos] += 1;
1728  }
1729  }
1730 
1731  /* free the buffer */
1732  SCIPfreeBufferArray(scip, &varbuffer);
1733 
1734  return SCIP_OKAY;
1735 }
1736 
1737 /** initialization method of variable graph data structure */
1739  SCIP* scip, /**< SCIP data structure */
1740  SCIP_VGRAPH** vargraph, /**< pointer to the variable graph */
1741  SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be
1742  * ignored by connectivity graph? */
1743  SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */
1744  int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
1745  )
1746 {
1747  int nvars;
1748  int nconss;
1749 
1750  assert(scip != NULL);
1751  assert(vargraph != NULL);
1752 
1753  nvars = SCIPgetNVars(scip);
1754  nconss = SCIPgetNConss(scip);
1755 
1756  if( nvars == 0 )
1757  return SCIP_OKAY;
1758 
1759  SCIP_CALL( SCIPallocBlockMemory(scip, vargraph) );
1760 
1761  SCIP_CALL( SCIPhashtableCreate(&(*vargraph)->visitedconss, SCIPblkmem(scip), 2 * nconss, SCIPhashGetKeyStandard,
1762  SCIPhashKeyEqPtr, SCIPhashKeyValPtr, NULL) );
1763 
1764  /* allocate and clear memory */
1765  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconss, nvars) );
1766  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars) );
1767  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars) );
1768 
1769  /* fill the variable graph with variable-constraint mapping for breadth-first search*/
1770  SCIP_CALL( fillVariableGraph(scip, *vargraph, relaxdenseconss, relaxdensity, nrelaxedconstraints) );
1771 
1772  return SCIP_OKAY;
1773 }
1774 
1775 /** deinitialization method of variable graph data structure */
1777  SCIP* scip, /**< SCIP data structure */
1778  SCIP_VGRAPH** vargraph /**< pointer to the variable graph */
1779  )
1780 {
1781  int nvars;
1782  int v;
1783  assert(scip != NULL);
1784  assert(vargraph != NULL);
1785 
1786  nvars = SCIPgetNVars(scip);
1787 
1788  for( v = nvars - 1; v >= 0; --v )
1789  {
1790  SCIPfreeBlockMemoryArrayNull(scip, &(*vargraph)->varconss[v], (*vargraph)->varconssize[v]); /*lint !e866*/
1791  }
1792 
1793  /* allocate and clear memory */
1794  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars);
1795  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars);
1796  SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconss, nvars);
1797 
1798  SCIPhashtableFree(&(*vargraph)->visitedconss);
1799 
1800  SCIPfreeBlockMemory(scip, vargraph);
1801 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool onlylpbranchcands
Definition: struct_heur.h:71
int * nvarconss
Definition: struct_heur.h:118
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_HEURTIMING SCIPheurGetTimingmask(SCIP_HEUR *heur)
Definition: heur.c:1228
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
void SCIPheurSetInitsol(SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: heur.c:1176
static SCIP_DECL_PARAMCHGD(paramChgdHeurPriority)
Definition: heur.c:72
SCIP_Longint totalnnodes
Definition: struct_heur.h:57
#define SCIP_DECL_HEURINITSOL(x)
Definition: type_heur.h:97
int SCIPdivesetGetMinSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:435
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition: heur.c:1259
SCIP_Real SCIPheurGetSetupTime(SCIP_HEUR *heur)
Definition: heur.c:1376
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:130
SCIP_RETCODE SCIPdivesetGetScore(SCIP_DIVESET *diveset, SCIP_SET *set, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
Definition: heur.c:647
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset)
Definition: heur.c:485
SCIP_HEUR * heur
Definition: struct_heur.h:39
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
SCIP_Longint totalnbacktracks
Definition: struct_heur.h:58
SCIP_DIVESET ** divesets
Definition: struct_heur.h:93
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:22622
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:661
#define SCIP_MAXSTRLEN
Definition: def.h:259
int ndivesets
Definition: struct_heur.h:101
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:553
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1344
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:1776
internal methods for clocks and timing issues
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22591
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:97
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:46807
void SCIPheurSetExitsol(SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: heur.c:1187
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:76
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:537
int delaypos
Definition: struct_heur.h:100
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:514
SCIP_Real maxreldepth
Definition: struct_heur.h:44
SCIP_Bool backtrack
Definition: struct_heur.h:70
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1396
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:530
static SCIP_RETCODE heurAddDiveset(SCIP_HEUR *heur, SCIP_DIVESET *diveset)
Definition: heur.c:154
SCIP_RETCODE SCIPheurFree(SCIP_HEUR **heur, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: heur.c:777
SCIP_Real maxlpiterquot
Definition: struct_heur.h:45
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:350
#define FALSE
Definition: def.h:64
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:280
SCIP_Longint nsolsfound
Definition: struct_heur.h:81
SCIP_CLOCK * heurclock
Definition: struct_heur.h:95
int * varconssize
Definition: struct_heur.h:119
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
SCIP_RETCODE SCIPheurExec(SCIP_HEUR *heur, SCIP_SET *set, SCIP_PRIMAL *primal, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, int *ndelayedheurs, SCIP_RESULT *result)
Definition: heur.c:1008
SCIP_Longint totaldepth
Definition: struct_heur.h:55
#define TRUE
Definition: def.h:63
char * name
Definition: struct_heur.h:40
#define SCIP_DECL_HEURCOPY(x)
Definition: type_heur.h:62
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_DECL_HEUREXEC(x)
Definition: type_heur.h:128
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:369
SCIP_RETCODE SCIPheurInitsol(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:892
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1304
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset)
Definition: heur.c:495
void SCIPheurSetPriority(SCIP_HEUR *heur, SCIP_SET *set, int priority)
Definition: heur.c:1269
SCIP_CLOCK * setuptime
Definition: struct_heur.h:94
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset)
Definition: heur.c:465
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:105
char dispchar
Definition: struct_heur.h:105
SCIP_Longint nsolsfound
Definition: struct_primal.h:39
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_Bool SCIPheurUsesSubscip(SCIP_HEUR *heur)
Definition: heur.c:1249
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:48
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:361
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip.c:12902
internal methods for handling parameter settings
SCIP_RETCODE SCIPheurCopyInclude(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:673
static SCIP_RETCODE fillVariableGraph(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1634
int SCIPdivesetGetNSolutionCalls(SCIP_DIVESET *diveset)
Definition: heur.c:395
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:250
SCIP_Real SCIPdivesetGetAvgSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:455
SCIP_RETCODE SCIPheurCreate(SCIP_HEUR **heur, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: heur.c:692
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define BMSfreeMemory(ptr)
Definition: memory.h:127
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_Bool usessubscip
Definition: struct_heur.h:103
#define SCIP_DECL_DIVESETGETSCORE(x)
Definition: type_heur.h:149
void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition: heur.c:1293
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:594
SCIP_RETCODE SCIPdivesetReset(SCIP_DIVESET *diveset, SCIP_SET *set)
Definition: heur.c:86
internal methods for collecting primal CIP solutions and primal informations
#define SCIP_HEURTIMING_AFTERPSEUDOPLUNGE
Definition: type_timing.h:82
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:506
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
SCIP_Real maxdiveavgquotnosol
Definition: struct_heur.h:51
void SCIPdivesetUpdateLPStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd)
Definition: heur.c:615
SCIP_RETCODE SCIPsetHeurPriority(SCIP *scip, SCIP_HEUR *heur, int priority)
Definition: scip.c:8262
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:322
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1738
int SCIPdivesetGetMaxSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:445
SCIP_HEURTIMING timingmask
Definition: struct_heur.h:102
char * name
Definition: struct_heur.h:83
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:129
int SCIPheurGetMaxdepth(SCIP_HEUR *heur)
Definition: heur.c:1314
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip.c:29170
SCIP_Longint nbestsolsfound
Definition: struct_primal.h:42
int ndivesetcalls
Definition: struct_stat.h:198
#define SCIP_HEURTIMING_AFTERLPNODE
Definition: type_timing.h:73
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:199
int SCIPdivesetGetMaxDepth(SCIP_DIVESET *diveset)
Definition: heur.c:415
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:545
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset)
Definition: heur.c:425
SCIP_SOL * sol
Definition: struct_heur.h:41
const char * SCIPheurGetDesc(SCIP_HEUR *heur)
Definition: heur.c:1208
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:428
void SCIPheurSetCopy(SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: heur.c:1132
internal miscellaneous methods
SCIP_Real lpresolvedomchgquot
Definition: struct_heur.h:52
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9350
SCIP_RANDNUMGEN * randnumgen
Definition: struct_heur.h:42
SCIP_Real maxdiveubquot
Definition: struct_heur.h:46
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1283
void SCIPrandomSetSeed(SCIP_RANDNUMGEN *randnumgen, unsigned int initseed)
Definition: misc.c:9280
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:350
#define SCIP_HEURTIMING_DURINGPRESOLLOOP
Definition: type_timing.h:87
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2473
SCIP_Bool initialized
Definition: struct_heur.h:104
#define SCIP_HEURTIMING_BEFOREPRESOL
Definition: type_timing.h:86
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, 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: set.c:2813
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:582
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1406
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
static void divesetFree(SCIP_DIVESET **divesetptr, BMS_BLKMEM *blkmem)
Definition: heur.c:629
SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype)
Definition: heur.c:604
SCIP_Longint nlpiterations
Definition: struct_heur.h:53
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip.c:29126
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:125
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:160
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:446
SCIP_Longint totalsoldepth
Definition: struct_heur.h:56
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
datastructures for primal heuristics
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_Longint ndivesetlpiterations
Definition: struct_stat.h:66
SCIP_Longint ndivesetlps
Definition: struct_stat.h:188
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition: heur.c:1435
void SCIPdivesetUpdateStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, int depth, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Bool leavesol)
Definition: heur.c:116
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:522
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:571
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:175
SCIP_Bool SCIPheurShouldBeExecuted(SCIP_HEUR *heur, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool *delayed)
Definition: heur.c:946
SCIP_RETCODE SCIPheurInit(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:812
#define MAX(x, y)
Definition: tclique_def.h:75
char * desc
Definition: struct_heur.h:84
void SCIPheurSetFree(SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: heur.c:1143
#define SCIPsetDebugMsg
Definition: set.h:1913
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8185
int priority
Definition: struct_heur.h:96
void SCIPheurEnableOrDisableClocks(SCIP_HEUR *heur, SCIP_Bool enable)
Definition: heur.c:1364
SCIP_DIVETYPE divetypemask
Definition: struct_heur.h:73
SCIP_HEURDATA * heurdata
Definition: struct_heur.h:92
unsigned int initialseed
Definition: struct_heur.h:69
#define SCIP_MAXTREEDEPTH
Definition: def.h:286
SCIP_CONS *** varconss
Definition: struct_heur.h:116
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2064
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define SCIP_REAL_MAX
Definition: def.h:150
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:716
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:340
SCIP_Real maxdiveavgquot
Definition: struct_heur.h:48
SCIP_HASHTABLE * visitedconss
Definition: struct_heur.h:117
SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
Definition: heur.c:41
SCIP_Longint ncalls
Definition: struct_heur.h:80
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12856
void SCIPheurSetExit(SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: heur.c:1165
#define SCIP_DECL_HEUREXIT(x)
Definition: type_heur.h:86
SCIP_RETCODE SCIPheurExit(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:862
public methods for message output
SCIP_Longint nsolsfound
Definition: struct_heur.h:59
#define SCIP_DECL_HEURINIT(x)
Definition: type_heur.h:78
#define SCIP_HEURTIMING_AFTERPSEUDONODE
Definition: type_timing.h:76
SCIP_Longint nbestsolsfound
Definition: struct_heur.h:82
#define SCIP_Real
Definition: def.h:149
void SCIPheurSetInit(SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: heur.c:1154
char SCIPheurGetDispchar(SCIP_HEUR *heur)
Definition: heur.c:1218
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9334
SCIP_Longint nbestsolsfound
Definition: struct_heur.h:60
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1238
#define SCIP_DECL_HEURFREE(x)
Definition: type_heur.h:70
#define BMSallocMemory(ptr)
Definition: memory.h:101
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:109
#define SCIP_Longint
Definition: def.h:134
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1334
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset)
Definition: heur.c:377
SCIP_Real minreldepth
Definition: struct_heur.h:43
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2377
SCIP_RETCODE SCIPdivesetCreate(SCIP_DIVESET **divesetptr, SCIP_HEUR *heur, const char *name, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_DIVETYPE divetypemask, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)))
Definition: heur.c:184
int SCIPsetInitializeRandomSeed(SCIP_SET *set, int initialseedvalue)
Definition: set.c:6956
#define SCIP_HEURTIMING_AFTERLPPLUNGE
Definition: type_timing.h:79
int maxlpiterofs
Definition: struct_heur.h:61
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:433
SCIP_Longint nlps
Definition: struct_heur.h:54
SCIP_Bool SCIPheurIsInitialized(SCIP_HEUR *heur)
Definition: heur.c:1354
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
SCIP_RETCODE SCIPsetAddRealParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, 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: set.c:2861
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
internal methods for primal heuristics
SCIP_RETCODE SCIPheurExitsol(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:922
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1386
#define SCIP_ALLOC(x)
Definition: def.h:361
SCIP_RETCODE SCIPsetAddBoolParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2791
#define SCIP_DECL_HEUREXITSOL(x)
Definition: type_heur.h:108
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset)
Definition: heur.c:385
SCIP_SOL * SCIPdivesetGetWorkSolution(SCIP_DIVESET *diveset)
Definition: heur.c:330
SCIP_Real maxdiveubquotnosol
Definition: struct_heur.h:50
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset)
Definition: heur.c:475
SCIP callable library.
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:561
int maxdepth
Definition: struct_heur.h:99
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_Longint totaldivesetdepth
Definition: struct_stat.h:196
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:351
int SCIPdivesetGetMinDepth(SCIP_DIVESET *diveset)
Definition: heur.c:405
int freqofs
Definition: struct_heur.h:98