1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	
41   	#include "blockmemshell/memory.h"
42   	#include "scip/heur_farkasdiving.h"
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 */
105  	struct 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 */
121  	static
122  	SCIP_RETCODE checkDivingCandidates(
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 */
249  	static
250  	SCIP_RETCODE checkGlobalProperties(
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) */
285  	static
286  	SCIP_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 */
293  	   SCIP_CALL( SCIPincludeHeurFarkasdiving(scip) );
294  	
295  	   return SCIP_OKAY;
296  	}
297  	
298  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
299  	static
300  	SCIP_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) */
320  	static
321  	SCIP_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) */
343  	static
344  	SCIP_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) */
362  	static
363  	SCIP_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 */
382  	static
383  	SCIP_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  	   {
401  	      SCIP_CALL( checkGlobalProperties(scip, heurdata) );
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 */
423  	      if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
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 */
450  	static
451  	SCIP_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 */
512  	   if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
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 */
524  	SCIP_RETCODE SCIPincludeHeurFarkasdiving(
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 */
535  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
536  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
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) */
550  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
551  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
552  	         DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, DIVESET_ISPUBLIC, DIVESET_DIVETYPES,
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  	}
581