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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_farkasdiving.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief LP diving heuristic that tries to construct a Farkas-proof
19  * @author Jakob Witzig
20  *
21  * The heuristic dives into the direction of the pseudosolution, i.e., variables get rounded
22  * towards their best bound w.r.t there objective coefficient. This strategy is twofold, if
23  * a feasible solution is found the solution has potentially a very good objective value; on the other
24  * hand, the left-hand side of a potential Farkas-proof \f$y^Tb - y^TA{l',u'} > 0\f$ (i.e., infeasibility proof)
25  * gets increased, where \f$l',u'\f$ are the local bounds. The contribution of each variable \f$x_i\f$ to the
26  * Farkas-proof can be approximated by \f$c_i = y^TA_i\f$ because we only dive on basic variables with
27  * reduced costs \f$c_i - y^TA_i = 0\f$.
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "blockmemshell/memory.h"
33 #include "scip/heur_farkasdiving.h"
34 #include "scip/heuristics.h"
35 #include "scip/pub_heur.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_misc.h"
38 #include "scip/pub_misc_sort.h"
39 #include "scip/pub_tree.h"
40 #include "scip/pub_var.h"
41 #include "scip/scip_branch.h"
42 #include "scip/scip_heur.h"
43 #include "scip/scip_lp.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_prob.h"
49 #include "scip/scip_sol.h"
50 #include "scip/scip_tree.h"
51 #include <string.h>
52 
53 #define HEUR_NAME "farkasdiving"
54 #define HEUR_DESC "LP diving heuristic that tries to construct a Farkas-proof"
55 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
56 #define HEUR_PRIORITY -900000
57 #define HEUR_FREQ 10
58 #define HEUR_FREQOFS 0
59 #define HEUR_MAXDEPTH -1
60 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
61 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
62 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
63 #define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
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 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
82 #define DEFAULT_LPSOLVEFREQ 1 /**< LP solve frequency for diving heuristics */
83 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
84  * more general constraint handler diving variable selection? */
85 #define DEFAULT_RANDSEED 151 /**< initial seed for random number generation */
86 
87 #define DEFAULT_MAXOBJOCC 1.0 /**< maximal occurance factor of an objective coefficient */
88 #define DEFAULT_OBJDYN 0.0001 /**< minimal objective dynamism (log) */
89 #define DEFAULT_CHECKCANDS FALSE /**< should diving candidates be checked before running? */
90 #define DEFAULT_SCALESCORE TRUE /**< should the score be scaled? */
91 #define DEFAULT_ROOTSUCCESS TRUE /**< should the heuristic only run within the tree if at least one solution
92  * was found at the root node? */
93 #define DEFAULT_SCALETYPE 'i' /**< scale score by [f]ractionality or [i]mpact on farkasproof */
94 
95 /* locally defined heuristic data */
96 struct SCIP_HeurData
97 {
98  SCIP_SOL* sol; /**< working solution */
99  SCIP_Real maxobjocc; /**< maximal occurance factor of an objective coefficient */
100  SCIP_Real objdynamism; /**< minimal objective dynamism (log) */
101  SCIP_Bool disabled; /**< remember if the heuristic should not run at all */
102  SCIP_Bool glbchecked; /**< remember whether one global check was performed */
103  SCIP_Bool checkcands; /**< should diving candidates be checked before running? */
104  SCIP_Bool scalescore; /**< should score be scaled by fractionality */
105  SCIP_Bool rootsuccess; /**< run if successfull at root */
106  SCIP_Bool foundrootsol; /**< was a solution found at the root node? */
107  char scaletype; /**< scale score by [f]ractionality or [i]mpact on farkasproof */
108 };
109 
110 
111 /** check whether the diving candidates fulfill requirements */
112 static
114  SCIP* scip, /**< SCIP data structure */
115  SCIP_HEURDATA* heurdata, /**< heuristic data */
116  SCIP_VAR** divecandvars, /**< diving candidates to check */
117  int ndivecands, /**< number of diving candidates */
118  SCIP_Bool* success /**< pointer to store whether the check was successfull */
119  )
120 {
121  SCIP_Real* objcoefs;
122  SCIP_Real lastobjcoef;
123  SCIP_Real objdynamism;
124  int maxfreq;
125  int nnzobjcoefs;
126 #ifdef SCIP_DEBUG
127  int ndiffnnzobjs;
128 #endif
129  int i;
130 
131  *success = TRUE;
132 
133  assert(heurdata != NULL);
134  assert(divecandvars != NULL);
135  assert(ndivecands >= 0);
136 
137  SCIP_CALL( SCIPallocBufferArray(scip, &objcoefs, ndivecands) );
138 
139  /* collect all absolute values of objective coefficients and count binary, integer,
140  * and implicit integer in the objective function
141  */
142  nnzobjcoefs = 0;
143 
144  if( SCIPgetNObjVars(scip) > 0 )
145  {
146  for( i = 0; i < ndivecands; i++ )
147  {
148  SCIP_Real obj = SCIPvarGetObj(divecandvars[i]);
149 
150  if( SCIPisZero(scip, obj) )
151  continue;
152 
153  objcoefs[nnzobjcoefs] = REALABS(obj);
154  ++nnzobjcoefs;
155  }
156  }
157 
158  if( nnzobjcoefs == 0 )
159  {
160  *success = FALSE;
161  goto TERMINATE;
162  }
163  assert(nnzobjcoefs > 0);
164 
165  /* skip here if we are cheching the global properties and want to check the local candidates, too */
166  if( !heurdata->glbchecked && heurdata->checkcands )
167  goto TERMINATE;
168 
169  /* sort in increasing order */
170  SCIPsortReal(objcoefs, nnzobjcoefs);
171  assert(!SCIPisZero(scip, objcoefs[0]));
172 
173  lastobjcoef = objcoefs[0];
174 #ifdef SCIP_DEBUG
175  ndiffnnzobjs = 1;
176 #endif
177 
178  objdynamism = log10(objcoefs[nnzobjcoefs-1] / objcoefs[0]);
179 
180  SCIPdebugMsg(scip, "minabscoef: %g, maxabscoef: %g, objdym: %g\n", objcoefs[0], objcoefs[nnzobjcoefs-1], objdynamism);
181 
182  /* CHECK#2: check objective dynamism */
183  if( objdynamism < heurdata->objdynamism )
184  {
185  SCIPdebugMsg(scip, " ---> disable farkasdiving at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
186 
187  *success = FALSE;
188  goto TERMINATE;
189  }
190 
191  /* CHECK#4: the check would be always fulfilled for heurdata->maxobjocc = 1.0 */
192  if( heurdata->maxobjocc < 1.0 )
193  {
194  int tmpmaxfreq;
195 
196  tmpmaxfreq = 0;
197  maxfreq = 0;
198 
199  /* count number of different absolute objective values */
200  for( i = 1; i < nnzobjcoefs; i++ )
201  {
202  if( SCIPisGT(scip, objcoefs[i], lastobjcoef) )
203  {
204  if( tmpmaxfreq > maxfreq )
205  maxfreq = tmpmaxfreq;
206  tmpmaxfreq = 0;
207 
208  lastobjcoef = objcoefs[i];
209 #ifdef SCIP_DEBUG
210  ++ndiffnnzobjs;
211 #endif
212  }
213  else
214  {
215  ++tmpmaxfreq;
216  }
217  }
218 
219 #ifdef SCIP_DEBUG
220  SCIPdebugMsg(scip, "%d divecands; %d nnzobjs; %d diffnnzobjs; %d maxfreq\n", ndivecands, nnzobjcoefs, ndiffnnzobjs,
221  maxfreq);
222 #endif
223 
224  if( maxfreq > heurdata->maxobjocc * nnzobjcoefs )
225  {
226  SCIPdebugMsg(scip, " ---> disable farkasdiving at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
227 
228  *success = FALSE;
229  }
230  }
231 
232  TERMINATE:
233  SCIPfreeBufferArray(scip, &objcoefs);
234 
235  return SCIP_OKAY;
236 }
237 
238 
239 /** check whether the objective functions has nonzero coefficients corresponding to binary and integer variables */
240 static
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_HEURDATA* heurdata /**< heuristic data */
244  )
245 {
246  SCIP_VAR** vars;
247  SCIP_Bool success;
248  int nbinvars;
249  int nintvars;
250 
251  assert(scip != NULL);
252  assert(heurdata != NULL);
253 
254  vars = SCIPgetVars(scip);
255  nbinvars = SCIPgetNBinVars(scip);
256  nintvars = SCIPgetNIntVars(scip);
257 
258  SCIP_CALL( checkDivingCandidates(scip, heurdata, vars, nbinvars+nintvars, &success) );
259 
260  if( !success )
261  {
262  SCIPdebugMsg(scip, " ---> disable farkasdiving (at least one global property is violated)\n");
263  heurdata->disabled = TRUE;
264  }
265 
266  heurdata->glbchecked = TRUE;
267 
268  return SCIP_OKAY;
269 }
270 
271 /*
272  * Callback methods
273  */
274 
275 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
276 static
277 SCIP_DECL_HEURCOPY(heurCopyFarkasdiving)
278 { /*lint --e{715}*/
279  assert(scip != NULL);
280  assert(heur != NULL);
281  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
282 
283  /* call inclusion method of primal heuristic */
285 
286  return SCIP_OKAY;
287 }
288 
289 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
290 static
291 SCIP_DECL_HEURFREE(heurFreeFarkasdiving)
292 { /*lint --e{715}*/
293  SCIP_HEURDATA* heurdata;
294 
295  assert(heur != NULL);
296  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
297  assert(scip != NULL);
298 
299  /* free heuristic data */
300  heurdata = SCIPheurGetData(heur);
301  assert(heurdata != NULL);
302 
303  SCIPfreeBlockMemory(scip, &heurdata);
304  SCIPheurSetData(heur, NULL);
305 
306  return SCIP_OKAY;
307 }
308 
309 
310 /** initialization method of primal heuristic (called after problem was transformed) */
311 static
312 SCIP_DECL_HEURINIT(heurInitFarkasdiving)
313 { /*lint --e{715}*/
314  SCIP_HEURDATA* heurdata;
315 
316  assert(heur != NULL);
317  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
318 
319  /* get heuristic data */
320  heurdata = SCIPheurGetData(heur);
321  assert(heurdata != NULL);
322 
323  /* create working solution */
324  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
325 
326  heurdata->disabled = FALSE;
327  heurdata->glbchecked = FALSE;
328 
329  return SCIP_OKAY;
330 }
331 
332 
333 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
334 static
335 SCIP_DECL_HEUREXIT(heurExitFarkasdiving)
336 { /*lint --e{715}*/
337  SCIP_HEURDATA* heurdata;
338 
339  assert(heur != NULL);
340  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
341 
342  /* get heuristic data */
343  heurdata = SCIPheurGetData(heur);
344  assert(heurdata != NULL);
345 
346  /* free working solution */
347  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
348 
349  return SCIP_OKAY;
350 }
351 
352 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
353 static
354 SCIP_DECL_HEURINITSOL(heurInitsolFarkasdiving)
355 { /*lint --e{715}*/
356  SCIP_HEURDATA* heurdata;
357 
358  assert(heur != NULL);
359  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
360 
361  /* get heuristic data */
362  heurdata = SCIPheurGetData(heur);
363  assert(heurdata != NULL);
364 
365  heurdata->glbchecked = FALSE;
366  heurdata->disabled = FALSE;
367  heurdata->foundrootsol = FALSE;
368 
369  return SCIP_OKAY;
370 }
371 
372 /** execution method of primal heuristic */
373 static
374 SCIP_DECL_HEUREXEC(heurExecFarkasdiving)
375 { /*lint --e{715}*/
376  SCIP_HEURDATA* heurdata;
377  SCIP_DIVESET* diveset;
378  SCIP_Bool success;
379 
380  heurdata = SCIPheurGetData(heur);
381  assert(SCIPheurGetNDivesets(heur) > 0);
382  assert(SCIPheurGetDivesets(heur) != NULL);
383 
384  diveset = SCIPheurGetDivesets(heur)[0];
385  assert(diveset != NULL);
386 
387  *result = SCIP_DIDNOTRUN;
388 
389  /* check some simple global properties that are needed to run this heuristic */
390  if( !heurdata->glbchecked )
391  {
392  SCIP_CALL( checkGlobalProperties(scip, heurdata) );
393  }
394 
395  /* terminate if the heuristic has been disabled */
396  if( heurdata->disabled )
397  return SCIP_OKAY;
398 
399  if( heurdata->rootsuccess && !heurdata->foundrootsol && SCIPgetDepth(scip) > 0 )
400  {
401  heurdata->disabled = TRUE;
402  return SCIP_OKAY;
403  }
404 
405  success = TRUE;
406 
407  /* check diving candidates in detail */
408  if( heurdata->checkcands )
409  {
410  SCIP_VAR** divecandvars;
411  int ndivecands;
412 
413  /* we can only access the branching candidates if the LP is solved to optimality */
415  {
416  SCIP_CALL( SCIPgetLPBranchCands(scip, &divecandvars, NULL, NULL, &ndivecands, NULL, NULL) );
417 
418  SCIP_CALL( checkDivingCandidates(scip, heurdata, divecandvars, ndivecands, &success) );
419  }
420  else
421  {
422  success = FALSE;
423  }
424  }
425 
426  if( success )
427  {
428  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, SCIP_DIVECONTEXT_SINGLE) );
429 
430  if( heurdata->rootsuccess && SCIPgetDepth(scip) == 0 && SCIPdivesetGetNSols(diveset, SCIP_DIVECONTEXT_SINGLE) > 0 )
431  heurdata->foundrootsol = TRUE;
432  }
433 
434  return SCIP_OKAY;
435 }
436 
437 #define MIN_RAND 1e-06
438 #define MAX_RAND 1e-05
439 
440 /** calculate score and preferred rounding direction for the candidate variable */
441 static
442 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreFarkasdiving)
443 { /*lint --e{715}*/
444  SCIP_HEUR* heur;
445  SCIP_HEURDATA* heurdata;
446  SCIP_RANDNUMGEN* randnumgen;
447  SCIP_Real obj;
448 
449  heur = SCIPdivesetGetHeur(diveset);
450  assert(heur != NULL);
451 
452  heurdata = SCIPheurGetData(heur);
453  assert(heurdata != NULL);
454 
455  randnumgen = SCIPdivesetGetRandnumgen(diveset);
456  assert(randnumgen != NULL);
457 
458  obj = SCIPvarGetObj(cand);
459 
460  /* dive towards the pseudosolution, at the same time approximate the contribution to
461  * a potentially Farkas-proof (infeasibility proof) by y^TA_i = c_i.
462  */
463  if( SCIPisNegative(scip, obj) )
464  {
465  *roundup = TRUE;
466  }
467  else if( SCIPisPositive(scip, obj) )
468  {
469  *roundup = FALSE;
470  }
471  else
472  {
473  if( SCIPisEQ(scip, candsfrac, 0.5) )
474  *roundup = !SCIPrandomGetInt(randnumgen, 0, 1);
475  else
476  *roundup = (candsfrac > 0.5);
477  }
478 
479  /* larger score is better */
480  *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND);
481 
482  if( heurdata->scalescore )
483  {
484  if( heurdata->scaletype == 'f' )
485  {
486  if( *roundup )
487  *score *= (1.0 - candsfrac);
488  else
489  *score *= candsfrac;
490  }
491  else
492  {
493  assert(heurdata->scaletype == 'i');
494 
495  if( *roundup )
496  *score *= (SCIPceil(scip, candsol) - SCIPvarGetLbLocal(cand));
497  else
498  *score *= (SCIPvarGetUbLocal(cand) - SCIPfloor(scip, candsol));
499  }
500  }
501 
502  /* prefer decisions on binary variables */
503  if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
504  *score = -1.0 / *score;
505 
506  return SCIP_OKAY;
507 }
508 
509 /*
510  * heuristic specific interface methods
511  */
512 #define divesetAvailableFarkasdiving NULL
513 
514 /** creates the farkasdiving heuristic and includes it in SCIP */
516  SCIP* scip /**< SCIP data structure */
517  )
518 {
519  SCIP_HEURDATA* heurdata;
520  SCIP_HEUR* heur;
521 
522  /* create Farkasdiving primal heuristic data */
523  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
524 
525  /* include primal heuristic */
526  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
528  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFarkasdiving, heurdata) );
529 
530  assert(heur != NULL);
531 
532  /* set non-NULL pointers to callback methods */
533  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFarkasdiving) );
534  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFarkasdiving) );
535  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitFarkasdiving) );
536  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitFarkasdiving) );
537  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolFarkasdiving) );
538 
539  /* farkasdiving heuristic parameters */
540  /* create a diveset (this will automatically install some additional parameters for the heuristic) */
544  divesetGetScoreFarkasdiving, divesetAvailableFarkasdiving) );
545 
546  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/checkcands",
547  "should diving candidates be checked before running?",
548  &heurdata->checkcands, TRUE, DEFAULT_CHECKCANDS, NULL, NULL) );
549 
550  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scalescore",
551  "should the score be scaled?",
552  &heurdata->scalescore, TRUE, DEFAULT_SCALESCORE, NULL, NULL) );
553 
554  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/rootsuccess",
555  "should the heuristic only run within the tree if at least one solution was found at the root node?",
556  &heurdata->rootsuccess, TRUE, DEFAULT_ROOTSUCCESS, NULL, NULL) );
557 
558  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxobjocc",
559  "maximal occurance factor of an objective coefficient",
560  &heurdata->maxobjocc, TRUE, DEFAULT_MAXOBJOCC, 0.0, 1.0, NULL, NULL) );
561 
562  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objdynamism",
563  "minimal objective dynamism (log) to run",
564  &heurdata->objdynamism, TRUE, DEFAULT_OBJDYN, 0.0, SCIPinfinity(scip), NULL, NULL) );
565 
566  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scaletype",
567  "scale score by [f]ractionality or [i]mpact on farkasproof",
568  &heurdata->scaletype, TRUE, DEFAULT_SCALETYPE, "fi", NULL, NULL) );
569 
570  return SCIP_OKAY;
571 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
#define DEFAULT_MINRELDEPTH
#define DEFAULT_SCALESCORE
static SCIP_RETCODE checkGlobalProperties(SCIP *scip, SCIP_HEURDATA *heurdata)
public methods for SCIP parameter handling
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
public methods for branch and bound tree
public methods for memory management
#define HEUR_TIMING
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
#define HEUR_DISPCHAR
#define DEFAULT_RANDSEED
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1639
static SCIP_DECL_HEURINIT(heurInitFarkasdiving)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_CHECKCANDS
#define FALSE
Definition: def.h:87
#define DEFAULT_MAXOBJOCC
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
methods commonly used by primal heuristics
#define DEFAULT_MAXDIVEUBQUOTNOSOL
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define DIVESET_ISPUBLIC
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:108
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
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:309
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_SCALETYPE
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
#define MAX_RAND
#define DEFAULT_BACKTRACK
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:209
public methods for numerical tolerances
#define DEFAULT_OBJDYN
public methods for the branch-and-bound tree
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:405
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7434
static SCIP_DECL_HEUREXEC(heurExecFarkasdiving)
#define divesetAvailableFarkasdiving
#define HEUR_PRIORITY
#define DEFAULT_MAXLPITERQUOT
static SCIP_DECL_HEURFREE(heurFreeFarkasdiving)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_RETCODE SCIPincludeHeurFarkasdiving(SCIP *scip)
LP diving heuristic that tries to construct a Farkas-proof.
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
#define DEFAULT_MAXDIVEUBQUOT
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:630
#define MIN_RAND
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_SOL * sol
Definition: struct_heur.h:62
static SCIP_RETCODE checkDivingCandidates(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **divecandvars, int ndivecands, SCIP_Bool *success)
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreFarkasdiving)
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
#define SCIP_CALL(x)
Definition: def.h:384
#define DEFAULT_LPRESOLVEDOMCHGQUOT
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1649
public methods for primal heuristic plugins and divesets
#define DEFAULT_ONLYLPBRANCHCANDS
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define DEFAULT_MAXRELDEPTH
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
#define HEUR_DESC
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:709
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2219
#define HEUR_USESSUBSCIP
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
public methods for the LP relaxation, rows and columns
static SCIP_DECL_HEURCOPY(heurCopyFarkasdiving)
#define DEFAULT_MAXDIVEAVGQUOT
methods for sorting joint arrays of various types
#define DEFAULT_LPSOLVEFREQ
public methods for branching rule plugins and branching
#define HEUR_NAME
#define DIVESET_DIVETYPES
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:158
public methods for solutions
static SCIP_DECL_HEURINITSOL(heurInitsolFarkasdiving)
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
#define HEUR_FREQOFS
#define SCIP_Real
Definition: def.h:177
static SCIP_DECL_HEUREXIT(heurExitFarkasdiving)
public methods for message handling
#define HEUR_FREQ
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_ROOTSUCCESS
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define DEFAULT_MAXLPITEROFS
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
public methods for global and local (sub)problems
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:130
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define HEUR_MAXDEPTH
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:48
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines