Scippy

SCIP

Solving Constraint Integer Programs

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);
143 assert(divecandvars != NULL);
144 assert(ndivecands >= 0);
145
146 SCIP_CALL( SCIPallocBufferArray(scip, &objcoefs, ndivecands) );
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
162 objcoefs[nnzobjcoefs] = REALABS(obj);
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 */
179 SCIPsortReal(objcoefs, nnzobjcoefs);
180 assert(!SCIPisZero(scip, objcoefs[0]));
181
182 lastobjcoef = objcoefs[0];
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 {
211 if( SCIPisGT(scip, objcoefs[i], lastobjcoef) )
212 {
213 if( tmpmaxfreq > maxfreq )
214 maxfreq = tmpmaxfreq;
215 tmpmaxfreq = 0;
216
217 lastobjcoef = objcoefs[i];
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:
242 SCIPfreeBufferArray(scip, &objcoefs);
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
263 vars = SCIPgetVars(scip);
264 nbinvars = SCIPgetNBinVars(scip);
265 nintvars = SCIPgetNIntVars(scip);
266
267 SCIP_CALL( checkDivingCandidates(scip, heurdata, vars, nbinvars+nintvars, &success) );
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
286SCIP_DECL_HEURCOPY(heurCopyFarkasdiving)
287{ /*lint --e{715}*/
288 assert(scip != NULL);
289 assert(heur != NULL);
290 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
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
300SCIP_DECL_HEURFREE(heurFreeFarkasdiving)
301{ /*lint --e{715}*/
302 SCIP_HEURDATA* heurdata;
303
304 assert(heur != NULL);
305 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
306 assert(scip != NULL);
307
308 /* free heuristic data */
309 heurdata = SCIPheurGetData(heur);
310 assert(heurdata != NULL);
311
312 SCIPfreeBlockMemory(scip, &heurdata);
313 SCIPheurSetData(heur, NULL);
314
315 return SCIP_OKAY;
316}
317
318
319/** initialization method of primal heuristic (called after problem was transformed) */
320static
321SCIP_DECL_HEURINIT(heurInitFarkasdiving)
322{ /*lint --e{715}*/
323 SCIP_HEURDATA* heurdata;
324
325 assert(heur != NULL);
326 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
327
328 /* get heuristic data */
329 heurdata = SCIPheurGetData(heur);
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
344SCIP_DECL_HEUREXIT(heurExitFarkasdiving)
345{ /*lint --e{715}*/
346 SCIP_HEURDATA* heurdata;
347
348 assert(heur != NULL);
349 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
350
351 /* get heuristic data */
352 heurdata = SCIPheurGetData(heur);
353 assert(heurdata != NULL);
354
355 /* free working solution */
356 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
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
363SCIP_DECL_HEURINITSOL(heurInitsolFarkasdiving)
364{ /*lint --e{715}*/
365 SCIP_HEURDATA* heurdata;
366
367 assert(heur != NULL);
368 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
369
370 /* get heuristic data */
371 heurdata = SCIPheurGetData(heur);
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
383SCIP_DECL_HEUREXEC(heurExecFarkasdiving)
384{ /*lint --e{715}*/
385 SCIP_HEURDATA* heurdata;
386 SCIP_DIVESET* diveset;
387 SCIP_Bool success;
388
389 heurdata = SCIPheurGetData(heur);
390 assert(SCIPheurGetNDivesets(heur) > 0);
391 assert(SCIPheurGetDivesets(heur) != NULL);
392
393 diveset = SCIPheurGetDivesets(heur)[0];
394 assert(diveset != NULL);
395
396 *result = SCIP_DIDNOTRUN;
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 {
419 SCIP_VAR** divecandvars;
420 int ndivecands;
421
422 /* we can only access the branching candidates if the LP is solved to optimality */
424 {
425 SCIP_CALL( SCIPgetLPBranchCands(scip, &divecandvars, NULL, NULL, &ndivecands, NULL, NULL) );
426
427 SCIP_CALL( checkDivingCandidates(scip, heurdata, divecandvars, ndivecands, &success) );
428 }
429 else
430 {
431 success = FALSE;
432 }
433 }
434
435 if( success )
436 {
437 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
438
439 if( heurdata->rootsuccess && SCIPgetDepth(scip) == 0 && SCIPdivesetGetNSols(diveset, SCIP_DIVECONTEXT_SINGLE) > 0 )
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
451SCIP_DECL_DIVESETGETSCORE(divesetGetScoreFarkasdiving)
452{ /*lint --e{715}*/
453 SCIP_HEUR* heur;
454 SCIP_HEURDATA* heurdata;
455 SCIP_RANDNUMGEN* randnumgen;
456 SCIP_Real obj;
457
458 heur = SCIPdivesetGetHeur(diveset);
459 assert(heur != NULL);
460
461 heurdata = SCIPheurGetData(heur);
462 assert(heurdata != NULL);
463
464 randnumgen = SCIPdivesetGetRandnumgen(diveset);
465 assert(randnumgen != NULL);
466
467 obj = SCIPvarGetObj(cand);
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
507 *score *= (SCIPvarGetUbLocal(cand) - SCIPfloor(scip, candsol));
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{
528 SCIP_HEURDATA* heurdata;
529 SCIP_HEUR* heur;
530
531 /* create Farkasdiving primal heuristic data */
532 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
533
534 /* include primal heuristic */
537 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFarkasdiving, heurdata) );
538
539 assert(heur != NULL);
540
541 /* set non-NULL pointers to callback methods */
542 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFarkasdiving) );
543 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFarkasdiving) );
544 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitFarkasdiving) );
545 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitFarkasdiving) );
546 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolFarkasdiving) );
547
548 /* farkasdiving heuristic parameters */
549 /* create a diveset (this will automatically install some additional parameters for the heuristic) */
553 divesetGetScoreFarkasdiving, divesetAvailableFarkasdiving) );
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 SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#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
Definition: scip_message.h:78
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)
Definition: scip_branch.c:395
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)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
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:7493
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
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
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_MAXDIVEUBQUOT
static SCIP_DECL_HEURINITSOL(heurInitsolFarkasdiving)
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define HEUR_TIMING
static SCIP_DECL_HEUREXIT(heurExitFarkasdiving)
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
static SCIP_DECL_HEUREXEC(heurExecFarkasdiving)
#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
static SCIP_DECL_HEURINIT(heurInitFarkasdiving)
#define DEFAULT_RANDSEED
static SCIP_DECL_HEURCOPY(heurCopyFarkasdiving)
#define DIVESET_DIVETYPES
static SCIP_RETCODE checkDivingCandidates(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **divecandvars, int ndivecands, SCIP_Bool *success)
static SCIP_DECL_HEURFREE(heurFreeFarkasdiving)
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreFarkasdiving)
#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.
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
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_DIVECONTEXT_SINGLE
Definition: type_heur.h:69
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62