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_conflictdiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that chooses fixings w.r.t. conflict locks
28   	 * @author Jakob Witzig
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heur_conflictdiving.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_var.h"
39   	#include "scip/scip_heur.h"
40   	#include "scip/scip_mem.h"
41   	#include "scip/scip_numerics.h"
42   	#include "scip/scip_param.h"
43   	#include "scip/scip_sol.h"
44   	#include "scip/scip_solvingstats.h"
45   	#include <string.h>
46   	
47   	#define HEUR_NAME                    "conflictdiving"
48   	#define HEUR_DESC                    "LP diving heuristic that chooses fixings w.r.t. conflict locks"
49   	#define HEUR_DISPCHAR                SCIP_HEURDISPCHAR_DIVING
50   	#define HEUR_PRIORITY                -1000100
51   	#define HEUR_FREQ                    10
52   	#define HEUR_FREQOFS                 0
53   	#define HEUR_MAXDEPTH                -1
54   	#define HEUR_TIMING                  SCIP_HEURTIMING_AFTERLPPLUNGE
55   	#define HEUR_USESSUBSCIP             FALSE  /**< does the heuristic use a secondary SCIP instance? */
56   	#define DIVESET_DIVETYPES            SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
57   	#define DIVESET_ISPUBLIC             FALSE  /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
58   	#define DEFAULT_RANDSEED             151 /**< default random seed */
59   	
60   	/*
61   	 * Default parameter settings
62   	 */
63   	
64   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
65   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
66   	#define DEFAULT_MAXLPITERQUOT      0.15 /**< maximal fraction of diving LP iterations compared to node LP iterations */
67   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
68   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
69   	                                         *   where diving is performed (0.0: no limit) */
70   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
71   	                                         *   where diving is performed (0.0: no limit) */
72   	#define DEFAULT_MAXDIVEUBQUOTNOSOL  0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
73   	#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
74   	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
75   	#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15/**< percentage of immediate domain changes during probing to trigger LP resolve */
76   	#define DEFAULT_LPSOLVEFREQ           0 /**< LP solve frequency for diving heuristics */
77   	#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
78   	                                         *   more general constraint handler diving variable selection? */
79   	#define DEFAULT_LOCKWEIGHT         0.75 /**< weight used in a convex combination of conflict and variable locks */
80   	#define DEFAULT_LIKECOEF          FALSE /**< perform rounding like coefficient diving */
81   	#define DEFAULT_MAXVIOL            TRUE /**< prefer rounding direction with most violation */
82   	#define DEFAULT_MINCONFLICTLOCKS      5 /**< threshold for penalizing the score */
83   	
84   	/* locally defined heuristic data */
85   	struct SCIP_HeurData
86   	{
87   	   SCIP_SOL*             sol;                /**< working solution */
88   	   SCIP_Real             lockweight;         /**< weight factor to combine conflict and variable locks */
89   	   SCIP_Bool             likecoefdiving;     /**< use the same rounding strategy like coefficent diving */
90   	   SCIP_Bool             maxviol;            /**< rounding into potentially infeasible direction */
91   	   int                   minconflictlocks;   /**< threshold for penalizing the score */
92   	};
93   	
94   	/*
95   	 * Callback methods
96   	 */
97   	
98   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
99   	static
100  	SCIP_DECL_HEURCOPY(heurCopyConflictdiving)
101  	{  /*lint --e{715}*/
102  	   assert(scip != NULL);
103  	   assert(heur != NULL);
104  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
105  	
106  	   /* call inclusion method of constraint handler */
107  	   SCIP_CALL( SCIPincludeHeurConflictdiving(scip) );
108  	
109  	   return SCIP_OKAY;
110  	}
111  	
112  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
113  	static
114  	SCIP_DECL_HEURFREE(heurFreeConflictdiving) /*lint --e{715}*/
115  	{  /*lint --e{715}*/
116  	   SCIP_HEURDATA* heurdata;
117  	
118  	   assert(heur != NULL);
119  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
120  	   assert(scip != NULL);
121  	
122  	   /* free heuristic data */
123  	   heurdata = SCIPheurGetData(heur);
124  	   assert(heurdata != NULL);
125  	
126  	   SCIPfreeBlockMemory(scip, &heurdata);
127  	   SCIPheurSetData(heur, NULL);
128  	
129  	   return SCIP_OKAY;
130  	}
131  	
132  	
133  	/** initialization method of primal heuristic (called after problem was transformed) */
134  	static
135  	SCIP_DECL_HEURINIT(heurInitConflictdiving) /*lint --e{715}*/
136  	{  /*lint --e{715}*/
137  	   SCIP_HEURDATA* heurdata;
138  	
139  	   assert(heur != NULL);
140  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
141  	
142  	   /* get heuristic data */
143  	   heurdata = SCIPheurGetData(heur);
144  	   assert(heurdata != NULL);
145  	
146  	   /* create working solution */
147  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
148  	
149  	   return SCIP_OKAY;
150  	}
151  	
152  	
153  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
154  	static
155  	SCIP_DECL_HEUREXIT(heurExitConflictdiving) /*lint --e{715}*/
156  	{  /*lint --e{715}*/
157  	   SCIP_HEURDATA* heurdata;
158  	
159  	   assert(heur != NULL);
160  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
161  	
162  	   /* get heuristic data */
163  	   heurdata = SCIPheurGetData(heur);
164  	   assert(heurdata != NULL);
165  	
166  	   /* free working solution */
167  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
168  	
169  	   return SCIP_OKAY;
170  	}
171  	
172  	/** execution method of primal heuristic */
173  	static
174  	SCIP_DECL_HEUREXEC(heurExecConflictdiving) /*lint --e{715}*/
175  	{  /*lint --e{715}*/
176  	   SCIP_HEURDATA* heurdata;
177  	   SCIP_DIVESET* diveset;
178  	
179  	   heurdata = SCIPheurGetData(heur);
180  	   assert(heurdata != NULL);
181  	
182  	   assert(SCIPheurGetNDivesets(heur) > 0);
183  	   assert(SCIPheurGetDivesets(heur) != NULL);
184  	   diveset = SCIPheurGetDivesets(heur)[0];
185  	   assert(diveset != NULL);
186  	
187  	   *result = SCIP_DELAYED;
188  	
189  	   /* don't run if no conflict constraints where found */
190  	   if( SCIPgetNConflictConssFound(scip) == 0 )
191  	      return SCIP_OKAY;
192  	
193  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
194  	
195  	   return SCIP_OKAY;
196  	}
197  	
198  	#define MIN_RAND 1e-06
199  	#define MAX_RAND 1e-05
200  	
201  	/** calculate score variant 1: use rounding strategy like coefficent diving */
202  	static
203  	SCIP_RETCODE getScoreLikeCoefdiving(
204  	   SCIP*                 scip,               /**< SCIP data structure */
205  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
206  	   SCIP_RANDNUMGEN*      rng,                /**< random number generator of the diveset */
207  	   SCIP_DIVETYPE         divetype,           /**< divetype of the heuristic */
208  	   SCIP_VAR*             cand,               /**< diving candidate */
209  	   SCIP_Real             candsol,            /**< diving candidate solution */
210  	   SCIP_Real             candsfrac,          /**< fractionality of the candidate solution */
211  	   SCIP_Real*            score,              /**< pointer to store the score */
212  	   SCIP_Bool*            roundup             /**< pointer to store whether the candidate should be rounded upwards */
213  	   )
214  	{
215  	   SCIP_Real upweight;
216  	   SCIP_Real downweight;
217  	   SCIP_Bool mayrounddown;
218  	   SCIP_Bool mayroundup;
219  	   int nconflictlocksdown;
220  	   int nconflictlocksup;
221  	   int nlocksdown;
222  	   int nlocksup;
223  	
224  	   /* get conflict locks */
225  	   nconflictlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_CONFLICT);
226  	   nconflictlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_CONFLICT);
227  	
228  	   /* get variable locks */
229  	   nlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL);
230  	   nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
231  	
232  	   /* combine conflict and variable locks */
233  	   upweight = heurdata->lockweight * nconflictlocksup +  (1.0 - heurdata->lockweight) * nlocksup;
234  	   downweight = heurdata->lockweight * nconflictlocksdown + (1.0 - heurdata->lockweight) * nlocksdown;
235  	
236  	   /* check whether there exists a direction w/o any locks */
237  	   mayrounddown = SCIPisZero(scip, upweight);
238  	   mayroundup = SCIPisZero(scip, downweight);
239  	
240  	   if( mayrounddown || mayroundup )
241  	   {
242  	      /* choose rounding direction:
243  	       * - if variable may be rounded in both directions, round corresponding to the fractionality
244  	       * - otherwise, round in the infeasible direction
245  	       */
246  	      if( mayrounddown && mayroundup )
247  	      {
248  	         assert(divetype != SCIP_DIVETYPE_SOS1VARIABLE || heurdata->lockweight > 0);
249  	
250  	         /* try to avoid variability; decide randomly if the LP solution can contain some noise */
251  	         if( SCIPisEQ(scip, candsfrac, 0.5) )
252  	            *roundup = (SCIPrandomGetInt(rng, 0, 1) == 0);
253  	         else
254  	            *roundup = (candsfrac > 0.5);
255  	      }
256  	      else
257  	         *roundup = mayrounddown;
258  	   }
259  	   else
260  	   {
261  	      /* the candidate may not be rounded */
262  	      *roundup = (SCIPisGT(scip, downweight, upweight) || (SCIPisEQ(scip, downweight, upweight) && candsfrac > 0.5));
263  	   }
264  	
265  	   if( *roundup )
266  	   {
267  	      switch( divetype )
268  	      {
269  	         case SCIP_DIVETYPE_INTEGRALITY:
270  	            candsfrac = 1.0 - candsfrac;
271  	            break;
272  	         case SCIP_DIVETYPE_SOS1VARIABLE:
273  	            if( SCIPisFeasPositive(scip, candsol) )
274  	               candsfrac = 1.0 - candsfrac;
275  	            break;
276  	         default:
277  	            SCIPerrorMessage("Error: Unsupported diving type\n");
278  	            SCIPABORT();
279  	            return SCIP_INVALIDDATA; /*lint !e527*/
280  	      } /*lint !e788*/
281  	
282  	      /* add some noise to avoid ties */
283  	      *score = upweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
284  	   }
285  	   else
286  	   {
287  	      if( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
288  	         candsfrac = 1.0 - candsfrac;
289  	
290  	      /* add some noise to avoid ties */
291  	      *score = downweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
292  	   }
293  	
294  	   /* penalize too small fractions */
295  	   if( SCIPisEQ(scip, candsfrac, 0.01) )
296  	   {
297  	      /* try to avoid variability; decide randomly if the LP solution can contain some noise.
298  	       * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score
299  	       */
300  	      if( SCIPrandomGetInt(rng, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
301  	         (*score) *= 0.01;
302  	   }
303  	   else if( candsfrac < 0.01 )
304  	      (*score) *= 0.1;
305  	
306  	   /* prefer decisions on binary variables */
307  	   if( !SCIPvarIsBinary(cand) )
308  	      *score = -1.0 / *score;
309  	
310  	   return SCIP_OKAY;
311  	}
312  	
313  	/** calculate score variant 2: use a rounding strategy that tends towards infeasibility */
314  	static
315  	SCIP_RETCODE getScore(
316  	   SCIP*                 scip,               /**< SCIP data structure */
317  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
318  	   SCIP_RANDNUMGEN*      rng,                /**< random number generator of the diveset */
319  	   SCIP_DIVETYPE         divetype,           /**< divetype of the heuristic */
320  	   SCIP_VAR*             cand,               /**< diving candidate */
321  	   SCIP_Real             candsol,            /**< diving candidate solution */
322  	   SCIP_Real             candsfrac,          /**< fractionality of the candidate solution */
323  	   SCIP_Real*            score,              /**< pointer to store the score */
324  	   SCIP_Bool*            roundup             /**< pointer to store whether the candidate should be rounded upwards */
325  	   )
326  	{
327  	   SCIP_Real conflictlocksum;
328  	   SCIP_Real upweight;
329  	   SCIP_Real downweight;
330  	   SCIP_Bool mayrounddown;
331  	   SCIP_Bool mayroundup;
332  	   int nlocksup;
333  	   int nlocksdown;
334  	   int nconflictlocksup;
335  	   int nconflictlocksdown;
336  	
337  	   assert(scip != NULL);
338  	   assert(heurdata != NULL);
339  	   assert(rng != NULL);
340  	
341  	   /* get conflict locks */
342  	   nconflictlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_CONFLICT);
343  	   nconflictlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_CONFLICT);
344  	   conflictlocksum = nconflictlocksup + nconflictlocksdown;
345  	
346  	   /* get variable locks */
347  	   nlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL);
348  	   nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
349  	
350  	   /* combine conflict and variable locks */
351  	   upweight = heurdata->lockweight * nconflictlocksup +  (1.0 - heurdata->lockweight) * nlocksup;
352  	   downweight = heurdata->lockweight * nconflictlocksdown + (1.0 - heurdata->lockweight) * nlocksdown;
353  	
354  	   /* check whether there exists a rounding direction w/o any locks */
355  	   mayrounddown = SCIPisZero(scip, upweight);
356  	   mayroundup = SCIPisZero(scip, downweight);
357  	
358  	   /* variable can be rounded in exactly one direction and we try to go into the feasible direction */
359  	   if( mayrounddown || mayroundup )
360  	   {
361  	      /* choose rounding direction:
362  	       * - if variable may be rounded in both directions, round corresponding to the fractionality
363  	       * - otherwise, round in the feasible direction
364  	       */
365  	      if( mayrounddown && mayroundup )
366  	      {
367  	         assert(divetype != SCIP_DIVETYPE_SOS1VARIABLE || heurdata->lockweight > 0);
368  	
369  	         /* try to avoid variability; decide randomly if the LP solution can contain some noise */
370  	         if( SCIPisEQ(scip, candsfrac, 0.5) )
371  	            *roundup = (SCIPrandomGetInt(rng, 0, 1) == 0);
372  	         else
373  	            *roundup = (candsfrac > 0.5);
374  	      }
375  	      else
376  	         *roundup = mayroundup;
377  	   }
378  	   else
379  	   {
380  	      assert(!mayrounddown);
381  	
382  	      /* both rounding directions have a different amount of locks */
383  	      if( !SCIPisEQ(scip, upweight, downweight) )
384  	      {
385  	         *roundup = (heurdata->maxviol ? SCIPisGT(scip, upweight, downweight) : SCIPisLT(scip, upweight, downweight));
386  	      }
387  	      /* break ties with lp fractionality != 0.5 */
388  	      else if( !SCIPisEQ(scip, candsfrac, 0.5) )
389  	      {
390  	         *roundup = (candsfrac > 0.5);
391  	      }
392  	      /* break tie randomly */
393  	      else
394  	      {
395  	         *roundup = (SCIPrandomGetInt(rng, 0, 1) == 1);
396  	      }
397  	   }
398  	
399  	   if( *roundup )
400  	   {
401  	      switch( divetype )
402  	      {
403  	         case SCIP_DIVETYPE_INTEGRALITY:
404  	            candsfrac = 1.0 - candsfrac;
405  	            break;
406  	         case SCIP_DIVETYPE_SOS1VARIABLE:
407  	            if( SCIPisFeasPositive(scip, candsol) )
408  	               candsfrac = 1.0 - candsfrac;
409  	            break;
410  	         default:
411  	            SCIPerrorMessage("Error: Unsupported diving type\n");
412  	            SCIPABORT();
413  	            return SCIP_INVALIDDATA; /*lint !e527*/
414  	      } /*lint !e788*/
415  	
416  	      /* add some noise to avoid ties */
417  	      *score = upweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
418  	   }
419  	   else
420  	   {
421  	      if( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
422  	         candsfrac = 1.0 - candsfrac;
423  	
424  	      /* add some noise to avoid ties */
425  	      *score = downweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
426  	   }
427  	
428  	   /* penalize too few conflict locks */
429  	   if( conflictlocksum > 0 && conflictlocksum < heurdata->minconflictlocks )
430  	      (*score) *= 0.1;
431  	
432  	   /* penalize if no conflict locks exist at all */
433  	   if( conflictlocksum == 0 )
434  	      (*score) *= 0.01;
435  	
436  	   /* penalize too small fractions */
437  	   if( SCIPisEQ(scip, candsfrac, 0.01) )
438  	   {
439  	      /* try to avoid variability; decide randomly if the LP solution can contain some noise.
440  	       * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score
441  	       */
442  	      if( SCIPrandomGetInt(rng, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
443  	         (*score) *= 0.01;
444  	   }
445  	   else if( candsfrac < 0.01 )
446  	      (*score) *= 0.01;
447  	
448  	   /* prefer decisions on binary variables */
449  	   if( !SCIPvarIsBinary(cand) )
450  	      *score = -1.0 / *score;
451  	
452  	   return SCIP_OKAY;
453  	}
454  	
455  	
456  	/** returns a score for the given candidate -- the best candidate maximizes the diving score */
457  	static
458  	SCIP_DECL_DIVESETGETSCORE(divesetGetScoreConflictdiving)
459  	{
460  	   SCIP_HEUR* heur;
461  	   SCIP_HEURDATA* heurdata;
462  	   SCIP_RANDNUMGEN* rng;
463  	
464  	   rng = SCIPdivesetGetRandnumgen(diveset);
465  	   assert(rng != NULL);
466  	
467  	   heur = SCIPdivesetGetHeur(diveset);
468  	   assert(heur != NULL);
469  	
470  	   heurdata = SCIPheurGetData(heur);
471  	   assert(heurdata != NULL);
472  	
473  	   if( heurdata->likecoefdiving )
474  	   {
475  	      SCIP_CALL( getScoreLikeCoefdiving(scip, heurdata, rng, divetype, cand, candsol, candsfrac, score, roundup) );
476  	   }
477  	   else
478  	   {
479  	      SCIP_CALL( getScore(scip, heurdata, rng, divetype, cand, candsol, candsfrac, score, roundup) );
480  	   }
481  	
482  	   /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
483  	   assert( (0.0 < candsfrac && candsfrac < 1.0) || SCIPvarIsBinary(cand) || divetype == SCIP_DIVETYPE_SOS1VARIABLE );
484  	
485  	   return SCIP_OKAY;
486  	}
487  	
488  	/*
489  	 * heuristic specific interface methods
490  	 */
491  	
492  	#define divesetAvailableConflictdiving NULL
493  	
494  	/** creates the conflictdiving heuristic and includes it in SCIP */
495  	SCIP_RETCODE SCIPincludeHeurConflictdiving(
496  	   SCIP*                 scip                /**< SCIP data structure */
497  	   )
498  	{
499  	   SCIP_HEURDATA* heurdata;
500  	   SCIP_HEUR* heur;
501  	
502  	   /* create conflictdiving primal heuristic data */
503  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
504  	
505  	   /* include primal heuristic */
506  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ,
507  	         HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecConflictdiving, heurdata) );
508  	
509  	   assert(heur != NULL);
510  	
511  	   /* set non-NULL pointers to callback methods */
512  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyConflictdiving) );
513  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeConflictdiving) );
514  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitConflictdiving) );
515  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitConflictdiving) );
516  	
517  	   /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
518  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
519  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
520  	         DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
521  	         DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreConflictdiving, divesetAvailableConflictdiving) );
522  	
523  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/maxviol", "try to maximize the violation",
524  	         &heurdata->maxviol, TRUE, DEFAULT_MAXVIOL, NULL, NULL) );
525  	
526  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/likecoef",
527  	         "perform rounding like coefficient diving",
528  	         &heurdata->likecoefdiving, TRUE, DEFAULT_LIKECOEF, NULL, NULL) );
529  	
530  	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minconflictlocks",
531  	         "minimal number of conflict locks per variable",
532  	         &heurdata->minconflictlocks, TRUE, DEFAULT_MINCONFLICTLOCKS, 0, INT_MAX, NULL, NULL) );
533  	
534  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lockweight",
535  	         "weight used in a convex combination of conflict and variable locks",
536  	         &heurdata->lockweight, TRUE, DEFAULT_LOCKWEIGHT, 0.0, 1.0, NULL, NULL) );
537  	
538  	   return SCIP_OKAY;
539  	}
540