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