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