SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_intdiving.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_intdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that fixes variables with integral LP value
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/heur_intdiving.h"
35#include "scip/pub_heur.h"
36#include "scip/pub_lp.h"
37#include "scip/pub_message.h"
38#include "scip/pub_var.h"
39#include "scip/scip_branch.h"
40#include "scip/scip_general.h"
41#include "scip/scip_heur.h"
42#include "scip/scip_lp.h"
43#include "scip/scip_mem.h"
44#include "scip/scip_message.h"
45#include "scip/scip_numerics.h"
46#include "scip/scip_param.h"
47#include "scip/scip_prob.h"
48#include "scip/scip_probing.h"
49#include "scip/scip_sol.h"
51#include "scip/scip_tree.h"
52#include "scip/scip_var.h"
53#include <string.h>
54
55#define HEUR_NAME "intdiving"
56#define HEUR_DESC "LP diving heuristic that fixes binary variables with large LP value to one"
57#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
58#define HEUR_PRIORITY -1003500
59#define HEUR_FREQ -1
60#define HEUR_FREQOFS 9
61#define HEUR_MAXDEPTH -1
62#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
63#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
64
65
66/*
67 * Default parameter settings
68 */
69
70#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
71#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
72#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
73#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
74#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
75 * where diving is performed (0.0: no limit) */
76#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
77 * where diving is performed (0.0: no limit) */
78#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
79#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
80#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
81
82#define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
83
84
85/* locally defined heuristic data */
86struct SCIP_HeurData
87{
88 SCIP_SOL* sol; /**< working solution */
89 SCIP_Real minreldepth; /**< minimal relative depth to start diving */
90 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
91 SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
92 int maxlpiterofs; /**< additional number of allowed LP iterations */
93 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
94 * where diving is performed (0.0: no limit) */
95 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
96 * where diving is performed (0.0: no limit) */
97 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
98 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
99 SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
100 SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
101 int nsuccess; /**< number of runs that produced at least one feasible solution */
102};
103
104
105/*
106 * local methods
107 */
108
109
110/*
111 * Callback methods
112 */
113
114/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
115static
117{ /*lint --e{715}*/
118 assert(scip != NULL);
119 assert(heur != NULL);
121
122 /* call inclusion method of primal heuristic */
124
125 return SCIP_OKAY;
126}
127
128/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
129static
130SCIP_DECL_HEURFREE(heurFreeIntdiving) /*lint --e{715}*/
131{ /*lint --e{715}*/
133
134 assert(heur != NULL);
137
138 /* free heuristic data */
143
144 return SCIP_OKAY;
145}
146
147
148/** initialization method of primal heuristic (called after problem was transformed) */
149static
150SCIP_DECL_HEURINIT(heurInitIntdiving) /*lint --e{715}*/
151{ /*lint --e{715}*/
153
154 assert(heur != NULL);
156
157 /* get heuristic data */
159 assert(heurdata != NULL);
160
161 /* create working solution */
163
164 /* initialize data */
165 heurdata->nlpiterations = 0;
166 heurdata->nsuccess = 0;
167
168 return SCIP_OKAY;
169}
170
171
172/** deinitialization method of primal heuristic (called before transformed problem is freed) */
173static
174SCIP_DECL_HEUREXIT(heurExitIntdiving) /*lint --e{715}*/
175{ /*lint --e{715}*/
177
178 assert(heur != NULL);
180
181 /* get heuristic data */
183 assert(heurdata != NULL);
184
185 /* free working solution */
187
188 return SCIP_OKAY;
189}
190
191
192/** execution method of primal heuristic */
193static
194SCIP_DECL_HEUREXEC(heurExecIntdiving) /*lint --e{715}*/
195{ /*lint --e{715}*/
200 SCIP_Real* fixcandscores;
201 SCIP_Real searchubbound;
202 SCIP_Real searchavgbound;
203 SCIP_Real searchbound;
204 SCIP_Real objval;
205 SCIP_Bool lperror;
206 SCIP_Bool cutoff;
207 SCIP_Bool backtracked;
208 SCIP_Longint ncalls;
209 SCIP_Longint nsolsfound;
210 SCIP_Longint nlpiterations;
211 SCIP_Longint maxnlpiterations;
214 int depth;
219 int c;
220
221 assert(heur != NULL);
223 assert(scip != NULL);
226
228
229 /* do not call heuristic of node was already detected to be infeasible */
231 return SCIP_OKAY;
232
233 /* only call heuristic, if an optimal LP solution is at hand */
235 return SCIP_OKAY;
236
237 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
239 return SCIP_OKAY;
240
241 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
242 if( !SCIPisLPSolBasic(scip) )
243 return SCIP_OKAY;
244
245 /* don't dive two times at the same node */
247 return SCIP_OKAY;
248
250
251 /* get heuristic's data */
253 assert(heurdata != NULL);
254
255 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
258 maxdepth = MAX(maxdepth, 100);
259 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
260 return SCIP_OKAY;
261
262 /* calculate the maximal number of LP iterations until heuristic is aborted */
265 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
266 maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
267 maxnlpiterations += heurdata->maxlpiterofs;
268
269 /* don't try to dive, if we took too many LP iterations during diving */
270 if( heurdata->nlpiterations >= maxnlpiterations )
271 return SCIP_OKAY;
272
273 /* allow at least a certain number of LP iterations in this dive */
275
276 /* get unfixed integer variables */
278
279 /* don't try to dive, if there are no fractional variables */
280 if( nfixcands == 0 )
281 return SCIP_OKAY;
282
283 /* calculate the objective search bound */
284 if( SCIPgetNSolsFound(scip) == 0 )
285 {
286 if( heurdata->maxdiveubquotnosol > 0.0 )
288 + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
289 else
291 if( heurdata->maxdiveavgquotnosol > 0.0 )
293 + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
294 else
296 }
297 else
298 {
299 if( heurdata->maxdiveubquot > 0.0 )
301 + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
302 else
304 if( heurdata->maxdiveavgquot > 0.0 )
306 + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
307 else
309 }
313
314 /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
317 maxdivedepth *= 10;
318
320
321 /* start diving */
323
324 /* enables collection of variable statistics during probing */
326
327 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
329
330 /* copy the pseudo candidates into own array, because we want to reorder them */
332
333 /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */
335 nbinfixcands = 0;
336 for( c = 0; c < nfixcands; ++c )
337 {
338 SCIP_VAR* var;
339 SCIP_Real score;
340 int colveclen;
341 int left;
342 int right;
343 int i;
344
346 var = fixcands[c];
349 if( SCIPvarIsBinary(var) )
350 {
351 score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE)
353
354 /* shift the non-binary variables one slot to the right */
355 for( i = c; i > nbinfixcands; --i )
356 {
357 fixcands[i] = fixcands[i-1];
359 }
360 /* put the new candidate into the first nbinfixcands slot */
361 left = 0;
362 right = nbinfixcands;
363 nbinfixcands++;
364 }
365 else
366 {
369 + (SCIP_Real)colveclen/10000.0;
370
371 /* put the new candidate in the slots after the binary candidates */
372 left = nbinfixcands;
373 right = c;
374 }
375 for( i = right; i > left && score > fixcandscores[i-1]; --i )
376 {
377 fixcands[i] = fixcands[i-1];
379 }
380 fixcands[i] = var;
381 fixcandscores[i] = score;
382 SCIPdebugMsg(scip, " <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d -> score=%g\n",
385 colveclen, score);
386 }
388
389 /* get LP objective value */
392
393 /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with
394 * the depth 10
395 */
396 lperror = FALSE;
397 cutoff = FALSE;
398 divedepth = 0;
399 nextcand = 0;
401 && (divedepth < 10
403 && !SCIPisStopped(scip) )
404 {
405 SCIP_VAR* var;
406 SCIP_Real bestsolval;
407 SCIP_Real bestfixval;
408 int bestcand;
409 SCIP_Longint nnewlpiterations;
410 SCIP_Longint nnewdomreds;
411
412 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
414 {
416 divedepth++;
417 }
418 else
419 break;
420
422 nnewdomreds = 0;
423
424 /* fix binary variable that is closest to 1 in the LP solution to 1;
425 * if all binary variables are fixed, fix integer variable with least fractionality in LP solution
426 */
427 bestcand = -1;
428 bestsolval = -1.0;
429 bestfixval = 1.0;
430
431 /* look in the binary variables for fixing candidates */
432 for( c = nextcand; c < nbinfixcands; ++c )
433 {
434 SCIP_Real solval;
435
436 var = fixcands[c];
437
438 /* ignore already fixed variables */
439 if( var == NULL )
440 continue;
441 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
442 {
443 fixcands[c] = NULL;
444 continue;
445 }
446
447 /* get the LP solution value */
448 solval = SCIPvarGetLPSol(var);
449
450 if( solval > bestsolval )
451 {
452 bestcand = c;
453 bestfixval = 1.0;
454 bestsolval = solval;
455 if( SCIPisGE(scip, bestsolval, 1.0) )
456 {
457 /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */
458 break;
459 }
460 else if( SCIPisLE(scip, bestsolval, 0.0) )
461 {
462 /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */
463 bestfixval = 0.0;
464 }
465 }
466 }
467
468 /* if all binary variables are fixed, look in the integer variables for a fixing candidate */
469 if( bestcand == -1 )
470 {
471 SCIP_Real bestfrac;
472
474 for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
475 {
476 SCIP_Real solval;
477 SCIP_Real frac;
478
479 var = fixcands[c];
480
481 /* ignore already fixed variables */
482 if( var == NULL )
483 continue;
485 {
486 fixcands[c] = NULL;
487 continue;
488 }
489
490 /* get the LP solution value */
491 solval = SCIPvarGetLPSol(var);
492 frac = SCIPfrac(scip, solval);
493
494 /* ignore integer variables that are currently integral */
496 continue;
497
498 if( frac < bestfrac )
499 {
500 bestcand = c;
501 bestsolval = solval;
502 bestfrac = frac;
504 if( SCIPisZero(scip, bestfrac) )
505 {
506 /* we found an unfixed integer variable with integral LP solution value */
507 break;
508 }
509 }
510 }
511 }
512 assert(-1 <= bestcand && bestcand < nfixcands);
513
514 /* if there is no unfixed candidate left, we are done */
515 if( bestcand == -1 )
516 break;
517
519 assert(var != NULL);
524
526 do
527 {
528 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
529 * occured or variable was fixed by propagation while backtracking => Abort diving!
530 */
532 {
533 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
535 cutoff = TRUE;
536 break;
537 }
539 {
540 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
543 break;
544 }
545
546 /* apply fixing of best candidate */
547 SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n",
551
552 /* apply domain propagation */
554 if( !cutoff )
555 {
556 /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution
557 * stays valid, and the LP does not need to be resolved
558 */
560 {
561 /* resolve the diving LP */
562 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
563 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
564 */
565#ifdef NDEBUG
569 if( retstat != SCIP_OKAY )
570 {
571 SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
572 }
573#else
576#endif
577
578 if( lperror )
579 break;
580
581 /* update iteration count */
583 heurdata->nlpiterations += nnewlpiterations;
584
585 /* get LP solution status */
589 }
590 }
591
592 /* perform backtracking if a cutoff was detected */
593 if( cutoff && !backtracked && heurdata->backtrack )
594 {
595 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
597
598 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
600
602
604 ? 1.0 - bestfixval
606
608 }
609 else
611 }
612 while( backtracked );
613
615 {
616 SCIP_Bool success;
617
618 /* get new objective value */
620
622 {
623 /* we must start again with the first candidate, since the LP solution changed */
624 nextcand = 0;
625
626 /* create solution from diving LP and try to round it */
629 if( success )
630 {
631 SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n",
633
634 /* try to add solution to SCIP */
636
637 /* check, if solution was feasible and good enough */
638 if( success )
639 {
640 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
642 }
643 }
644 }
645 else
646 nextcand = bestcand+1; /* continue with the next candidate in the following loop */
647 }
648 SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
649 }
650
651 /* free temporary memory */
653
654 /* end diving */
656
657 if( *result == SCIP_FOUNDSOL )
658 heurdata->nsuccess++;
659
660 SCIPdebugMsg(scip, "intdiving heuristic finished\n");
661
662 return SCIP_OKAY; /*lint !e438*/
663}
664
665
666/*
667 * heuristic specific interface methods
668 */
669
670/** creates the intdiving heuristic and includes it in SCIP */
672 SCIP* scip /**< SCIP data structure */
673 )
674{
676 SCIP_HEUR* heur;
677
678 /* create Intdiving primal heuristic data */
680
681 /* include primal heuristic */
685
686 assert(heur != NULL);
687
688 /* set non-NULL pointers to callback methods */
693
694 /* intdiving heuristic parameters */
696 "heuristics/intdiving/minreldepth",
697 "minimal relative depth to start diving",
698 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
700 "heuristics/intdiving/maxreldepth",
701 "maximal relative depth to start diving",
702 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
704 "heuristics/intdiving/maxlpiterquot",
705 "maximal fraction of diving LP iterations compared to node LP iterations",
706 &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
708 "heuristics/intdiving/maxlpiterofs",
709 "additional number of allowed LP iterations",
710 &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
712 "heuristics/intdiving/maxdiveubquot",
713 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
714 &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
716 "heuristics/intdiving/maxdiveavgquot",
717 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
718 &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
720 "heuristics/intdiving/maxdiveubquotnosol",
721 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
722 &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
724 "heuristics/intdiving/maxdiveavgquotnosol",
725 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
726 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
728 "heuristics/intdiving/backtrack",
729 "use one level of backtracking if infeasibility is encountered?",
730 &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
731
732 return SCIP_OKAY;
733}
#define NULL
Definition def.h:267
#define SCIP_Longint
Definition def.h:158
#define SCIP_MAXTREEDEPTH
Definition def.h:316
#define SCIP_REAL_MAX
Definition def.h:174
#define SCIP_INVALID
Definition def.h:193
#define MIN(x, y)
Definition def.h:243
#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_LONGINT_FORMAT
Definition def.h:165
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition scip_prob.c:1562
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPincludeHeurIntdiving(SCIP *scip)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
int SCIPgetNPseudoBranchCands(SCIP *scip)
int SCIPcolGetNNonz(SCIP_COL *col)
Definition lp.c:17126
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition scip_heur.c:117
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition scip_lp.c:2745
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:247
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:667
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition scip_sol.c:2311
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:2954
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1300
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1432
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasFracIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17789
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:9475
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18356
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18452
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
void SCIPenableVarHistory(SCIP *scip)
Definition scip_var.c:8743
SCIP_VAR ** fixcands
int divedepth
#define DEFAULT_MAXDIVEUBQUOT
int maxdivedepth
SCIP_Real searchavgbound
* result
SCIP_VAR ** pseudocands
int nbinfixcands
SCIP_Longint nsolsfound
SCIP_Bool lperror
heurdata
SCIPheurSetData(heur, NULL)
SCIP_Longint ncalls
#define HEUR_TIMING
return SCIP_OKAY
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
int c
#define HEUR_DESC
SCIP_Real searchubbound
static SCIP_LPSOLSTAT lpsolstat
SCIP_Bool backtracked
#define MINLPITER
#define DEFAULT_MAXDIVEAVGQUOT
heurdata nsuccess
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
heurdata nlpiterations
SCIPfreeSol(scip, &heurdata->sol))
SCIPendProbing(scip))
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
SCIP_Real searchbound
#define HEUR_NAME
SCIP_Longint maxnlpiterations
int maxdepth
int depth
#define HEUR_FREQ
#define DEFAULT_MINRELDEPTH
SCIP_Bool cutoff
#define HEUR_USESSUBSCIP
int nextcand
SCIP_Real objval
int nfixcands
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIP_Real * fixcandscores
LP diving heuristic that fixes variables with integral LP value.
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
SCIP_VAR * var
int bestcand
SCIP_Real frac
memory allocation routines
public methods for primal heuristics
public methods for LP management
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
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
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition type_lp.h:51
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition type_lp.h:46
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51