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_locks.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  rounding locks primal heuristic
28   	 * @author Michael Winkler
29   	 * @author Gerald Gamrath
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/heur_locks.h"
36   	#include "scip/pub_cons.h"
37   	#include "scip/pub_heur.h"
38   	#include "scip/pub_lp.h"
39   	#include "scip/pub_message.h"
40   	#include "scip/pub_misc.h"
41   	#include "scip/pub_var.h"
42   	#include "scip/scip_branch.h"
43   	#include "scip/scip_cons.h"
44   	#include "scip/scip_copy.h"
45   	#include "scip/scip_general.h"
46   	#include "scip/scip_heur.h"
47   	#include "scip/scip_lp.h"
48   	#include "scip/scip_mem.h"
49   	#include "scip/scip_message.h"
50   	#include "scip/scip_numerics.h"
51   	#include "scip/scip_param.h"
52   	#include "scip/scip_prob.h"
53   	#include "scip/scip_probing.h"
54   	#include "scip/scip_randnumgen.h"
55   	#include "scip/scip_sol.h"
56   	#include "scip/scip_solve.h"
57   	#include "scip/scip_solvingstats.h"
58   	#include "scip/scip_timing.h"
59   	#include "scip/scip_tree.h"
60   	#include <string.h>
61   	
62   	#define HEUR_NAME             "locks"
63   	#define HEUR_DESC             "heuristic that fixes variables based on their rounding locks"
64   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
65   	#define HEUR_PRIORITY         3000
66   	#define HEUR_FREQ             0
67   	#define HEUR_FREQOFS          0
68   	#define HEUR_MAXDEPTH         -1
69   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE
70   	#define HEUR_USESSUBSCIP      TRUE           /**< does the heuristic use a secondary SCIP instance? */
71   	
72   	#define DEFAULT_MAXNODES      5000LL         /**< maximum number of nodes to regard in the subproblem */
73   	#define DEFAULT_ROUNDUPPROBABILITY 0.67      /**< probability for rounding a variable up in case of ties */
74   	#define DEFAULT_MINFIXINGRATE 0.65           /**< minimum percentage of variables that have to be fixed */
75   	#define DEFAULT_MINIMPROVE    0.01           /**< factor by which locks heuristic should at least improve the
76   	                                              *   incumbent */
77   	#define DEFAULT_MINNODES      500LL          /**< minimum number of nodes to regard in the subproblem */
78   	#define DEFAULT_NODESOFS      500LL          /**< number of nodes added to the contingent of the total nodes */
79   	#define DEFAULT_NODESQUOT     0.1            /**< subproblem nodes in relation to nodes of the original problem */
80   	#define DEFAULT_MAXPROPROUNDS 2              /**< maximum number of propagation rounds during probing */
81   	#define DEFAULT_UPDATELOCKS   TRUE           /**< should the locks be updated based on LP rows? */
82   	#define DEFAULT_COPYCUTS      TRUE           /**< should all active cuts from the cutpool of the
83   	                                              *   original scip be copied to constraints of the subscip? */
84   	#define DEFAULT_USEFINALSUBMIP TRUE          /**< should a final sub-MIP be solved to construct a feasible
85   	                                              *   solution if the LP was not roundable? */
86   	#define DEFAULT_RANDSEED      73             /**< initial random seed */
87   	#define DEFAULT_MINFIXINGRATELP 0.0          /**< minimum fixing rate over all variables (including continuous)
88   	                                              *   to solve LP */
89   	
90   	/** primal heuristic data */
91   	struct SCIP_HeurData
92   	{
93   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generation */
94   	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem */
95   	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem */
96   	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes */
97   	   SCIP_Longint          usednodes;          /**< nodes already used by locks heuristic in earlier calls */
98   	   SCIP_Real             roundupprobability; /**< probability for rounding a variable up in case of ties */
99   	   SCIP_Real             minfixingrate;      /**< minimum percentage of variables that have to be fixed */
100  	   SCIP_Real             minfixingratelp;    /**< minimum fixing rate over all variables (including continuous) to solve LP */
101  	   SCIP_Real             minimprove;         /**< factor by which locks heuristic should at least improve the incumbent */
102  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
103  	   int                   maxproprounds;      /**< maximum number of propagation rounds during probing */
104  	   SCIP_Bool             updatelocks;        /**< should the locks be updated based on LP rows? */
105  	   SCIP_Bool             copycuts;           /**< should all active cuts from cutpool be copied to constraints in
106  	                                              *   the subproblem? */
107  	   SCIP_Bool             usefinalsubmip;     /**< should a final sub-MIP be solved to construct a feasible solution if
108  	                                              *   the LP was not roundable? */
109  	};
110  	
111  	/*
112  	 * Local methods
113  	 */
114  	
115  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
116  	static
117  	SCIP_DECL_HEURCOPY(heurCopyLocks)
118  	{  /*lint --e{715}*/
119  	   assert(scip != NULL);
120  	   assert(heur != NULL);
121  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
122  	
123  	   /* call inclusion method of primal heuristic */
124  	   SCIP_CALL( SCIPincludeHeurLocks(scip) );
125  	
126  	   return SCIP_OKAY;
127  	}
128  	
129  	/** free method for primal heuristic plugins (called when SCIP is exiting) */
130  	static
131  	SCIP_DECL_HEURFREE(heurFreeLocks)
132  	{  /*lint --e{715}*/
133  	   SCIP_HEURDATA* heurdata;
134  	
135  	   assert(scip != NULL);
136  	   assert(heur != NULL);
137  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
138  	
139  	   heurdata = SCIPheurGetData(heur);
140  	
141  	    /* free primal heuristic data */
142  	   SCIPfreeBlockMemory(scip, &heurdata);
143  	
144  	   return SCIP_OKAY;
145  	}
146  	
147  	/** initialization method of primal heuristic (called after problem was transformed) */
148  	static
149  	SCIP_DECL_HEURINIT(heurInitLocks) /*lint --e{715}*/
150  	{  /*lint --e{715}*/
151  	   SCIP_HEURDATA* heurdata;
152  	
153  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
154  	   heurdata = SCIPheurGetData(heur);
155  	   assert(heurdata != NULL);
156  	
157  	   /* initialize data */
158  	   heurdata->usednodes = 0;
159  	
160  	   /* create random number generator */
161  	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
162  	         DEFAULT_RANDSEED, TRUE) );
163  	
164  	   return SCIP_OKAY;
165  	}
166  	
167  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
168  	static
169  	SCIP_DECL_HEUREXIT(heurExitLocks) /*lint --e{715}*/
170  	{  /*lint --e{715}*/
171  	   SCIP_HEURDATA* heurdata;
172  	
173  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
174  	
175  	   /* free heuristic data */
176  	   heurdata = SCIPheurGetData(heur);
177  	   assert(heurdata != NULL);
178  	
179  	   /* free random number generator */
180  	   SCIPfreeRandom(scip, &heurdata->randnumgen);
181  	
182  	   return SCIP_OKAY;
183  	}
184  	
185  	#define heurInitsolLocks NULL
186  	#define heurExitsolLocks NULL
187  	
188  	/** apply fix-and-propagate scheme based on variable locks
189  	 *
190  	 *  @note probing mode of SCIP needs to be enabled before
191  	 */
192  	SCIP_RETCODE SCIPapplyLockFixings(
193  	   SCIP*                 scip,               /**< SCIP data structure */
194  	   SCIP_HEURDATA*        heurdata,           /**< primal heuristic data */
195  	   SCIP_Bool*            cutoff,             /**< pointer to store if a cutoff was detected */
196  	   SCIP_Bool*            allrowsfulfilled    /**< pointer to store if all rows became redundant */
197  	   )
198  	{
199  	   SCIP_ROW** lprows;
200  	   SCIP_VAR** vars;
201  	   SCIP_VAR** sortvars;
202  	   SCIP_Real* minact;
203  	   SCIP_Real* maxact;
204  	   SCIP_Bool* fulfilled;
205  	   SCIP_VAR* var;
206  	   SCIP_ROW* row;
207  	   SCIP_COL* col;
208  	   SCIP_ROW** colrows;
209  	   SCIP_Real* colvals;
210  	   int ncolrows;
211  	   int* ndownlocks;
212  	   int* nuplocks;
213  	   int* varpos = NULL;
214  	   SCIP_Real lastfixval;
215  	   SCIP_Real randnumber;
216  	   SCIP_Real roundupprobability;
217  	   SCIP_Bool propagate;
218  	   SCIP_Bool propagated;
219  	   SCIP_Bool haslhs;
220  	   SCIP_Bool hasrhs;
221  	   SCIP_Bool updatelocks;
222  	   int lastfixlocks;
223  	   int maxproprounds;
224  	   int nglbfulfilledrows;
225  	   int rowpos;
226  	   int nbinvars;
227  	   int nvars;
228  	   int nlprows;
229  	   int nfulfilledrows;
230  	   int bestpos;
231  	   int lastbestscore;
232  	   int bestscore;
233  	   int score;
234  	   int v;
235  	   int r;
236  	   int i;
237  	
238  	   assert(scip != NULL);
239  	   assert(cutoff != NULL);
240  	   assert(allrowsfulfilled != NULL);
241  	   assert(SCIPinProbing(scip));
242  	
243  	   if( heurdata == NULL )
244  	   {
245  	      SCIP_HEUR* heur = SCIPfindHeur(scip, HEUR_NAME);
246  	      heurdata = SCIPheurGetData(heur);
247  	   }
248  	   assert(heurdata != NULL);
249  	
250  	   *cutoff = FALSE;
251  	   *allrowsfulfilled = FALSE;
252  	
253  	   propagate = (heurdata->maxproprounds != 0);
254  	
255  	   if( heurdata->maxproprounds == -2 )
256  	      maxproprounds = 0;
257  	   else
258  	      maxproprounds = heurdata->maxproprounds;
259  	
260  	   roundupprobability = heurdata->roundupprobability;
261  	
262  	   updatelocks = heurdata->updatelocks && (SCIPgetNCheckConss(scip) == SCIPgetNLPRows(scip));
263  	
264  	   SCIPdebugMsg(scip, "%d constraints: %d logicor, updatelocks=%u\n", SCIPgetNConss(scip), SCIPconshdlrGetNCheckConss(SCIPfindConshdlr(scip, "logicor")), updatelocks);
265  	
266  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
267  	   assert(vars != NULL);
268  	
269  	   /* allocate memory */
270  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &sortvars, vars, nbinvars) );
271  	   SCIP_CALL( SCIPallocBufferArray(scip, &nuplocks, nbinvars) );
272  	   SCIP_CALL( SCIPallocBufferArray(scip, &ndownlocks, nbinvars) );
273  	
274  	   /* get LP data */
275  	   SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
276  	   SCIP_CALL( SCIPallocBufferArray(scip, &minact, nlprows) );
277  	   SCIP_CALL( SCIPallocBufferArray(scip, &maxact, nlprows) );
278  	   SCIP_CALL( SCIPallocClearBufferArray(scip, &fulfilled, nlprows) );
279  	
280  	   /* @todo add objective value as second sorting criteria */
281  	
282  	   nglbfulfilledrows = 0;
283  	
284  	   /* get locks of variables */
285  	   for( v = 0; v < nbinvars; ++v )
286  	   {
287  	      var = sortvars[v];
288  	      nuplocks[v] = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
289  	      ndownlocks[v] = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
290  	   }
291  	
292  	   /* get activities of rows */
293  	   for( r = 0; r < nlprows; ++r )
294  	   {
295  	      row = lprows[r];
296  	      assert(SCIProwGetLPPos(row) == r);
297  	
298  	      /* no trivial rows */
299  	      assert(!SCIPisInfinity(scip, -SCIProwGetLhs(row)) || !SCIPisInfinity(scip, SCIProwGetRhs(row)));
300  	
301  	      minact[r] = SCIPgetRowMinActivity(scip, row);
302  	      maxact[r] = SCIPgetRowMaxActivity(scip, row);
303  	   }
304  	
305  	   propagated = TRUE;
306  	   lastbestscore = INT_MAX;
307  	
308  	   /* fix variables */
309  	   for( v = 0; v < nbinvars; v++ )
310  	   {
311  	      if( SCIPisStopped(scip) )
312  	         break;
313  	
314  	      assert(!(*cutoff));
315  	
316  	      nfulfilledrows = 0;
317  	
318  	      while( v < nbinvars && (SCIPvarGetLbLocal(sortvars[v]) > 0.5 || SCIPvarGetUbLocal(sortvars[v]) < 0.5) )
319  	      {
320  	         ++v;
321  	      }
322  	      if( v == nbinvars )
323  	         break;
324  	
325  	      bestpos = v;
326  	      bestscore = nuplocks[v] + ndownlocks[v];
327  	
328  	      /* get best variable */
329  	      if( bestscore < lastbestscore )
330  	      {
331  	         for( i = v + 1; i < nbinvars; ++i )
332  	         {
333  	            var = sortvars[i];
334  	
335  	            /* variable is already fixed; move it to the front and increment v to ignore it */
336  	            if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
337  	            {
338  	               int locks;
339  	
340  	               sortvars[i] = sortvars[v];
341  	               sortvars[v] = var;
342  	
343  	               locks = nuplocks[i];
344  	               nuplocks[i] = nuplocks[v];
345  	               nuplocks[v] = locks;
346  	
347  	               locks = ndownlocks[i];
348  	               ndownlocks[i] = ndownlocks[v];
349  	               ndownlocks[v] = locks;
350  	
351  	               if( varpos != NULL )
352  	               {
353  	                  varpos[SCIPvarGetProbindex(sortvars[i])] = i;
354  	                  varpos[SCIPvarGetProbindex(sortvars[v])] = v;
355  	               }
356  	
357  	               if( bestpos == v )
358  	                  bestpos = i;
359  	
360  	               ++v;
361  	
362  	               continue;
363  	            }
364  	
365  	            score = nuplocks[i] + ndownlocks[i];
366  	            assert(score <= lastbestscore);
367  	
368  	            if( score > bestscore )
369  	            {
370  	               bestscore = score;
371  	               bestpos = i;
372  	
373  	               if( bestscore == lastbestscore )
374  	                  break;
375  	            }
376  	         }
377  	         if( v == nbinvars )
378  	            break;
379  	      }
380  	      lastbestscore = bestscore;
381  	
382  	      /* move best variable to the front (at position v) */
383  	      if( bestpos != v )
384  	      {
385  	         int locks;
386  	
387  	         var = sortvars[bestpos];
388  	         sortvars[bestpos] = sortvars[v];
389  	         sortvars[v] = var;
390  	
391  	         locks = nuplocks[bestpos];
392  	         nuplocks[bestpos] = nuplocks[v];
393  	         nuplocks[v] = locks;
394  	
395  	         locks = ndownlocks[bestpos];
396  	         ndownlocks[bestpos] = ndownlocks[v];
397  	         ndownlocks[v] = locks;
398  	
399  	         if( varpos != NULL )
400  	         {
401  	            varpos[SCIPvarGetProbindex(sortvars[bestpos])] = bestpos;
402  	            varpos[SCIPvarGetProbindex(sortvars[v])] = v;
403  	         }
404  	      }
405  	
406  	      var = sortvars[v];
407  	
408  	      /* all remaining variables are fixed, we can break the fix-and-propagate loop */
409  	      if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
410  	      {
411  	         assert(v == nbinvars);
412  	
413  	         break;
414  	      }
415  	
416  	      /* stop if we reached the depth limit */
417  	      if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) )
418  	         break;
419  	
420  	      if( propagated )
421  	      {
422  	         SCIP_CALL( SCIPnewProbingNode(scip) );
423  	         propagated = FALSE;
424  	      }
425  	
426  	      /* set variables to the bound with fewer locks, if tie choose an average value */
427  	      if( ndownlocks[v] > nuplocks[v] )
428  	         lastfixval = 1.0;
429  	      else if( ndownlocks[v] < nuplocks[v] )
430  	         lastfixval = 0.0;
431  	      else
432  	      {
433  	         /* prefer one-fixing if objective value is not positive */
434  	         if( !SCIPisPositive(scip, SCIPvarGetObj(var)) )
435  	            lastfixval = 1.0;
436  	         else
437  	         {
438  	            randnumber = SCIPrandomGetReal(heurdata->randnumgen, 0.0, 1.0);
439  	
440  	            /* if a tie occurs, we randomly round the variable based on the parameter 'roundupprobability' */
441  	            if( randnumber < roundupprobability )
442  	               lastfixval = 1.0;
443  	            else
444  	               lastfixval = 0.0;
445  	         }
446  	      }
447  	
448  	      lastfixlocks = lastfixval > 0.5 ? nuplocks[v] : ndownlocks[v];
449  	
450  	      SCIP_CALL( SCIPfixVarProbing(scip, var, lastfixval) );
451  	
452  	      SCIPdebugMsg(scip, "iteration %d: fixing variable <%s> to %d with locks (%d, %d)\n", v, SCIPvarGetName(var), lastfixval > 0.5 ? 1 : 0, ndownlocks[v], nuplocks[v]);
453  	
454  	      if( propagate && lastfixlocks > 0 )
455  	      {
456  	         /* apply propagation */
457  	         SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
458  	         propagated = TRUE;
459  	
460  	         if( *cutoff )
461  	         {
462  	            SCIPdebugMsg(scip, "last fixing led to infeasibility trying other bound\n");
463  	
464  	            /* fix cutoff variable in other direction */
465  	            SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) );
466  	            *cutoff = FALSE;
467  	
468  	            if( lastfixval < 0.5 )
469  	            {
470  	               lastfixval = 1.0;
471  	
472  	               if( SCIPvarGetUbLocal(var) > 0.5 )
473  	               {
474  	                  SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) );
475  	               }
476  	               /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
477  	                * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
478  	                * after backtracking; in that case, we ran into a deadend and stop
479  	                */
480  	               else
481  	                  *cutoff = TRUE;
482  	            }
483  	            else
484  	            {
485  	               lastfixval = 0.0;
486  	
487  	               if( SCIPvarGetLbLocal(var) < 0.5 )
488  	               {
489  	                  SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
490  	               }
491  	               /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a
492  	                * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing
493  	                * after backtracking; in that case, we ran into a deadend and stop
494  	                */
495  	               else
496  	                  *cutoff = TRUE;
497  	            }
498  	
499  	            if( !(*cutoff) )
500  	            {
501  	               SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
502  	            }
503  	            if( *cutoff )
504  	            {
505  	               SCIPdebugMsg(scip, "probing was infeasible\n");
506  	
507  	               break;
508  	            }
509  	         }
510  	         /* @todo collect propagated bounds and use them to update row activities as well */
511  	      }
512  	
513  	      if( updatelocks )
514  	      {
515  	         if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
516  	            continue;
517  	
518  	         col = SCIPvarGetCol(var);
519  	         assert(col != NULL);
520  	
521  	         colrows = SCIPcolGetRows(col);
522  	         colvals = SCIPcolGetVals(col);
523  	         ncolrows = SCIPcolGetNNonz(col);
524  	
525  	         /* update activities */
526  	         for( r = 0; r < ncolrows; ++r )
527  	         {
528  	            row = colrows[r];
529  	            rowpos = SCIProwGetLPPos(row);
530  	
531  	            /* the row is not in the LP */
532  	            if( rowpos == -1 )
533  	               continue;
534  	
535  	            assert(lprows[rowpos] == row);
536  	
537  	            /* we disregard cuts */
538  	            if( SCIProwGetRank(row) > 0 )
539  	               continue;
540  	
541  	            /* the row is already fulfilled */
542  	            if( fulfilled[rowpos] )
543  	               continue;
544  	
545  	            haslhs = !SCIPisInfinity(scip, -SCIProwGetLhs(row));
546  	            hasrhs = !SCIPisInfinity(scip, SCIProwGetRhs(row));
547  	
548  	            /* no trivial rows */
549  	            assert(hasrhs || haslhs);
550  	
551  	            if( ((colvals[r] > 0) == (lastfixval < 0.5)) )
552  	            {
553  	               maxact[rowpos] -= REALABS(colvals[r]);
554  	            }
555  	            if( ((colvals[r] > 0) == (lastfixval > 0.5)) )
556  	            {
557  	               minact[rowpos] += REALABS(colvals[r]);
558  	            }
559  	
560  	            /* check if the row cannot be violated anymore */
561  	            if( (!haslhs || SCIPisFeasGE(scip, minact[rowpos], SCIProwGetLhs(row)))
562  	               && (!hasrhs || SCIPisFeasLE(scip, maxact[rowpos], SCIProwGetRhs(row))) )
563  	            {
564  	               SCIP_COL** cols;
565  	               SCIP_VAR* colvar;
566  	               SCIP_Real* vals;
567  	               int ncols;
568  	               int pos;
569  	               int w;
570  	
571  	               SCIPdebugMsg(scip, "Row <%s> has activity [%g, %g], lhs=%g, rhs=%g\n", SCIProwGetName(row), minact[rowpos], maxact[rowpos], SCIProwGetLhs(row), SCIProwGetRhs(row));
572  	               SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
573  	
574  	               if( varpos == NULL )
575  	               {
576  	                  SCIP_CALL( SCIPallocBufferArray(scip, &varpos, nbinvars) );
577  	
578  	                  for( pos = 0; pos < nbinvars; ++pos )
579  	                     varpos[SCIPvarGetProbindex(sortvars[pos])] = pos;
580  	               }
581  	
582  	               ++nfulfilledrows;
583  	               fulfilled[rowpos] = TRUE;
584  	               cols = SCIProwGetCols(row);
585  	               vals = SCIProwGetVals(row);
586  	               ncols = SCIProwGetNNonz(row);
587  	
588  	               /* we assume that all rows are locking the variables */
589  	               for( w = ncols - 1; w >= 0; --w  )
590  	               {
591  	                  colvar = SCIPcolGetVar(cols[w]);
592  	                  if( SCIPvarGetType(colvar) == SCIP_VARTYPE_BINARY && colvar != var )
593  	                  {
594  	                     assert(sortvars[varpos[SCIPvarGetProbindex(colvar)]] == colvar);
595  	                     pos = varpos[SCIPvarGetProbindex(colvar)];
596  	
597  	                     if( haslhs )
598  	                     {
599  	                        if( vals[w] > 0.0 )
600  	                           --(ndownlocks[pos]);
601  	                        else
602  	                           --(nuplocks[pos]);
603  	                     }
604  	                     if( hasrhs )
605  	                     {
606  	                        if( vals[w] > 0.0 )
607  	                           --(nuplocks[pos]);
608  	                        else
609  	                           --(ndownlocks[pos]);
610  	                     }
611  	                  }
612  	               }
613  	
614  	               continue;
615  	            }
616  	            else if( SCIPisFeasLT(scip, maxact[rowpos], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, minact[rowpos], SCIProwGetRhs(row)) )
617  	            {
618  	               *cutoff = TRUE;
619  	               break;
620  	            }
621  	         }
622  	
623  	         if( *cutoff )
624  	         {
625  	            SCIPdebugMsg(scip, "found infeasible row, stopping heur\n");
626  	            break;
627  	         }
628  	
629  	         nglbfulfilledrows += nfulfilledrows;
630  	         SCIPdebugMsg(scip, "last fixing led to %d fulfilled rows, now %d of %d rows are fulfilled\n", nfulfilledrows, nglbfulfilledrows, nlprows);
631  	
632  	         if( nglbfulfilledrows == nlprows )
633  	         {
634  	            *allrowsfulfilled = TRUE;
635  	            break;
636  	         }
637  	      }
638  	   } /*lint --e{850}*/
639  	
640  	   SCIPfreeBufferArrayNull(scip, &varpos);
641  	   SCIPfreeBufferArray(scip, &fulfilled);
642  	   SCIPfreeBufferArray(scip, &maxact);
643  	   SCIPfreeBufferArray(scip, &minact);
644  	   SCIPfreeBufferArray(scip, &ndownlocks);
645  	   SCIPfreeBufferArray(scip, &nuplocks);
646  	   SCIPfreeBufferArray(scip, &sortvars);
647  	
648  	   return SCIP_OKAY;
649  	}
650  	
651  	
652  	
653  	
654  	/** execution method of primal heuristic */
655  	static
656  	SCIP_DECL_HEUREXEC(heurExecLocks)
657  	{  /*lint --e{715}*/
658  	   SCIP_HEURDATA* heurdata;
659  	   SCIP_VAR** vars;
660  	   SCIP_LPSOLSTAT lpstatus = SCIP_LPSOLSTAT_ERROR;
661  	   SCIP_Real lowerbound;
662  	   SCIP_Bool cutoff;
663  	   SCIP_Bool lperror;
664  	   SCIP_Bool allrowsfulfilled = FALSE;
665  	#ifdef NOCONFLICT
666  	   SCIP_Bool enabledconflicts;
667  	#endif
668  	   int oldnpscands;
669  	   int npscands;
670  	
671  	   int nvars;
672  	   int i;
673  	
674  	   *result = SCIP_DIDNOTRUN;
675  	
676  	   /* only run once */
677  	   if( SCIPgetNRuns(scip) > 1 )
678  	      return SCIP_OKAY;
679  	
680  	   if( SCIPgetNBinVars(scip) == 0 )
681  	      return SCIP_OKAY;
682  	
683  	   /* only run if we are allowed to solve an LP at the current node in the tree */
684  	   if( !SCIPhasCurrentNodeLP(scip) )
685  	      return SCIP_OKAY;
686  	
687  	   if( !SCIPisLPConstructed(scip) )
688  	   {
689  	      SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
690  	
691  	      /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
692  	      if( cutoff )
693  	      {
694  	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
695  	         return SCIP_OKAY;
696  	      }
697  	
698  	      SCIP_CALL( SCIPflushLP(scip) );
699  	
700  	      /* we need an LP */
701  	      if( SCIPgetNLPRows(scip) == 0 )
702  	         return SCIP_OKAY;
703  	   }
704  	
705  	   *result = SCIP_DIDNOTFIND;
706  	
707  	   heurdata = SCIPheurGetData(heur);
708  	   assert(heurdata != NULL);
709  	
710  	#ifdef NOCONFLICT
711  	   /* disable conflict analysis */
712  	   SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
713  	
714  	   if( !SCIPisParamFixed(scip, "conflict/enable") )
715  	   {
716  	      SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
717  	   }
718  	#endif
719  	
720  	   lowerbound = SCIPgetLowerbound(scip);
721  	   oldnpscands = SCIPgetNPseudoBranchCands(scip);
722  	
723  	   /* start probing mode */
724  	   SCIP_CALL( SCIPstartProbing(scip) );
725  	
726  	#ifdef COLLECTSTATISTICS
727  	   SCIPenableVarHistory(scip);
728  	#endif
729  	
730  	   cutoff = FALSE;
731  	   lperror = FALSE;
732  	
733  	   SCIP_CALL( SCIPapplyLockFixings(scip, heurdata, &cutoff, &allrowsfulfilled) );
734  	
735  	   if( cutoff || SCIPisStopped(scip) )
736  	      goto TERMINATE;
737  	
738  	   /* check that we had enough fixings */
739  	   npscands = SCIPgetNPseudoBranchCands(scip);
740  	
741  	   SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, allrowsfulfilled=%u heurdata->minfixingrate=%g\n",
742  	      npscands, oldnpscands, allrowsfulfilled, heurdata->minfixingrate);
743  	
744  	   if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minfixingrate) )
745  	   {
746  	      SCIPdebugMsg(scip, "--> too few fixings\n");
747  	
748  	      goto TERMINATE;
749  	   }
750  	   else
751  	   {
752  	      char strbuf[SCIP_MAXSTRLEN];
753  	      int ncols;
754  	
755  	      if( SCIPgetNContVars(scip) > 0 )
756  	      {
757  	         int nminfixings;
758  	         int nfixedvars = 0;
759  	
760  	         nvars = SCIPgetNVars(scip);
761  	         vars = SCIPgetVars(scip);
762  	         nminfixings = (int)(SCIPceil(scip, heurdata->minfixingratelp * nvars));
763  	
764  	         /* count fixed variables */
765  	         for( i = 0; i < nvars && nfixedvars < nminfixings; ++i )
766  	         {
767  	            if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
768  	               ++nfixedvars;
769  	         }
770  	
771  	         SCIPdebugMsg(scip, "Fixed %d of %d (%.1f %%) variables after probing -> %s\n",
772  	            nfixedvars, nvars, (100.0 * nfixedvars / (SCIP_Real)nvars),
773  	         nfixedvars >= nminfixings ? "continue and solve LP for remaining variables" : "terminate without LP");
774  	
775  	         if( nfixedvars < nminfixings )
776  	            goto TERMINATE;
777  	      }
778  	
779  	      /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
780  	       * which the user sees no output; more detailed probing stats only in debug mode */
781  	      ncols = SCIPgetNLPCols(scip);
782  	      if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
783  	      {
784  	         int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
785  	
786  	         if( nunfixedcols > 0.5 * ncols )
787  	         {
788  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
789  	               "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
790  	               100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
791  	         }
792  	      }
793  	      SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
794  	         SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
795  	
796  	      /* solve LP;
797  	       * errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
798  	       * hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
799  	       */
800  	      SCIPdebugMsg(scip, "starting solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
801  	#ifdef NDEBUG
802  	      {
803  	         SCIP_Bool retstat;
804  	         retstat = SCIPsolveProbingLP(scip, -1, &lperror, &cutoff);
805  	         if( retstat != SCIP_OKAY )
806  	         {
807  	            SCIPwarningMessage(scip, "Error while solving LP in LOCKS heuristic; LP solve terminated with code <%d>\n",
808  	               retstat);
809  	         }
810  	      }
811  	#else
812  	      SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &cutoff) );
813  	#endif
814  	      SCIPdebugMsg(scip, "ending solving locks-lp at time %g\n", SCIPgetSolvingTime(scip));
815  	
816  	      lpstatus = SCIPgetLPSolstat(scip);
817  	
818  	      SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
819  	      SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
820  	
821  	      /* check if this is a feasible solution */
822  	      if( !lperror && lpstatus == SCIP_LPSOLSTAT_OPTIMAL )
823  	      {
824  	         SCIP_SOL* sol;
825  	         SCIP_Bool success;
826  	
827  	         lowerbound = SCIPgetLPObjval(scip);
828  	
829  	         /* create a copy of the current LP solution */
830  	         SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
831  	         SCIP_CALL( SCIPlinkLPSol(scip, sol) );
832  	
833  	         SCIP_CALL( SCIProundSol(scip, sol, &success) );
834  	
835  	         if( success )
836  	         {
837  	            SCIP_Bool stored;
838  	
839  	            /* check solution for feasibility, and add it to solution store if possible.
840  	             * Neither integrality nor feasibility of LP rows have to be checked, because they
841  	             * are guaranteed by the heuristic at this stage.
842  	             */
843  	            SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
844  	
845  	            if( stored )
846  	            {
847  	#ifdef SCIP_MORE_DEBUG
848  	               SCIP_Bool feasible;
849  	               SCIP_CALL( SCIPcheckSol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &feasible) );
850  	               assert(feasible);
851  	#endif
852  	
853  	               SCIPdebugMsg(scip, "found feasible solution:\n");
854  	               SCIPdebug(SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE)) );
855  	               *result = SCIP_FOUNDSOL;
856  	            }
857  	
858  	            SCIP_CALL( SCIPfreeSol(scip, &sol) );
859  	
860  	            /* we found a solution, so we are done */
861  	            goto TERMINATE;
862  	         }
863  	
864  	         SCIP_CALL( SCIPfreeSol(scip, &sol) );
865  	      }
866  	   }
867  	
868  	   if( heurdata->usefinalsubmip && !cutoff && !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
869  	   {
870  	      SCIP* subscip;
871  	      SCIP_VAR** subvars;
872  	      SCIP_HASHMAP* varmap;
873  	      SCIP_Longint nstallnodes;
874  	      SCIP_Bool valid;
875  	
876  	      /* calculate the maximal number of branching nodes until heuristic is aborted */
877  	      nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
878  	
879  	      /* reward locks heuristic if it succeeded often */
880  	      nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
881  	      nstallnodes -= 100 * SCIPheurGetNCalls(heur);  /* count the setup costs for the sub-MIP as 100 nodes */
882  	      nstallnodes += heurdata->nodesofs;
883  	
884  	      /* determine the node limit for the current process */
885  	      nstallnodes -= heurdata->usednodes;
886  	      nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
887  	
888  	      /* check whether we have enough nodes left to call subproblem solving */
889  	      if( nstallnodes < heurdata->minnodes )
890  	      {
891  	         SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
892  	         goto TERMINATE;
893  	      }
894  	
895  	      /* check whether there is enough time and memory left */
896  	      SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
897  	
898  	      if( !valid )
899  	         goto TERMINATE;
900  	
901  	      /* get all variables */
902  	      SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
903  	
904  	      /* create subproblem */
905  	      SCIP_CALL( SCIPcreate(&subscip) );
906  	
907  	      /* allocate temporary memory for subscip variables */
908  	      SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
909  	
910  	      /* create the variable mapping hash map */
911  	      SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
912  	
913  	      SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "_locks", FALSE, FALSE, FALSE, TRUE, &valid) );
914  	
915  	      if( heurdata->copycuts )
916  	      {
917  	         /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
918  	         SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
919  	      }
920  	
921  	      for( i = 0; i < nvars; i++ )
922  	         subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
923  	
924  	      /* free hash map */
925  	      SCIPhashmapFree(&varmap);
926  	
927  	      /* do not abort subproblem on CTRL-C */
928  	      SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
929  	
930  	#ifdef SCIP_DEBUG
931  	      /* for debugging, enable full output */
932  	      SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
933  	      SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
934  	#else
935  	      /* disable statistic timing inside sub SCIP and output to console */
936  	      SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
937  	      SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
938  	#endif
939  	
940  	      /* set limits for the subproblem */
941  	      SCIP_CALL( SCIPcopyLimits(scip, subscip) );
942  	      SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
943  	      SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
944  	
945  	      /* forbid call of heuristics and separators solving sub-CIPs */
946  	      SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
947  	
948  	      /* disable cutting plane separation */
949  	      SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
950  	
951  	      /* disable expensive presolving */
952  	      SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
953  	
954  	      /* use inference branching */
955  	      if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
956  	      {
957  	         SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
958  	      }
959  	
960  	      /* speed up sub-SCIP by not checking dual LP feasibility */
961  	      SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
962  	
963  	      /* if there is already a solution, add an objective cutoff */
964  	      if( SCIPgetNSols(scip) > 0 )
965  	      {
966  	         SCIP_Real upperbound;
967  	         SCIP_Real minimprove;
968  	         SCIP_Real cutoffbound;
969  	
970  	         minimprove = heurdata->minimprove;
971  	         assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
972  	
973  	         upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
974  	
975  	         if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
976  	         {
977  	            cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
978  	         }
979  	         else
980  	         {
981  	            if( SCIPgetUpperbound ( scip ) >= 0 )
982  	               cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
983  	            else
984  	               cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
985  	         }
986  	         cutoffbound = MIN(upperbound, cutoffbound);
987  	         SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
988  	         SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound);
989  	      }
990  	
991  	      SCIPdebugMsg(scip, "starting solving locks-submip at time %g\n", SCIPgetSolvingTime(scip));
992  	
993  	      /* solve the subproblem */
994  	      /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
995  	       * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
996  	       */
997  	#ifdef NDEBUG
998  	      {
999  	         SCIP_RETCODE retstat;
1000 	         retstat = SCIPpresolve(subscip);
1001 	         if( retstat != SCIP_OKAY )
1002 	         {
1003 	            SCIPwarningMessage(scip, "Error while presolving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n", retstat);
1004 	
1005 	            goto FREESCIPANDTERMINATE;
1006 	         }
1007 	      }
1008 	#else
1009 	      SCIP_CALL_ABORT( SCIPpresolve(subscip) );
1010 	#endif
1011 	
1012 	      SCIPdebugMsg(scip, "locks heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n", SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip), ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
1013 	
1014 	      /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
1015 	       * to ensure that not only the MIP but also the LP relaxation is easy enough
1016 	       */
1017 	      if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minfixingrate )
1018 	      {
1019 	         SCIP_Bool success;
1020 	
1021 	         SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
1022 	
1023 	#ifdef NDEBUG
1024 	         {
1025 	            SCIP_RETCODE retstat;
1026 	            retstat = SCIPsolve(subscip);
1027 	            if( retstat != SCIP_OKAY )
1028 	            {
1029 	               SCIPwarningMessage(scip, "Error while solving subMIP in locks heuristic; sub-SCIP terminated with code <%d>\n",retstat);
1030 	
1031 	               goto FREESCIPANDTERMINATE;
1032 	            }
1033 	         }
1034 	#else
1035 	         SCIP_CALL_ABORT( SCIPsolve(subscip) );
1036 	#endif
1037 	         SCIPdebugMsg(scip, "ending solving locks-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
1038 	
1039 	         /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
1040 	          * try all solutions until one was accepted
1041 	          */
1042 	         SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
1043 	         if( success )
1044 	            *result = SCIP_FOUNDSOL;
1045 	      }
1046 	
1047 	#ifdef SCIP_DEBUG
1048 	      SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
1049 	#endif
1050 	
1051 	      heurdata->usednodes += SCIPgetNNodes(subscip);
1052 	#ifdef NDEBUG
1053 	   FREESCIPANDTERMINATE:
1054 	#endif
1055 	      /* free subproblem */
1056 	      SCIPfreeBufferArray(scip, &subvars);
1057 	      SCIP_CALL( SCIPfree(&subscip) );
1058 	   }
1059 	
1060 	 TERMINATE:
1061 	   /* exit probing mode */
1062 	   SCIP_CALL( SCIPendProbing(scip) );
1063 	
1064 	#ifdef NOCONFLICT
1065 	   /* reset the conflict analysis */
1066 	   if( !SCIPisParamFixed(scip, "conflict/enable") )
1067 	   {
1068 	      SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1069 	   }
1070 	#endif
1071 	
1072 	   return SCIP_OKAY;
1073 	}
1074 	
1075 	
1076 	/*
1077 	 * primal heuristic specific interface methods
1078 	 */
1079 	
1080 	/** creates the locks primal heuristic and includes it in SCIP */
1081 	SCIP_RETCODE SCIPincludeHeurLocks(
1082 	   SCIP*                 scip                /**< SCIP data structure */
1083 	   )
1084 	{
1085 	   SCIP_HEURDATA* heurdata;
1086 	
1087 	   /* create primal heuristic data */
1088 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1089 	
1090 	   /* include primal heuristic */
1091 	   SCIP_CALL( SCIPincludeHeur(scip, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1092 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP,
1093 	         heurCopyLocks,
1094 	         heurFreeLocks, heurInitLocks, heurExitLocks,
1095 	         heurInitsolLocks, heurExitsolLocks, heurExecLocks,
1096 	         heurdata) );
1097 	
1098 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1099 	         "maximum number of propagation rounds to be performed in each propagation call (-1: no limit, -2: parameter settings)",
1100 	         &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1101 	
1102 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1103 	         "minimum percentage of integer variables that have to be fixable",
1104 	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1105 	
1106 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundupprobability",
1107 	         "probability for rounding a variable up in case of ties",
1108 	         &heurdata->roundupprobability, FALSE, DEFAULT_ROUNDUPPROBABILITY, 0.0, 1.0, NULL, NULL) );
1109 	
1110 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinalsubmip",
1111 	         "should a final sub-MIP be solved to costruct a feasible solution if the LP was not roundable?",
1112 	         &heurdata->usefinalsubmip, TRUE, DEFAULT_USEFINALSUBMIP, NULL, NULL) );
1113 	
1114 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1115 	         "maximum number of nodes to regard in the subproblem",
1116 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1117 	
1118 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1119 	         "number of nodes added to the contingent of the total nodes",
1120 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1121 	
1122 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1123 	         "minimum number of nodes required to start the subproblem",
1124 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1125 	
1126 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1127 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1128 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1129 	
1130 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1131 	         "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1132 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1133 	
1134 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1135 	         "should all active cuts from cutpool be copied to constraints in subproblem?",
1136 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1137 	
1138 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/updatelocks",
1139 	         "should the locks be updated based on LP rows?",
1140 	         &heurdata->updatelocks, TRUE, DEFAULT_UPDATELOCKS, NULL, NULL) );
1141 	
1142 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingratelp",
1143 	         "minimum fixing rate over all variables (including continuous) to solve LP",
1144 	         &heurdata->minfixingratelp, TRUE, DEFAULT_MINFIXINGRATELP, 0.0, 1.0, NULL, NULL) );
1145 	
1146 	   return SCIP_OKAY;
1147 	}
1148