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