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_proximity.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  improvement heuristic which uses an auxiliary objective instead of the original objective function which
28   	 *         is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti
29   	 *         and Michele Monaci.
30   	 * @author Gregor Hendel
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#include "blockmemshell/memory.h"
36   	#include "scip/cons_linear.h"
37   	#include "scip/heuristics.h"
38   	#include "scip/heur_proximity.h"
39   	#include "scip/pub_event.h"
40   	#include "scip/pub_heur.h"
41   	#include "scip/pub_message.h"
42   	#include "scip/pub_misc.h"
43   	#include "scip/pub_sol.h"
44   	#include "scip/pub_var.h"
45   	#include "scip/scip_branch.h"
46   	#include "scip/scip_cons.h"
47   	#include "scip/scip_copy.h"
48   	#include "scip/scip_event.h"
49   	#include "scip/scip_general.h"
50   	#include "scip/scip_heur.h"
51   	#include "scip/scip_lp.h"
52   	#include "scip/scip_mem.h"
53   	#include "scip/scip_message.h"
54   	#include "scip/scip_nlp.h"
55   	#include "scip/scip_nodesel.h"
56   	#include "scip/scip_numerics.h"
57   	#include "scip/scip_param.h"
58   	#include "scip/scip_prob.h"
59   	#include "scip/scip_sol.h"
60   	#include "scip/scip_solve.h"
61   	#include "scip/scip_solvingstats.h"
62   	#include "scip/scip_timing.h"
63   	#include "scip/scip_var.h"
64   	#include <string.h>
65   	
66   	#define HEUR_NAME             "proximity"
67   	#define HEUR_DESC             "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
68   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
69   	#define HEUR_PRIORITY         -2000000
70   	#define HEUR_FREQ             -1
71   	#define HEUR_FREQOFS          0
72   	#define HEUR_MAXDEPTH         -1
73   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
74   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
75   	
76   	/* event handler properties */
77   	#define EVENTHDLR_NAME        "Proximity"
78   	#define EVENTHDLR_DESC        "LP event handler for " HEUR_NAME " heuristic"
79   	
80   	/* default values for proximity-specific parameters */
81   	/* todo refine these values */
82   	#define DEFAULT_MAXNODES      10000LL    /**< maximum number of nodes to regard in the subproblem                        */
83   	#define DEFAULT_MINIMPROVE    0.02       /**< factor by which proximity should at least improve the incumbent            */
84   	#define DEFAULT_MINGAP        0.01       /**< minimum primal-dual gap for which the heuristic is executed                */
85   	#define DEFAULT_MINNODES      1LL        /**< minimum number of nodes to regard in the subproblem                        */
86   	#define DEFAULT_MINLPITERS    200LL      /**< minimum number of LP iterations to perform in one sub-mip                  */
87   	#define DEFAULT_MAXLPITERS    100000LL   /**< maximum number of LP iterations to be performed in the subproblem          */
88   	#define DEFAULT_NODESOFS      50LL       /**< number of nodes added to the contingent of the total nodes                 */
89   	#define DEFAULT_WAITINGNODES  100LL      /**< default waiting nodes since last incumbent before heuristic is executed    */
90   	#define DEFAULT_NODESQUOT     0.1        /**< default quotient of sub-MIP nodes with respect to number of processed nodes*/
91   	#define DEFAULT_USELPROWS     FALSE      /**< should subproblem be constructed based on LP row information? */
92   	#define DEFAULT_BINVARQUOT    0.1        /**< default threshold for percentage of binary variables required to start     */
93   	#define DEFAULT_RESTART       TRUE       /**< should the heuristic immediately run again on its newly found solution? */
94   	#define DEFAULT_USEFINALLP    FALSE      /**< should the heuristic solve a final LP in case of continuous objective variables? */
95   	#define DEFAULT_LPITERSQUOT   0.2        /**< default quotient of sub-MIP LP iterations with respect to LP iterations so far */
96   	#define DEFAULT_USEUCT        FALSE      /**< should uct node selection be used at the beginning of the search?     */
97   	
98   	/*
99   	 * Data structures
100  	 */
101  	
102  	/** primal heuristic data */
103  	struct SCIP_HeurData
104  	{
105  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem                 */
106  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem                 */
107  	   SCIP_Longint          maxlpiters;         /**< maximum number of LP iterations to be performed in the subproblem   */
108  	   SCIP_Longint          nusedlpiters;       /**< number of actually performed LP iterations                          */
109  	   SCIP_Longint          minlpiters;         /**< minimum number of LP iterations to perform in one sub-mip           */
110  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes          */
111  	   SCIP_Longint          usednodes;          /**< nodes already used by proximity in earlier calls                    */
112  	   SCIP_Longint          waitingnodes;       /**< waiting nodes since last incumbent before heuristic is executed     */
113  	   SCIP_Real             lpitersquot;        /**< quotient of sub-MIP LP iterations with respect to LP iterations so far */
114  	   SCIP_Real             minimprove;         /**< factor by which proximity should at least improve the incumbent     */
115  	   SCIP_Real             mingap;             /**< minimum primal-dual gap for which the heuristic is executed         */
116  	   SCIP_Real             nodesquot;          /**< quotient of sub-MIP nodes with respect to number of processed nodes */
117  	   SCIP_Real             binvarquot;         /**<  threshold for percantage of binary variables required to start     */
118  	
119  	   SCIP*                 subscip;            /**< the subscip used by the heuristic                                   */
120  	   SCIP_HASHMAP*         varmapfw;           /**< map between scip variables and subscip variables                    */
121  	   SCIP_VAR**            subvars;            /**< variables in subscip                                                */
122  	   SCIP_CONS*            objcons;            /**< the objective cutoff constraint of the subproblem                   */
123  	
124  	   int                   nsubvars;           /**< the number of subvars                                               */
125  	   int                   lastsolidx;         /**< index of last solution on which the heuristic was processed         */
126  	   int                   subprobidx;         /**< counter for the subproblem index to be solved by proximity */
127  	
128  	   SCIP_Bool             uselprows;          /**< should subproblem be constructed based on LP row information? */
129  	   SCIP_Bool             restart;            /**< should the heuristic immediately run again on its newly found solution? */
130  	   SCIP_Bool             usefinallp;         /**< should the heuristic solve a final LP in case of continuous objective variables? */
131  	   SCIP_Bool             useuct;             /**< should uct node selection be used at the beginning of the search?  */
132  	};
133  	
134  	
135  	/*
136  	 * Local methods
137  	 */
138  	
139  	/** optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values */
140  	static
141  	SCIP_RETCODE solveLp(
142  	   SCIP*                 scip,               /**< SCIP data structure */
143  	   SCIP_SOL*             sol,                /**< candidate solution for which continuous variables should be optimized */
144  	   SCIP_Bool*            success             /**< was the dive successful? */
145  	   )
146  	{
147  	   SCIP_VAR** vars;
148  	   SCIP_RETCODE retstat;
149  	
150  	   int v;
151  	   int nvars;
152  	   int ncontvars;
153  	   int nintvars;
154  	
155  	   SCIP_Bool lperror;
156  	   SCIP_Bool requiresnlp;
157  	
158  	   assert(success != NULL);
159  	
160  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
161  	
162  	   nintvars = nvars - ncontvars;
163  	
164  	   /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE rather solve the NLP instead of the LP */
165  	   requiresnlp = SCIPisNLPConstructed(scip);
166  	   if( requiresnlp || ncontvars == 0 )
167  	      return SCIP_OKAY;
168  	
169  	   /* start diving to calculate the LP relaxation */
170  	   SCIP_CALL( SCIPstartDive(scip) );
171  	
172  	   /* set the bounds of the variables: fixed for integers, global bounds for continuous */
173  	   for( v = 0; v < nvars; ++v )
174  	   {
175  	      if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
176  	      {
177  	         SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) );
178  	         SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) );
179  	      }
180  	   }
181  	
182  	   /* apply this after global bounds to not cause an error with intermediate empty domains */
183  	   for( v = 0; v < nintvars; ++v )
184  	   {
185  	      if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
186  	      {
187  	         SCIP_Real solval;
188  	
189  	         solval = SCIPgetSolVal(scip, sol, vars[v]);
190  	         SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) );
191  	         SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) );
192  	      }
193  	   }
194  	
195  	   /* solve LP */
196  	   SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
197  	
198  	   /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
199  	    * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
200  	    */
201  	   retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
202  	   if( retstat != SCIP_OKAY )
203  	   {
204  	#ifdef NDEBUG
205  	      SCIPwarningMessage(scip, "Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat);
206  	#else
207  	      SCIP_CALL( retstat );
208  	#endif
209  	   }
210  	
211  	   SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
212  	   SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
213  	   if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
214  	   {
215  	      SCIP_CALL( SCIPlinkLPSol(scip, sol) );
216  	      SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
217  	   }
218  	
219  	   /* terminate diving mode */
220  	   SCIP_CALL( SCIPendDive(scip) );
221  	
222  	   return SCIP_OKAY;
223  	}
224  	
225  	/** creates a new solution for the original problem by copying the solution of the subproblem */
226  	static
227  	SCIP_RETCODE createNewSol(
228  	   SCIP*                 scip,               /**< original SCIP data structure                        */
229  	   SCIP*                 subscip,            /**< SCIP structure of the subproblem                    */
230  	   SCIP_VAR**            subvars,            /**< the variables of the subproblem                     */
231  	   SCIP_HEUR*            heur,               /**< proximity heuristic structure                       */
232  	   SCIP_SOL*             subsol,             /**< solution of the subproblem                          */
233  	   SCIP_Bool             usefinallp,         /**< should continuous variables be optimized by a final LP */
234  	   SCIP_Bool*            success             /**< used to store whether new solution was found or not */
235  	   )
236  	{
237  	   SCIP_VAR** vars;                          /* the original problem's variables                */
238  	   int        nvars;                         /* the original problem's number of variables      */
239  	   int        ncontvars;                     /* the original problem's number of continuous variables */
240  	   SCIP_Real* subsolvals;                    /* solution values of the subproblem               */
241  	   SCIP_SOL*  newsol;                        /* solution to be created for the original problem */
242  	   int i;
243  	
244  	   assert(scip != NULL);
245  	   assert(subscip != NULL);
246  	   assert(subvars != NULL);
247  	   assert(subsol != NULL);
248  	   assert(success != NULL);
249  	
250  	   /* get variables' data */
251  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
252  	
253  	   SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
254  	
255  	   /* copy the solution */
256  	   for( i = 0; i < nvars; ++i )
257  	   {
258  	      if( subvars[i] == NULL )
259  	         subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i]));  /*lint !e666*/
260  	      else
261  	         subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvars[i]);
262  	   }
263  	
264  	   /* create new solution for the original problem */
265  	   SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
266  	   SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
267  	
268  	   *success = FALSE;
269  	
270  	   /* solve an LP with all integer variables fixed to improve solution quality */
271  	   if( ncontvars > 0 && usefinallp && SCIPisLPConstructed(scip) )
272  	   {
273  	      int v;
274  	      int ncontobjvars = 0;    /* does the problem instance have continuous variables with nonzero objective coefficients? */
275  	      SCIP_Real sumofobjsquares = 0.0;
276  	
277  	      /* check if continuous variables with nonzero objective coefficient are present */
278  	      for( v = nvars - 1; v >= nvars - ncontvars; --v )
279  	      {
280  	         SCIP_VAR* var;
281  	
282  	         var = vars[v];
283  	         assert(vars[v] != NULL);
284  	         assert(!SCIPvarIsIntegral(var));
285  	
286  	         if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN && !SCIPisZero(scip, SCIPvarGetObj(var)) )
287  	         {
288  	            ++ncontobjvars;
289  	            sumofobjsquares += SCIPvarGetObj(var) * SCIPvarGetObj(var);
290  	         }
291  	      }
292  	
293  	      SCIPstatisticMessage(" Continuous Objective variables: %d, Euclidean OBJ: %g total, %g continuous\n", ncontobjvars, SCIPgetObjNorm(scip), sumofobjsquares);
294  	
295  	      /* solve a final LP to optimize solution values of continuous problem variables */
296  	      SCIPstatisticMessage("Solution Value before LP resolve: %g\n", SCIPgetSolOrigObj(scip, newsol));
297  	      SCIP_CALL( solveLp(scip, newsol, success) );
298  	
299  	      /* if the LP solve was not successful, reset the solution */
300  	      if( !*success )
301  	      {
302  	         for( v = nvars - 1; v >= nvars - ncontvars; --v )
303  	         {
304  	            SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], subsolvals[v]) );
305  	         }
306  	      }
307  	   }
308  	
309  	   /* try to add new solution to SCIP and free it immediately */
310  	   if( !*success )
311  	   {
312  	      SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
313  	   }
314  	   SCIP_CALL( SCIPfreeSol(scip, &newsol) );
315  	
316  	   SCIPfreeBufferArray(scip, &subsolvals);
317  	
318  	   return SCIP_OKAY;
319  	}
320  	
321  	/** sets solving parameters for the subproblem created by the heuristic */
322  	static
323  	SCIP_RETCODE setupSubproblem(
324  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
325  	   SCIP*                 subscip             /**< copied SCIP data structure */
326  	   )
327  	{
328  	   assert(subscip != NULL);
329  	
330  	   /* do not abort subproblem on CTRL-C */
331  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
332  	
333  	#ifdef SCIP_DEBUG
334  	   /* for debugging, enable full output */
335  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
336  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
337  	#else
338  	   /* disable statistic timing inside sub SCIP and output to console */
339  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
340  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
341  	#endif
342  	
343  	   /* forbid recursive call of heuristics and separators solving sub-SCIPs */
344  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
345  	
346  	   /* use restart dfs node selection */
347  	   if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
348  	   {
349  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
350  	   }
351  	
352  	   /* activate uct node selection at the top of the tree */
353  	   if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
354  	   {
355  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
356  	   }
357  	
358  	   /* disable expensive presolving
359  	    * todo maybe presolving can be entirely turned off here - parameter???
360  	    */
361  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
362  	
363  	   /* SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) ); */
364  	   if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
365  	   {
366  	      SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
367  	   }
368  	
369  	   /* disable cutting plane separation */
370  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
371  	
372  	   /* todo: check branching rule in sub-SCIP */
373  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
374  	   {
375  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
376  	   }
377  	
378  	   /* disable feasibility pump and fractional diving */
379  	   if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
380  	   {
381  	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
382  	   }
383  	   if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
384  	   {
385  	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
386  	   }
387  	
388  	   /* todo check if
389  	    * SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
390  	    * improves performance */
391  	
392  	   return SCIP_OKAY;
393  	}
394  	
395  	/** frees the subproblem */
396  	static
397  	SCIP_RETCODE deleteSubproblem(
398  	   SCIP*                 scip,               /**< SCIP data structure */
399  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
400  	   )
401  	{
402  	   /* free remaining memory from heuristic execution */
403  	   if( heurdata->subscip != NULL )
404  	   {
405  	      assert(heurdata->varmapfw != NULL);
406  	      assert(heurdata->subvars != NULL);
407  	      assert(heurdata->objcons != NULL);
408  	
409  	      SCIPdebugMsg(scip, "Freeing subproblem of proximity heuristic\n");
410  	      SCIPfreeBlockMemoryArray(scip, &heurdata->subvars, heurdata->nsubvars);
411  	      SCIPhashmapFree(&heurdata->varmapfw);
412  	      SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &heurdata->objcons) );
413  	      SCIP_CALL( SCIPfree(&heurdata->subscip) );
414  	
415  	      heurdata->subscip = NULL;
416  	      heurdata->varmapfw = NULL;
417  	      heurdata->subvars = NULL;
418  	      heurdata->objcons = NULL;
419  	   }
420  	   return SCIP_OKAY;
421  	}
422  	
423  	/* ---------------- Callback methods of event handler ---------------- */
424  	
425  	/** exec the event handler
426  	 *
427  	 *  We interrupt the solution process.
428  	 */
429  	static
430  	SCIP_DECL_EVENTEXEC(eventExecProximity)
431  	{
432  	   SCIP_HEURDATA* heurdata;
433  	
434  	   assert(eventhdlr != NULL);
435  	   assert(eventdata != NULL);
436  	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
437  	   assert(event != NULL);
438  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_NODESOLVED);
439  	
440  	   heurdata = (SCIP_HEURDATA*)eventdata;
441  	   assert(heurdata != NULL);
442  	
443  	   /* interrupt solution process of sub-SCIP
444  	    * todo adjust interruption limit */
445  	   if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
446  	   {
447  	      SCIP_CALL( SCIPinterruptSolve(scip) );
448  	   }
449  	
450  	   return SCIP_OKAY;
451  	}
452  	
453  	
454  	/* ---------------- Callback methods of primal heuristic ---------------- */
455  	
456  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
457  	static
458  	SCIP_DECL_HEURCOPY(heurCopyProximity)
459  	{  /*lint --e{715}*/
460  	   assert(scip != NULL);
461  	   assert(heur != NULL);
462  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
463  	
464  	   /* call inclusion method of primal heuristic */
465  	   SCIP_CALL( SCIPincludeHeurProximity(scip) );
466  	
467  	   return SCIP_OKAY;
468  	}
469  	
470  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
471  	static
472  	SCIP_DECL_HEURFREE(heurFreeProximity)
473  	{  /*lint --e{715}*/
474  	   SCIP_HEURDATA* heurdata;
475  	
476  	   assert( heur != NULL );
477  	   assert( scip != NULL );
478  	
479  	   /* get heuristic data */
480  	   heurdata = SCIPheurGetData(heur);
481  	   assert( heurdata != NULL );
482  	
483  	   /* free heuristic data */
484  	   SCIPfreeBlockMemory(scip, &heurdata);
485  	   SCIPheurSetData(heur, NULL);
486  	
487  	   return SCIP_OKAY;
488  	}
489  	
490  	
491  	/** initialization method of primal heuristic (called after problem was transformed) */
492  	static
493  	SCIP_DECL_HEURINIT(heurInitProximity)
494  	{  /*lint --e{715}*/
495  	   SCIP_HEURDATA* heurdata;
496  	
497  	   assert( heur != NULL );
498  	   assert( scip != NULL );
499  	
500  	   /* get heuristic data */
501  	   heurdata = SCIPheurGetData(heur);
502  	   assert( heurdata != NULL );
503  	
504  	   /* initialize data */
505  	   heurdata->usednodes = 0LL;
506  	   heurdata->lastsolidx = -1;
507  	   heurdata->nusedlpiters = 0LL;
508  	   heurdata->subprobidx = 0;
509  	
510  	   heurdata->subscip = NULL;
511  	   heurdata->varmapfw = NULL;
512  	   heurdata->subvars = NULL;
513  	   heurdata->objcons = NULL;
514  	
515  	   heurdata->nsubvars = 0;
516  	
517  	   return SCIP_OKAY;
518  	}
519  	
520  	/** solution process exiting method of proximity heuristic */
521  	static
522  	SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
523  	{
524  	   SCIP_HEURDATA* heurdata;
525  	
526  	   assert( heur != NULL );
527  	   assert( scip != NULL );
528  	
529  	   /* get heuristic data */
530  	   heurdata = SCIPheurGetData(heur);
531  	   assert( heurdata != NULL );
532  	
533  	   SCIP_CALL( deleteSubproblem(scip, heurdata) );
534  	
535  	   assert(heurdata->subscip == NULL && heurdata->varmapfw == NULL && heurdata->subvars == NULL && heurdata->objcons == NULL);
536  	
537  	   return SCIP_OKAY;
538  	}
539  	
540  	/** execution method of primal heuristic */
541  	static
542  	SCIP_DECL_HEUREXEC(heurExecProximity)
543  	{  /*lint --e{715}*/
544  	   SCIP_HEURDATA* heurdata; /* heuristic's data                            */
545  	   SCIP_Longint nnodes;     /* number of stalling nodes for the subproblem */
546  	   SCIP_Longint nlpiters;   /* lp iteration limit for the subproblem       */
547  	   SCIP_Bool foundsol = FALSE;
548  	
549  	   assert(heur != NULL);
550  	   assert(scip != NULL);
551  	   assert(result != NULL);
552  	
553  	   *result = SCIP_DIDNOTRUN;
554  	
555  	   /* get heuristic data */
556  	   heurdata = SCIPheurGetData(heur);
557  	   assert(heurdata != NULL);
558  	
559  	   /* do not run heuristic when there are only few binary varables */
560  	   if( SCIPgetNBinVars(scip) < heurdata->binvarquot * SCIPgetNVars(scip) )
561  	      return SCIP_OKAY;
562  	
563  	   /* calculate branching node limit for sub problem */
564  	   /* todo maybe treat root node differently */
565  	   nnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
566  	   nnodes += heurdata->nodesofs;
567  	
568  	   /* determine the node and LP iteration limit for the solve of the sub-SCIP */
569  	   nnodes -= heurdata->usednodes;
570  	   nnodes = MIN(nnodes, heurdata->maxnodes);
571  	
572  	   nlpiters = (SCIP_Longint) (heurdata->lpitersquot * SCIPgetNRootFirstLPIterations(scip));
573  	   nlpiters = MIN(nlpiters, heurdata->maxlpiters);
574  	
575  	   /* check whether we have enough nodes left to call subproblem solving */
576  	   if( nnodes < heurdata->minnodes )
577  	   {
578  	      SCIPdebugMsg(scip, "skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
579  	      return SCIP_OKAY;
580  	   }
581  	
582  	   /* do not run proximity, if the problem does not have an objective function anyway */
583  	   if( SCIPgetNObjVars(scip) == 0 )
584  	   {
585  	      SCIPdebugMsg(scip, "skipping proximity: pure feasibility problem anyway\n");
586  	      return SCIP_OKAY;
587  	   }
588  	
589  	   do
590  	   {
591  	      /* main loop of proximity: in every iteration, a new subproblem is set up and solved until no improved solution
592  	       * is found or one of the heuristic limits on nodes or LP iterations is hit
593  	       * heuristic performs only one iteration if restart parameter is set to FALSE
594  	       */
595  	      SCIP_Longint nusednodes = 0LL;
596  	      SCIP_Longint nusedlpiters = 0LL;
597  	
598  	      nlpiters = MAX(nlpiters, heurdata->minlpiters);
599  	
600  	      /* define and solve the proximity subproblem */
601  	      SCIP_CALL( SCIPapplyProximity(scip, heur, result, heurdata->minimprove, nnodes, nlpiters, &nusednodes, &nusedlpiters, FALSE) );
602  	
603  	      /* adjust node limit and LP iteration limit for future iterations */
604  	      assert(nusednodes <= nnodes);
605  	      heurdata->usednodes += nusednodes;
606  	      nnodes -= nusednodes;
607  	
608  	      nlpiters -= nusedlpiters;
609  	      heurdata->nusedlpiters += nusedlpiters;
610  	
611  	      /* memorize if a new solution has been found in at least one iteration */
612  	      if( *result == SCIP_FOUNDSOL )
613  	         foundsol = TRUE;
614  	   }
615  	   while( *result == SCIP_FOUNDSOL && heurdata->restart && !SCIPisStopped(scip) && nnodes > 0 );
616  	
617  	   /* reset result pointer if solution has been found in previous iteration */
618  	   if( foundsol )
619  	      *result = SCIP_FOUNDSOL;
620  	
621  	   /* free the occupied memory */
622  	   if( heurdata->subscip != NULL )
623  	   {
624  	      /* just for testing the library method, in debug mode, we call the wrapper method for the actual delete method */
625  	#ifndef NDEBUG
626  	      SCIP_CALL( SCIPdeleteSubproblemProximity(scip) );
627  	#else
628  	      SCIP_CALL( deleteSubproblem(scip, heurdata) );
629  	#endif
630  	   }
631  	   return SCIP_OKAY;
632  	}
633  	
634  	
635  	/*
636  	 * primal heuristic specific interface methods
637  	 */
638  	
639  	/** frees the sub-MIP created by proximity */
640  	SCIP_RETCODE SCIPdeleteSubproblemProximity(
641  	   SCIP*                 scip                /** SCIP data structure */
642  	   )
643  	{
644  	   SCIP_HEUR* heur;
645  	   SCIP_HEURDATA* heurdata;
646  	
647  	   assert(scip != NULL);
648  	
649  	   heur = SCIPfindHeur(scip, HEUR_NAME);
650  	   assert(heur != NULL);
651  	
652  	   heurdata = SCIPheurGetData(heur);
653  	   if( heurdata != NULL )
654  	   {
655  	      SCIP_CALL( deleteSubproblem(scip, heurdata) );
656  	   }
657  	
658  	   return SCIP_OKAY;
659  	}
660  	
661  	/** main procedure of the proximity heuristic, creates and solves a sub-SCIP
662  	 *
663  	 *  @note The method can be applied in an iterative way, keeping the same subscip in between. If the @p freesubscip
664  	 *        parameter is set to FALSE, the heuristic will keep the subscip data structures. Always set this parameter
665  	 *        to TRUE, or call SCIPdeleteSubproblemProximity() afterwards.
666  	 */
667  	SCIP_RETCODE SCIPapplyProximity(
668  	   SCIP*                 scip,               /**< original SCIP data structure                                        */
669  	   SCIP_HEUR*            heur,               /**< heuristic data structure                                            */
670  	   SCIP_RESULT*          result,             /**< result data structure                                               */
671  	   SCIP_Real             minimprove,         /**< factor by which proximity should at least improve the incumbent     */
672  	   SCIP_Longint          nnodes,             /**< node limit for the subproblem                                       */
673  	   SCIP_Longint          nlpiters,           /**< LP iteration limit for the subproblem                               */
674  	   SCIP_Longint*         nusednodes,         /**< pointer to store number of used nodes in subscip                    */
675  	   SCIP_Longint*         nusedlpiters,       /**< pointer to store number of used LP iterations in subscip            */
676  	   SCIP_Bool             freesubscip         /**< should the created sub-MIP be freed at the end of the method?       */
677  	   )
678  	{
679  	   SCIP*                 subscip;            /* the subproblem created by proximity              */
680  	   SCIP_HASHMAP*         varmapfw;           /* mapping of SCIP variables to sub-SCIP variables */
681  	   SCIP_VAR**            vars;               /* original problem's variables                    */
682  	   SCIP_VAR**            subvars;            /* subproblem's variables                          */
683  	   SCIP_HEURDATA*        heurdata;           /* heuristic's private data structure              */
684  	   SCIP_EVENTHDLR*       eventhdlr;          /* event handler for LP events                     */
685  	
686  	   SCIP_SOL* incumbent;
687  	   SCIP_CONS* objcons;
688  	   SCIP_Longint iterlim;
689  	
690  	   SCIP_Real large;
691  	   SCIP_Real inf;
692  	
693  	   SCIP_Real bestobj;
694  	   SCIP_Real objcutoff;
695  	   SCIP_Real lowerbound;
696  	
697  	   int nvars;                                /* number of original problem's variables          */
698  	   int nfixedvars;
699  	   int nsubsols;
700  	   int solidx;
701  	   int i;
702  	
703  	   SCIP_Bool valid;
704  	   SCIP_Bool success;
705  	
706  	   assert(scip != NULL);
707  	   assert(heur != NULL);
708  	   assert(result != NULL);
709  	
710  	   assert(nnodes >= 0);
711  	   assert(0.0 <= minimprove && minimprove <= 1.0);
712  	
713  	   *result = SCIP_DIDNOTRUN;
714  	
715  	   /* get heuristic data */
716  	   heurdata = SCIPheurGetData(heur);
717  	   assert(heurdata != NULL);
718  	
719  	   /* only call the heuristic if we have an incumbent  */
720  	   if( SCIPgetNSolsFound(scip) == 0 )
721  	      return SCIP_OKAY;
722  	
723  	   /* do not use heuristic on problems without binary variables */
724  	   if( SCIPgetNBinVars(scip) == 0 )
725  	      return SCIP_OKAY;
726  	
727  	   incumbent = SCIPgetBestSol(scip);
728  	   assert(incumbent != NULL);
729  	
730  	   /* make sure that the incumbent is valid for the transformed space, otherwise terminate */
731  	   if( SCIPsolIsOriginal(incumbent) )
732  	      return SCIP_OKAY;
733  	
734  	   solidx = SCIPsolGetIndex(incumbent);
735  	
736  	   if( heurdata->lastsolidx == solidx )
737  	      return SCIP_OKAY;
738  	
739  	   /* only call heuristic, if the best solution does not come from trivial heuristic */
740  	   if( SCIPsolGetHeur(incumbent) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(incumbent)), "trivial") == 0 )
741  	      return SCIP_OKAY;
742  	
743  	   /* waitingnodes parameter defines the minimum number of nodes to wait before a new incumbent is processed */
744  	   if( SCIPgetNNodes(scip) > 1 && SCIPgetNNodes(scip) - SCIPsolGetNodenum(incumbent) < heurdata->waitingnodes )
745  	      return SCIP_OKAY;
746  	
747  	   bestobj = SCIPgetSolTransObj(scip, incumbent);
748  	   lowerbound = SCIPgetLowerbound(scip);
749  	
750  	   /* use knowledge about integrality of objective to round up lower bound */
751  	   if( SCIPisObjIntegral(scip) )
752  	   {
753  	      SCIPdebugMsg(scip, " Rounding up lower bound: %f --> %f \n", lowerbound, SCIPfeasCeil(scip, lowerbound));
754  	      lowerbound = SCIPfeasCeil(scip, lowerbound);
755  	   }
756  	
757  	   /* do not trigger heuristic if primal and dual bound are already close together */
758  	   if( SCIPisFeasLE(scip, bestobj, lowerbound) || SCIPgetGap(scip) <= heurdata->mingap )
759  	      return SCIP_OKAY;
760  	
761  	   /* calculate the minimum improvement for a heuristic solution in terms of the distance between incumbent objective
762  	    * and the lower bound */
763  	   if( SCIPisInfinity(scip, REALABS(lowerbound)) )
764  	   {
765  	      if( SCIPisZero(scip, bestobj) )
766  	         objcutoff = bestobj - 1;
767  	      else
768  	         objcutoff = (1 - minimprove) * bestobj;
769  	   }
770  	   else
771  	      objcutoff = minimprove * lowerbound + (1 - minimprove) * (bestobj);
772  	
773  	   /* use integrality of the objective function to round down (and thus strengthen) the objective cutoff */
774  	   if( SCIPisObjIntegral(scip) )
775  	      objcutoff = SCIPfeasFloor(scip, objcutoff);
776  	
777  	   if( SCIPisFeasLT(scip, objcutoff, lowerbound) )
778  	      objcutoff = lowerbound;
779  	
780  	   /* exit execution if the right hand side of the objective constraint does not change (suggests that the heuristic
781  	    * was not successful in a previous iteration) */
782  	   if( heurdata->objcons != NULL && SCIPisFeasEQ(scip, SCIPgetRhsLinear(heurdata->subscip, heurdata->objcons), objcutoff) )
783  	      return SCIP_OKAY;
784  	
785  	   /* check whether there is enough time and memory left */
786  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
787  	
788  	   if( ! valid )
789  	      return SCIP_OKAY;
790  	
791  	   *result = SCIP_DIDNOTFIND;
792  	
793  	   heurdata->lastsolidx = solidx;
794  	
795  	   /* get variable data */
796  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
797  	
798  	   /* create a subscip and copy the original scip instance into it */
799  	   if( heurdata->subscip == NULL )
800  	   {
801  	      assert(heurdata->varmapfw == NULL);
802  	      assert(heurdata->objcons == NULL);
803  	
804  	      /* initialize the subproblem */
805  	      SCIP_CALL( SCIPcreate(&subscip) );
806  	
807  	      /* create the variable mapping hash map */
808  	      SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
809  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &subvars, nvars) );
810  	
811  	      /* copy complete SCIP instance */
812  	      valid = FALSE;
813  	
814  	      /* create a problem copy as sub SCIP */
815  	      SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "proximity", NULL, NULL, 0, heurdata->uselprows, TRUE,
816  	            &success, &valid) );
817  	
818  	      SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
819  	
820  	      /* create event handler for LP events */
821  	      eventhdlr = NULL;
822  	      SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecProximity, NULL) );
823  	      if( eventhdlr == NULL )
824  	      {
825  	         SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
826  	         return SCIP_PLUGINNOTFOUND;
827  	      }
828  	
829  	      /* set up parameters for the copied instance */
830  	      SCIP_CALL( setupSubproblem(heurdata, subscip) );
831  	
832  	      /* create the objective constraint in the sub scip, first without variables and values which will be added later */
833  	      SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), SCIPinfinity(subscip)) );
834  	
835  	      /* determine large value to set variable bounds to, safe-guard to avoid fixings to infinite values */
836  	      large = SCIPinfinity(scip);
837  	      if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
838  	         large = 0.1 / SCIPfeastol(scip);
839  	      inf = SCIPinfinity(subscip);
840  	
841  	      /* get variable image and change objective to proximity function (Manhattan distance) in sub-SCIP */
842  	      for( i = 0; i < nvars; i++ )
843  	      {
844  	         SCIP_Real adjustedbound;
845  	         SCIP_Real lb;
846  	         SCIP_Real ub;
847  	
848  	         subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
849  	
850  	         if( subvars[i] == NULL )
851  	            continue;
852  	
853  	         SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
854  	
855  	         lb = SCIPvarGetLbGlobal(subvars[i]);
856  	         ub = SCIPvarGetUbGlobal(subvars[i]);
857  	
858  	         /* adjust infinite bounds in order to avoid that variables with non-zero objective
859  	          * get fixed to infinite value in proximity subproblem
860  	          */
861  	         if( SCIPisInfinity(subscip, ub) )
862  	         {
863  	            adjustedbound = MAX(large, lb + large);
864  	            adjustedbound = MIN(adjustedbound, inf);
865  	            SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
866  	         }
867  	         if( SCIPisInfinity(subscip, -lb) )
868  	         {
869  	            adjustedbound = MIN(-large, ub - large);
870  	            adjustedbound = MAX(adjustedbound, -inf);
871  	            SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
872  	         }
873  	
874  	         /* add all nonzero objective coefficients to the objective constraint */
875  	         if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
876  	         {
877  	            SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
878  	         }
879  	      }
880  	
881  	      /* add objective constraint to the subscip */
882  	      SCIP_CALL( SCIPaddCons(subscip, objcons) );
883  	   }
884  	   else
885  	   {
886  	      /* the instance, event handler, hash map and variable array were already copied in a previous iteration
887  	       * and stored in heuristic data
888  	       */
889  	      assert(heurdata->varmapfw != NULL);
890  	      assert(heurdata->subvars != NULL);
891  	      assert(heurdata->objcons != NULL);
892  	
893  	      subscip = heurdata->subscip;
894  	      varmapfw = heurdata->varmapfw;
895  	      subvars = heurdata->subvars;
896  	      objcons = heurdata->objcons;
897  	
898  	      eventhdlr = SCIPfindEventhdlr(subscip, EVENTHDLR_NAME);
899  	      assert(eventhdlr != NULL);
900  	   }
901  	
902  	   SCIP_CALL( SCIPchgRhsLinear(subscip, objcons, objcutoff) );
903  	
904  	   for( i = 0; i < SCIPgetNBinVars(scip); ++i )
905  	   {
906  	      SCIP_Real solval;
907  	
908  	      if( subvars[i] == NULL )
909  	         continue;
910  	
911  	      /* objective coefficients are only set for binary variables of the problem */
912  	      assert(SCIPvarIsBinary(subvars[i]));
913  	
914  	      solval = SCIPgetSolVal(scip, incumbent, vars[i]);
915  	      assert(SCIPisFeasGE(scip, solval, 0.0));
916  	      assert(SCIPisFeasLE(scip, solval, 1.0));
917  	      assert(SCIPisFeasIntegral(scip, solval));
918  	
919  	      if( solval < 0.5 )
920  	      {
921  	         SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 1.0) );
922  	      }
923  	      else
924  	      {
925  	         SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], -1.0) );
926  	      }
927  	   }
928  	
929  	   /* set limits for the subproblem */
930  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
931  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
932  	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
933  	
934  	   /* restrict LP iterations */
935  	   /* todo set iterations limit depending on the number of iterations of the original problem root */
936  	   iterlim = nlpiters;
937  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", MAX(1, iterlim / MIN(10, nnodes))) );
938  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", iterlim) );
939  	
940  	   /* catch LP events of sub-SCIP */
941  	   SCIP_CALL( SCIPtransformProb(subscip) );
942  	   SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
943  	
944  	   SCIPstatisticMessage("solving subproblem at Node: %" SCIP_LONGINT_FORMAT " "
945  	         "nnodes: %" SCIP_LONGINT_FORMAT " "
946  	         "iterlim: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNNodes(scip), nnodes, iterlim);
947  	
948  	   /* solve the subproblem with all previously adjusted parameters */
949  	   nfixedvars = SCIPgetNFixedVars(subscip);
950  	
951  	   SCIP_CALL( SCIPpresolve(subscip) );
952  	
953  	   nfixedvars = SCIPgetNFixedVars(subscip) - nfixedvars;
954  	   assert(nfixedvars >= 0);
955  	   SCIPstatisticMessage("presolve fixings %d: %d\n", ++(heurdata->subprobidx), nfixedvars);
956  	
957  	   /* errors in solving the subproblem should not kill the overall solving process;
958  	    * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
959  	    */
960  	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
961  	
962  	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
963  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
964  	   SCIPstatisticMessage("solve of subscip %d:"
965  	         "usednodes: %" SCIP_LONGINT_FORMAT " "
966  	         "lp iters: %" SCIP_LONGINT_FORMAT " "
967  	         "root iters: %" SCIP_LONGINT_FORMAT " "
968  	         "Presolving Time: %.2f\n", heurdata->subprobidx,
969  	         SCIPgetNNodes(subscip), SCIPgetNLPIterations(subscip), SCIPgetNRootLPIterations(subscip), SCIPgetPresolvingTime(subscip));
970  	
971  	   SCIPstatisticMessage("Solving Time %d: %.2f\n", heurdata->subprobidx, SCIPgetSolvingTime(subscip) );
972  	
973  	   /* drop LP events of sub-SCIP */
974  	   SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
975  	
976  	   /* keep track of relevant information for future runs of heuristic */
977  	   if( nusednodes != NULL )
978  	      *nusednodes = SCIPgetNNodes(subscip);
979  	   if( nusedlpiters != NULL )
980  	      *nusedlpiters = SCIPgetNLPIterations(subscip);
981  	
982  	   /* check whether a solution was found */
983  	   nsubsols = SCIPgetNSols(subscip);
984  	   incumbent = SCIPgetBestSol(subscip);
985  	   assert(nsubsols == 0 || incumbent != NULL);
986  	
987  	   SCIPstatisticMessage("primal bound before subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
988  	   if( nsubsols > 0 )
989  	   {
990  	      /* try to translate the sub problem solution to the original scip instance */
991  	      success = FALSE;
992  	      SCIP_CALL( createNewSol(scip, subscip, subvars, heur, incumbent, heurdata->usefinallp, &success) );
993  	
994  	      if( success )
995  	         *result = SCIP_FOUNDSOL;
996  	   }
997  	   SCIPstatisticMessage("primal bound after subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
998  	
999  	   /* free the transformed subproblem data */
1000 	   SCIP_CALL( SCIPfreeTransform(subscip) );
1001 	
1002 	   /* save subproblem in heuristic data for subsequent runs if it has been successful, otherwise free subproblem */
1003 	   heurdata->subscip = subscip;
1004 	   heurdata->varmapfw = varmapfw;
1005 	   heurdata->subvars = subvars;
1006 	   heurdata->objcons = objcons;
1007 	   heurdata->nsubvars = nvars;
1008 	
1009 	   /* delete the sub problem */
1010 	   if( freesubscip )
1011 	   {
1012 	      SCIP_CALL( deleteSubproblem(scip, heurdata) );
1013 	   }
1014 	
1015 	   return SCIP_OKAY;
1016 	}
1017 	
1018 	
1019 	/** creates the proximity primal heuristic and includes it in SCIP */
1020 	SCIP_RETCODE SCIPincludeHeurProximity(
1021 	   SCIP*                 scip                /**< SCIP data structure */
1022 	   )
1023 	{
1024 	   SCIP_HEURDATA* heurdata;
1025 	   SCIP_HEUR* heur = NULL;
1026 	
1027 	   /* create heuristic data */
1028 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1029 	
1030 	   /* include primal heuristic */
1031 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1032 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1033 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecProximity, heurdata) );
1034 	   assert(heur != NULL);
1035 	
1036 	   /* set non-NULL pointers to callback methods */
1037 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyProximity) );
1038 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeProximity) );
1039 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitProximity) );
1040 	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolProximity) );
1041 	
1042 	   /* add proximity primal heuristic parameters */
1043 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1044 	         "should subproblem be constructed based on LP row information?",
1045 	         &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1046 	
1047 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/restart",
1048 	         "should the heuristic immediately run again on its newly found solution?",
1049 	         &heurdata->restart, TRUE, DEFAULT_RESTART, NULL, NULL) );
1050 	
1051 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinallp",
1052 	         "should the heuristic solve a final LP in case of continuous objective variables?",
1053 	         &heurdata->usefinallp, TRUE, DEFAULT_USEFINALLP, NULL, NULL) );
1054 	
1055 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1056 	         "maximum number of nodes to regard in the subproblem",
1057 	         &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1058 	
1059 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1060 	         "number of nodes added to the contingent of the total nodes",
1061 	         &heurdata->nodesofs, TRUE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1062 	
1063 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1064 	         "minimum number of nodes required to start the subproblem",
1065 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1066 	
1067 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
1068 	         "maximum number of LP iterations to be performed in the subproblem",
1069 	         &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1070 	
1071 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minlpiters",
1072 	         "minimum number of LP iterations performed in subproblem",
1073 	         &heurdata->minlpiters, TRUE, DEFAULT_MINLPITERS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1074 	
1075 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
1076 	          "waiting nodes since last incumbent before heuristic is executed",
1077 	         &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1078 	
1079 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1080 	         "factor by which proximity should at least improve the incumbent",
1081 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1082 	
1083 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1084 	         "sub-MIP node limit w.r.t number of original nodes",
1085 	         &heurdata->nodesquot, TRUE, DEFAULT_NODESQUOT, 0.0, SCIPinfinity(scip), NULL, NULL) );
1086 	
1087 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/binvarquot",
1088 	         "threshold for percentage of binary variables required to start",
1089 	         &heurdata->binvarquot, TRUE, DEFAULT_BINVARQUOT, 0.0, 1.0, NULL, NULL) );
1090 	
1091 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lpitersquot",
1092 	            "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1093 	            &heurdata->lpitersquot, TRUE, DEFAULT_LPITERSQUOT, 0.0, 1.0, NULL, NULL) );
1094 	
1095 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
1096 	         "minimum primal-dual gap for which the heuristic is executed",
1097 	         &heurdata->mingap, TRUE, DEFAULT_MINGAP, 0.0, SCIPinfinity(scip), NULL, NULL) );
1098 	
1099 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
1100 	         "should uct node selection be used at the beginning of the search?",
1101 	         &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
1102 	
1103 	   return SCIP_OKAY;
1104 	}
1105