SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_farkasdiving.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_farkasdiving.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief LP diving heuristic that tries to construct a Farkas-proof
28 * @author Jakob Witzig
29 *
30 * The heuristic dives into the direction of the pseudosolution, i.e., variables get rounded
31 * towards their best bound w.r.t there objective coefficient. This strategy is twofold, if
32 * a feasible solution is found the solution has potentially a very good objective value; on the other
33 * hand, the left-hand side of a potential Farkas-proof \f$y^Tb - y^TA{l',u'} > 0\f$ (i.e., infeasibility proof)
34 * gets increased, where \f$l',u'\f$ are the local bounds. The contribution of each variable \f$x_i\f$ to the
35 * Farkas-proof can be approximated by \f$c_i = y^TA_i\f$ because we only dive on basic variables with
36 * reduced costs \f$c_i - y^TA_i = 0\f$.
37 */
38
39/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40
43#include "scip/heuristics.h"
44#include "scip/pub_heur.h"
45#include "scip/pub_message.h"
46#include "scip/pub_misc.h"
47#include "scip/pub_misc_sort.h"
48#include "scip/pub_tree.h"
49#include "scip/pub_var.h"
50#include "scip/scip_branch.h"
51#include "scip/scip_heur.h"
52#include "scip/scip_lp.h"
53#include "scip/scip_mem.h"
54#include "scip/scip_message.h"
55#include "scip/scip_numerics.h"
56#include "scip/scip_param.h"
57#include "scip/scip_prob.h"
58#include "scip/scip_sol.h"
59#include "scip/scip_tree.h"
60#include <string.h>
61
62#define HEUR_NAME "farkasdiving"
63#define HEUR_DESC "LP diving heuristic that tries to construct a Farkas-proof"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
65#define HEUR_PRIORITY -900000
66#define HEUR_FREQ 10
67#define HEUR_FREQOFS 0
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
70#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
71#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
72#define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
73
74
75/*
76 * Default parameter settings
77 */
78
79#define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
80#define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
81#define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
82#define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
83#define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
84 * where diving is performed (0.0: no limit) */
85#define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
86 * where diving is performed (0.0: no limit) */
87#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
88#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
89#define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
90#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
91#define DEFAULT_LPSOLVEFREQ 1 /**< LP solve frequency for diving heuristics */
92#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
93 * more general constraint handler diving variable selection? */
94#define DEFAULT_RANDSEED 151 /**< initial seed for random number generation */
95
96#define DEFAULT_MAXOBJOCC 1.0 /**< maximal occurance factor of an objective coefficient */
97#define DEFAULT_OBJDYN 0.0001 /**< minimal objective dynamism (log) */
98#define DEFAULT_CHECKCANDS FALSE /**< should diving candidates be checked before running? */
99#define DEFAULT_SCALESCORE TRUE /**< should the score be scaled? */
100#define DEFAULT_ROOTSUCCESS TRUE /**< should the heuristic only run within the tree if at least one solution
101 * was found at the root node? */
102#define DEFAULT_SCALETYPE 'i' /**< scale score by [f]ractionality or [i]mpact on farkasproof */
103
104/* locally defined heuristic data */
105struct SCIP_HeurData
106{
107 SCIP_SOL* sol; /**< working solution */
108 SCIP_Real maxobjocc; /**< maximal occurance factor of an objective coefficient */
109 SCIP_Real objdynamism; /**< minimal objective dynamism (log) */
110 SCIP_Bool disabled; /**< remember if the heuristic should not run at all */
111 SCIP_Bool glbchecked; /**< remember whether one global check was performed */
112 SCIP_Bool checkcands; /**< should diving candidates be checked before running? */
113 SCIP_Bool scalescore; /**< should score be scaled by fractionality */
114 SCIP_Bool rootsuccess; /**< run if successfull at root */
115 SCIP_Bool foundrootsol; /**< was a solution found at the root node? */
116 char scaletype; /**< scale score by [f]ractionality or [i]mpact on farkasproof */
117};
118
119
120/** check whether the diving candidates fulfill requirements */
121static
123 SCIP* scip, /**< SCIP data structure */
124 SCIP_HEURDATA* heurdata, /**< heuristic data */
125 SCIP_VAR** divecandvars, /**< diving candidates to check */
126 int ndivecands, /**< number of diving candidates */
127 SCIP_Bool* success /**< pointer to store whether the check was successfull */
128 )
129{
130 SCIP_Real* objcoefs;
131 SCIP_Real lastobjcoef;
132 SCIP_Real objdynamism;
133 int maxfreq;
134 int nnzobjcoefs;
135#ifdef SCIP_DEBUG
136 int ndiffnnzobjs;
137#endif
138 int i;
139
140 *success = TRUE;
141
142 assert(heurdata != NULL);
144 assert(ndivecands >= 0);
145
147
148 /* collect all absolute values of objective coefficients and count binary, integer,
149 * and implicit integer in the objective function
150 */
151 nnzobjcoefs = 0;
152
153 if( SCIPgetNObjVars(scip) > 0 )
154 {
155 for( i = 0; i < ndivecands; i++ )
156 {
157 SCIP_Real obj = SCIPvarGetObj(divecandvars[i]);
158
159 if( SCIPisZero(scip, obj) )
160 continue;
161
163 ++nnzobjcoefs;
164 }
165 }
166
167 if( nnzobjcoefs == 0 )
168 {
169 *success = FALSE;
170 goto TERMINATE;
171 }
172 assert(nnzobjcoefs > 0);
173
174 /* skip here if we are cheching the global properties and want to check the local candidates, too */
175 if( !heurdata->glbchecked && heurdata->checkcands )
176 goto TERMINATE;
177
178 /* sort in increasing order */
181
183#ifdef SCIP_DEBUG
184 ndiffnnzobjs = 1;
185#endif
186
187 objdynamism = log10(objcoefs[nnzobjcoefs-1] / objcoefs[0]);
188
189 SCIPdebugMsg(scip, "minabscoef: %g, maxabscoef: %g, objdym: %g\n", objcoefs[0], objcoefs[nnzobjcoefs-1], objdynamism);
190
191 /* CHECK#2: check objective dynamism */
192 if( objdynamism < heurdata->objdynamism )
193 {
194 SCIPdebugMsg(scip, " ---> disable farkasdiving at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
195
196 *success = FALSE;
197 goto TERMINATE;
198 }
199
200 /* CHECK#4: the check would be always fulfilled for heurdata->maxobjocc = 1.0 */
201 if( heurdata->maxobjocc < 1.0 )
202 {
203 int tmpmaxfreq;
204
205 tmpmaxfreq = 0;
206 maxfreq = 0;
207
208 /* count number of different absolute objective values */
209 for( i = 1; i < nnzobjcoefs; i++ )
210 {
212 {
213 if( tmpmaxfreq > maxfreq )
215 tmpmaxfreq = 0;
216
218#ifdef SCIP_DEBUG
219 ++ndiffnnzobjs;
220#endif
221 }
222 else
223 {
224 ++tmpmaxfreq;
225 }
226 }
227
228#ifdef SCIP_DEBUG
229 SCIPdebugMsg(scip, "%d divecands; %d nnzobjs; %d diffnnzobjs; %d maxfreq\n", ndivecands, nnzobjcoefs, ndiffnnzobjs,
230 maxfreq);
231#endif
232
233 if( maxfreq > heurdata->maxobjocc * nnzobjcoefs )
234 {
235 SCIPdebugMsg(scip, " ---> disable farkasdiving at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
236
237 *success = FALSE;
238 }
239 }
240
241 TERMINATE:
243
244 return SCIP_OKAY;
245}
246
247
248/** check whether the objective functions has nonzero coefficients corresponding to binary and integer variables */
249static
251 SCIP* scip, /**< SCIP data structure */
252 SCIP_HEURDATA* heurdata /**< heuristic data */
253 )
254{
255 SCIP_VAR** vars;
256 SCIP_Bool success;
257 int nbinvars;
258 int nintvars;
259
260 assert(scip != NULL);
261 assert(heurdata != NULL);
262
266
268
269 if( !success )
270 {
271 SCIPdebugMsg(scip, " ---> disable farkasdiving (at least one global property is violated)\n");
272 heurdata->disabled = TRUE;
273 }
274
275 heurdata->glbchecked = TRUE;
276
277 return SCIP_OKAY;
278}
279
280/*
281 * Callback methods
282 */
283
284/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
285static
287{ /*lint --e{715}*/
288 assert(scip != NULL);
289 assert(heur != NULL);
291
292 /* call inclusion method of primal heuristic */
294
295 return SCIP_OKAY;
296}
297
298/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
299static
301{ /*lint --e{715}*/
303
304 assert(heur != NULL);
306 assert(scip != NULL);
307
308 /* free heuristic data */
310 assert(heurdata != NULL);
311
313 SCIPheurSetData(heur, NULL);
314
315 return SCIP_OKAY;
316}
317
318
319/** initialization method of primal heuristic (called after problem was transformed) */
320static
322{ /*lint --e{715}*/
324
325 assert(heur != NULL);
327
328 /* get heuristic data */
330 assert(heurdata != NULL);
331
332 /* create working solution */
333 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
334
335 heurdata->disabled = FALSE;
336 heurdata->glbchecked = FALSE;
337
338 return SCIP_OKAY;
339}
340
341
342/** deinitialization method of primal heuristic (called before transformed problem is freed) */
343static
345{ /*lint --e{715}*/
347
348 assert(heur != NULL);
350
351 /* get heuristic data */
353 assert(heurdata != NULL);
354
355 /* free working solution */
357
358 return SCIP_OKAY;
359}
360
361/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
362static
364{ /*lint --e{715}*/
366
367 assert(heur != NULL);
369
370 /* get heuristic data */
372 assert(heurdata != NULL);
373
374 heurdata->glbchecked = FALSE;
375 heurdata->disabled = FALSE;
376 heurdata->foundrootsol = FALSE;
377
378 return SCIP_OKAY;
379}
380
381/** execution method of primal heuristic */
382static
384{ /*lint --e{715}*/
387 SCIP_Bool success;
388
390 assert(SCIPheurGetNDivesets(heur) > 0);
392
393 diveset = SCIPheurGetDivesets(heur)[0];
394 assert(diveset != NULL);
395
397
398 /* check some simple global properties that are needed to run this heuristic */
399 if( !heurdata->glbchecked )
400 {
402 }
403
404 /* terminate if the heuristic has been disabled */
405 if( heurdata->disabled )
406 return SCIP_OKAY;
407
408 if( heurdata->rootsuccess && !heurdata->foundrootsol && SCIPgetDepth(scip) > 0 )
409 {
410 heurdata->disabled = TRUE;
411 return SCIP_OKAY;
412 }
413
414 success = TRUE;
415
416 /* check diving candidates in detail */
417 if( heurdata->checkcands )
418 {
420 int ndivecands;
421
422 /* we can only access the branching candidates if the LP is solved to optimality */
424 {
426
428 }
429 else
430 {
431 success = FALSE;
432 }
433 }
434
435 if( success )
436 {
438
440 heurdata->foundrootsol = TRUE;
441 }
442
443 return SCIP_OKAY;
444}
445
446#define MIN_RAND 1e-06
447#define MAX_RAND 1e-05
448
449/** calculate score and preferred rounding direction for the candidate variable */
450static
452{ /*lint --e{715}*/
453 SCIP_HEUR* heur;
455 SCIP_RANDNUMGEN* randnumgen;
456 SCIP_Real obj;
457
459 assert(heur != NULL);
460
462 assert(heurdata != NULL);
463
464 randnumgen = SCIPdivesetGetRandnumgen(diveset);
465 assert(randnumgen != NULL);
466
468
469 /* dive towards the pseudosolution, at the same time approximate the contribution to
470 * a potentially Farkas-proof (infeasibility proof) by y^TA_i = c_i.
471 */
472 if( SCIPisNegative(scip, obj) )
473 {
474 *roundup = TRUE;
475 }
476 else if( SCIPisPositive(scip, obj) )
477 {
478 *roundup = FALSE;
479 }
480 else
481 {
482 if( SCIPisEQ(scip, candsfrac, 0.5) )
483 *roundup = !SCIPrandomGetInt(randnumgen, 0, 1);
484 else
485 *roundup = (candsfrac > 0.5);
486 }
487
488 /* larger score is better */
489 *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND);
490
491 if( heurdata->scalescore )
492 {
493 if( heurdata->scaletype == 'f' )
494 {
495 if( *roundup )
496 *score *= (1.0 - candsfrac);
497 else
498 *score *= candsfrac;
499 }
500 else
501 {
502 assert(heurdata->scaletype == 'i');
503
504 if( *roundup )
505 *score *= (SCIPceil(scip, candsol) - SCIPvarGetLbLocal(cand));
506 else
508 }
509 }
510
511 /* prefer decisions on binary variables */
513 *score = -1.0 / *score;
514
515 return SCIP_OKAY;
516}
517
518/*
519 * heuristic specific interface methods
520 */
521#define divesetAvailableFarkasdiving NULL
522
523/** creates the farkasdiving heuristic and includes it in SCIP */
525 SCIP* scip /**< SCIP data structure */
526 )
527{
529 SCIP_HEUR* heur;
530
531 /* create Farkasdiving primal heuristic data */
533
534 /* include primal heuristic */
538
539 assert(heur != NULL);
540
541 /* set non-NULL pointers to callback methods */
547
548 /* farkasdiving heuristic parameters */
549 /* create a diveset (this will automatically install some additional parameters for the heuristic) */
554
555 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/checkcands",
556 "should diving candidates be checked before running?",
557 &heurdata->checkcands, TRUE, DEFAULT_CHECKCANDS, NULL, NULL) );
558
559 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scalescore",
560 "should the score be scaled?",
561 &heurdata->scalescore, TRUE, DEFAULT_SCALESCORE, NULL, NULL) );
562
563 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/rootsuccess",
564 "should the heuristic only run within the tree if at least one solution was found at the root node?",
565 &heurdata->rootsuccess, TRUE, DEFAULT_ROOTSUCCESS, NULL, NULL) );
566
567 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxobjocc",
568 "maximal occurance factor of an objective coefficient",
569 &heurdata->maxobjocc, TRUE, DEFAULT_MAXOBJOCC, 0.0, 1.0, NULL, NULL) );
570
571 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objdynamism",
572 "minimal objective dynamism (log) to run",
573 &heurdata->objdynamism, TRUE, DEFAULT_OBJDYN, 0.0, SCIPinfinity(scip), NULL, NULL) );
574
575 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scaletype",
576 "scale score by [f]ractionality or [i]mpact on farkasproof",
577 &heurdata->scaletype, TRUE, DEFAULT_SCALETYPE, "fi", NULL, NULL) );
578
579 return SCIP_OKAY;
580}
#define NULL
Definition def.h:267
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
int SCIPgetNObjVars(SCIP *scip)
Definition scip_prob.c:2220
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:167
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 SCIPincludeHeurFarkasdiving(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, 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_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)),)
Definition scip_heur.c:318
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:641
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition heur.c:720
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_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition heur.c:1661
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_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition heur.c:1651
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1374
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition tree.c:7444
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition scip_tree.c:91
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10130
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10108
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition heur.c:416
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define HEUR_TIMING
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_SCALESCORE
#define DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXLPITEROFS
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_SCALETYPE
#define HEUR_NAME
#define DEFAULT_ROOTSUCCESS
static SCIP_RETCODE checkGlobalProperties(SCIP *scip, SCIP_HEURDATA *heurdata)
#define divesetAvailableFarkasdiving
#define MAX_RAND
#define DEFAULT_CHECKCANDS
#define DEFAULT_RANDSEED
#define DIVESET_DIVETYPES
static SCIP_RETCODE checkDivingCandidates(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **divecandvars, int ndivecands, SCIP_Bool *success)
#define DIVESET_ISPUBLIC
#define DEFAULT_MAXOBJOCC
#define HEUR_FREQ
#define MIN_RAND
#define DEFAULT_MINRELDEPTH
#define HEUR_USESSUBSCIP
#define DEFAULT_OBJDYN
LP diving heuristic that tries to construct a Farkas-proof.
static SCIP_SOL * sol
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool roundup
static SCIP_VAR ** vars
int nbinvars
int nintvars
methods commonly used by primal heuristics
memory allocation routines
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
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 solutions
public methods for the branch-and-bound tree
SCIP_SOL * sol
Definition struct_heur.h:71
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:132
#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_DIVESETGETSCORE(x)
Definition type_heur.h:184
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_DIVECONTEXT_SINGLE
Definition type_heur.h:69
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_DIDNOTRUN
Definition type_result.h:42
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62