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_completesol.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  COMPLETESOL - primal heuristic trying to complete given partial solutions
28   	 * @author Jakob Witzig
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/cons_linear.h"
35   	#include "scip/heur_completesol.h"
36   	#include "scip/pub_event.h"
37   	#include "scip/pub_heur.h"
38   	#include "scip/pub_message.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/pub_sol.h"
41   	#include "scip/pub_var.h"
42   	#include "scip/scip_branch.h"
43   	#include "scip/scip_cons.h"
44   	#include "scip/scip_copy.h"
45   	#include "scip/scip_event.h"
46   	#include "scip/scip_general.h"
47   	#include "scip/scip_heur.h"
48   	#include "scip/scip_mem.h"
49   	#include "scip/scip_message.h"
50   	#include "scip/scip_nlp.h"
51   	#include "scip/scip_nodesel.h"
52   	#include "scip/scip_numerics.h"
53   	#include "scip/scip_param.h"
54   	#include "scip/scip_prob.h"
55   	#include "scip/scip_probing.h"
56   	#include "scip/scip_sol.h"
57   	#include "scip/scip_solve.h"
58   	#include "scip/scip_solvingstats.h"
59   	#include "scip/scip_timing.h"
60   	#include "scip/scip_tree.h"
61   	#include "scip/scip_var.h"
62   	#include <string.h>
63   	
64   	#define HEUR_NAME             "completesol"
65   	#define HEUR_DESC             "primal heuristic trying to complete given partial solutions"
66   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
67   	#define HEUR_PRIORITY         0
68   	#define HEUR_FREQ             0
69   	#define HEUR_FREQOFS          0
70   	#define HEUR_MAXDEPTH         0
71   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
72   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
73   	
74   	/* default values for heuristic plugins */
75   	#define DEFAULT_MAXNODES      5000LL    /**< maximum number of nodes to regard in the subproblem */
76   	#define DEFAULT_MAXUNKRATE    0.85      /**< maximum percentage of unknown solution values */
77   	#define DEFAULT_ADDALLSOLS   FALSE      /**< should all subproblem solutions be added to the original SCIP? */
78   	#define DEFAULT_MINNODES      50LL      /**< minimum number of nodes to regard in the subproblem */
79   	#define DEFAULT_NODESOFS      500LL     /**< number of nodes added to the contingent of the total nodes */
80   	#define DEFAULT_NODESQUOT     0.1       /**< subproblem nodes in relation to nodes of the original problem */
81   	#define DEFAULT_LPLIMFAC      2.0       /**< factor by which the limit on the number of LP depends on the node limit */
82   	#define DEFAULT_OBJWEIGHT     1.0       /**< weight of the original objective function (1: only original objective) */
83   	#define DEFAULT_BOUNDWIDENING 0.1       /**< bound widening factor applied to continuous variables
84   	                                         *   (0: round bounds to next integer, 1: relax to global bounds)
85   	                                         */
86   	#define DEFAULT_MINIMPROVE    0.01      /**< factor by which the incumbent should be improved at least */
87   	#define DEFAULT_MINOBJWEIGHT 1e-3       /**< minimal weight for original objective function (zero could lead to infinite solutions) */
88   	#define DEFAULT_IGNORECONT  FALSE       /**< should solution values for continuous variables be ignored? */
89   	#define DEFAULT_BESTSOLS        5       /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
90   	#define DEFAULT_MAXPROPROUNDS  10       /**< maximal number of iterations in propagation (-1: no limit) */
91   	#define DEFAULT_MAXLPITER      -1LL     /**< maximal number of LP iterations (-1: no limit) */
92   	#define DEFAULT_MAXCONTVARS    -1       /**< maximal number of continuous variables after presolving (-1: no limit) */
93   	#define DEFAULT_BEFOREPRESOL  TRUE      /**< should the heuristic run before presolving? */
94   	
95   	/* event handler properties */
96   	#define EVENTHDLR_NAME         "Completesol"
97   	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
98   	
99   	
100  	/** primal heuristic data */
101  	struct SCIP_HeurData
102  	{
103  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem */
104  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem */
105  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes */
106  	   SCIP_Longint          maxlpiter;          /**< maximal number of LP iterations (-1: no limit) */
107  	   SCIP_Real             maxunknownrate;     /**< maximal rate of changed coefficients in the objective function */
108  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
109  	   SCIP_Real             nodelimit;          /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
110  	   SCIP_Real             lplimfac;           /**< factor by which the limit on the number of LP depends on the node limit */
111  	   SCIP_Real             objweight;          /**< weight of the original objective function (1: only original obj, 0: try to keep to given solution) */
112  	   SCIP_Real             boundwidening;      /**< bound widening factor applied to continuous variables
113  	                                              *   (0: fix variables to given solution values, 1: relax to global bounds)
114  	                                              */
115  	   SCIP_Real             minimprove;         /**< factor by which the incumbent should be improved at least */
116  	   SCIP_Bool             addallsols;         /**< should all subproblem solutions be added to the original SCIP? */
117  	   SCIP_Bool             ignorecont;         /**< should solution values for continuous variables be ignored? */
118  	   SCIP_Bool             beforepresol;       /**< should the heuristic run before presolving? */
119  	   int                   bestsols;           /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */
120  	   int                   maxcontvars;        /**< maximal number of continuous variables after presolving (-1: no limit) */
121  	   int                   maxproprounds;      /**< maximal number of iterations in propagation (-1: no limit) */
122  	};
123  	
124  	/* ---------------- Callback methods of event handler ---------------- */
125  	
126  	/* exec the event handler
127  	 *
128  	 * we interrupt the solution process
129  	 */
130  	static
131  	SCIP_DECL_EVENTEXEC(eventExecCompletesol)
132  	{
133  	   SCIP_HEURDATA* heurdata;
134  	
135  	   assert(eventhdlr != NULL);
136  	   assert(eventdata != NULL);
137  	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
138  	   assert(event != NULL);
139  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
140  	
141  	   heurdata = (SCIP_HEURDATA*)eventdata;
142  	   assert(heurdata != NULL);
143  	
144  	   /* interrupt solution process of sub-SCIP */
145  	   if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
146  	   {
147  	      SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
148  	      SCIP_CALL( SCIPinterruptSolve(scip) );
149  	   }
150  	
151  	   return SCIP_OKAY;
152  	}
153  	
154  	/** creates a subproblem by fixing a number of variables */
155  	static
156  	SCIP_RETCODE createSubproblem(
157  	   SCIP*                 scip,               /**< original SCIP data structure */
158  	   SCIP*                 subscip,            /**< SCIP data structure for the subproblem */
159  	   SCIP_HEURDATA*        heurdata,           /**< heuristic's private data structure */
160  	   SCIP_VAR**            subvars,            /**< the variables of the subproblem */
161  	   SCIP_SOL*             partialsol,         /**< partial solution */
162  	   SCIP_Bool*            tightened           /**< array to store for which variables we have found bound tightenings */
163  	   )
164  	{
165  	   SCIP_VAR** vars;
166  	   SCIP_CONS* objcons;
167  	   SCIP_Real epsobj;
168  	   SCIP_Real cutoff;
169  	   SCIP_Real upperbound;
170  	   char consobjname[SCIP_MAXSTRLEN];
171  	   int nvars;
172  	   int i;
173  	
174  	   assert(scip != NULL);
175  	   assert(subscip != NULL);
176  	   assert(subvars != NULL);
177  	   assert(heurdata != NULL);
178  	
179  	   /* if there is already a solution, add an objective cutoff */
180  	   if( SCIPgetNSols(scip) > 0 )
181  	   {
182  	      assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
183  	
184  	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
185  	
186  	      if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
187  	         cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
188  	      else
189  	      {
190  	         if( SCIPgetUpperbound(scip) >= 0 )
191  	            cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
192  	         else
193  	            cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
194  	      }
195  	      cutoff = MIN(upperbound, cutoff);
196  	      SCIPdebugMsg(scip, "set cutoff=%g for sub-SCIP\n", cutoff);
197  	   }
198  	   else
199  	      cutoff = SCIPinfinity(scip);
200  	
201  	   /* calculate objective coefficients for all potential epsilons */
202  	   if( SCIPisEQ(scip, heurdata->objweight, 1.0) )
203  	      return SCIP_OKAY;
204  	   else if( !SCIPisInfinity(scip, cutoff) )
205  	      epsobj = 1.0;
206  	   else
207  	   {
208  	      /* divide by objweight to avoid changing objective coefficient of original problem variables */
209  	      epsobj = (1.0 - heurdata->objweight)/heurdata->objweight;
210  	
211  	      /* scale with -1 if we have a maximization problem */
212  	      if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE )
213  	         epsobj *= -1.0;
214  	   }
215  	
216  	   /* get active variables */
217  	   vars = SCIPgetVars(scip);
218  	   nvars = SCIPgetNVars(scip);
219  	
220  	   objcons = NULL;
221  	
222  	   /* add constraints to measure the distance to the given partial solution */
223  	   for( i = 0; i < nvars; i++ )
224  	   {
225  	      SCIP_Real solval;
226  	      int idx;
227  	
228  	      assert(SCIPvarIsActive(vars[i]));
229  	
230  	      if( subvars[i] == NULL )
231  	         continue;
232  	
233  	      /* add objective function as a constraint, if a primal bound exists */
234  	      if( SCIPisInfinity(scip, cutoff) )
235  	      {
236  	         /* create the constraints */
237  	         if( objcons == NULL )
238  	         {
239  	            SCIP_Real lhs;
240  	            SCIP_Real rhs;
241  	
242  	            if( SCIPgetObjsense(subscip) == SCIP_OBJSENSE_MINIMIZE )
243  	            {
244  	               lhs = -SCIPinfinity(subscip);
245  	               rhs = cutoff;
246  	            }
247  	            else
248  	            {
249  	               lhs = cutoff;
250  	               rhs = SCIPinfinity(subscip);
251  	            }
252  	
253  	            (void)SCIPsnprintf(consobjname, SCIP_MAXSTRLEN, "obj");
254  	            SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, consobjname, 0, NULL, NULL, lhs, rhs) );
255  	         }
256  	
257  	         /* add the variable to the constraints */
258  	         SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(subvars[i])) );
259  	
260  	         /* set objective coefficient to 0.0 */
261  	         SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
262  	      }
263  	
264  	      solval = SCIPgetSolVal(scip, partialsol, vars[i]);
265  	
266  	      /* skip variables with unknown solution value */
267  	      if( solval == SCIP_UNKNOWN ) /*lint !e777*/
268  	         continue;
269  	
270  	      idx = SCIPvarGetProbindex(vars[i]);
271  	      assert(idx >= 0);
272  	
273  	      /* skip variables where we already found some bound tightenings */
274  	      if( tightened[idx] == FALSE )
275  	      {
276  	         /* special case: vars[i] is binary; we do not add an extra variable, but we mimic the behavior we would get with it.
277  	          * E.g., if the solval is 0.3, setting the variable to 0 would give a cost of 0.3 * epsobj, setting it to 1 gives
278  	          * 0.7 * epsobj. Thus, 0.3 * epsobj can be treated as a constant in the objective function and the variable gets
279  	          * an objective coefficient of 0.4 * epsobj.
280  	          */
281  	         if( SCIPvarIsBinary(vars[i]) )
282  	         {
283  	            SCIP_Real frac = SCIPfeasFrac(scip, solval);
284  	            SCIP_Real objcoef;
285  	
286  	            frac = MIN(frac, 1-frac);
287  	            objcoef = (1 - 2*frac) * epsobj * (int)SCIPgetObjsense(scip);
288  	
289  	            if( solval > 0.5 )
290  	            {
291  	               SCIP_CALL( SCIPchgVarObj(scip, vars[i], -objcoef) );
292  	            }
293  	            else
294  	            {
295  	               SCIP_CALL( SCIPchgVarObj(scip, vars[i], objcoef) );
296  	            }
297  	         }
298  	         else
299  	         {
300  	            SCIP_CONS* conspos;
301  	            SCIP_CONS* consneg;
302  	            SCIP_VAR* eps;
303  	            char consnamepos[SCIP_MAXSTRLEN];
304  	            char consnameneg[SCIP_MAXSTRLEN];
305  	            char epsname[SCIP_MAXSTRLEN];
306  	
307  	            /* create two new variables */
308  	            (void)SCIPsnprintf(epsname, SCIP_MAXSTRLEN, "eps_%s", SCIPvarGetName(subvars[i]));
309  	
310  	            SCIP_CALL( SCIPcreateVarBasic(subscip, &eps, epsname, 0.0, SCIPinfinity(scip), epsobj, SCIP_VARTYPE_CONTINUOUS) );
311  	            SCIP_CALL( SCIPaddVar(subscip, eps) );
312  	
313  	            /* create two constraints */
314  	            (void)SCIPsnprintf(consnamepos, SCIP_MAXSTRLEN, "cons_%s_pos", SCIPvarGetName(subvars[i]));
315  	            (void)SCIPsnprintf(consnameneg, SCIP_MAXSTRLEN, "cons_%s_neq", SCIPvarGetName(subvars[i]));
316  	
317  	            /* x_{i} - s_{i} <= e_{i}   <==>   x_{i} - e_{i} <= s_{i} */
318  	            SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &conspos, consnamepos, 0, NULL, NULL, -SCIPinfinity(scip), solval) );
319  	            SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, subvars[i], 1.0) );
320  	            SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, eps, -1.0) );
321  	            SCIP_CALL( SCIPaddCons(subscip, conspos) );
322  	            SCIP_CALL( SCIPreleaseCons(subscip, &conspos) );
323  	
324  	            /* s_{i} - x_{i} <= e_{i}   <==>   e_{i} - x_{i} >= s_{i} */
325  	            SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &consneg, consnameneg, 0, NULL, NULL, solval, SCIPinfinity(scip)) );
326  	            SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, subvars[i], -1.0) );
327  	            SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, eps, 1.0) );
328  	            SCIP_CALL( SCIPaddCons(subscip, consneg) );
329  	            SCIP_CALL( SCIPreleaseCons(subscip, &consneg) );
330  	
331  	            /* release the variables */
332  	            SCIP_CALL( SCIPreleaseVar(subscip, &eps) );
333  	         }
334  	      }
335  	   }
336  	
337  	   /* add and release the constraint representing the original objective function */
338  	   if( objcons != NULL )
339  	   {
340  	      SCIP_CALL( SCIPaddCons(subscip, objcons) );
341  	      SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
342  	   }
343  	
344  	   return SCIP_OKAY;
345  	}
346  	
347  	/** perform a probing bound change or fixes the variable */
348  	static
349  	SCIP_RETCODE chgProbingBound(
350  	   SCIP*                 scip,               /**< original SCIP data structure */
351  	   SCIP_VAR*             var,                /**< problem variable */
352  	   SCIP_Real             newval,             /**< new bound */
353  	   SCIP_BRANCHDIR        branchdir,          /**< bound change direction */
354  	   SCIP_Bool*            success             /**< pointer to store whether the bound could be tightened */
355  	   )
356  	{
357  	   SCIP_Real ub;
358  	   SCIP_Real lb;
359  	
360  	   assert(scip != NULL);
361  	   assert(var != NULL);
362  	
363  	   (*success) = FALSE;
364  	
365  	   ub = SCIPvarGetUbLocal(var);
366  	   lb = SCIPvarGetLbLocal(var);
367  	
368  	   switch (branchdir) {
369  	   case SCIP_BRANCHDIR_DOWNWARDS:
370  	      if( SCIPisLT(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
371  	      {
372  	         SCIP_CALL( SCIPchgVarUbProbing(scip, var, newval) );
373  	         (*success) = TRUE;
374  	      }
375  	      break;
376  	   case SCIP_BRANCHDIR_UPWARDS:
377  	      if( SCIPisLE(scip, newval, ub) && SCIPisGT(scip, newval, lb) )
378  	      {
379  	         SCIP_CALL( SCIPchgVarLbProbing(scip, var, newval) );
380  	         (*success) = TRUE;
381  	      }
382  	      break;
383  	   case SCIP_BRANCHDIR_FIXED:
384  	      if( SCIPisLE(scip, newval, ub) && SCIPisGE(scip, newval, lb) )
385  	      {
386  	         SCIP_CALL( SCIPfixVarProbing(scip, var, newval) );
387  	         (*success) = TRUE;
388  	      }
389  	      break;
390  	   default:
391  	      return SCIP_INVALIDDATA;
392  	   }/*lint !e788*/
393  	
394  	   return SCIP_OKAY;
395  	}
396  	
397  	/** tries variables bound changes guided by the given solution */
398  	static
399  	SCIP_RETCODE tightenVariables(
400  	   SCIP*                 scip,               /**< original SCIP data structure */
401  	   SCIP_HEURDATA*        heurdata,           /**< heuristic's private data structure */
402  	   SCIP_VAR**            vars,               /**< problem variables */
403  	   int                   nvars,              /**< number of problem variables */
404  	   SCIP_SOL*             sol,                /**< solution to guide the bound changes */
405  	   SCIP_Bool*            tightened,          /**< array to store if variable bound could be tightened */
406  	   SCIP_Bool*            infeasible          /**< pointer to store whether subproblem is infeasible */
407  	   )
408  	{
409  	#ifndef NDEBUG
410  	   SCIP_Bool incontsection;
411  	#endif
412  	   SCIP_Bool abortearly;
413  	   SCIP_Bool cutoff;
414  	   SCIP_Bool probingsuccess;
415  	   SCIP_Longint ndomreds;
416  	   SCIP_Longint ndomredssum;
417  	   int nbndtightenings;
418  	   int v;
419  	
420  	   assert(scip != NULL);
421  	   assert(heurdata != NULL);
422  	   assert(vars != NULL);
423  	   assert(nvars >= 0);
424  	   assert(sol != NULL);
425  	   assert(tightened != NULL);
426  	
427  	   assert(SCIPsolGetOrigin(sol) == SCIP_SOLORIGIN_PARTIAL);
428  	
429  	   SCIPdebugMsg(scip, "> start probing along the solution values\n");
430  	
431  	   *infeasible = FALSE;
432  	   abortearly = FALSE;
433  	   nbndtightenings = 0;
434  	   ndomredssum = 0;
435  	#ifndef NDEBUG
436  	   incontsection = FALSE;
437  	#endif
438  	
439  	   /* there is at least one integral variable; open one probing node for all non-continuous variables */
440  	   if( nvars - SCIPgetNContVars(scip) > 0 )
441  	   {
442  	      SCIP_CALL( SCIPnewProbingNode(scip) );
443  	   }
444  	
445  	   for( v = 0; v < nvars && !abortearly; v++ )
446  	   {
447  	      SCIP_Real solval;
448  	
449  	      assert(SCIPvarIsActive(vars[v]));
450  	
451  	      cutoff = FALSE;
452  	      ndomreds = 0;
453  	
454  	#ifndef NDEBUG
455  	      incontsection |= (!SCIPvarIsIntegral(vars[v])); /*lint !e514*/
456  	      assert(!incontsection || !SCIPvarIsIntegral(vars[v]));
457  	#endif
458  	
459  	      /* return if we have found enough domain reductions tightenings */
460  	      if( ndomredssum > 0.3*nvars )
461  	         break;
462  	
463  	      solval = SCIPgetSolVal(scip, sol, vars[v]);
464  	
465  	      /* skip unknown variables */
466  	      if( solval == SCIP_UNKNOWN ) /*lint !e777*/
467  	         continue;
468  	      assert(!SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval));
469  	
470  	      /* variable is binary or integer */
471  	      if( SCIPvarIsIntegral(vars[v]) )
472  	      {
473  	         /* the solution value is integral, try to fix them */
474  	         if( SCIPisIntegral(scip, solval) )
475  	         {
476  	            SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
477  	            tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
478  	            ++nbndtightenings;
479  	
480  	#ifdef SCIP_MORE_DEBUG
481  	               SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g \n", SCIPvarGetName(vars[v]),
482  	                     SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval);
483  	#endif
484  	         }
485  	         else
486  	         {
487  	            SCIP_Real ub = SCIPceil(scip, solval) + 1.0;
488  	            SCIP_Real lb = SCIPfloor(scip, solval) - 1.0;
489  	
490  	            /* try tightening of upper bound */
491  	            if( SCIPisLT(scip, ub, SCIPvarGetUbLocal(vars[v])) )
492  	            {
493  	               SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
494  	               tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
495  	               ++nbndtightenings;
496  	
497  	#ifdef SCIP_MORE_DEBUG
498  	               SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
499  	                     SCIPvarGetUbGlobal(vars[v]), ub);
500  	#endif
501  	            }
502  	
503  	            /* try tightening of lower bound */
504  	            if( SCIPisGT(scip, lb, SCIPvarGetLbLocal(vars[v])) )
505  	            {
506  	               SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
507  	               tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
508  	               ++nbndtightenings;
509  	
510  	#ifdef SCIP_MORE_DEBUG
511  	               SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]),
512  	                     SCIPvarGetLbGlobal(vars[v]), ub);
513  	#endif
514  	            }
515  	         }
516  	      }
517  	      /* variable is continuous */
518  	      else
519  	      {
520  	         /* fix to lb or ub */
521  	         if( SCIPisEQ(scip, solval, SCIPvarGetLbLocal(vars[v])) || SCIPisEQ(scip, solval, SCIPvarGetUbLocal(vars[v])) )
522  	         {
523  	            /* open a new probing node */
524  	            if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
525  	            {
526  	               SCIP_CALL( SCIPnewProbingNode(scip) );
527  	
528  	               SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) );
529  	
530  	               /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
531  	                * domain propagation
532  	                */
533  	               if( probingsuccess )
534  	               {
535  	                  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
536  	               }
537  	
538  	               if( cutoff )
539  	               {
540  	                  ndomreds = 0;
541  	                  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
542  	               }
543  	               else
544  	               {
545  	                  assert(SCIPvarGetProbindex(vars[v]) >= 0);
546  	                  tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
547  	                  ++nbndtightenings;
548  	#ifdef SCIP_MORE_DEBUG
549  	                  SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g (ndomreds=%lld)\n", SCIPvarGetName(vars[v]),
550  	                        SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval, ndomreds);
551  	#endif
552  	               }
553  	            }
554  	            else
555  	               /* abort probing */
556  	               abortearly = TRUE;
557  	         }
558  	         else
559  	         {
560  	            SCIP_Real offset;
561  	            SCIP_Real newub = SCIPvarGetUbGlobal(vars[v]);
562  	            SCIP_Real newlb = SCIPvarGetLbGlobal(vars[v]);
563  	
564  	            /* both bound are finite */
565  	            if( !SCIPisInfinity(scip, -newlb) && !SCIPisInfinity(scip, newub) )
566  	               offset = REALABS(heurdata->boundwidening * (newub-newlb));
567  	            else
568  	            {
569  	               offset = 0.0;
570  	
571  	               /* if exactly one bound is finite, widen bound w.r.t. solution value and finite bound */
572  	               if( !SCIPisInfinity(scip, -newlb) )
573  	                  offset = REALABS(heurdata->boundwidening * (solval-newlb));
574  	               else if( !SCIPisInfinity(scip, newub) )
575  	                  offset = REALABS(heurdata->boundwidening * (newub-solval));
576  	            }
577  	
578  	            /* update bounds */
579  	            newub = SCIPceil(scip, solval) + offset;
580  	            newlb = SCIPfloor(scip, solval) - offset;
581  	
582  	            /* try tightening of upper bound */
583  	            if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(vars[v])) )
584  	            {
585  	               /* open a new probing node */
586  	               if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
587  	               {
588  	                  SCIP_CALL( SCIPnewProbingNode(scip) );
589  	                  SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
590  	
591  	                  /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
592  	                   * domain propagation
593  	                   */
594  	                  if( probingsuccess )
595  	                  {
596  	                     SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
597  	                  }
598  	
599  	                  if( cutoff )
600  	                  {
601  	                     ndomreds = 0;
602  	
603  	                     /* backtrack to last feasible probing node */
604  	                     SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
605  	
606  	                     /* we can tighten the lower bound by newub */
607  	                     SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
608  	
609  	                     /* propagate the new bound */
610  	                     SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
611  	
612  	                     /* there is no feasible solution w.r.t. the current bounds */
613  	                     if( cutoff )
614  	                     {
615  	                        SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
616  	                        *infeasible = TRUE;
617  	                        return SCIP_OKAY;
618  	                     }
619  	#ifdef SCIP_MORE_DEBUG
620  	                     SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n",
621  	                           SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newub);
622  	#endif
623  	                  }
624  	                  else
625  	                  {
626  	                     assert(SCIPvarGetProbindex(vars[v]) >= 0);
627  	                     tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
628  	                     ++nbndtightenings;
629  	#ifdef SCIP_MORE_DEBUG
630  	                     SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
631  	                           SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newub, ndomreds);
632  	#endif
633  	                  }
634  	               }
635  	               else
636  	                  /* abort probing */
637  	                  abortearly = TRUE;
638  	            }
639  	
640  	            /* try tightening of lower bound */
641  	            if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(vars[v])) )
642  	            {
643  	               /* open a new probing node */
644  	               if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 )
645  	               {
646  	                  SCIP_CALL( SCIPnewProbingNode(scip) );
647  	                  SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) );
648  	
649  	                  /* skip propagation if the bound could not be changed, e.g., already tightened due to previous
650  	                   * domain propagation
651  	                   */
652  	                  if( probingsuccess )
653  	                  {
654  	                     SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, &ndomreds) );
655  	                  }
656  	
657  	                  if( cutoff )
658  	                  {
659  	                     ndomreds = 0;
660  	
661  	                     /* backtrack to last feasible probing node */
662  	                     SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
663  	
664  	                     /* we can tighten the upper bound by newlb */
665  	                     SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) );
666  	
667  	                     /* propagate the new bound */
668  	                     SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
669  	
670  	                     /* there is no feasible solution w.r.t. the current bounds */
671  	                     if( cutoff )
672  	                     {
673  	                        SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n");
674  	                        *infeasible = TRUE;
675  	                        return SCIP_OKAY;
676  	                     }
677  	#ifdef SCIP_MORE_DEBUG
678  	                     SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n",
679  	                           SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newlb);
680  	#endif
681  	                  }
682  	                  else
683  	                  {
684  	                     assert(SCIPvarGetProbindex(vars[v]) >= 0);
685  	                     tightened[SCIPvarGetProbindex(vars[v])] = TRUE;
686  	                     ++nbndtightenings;
687  	#ifdef SCIP_MORE_DEBUG
688  	                     SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
689  	                           SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newlb, ndomreds);
690  	#endif
691  	                  }
692  	               }
693  	               else
694  	                  /* abort probing */
695  	                  abortearly = TRUE;
696  	            }
697  	         }
698  	      }
699  	
700  	      ndomredssum += ndomreds;
701  	   }
702  	
703  	   SCIPdebugMsg(scip, "> found %d bound tightenings and %lld induced domain reductions (abort=%u).\n", nbndtightenings,
704  	         ndomredssum, abortearly);
705  	
706  	   return SCIP_OKAY;
707  	}
708  	
709  	/* setup and solve the sub-SCIP */
710  	static
711  	SCIP_RETCODE setupAndSolve(
712  	   SCIP*                 scip,               /**< original SCIP data structure */
713  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
714  	   SCIP_HEUR*            heur,               /**< heuristic data structure */
715  	   SCIP_HEURDATA*        heurdata,           /**< heuristic's private data structure */
716  	   SCIP_RESULT*          result,             /**< result data structure */
717  	   SCIP_Longint          nstallnodes,        /**< number of stalling nodes for the subproblem */
718  	   SCIP_SOL*             partialsol,         /**< partial solution */
719  	   SCIP_Bool*            tightened           /**< array to store whether a variable was already tightened */
720  	   )
721  	{
722  	   SCIP_HASHMAP* varmapf;
723  	   SCIP_VAR** vars;
724  	   SCIP_VAR** subvars = NULL;
725  	   SCIP_EVENTHDLR* eventhdlr;
726  	   int nvars;
727  	   int i;
728  	
729  	   SCIP_SOL** subsols;
730  	   int nsubsols;
731  	
732  	   SCIP_Bool valid;
733  	   SCIP_Bool success;
734  	   SCIP_RETCODE retcode;
735  	
736  	   assert(scip != NULL);
737  	   assert(subscip != NULL);
738  	   assert(heur != NULL);
739  	   assert(heurdata != NULL);
740  	   assert(result != NULL);
741  	   assert(partialsol != NULL);
742  	
743  	   vars = SCIPgetVars(scip);
744  	   nvars = SCIPgetNVars(scip);
745  	
746  	   /* create the variable mapping hash map */
747  	   SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(subscip), nvars) );
748  	
749  	   eventhdlr = NULL;
750  	   valid = FALSE;
751  	
752  	   /* copy complete SCIP instance */
753  	   SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapf, NULL, "completesol", NULL, NULL, 0, FALSE, FALSE, FALSE,
754  	         TRUE, &valid) );
755  	   SCIPdebugMsg(scip, "Copying the SCIP instance returned with valid=%u.\n", valid);
756  	
757  	   /* create event handler for LP events */
758  	   SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCompletesol, NULL) );
759  	   if( eventhdlr == NULL )
760  	   {
761  	      SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
762  	      return SCIP_PLUGINNOTFOUND;
763  	   }
764  	
765  	   /* allocate memory to align the SCIP and the sub-SCIP variables */
766  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
767  	
768  	   /* map all variables */
769  	   for( i = 0; i < nvars; i++ )
770  	     subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapf, vars[i]);
771  	
772  	   /* free hash map */
773  	   SCIPhashmapFree(&varmapf);
774  	
775  	   /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
776  	   SCIP_CALL( createSubproblem(scip, subscip, heurdata, subvars, partialsol, tightened) );
777  	   SCIPdebugMsg(scip, "Completesol subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
778  	
779  	   /* do not abort subproblem on CTRL-C */
780  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
781  	
782  	#ifdef SCIP_DEBUG
783  	   /* for debugging, enable full output */
784  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", SCIP_VERBLEVEL_FULL) );
785  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
786  	#else
787  	   /* disable statistic timing inside sub SCIP and output to console */
788  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) );
789  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
790  	#endif
791  	
792  	   /* set limits for the subproblem */
793  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
794  	   heurdata->nodelimit = heurdata->maxnodes;
795  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
796  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
797  	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsols) );
798  	
799  	   /* limit the number of LP iterations */
800  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", heurdata->maxlpiter) );
801  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiter) );
802  	
803  	   /* forbid recursive call of heuristics and separators solving sub-SCIPs */
804  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
805  	
806  	   /* disable cutting plane separation */
807  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
808  	
809  	   /* disable expensive presolving */
810  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
811  	
812  	   /* use best estimate node selection */
813  	   if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
814  	   {
815  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
816  	   }
817  	
818  	   /* use inference branching */
819  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
820  	   {
821  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
822  	   }
823  	
824  	   /* disable conflict analysis */
825  	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
826  	   {
827  	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
828  	   }
829  	
830  	   /* speed up sub-SCIP by not checking dual LP feasibility */
831  	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
832  	
833  	   SCIP_CALL( SCIPtransformProb(subscip) );
834  	   SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
835  	
836  	   /* solve the subproblem */
837  	   SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
838  	
839  	   /* errors in solving the subproblem should not kill the overall solving process;
840  	    * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
841  	    */
842  	
843  	   retcode = SCIPpresolve(subscip);
844  	
845  	   /* errors in presolving the subproblem should not kill the overall solving process;
846  	    * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
847  	    */
848  	   if( retcode != SCIP_OKAY )
849  	   {
850  	      SCIPwarningMessage(scip, "Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
851  	
852  	      SCIPABORT(); /*lint --e{527}*/
853  	
854  	      goto TERMINATE;
855  	   }
856  	
857  	   if( SCIPgetStage(subscip) == SCIP_STAGE_PRESOLVED )
858  	   {
859  	      SCIPdebugMsg(scip, "presolved instance has bin=%d, int=%d, cont=%d variables\n",
860  	            SCIPgetNBinVars(subscip), SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip));
861  	
862  	      /* check whether the presolved instance is small enough */
863  	      if( heurdata->maxcontvars >= 0 && SCIPgetNContVars(subscip) > heurdata->maxcontvars )
864  	      {
865  	         SCIPdebugMsg(scip, "presolved instance has too many continuous variables (maxcontvars: %d)\n", heurdata->maxcontvars);
866  	         goto TERMINATE;
867  	      }
868  	
869  	      /* set node limit of 1 if the presolved problem is an LP, otherwise we would start branching if an LP iteration
870  	       * limit was set by the user.
871  	       */
872  	      if( !SCIPisNLPEnabled(subscip) && SCIPgetNContVars(subscip) == SCIPgetNVars(subscip) )
873  	      {
874  	         SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
875  	      }
876  	
877  	      retcode = SCIPsolve(subscip);
878  	
879  	      /* errors in solving the subproblem should not kill the overall solving process;
880  	       * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
881  	       */
882  	      if( retcode != SCIP_OKAY )
883  	      {
884  	         SCIPwarningMessage(scip, "Error while solving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode);
885  	
886  	         SCIPABORT(); /*lint --e{527}*/
887  	
888  	         goto TERMINATE;
889  	      }
890  	   }
891  	
892  	   SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
893  	
894  	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
895  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
896  	
897  	   /* check, whether a solution was found;
898  	    * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
899  	    */
900  	   nsubsols = SCIPgetNSols(subscip);
901  	   subsols = SCIPgetSols(subscip);
902  	   success = FALSE;
903  	   for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ )
904  	   {
905  	      SCIP_SOL* newsol;
906  	
907  	      /* create new solution, try to add to SCIP, and free it immediately */
908  	      SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
909  	      SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
910  	
911  	      if( success )
912  	         *result = SCIP_FOUNDSOL;
913  	   }
914  	
915  	   SCIPstatisticPrintf("%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n",
916  	      HEUR_NAME, 0.0, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip),
917  	      nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
918  	
919  	   /* print message if the completion of a partial solution failed */
920  	   if( *result != SCIP_FOUNDSOL )
921  	   {
922  	      switch( SCIPgetStatus(subscip) )
923  	      {
924  	      case SCIP_STATUS_INFEASIBLE:
925  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n");
926  	         break;
927  	      case SCIP_STATUS_NODELIMIT:
928  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (node limit exceeded)\n");
929  	         break;
930  	      case SCIP_STATUS_TIMELIMIT:
931  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (time limit exceeded)\n");
932  	         break;
933  	      case SCIP_STATUS_MEMLIMIT:
934  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (memory limit exceeded)\n");
935  	         break;
936  	      default:
937  	         break;
938  	      } /*lint !e788*/
939  	   }
940  	
941  	TERMINATE:
942  	   SCIPfreeBufferArray(scip, &subvars);
943  	
944  	   return SCIP_OKAY;
945  	}
946  	
947  	/** main procedure of the completesol heuristic, creates and solves a sub-SCIP */
948  	static
949  	SCIP_RETCODE applyCompletesol(
950  	   SCIP*                 scip,               /**< original SCIP data structure */
951  	   SCIP_HEUR*            heur,               /**< heuristic data structure */
952  	   SCIP_HEURDATA*        heurdata,           /**< heuristic's private data structure */
953  	   SCIP_RESULT*          result,             /**< result data structure */
954  	   SCIP_Longint          nstallnodes,        /**< number of stalling nodes for the subproblem */
955  	   SCIP_SOL*             partialsol          /**< partial solution */
956  	   )
957  	{
958  	   SCIP* subscip;
959  	   SCIP_VAR** vars;
960  	   SCIP_Bool* tightened;
961  	   SCIP_Bool infeasible;
962  	   SCIP_Bool success;
963  	   SCIP_RETCODE retcode;
964  	   int nvars;
965  	
966  	   assert(scip != NULL);
967  	   assert(heur != NULL);
968  	   assert(heurdata != NULL);
969  	   assert(result != NULL);
970  	   assert(partialsol != NULL);
971  	
972  	   *result = SCIP_DIDNOTRUN;
973  	
974  	   SCIPdebugMsg(scip, "+---+ Start Completesol heuristic +---+\n");
975  	
976  	   /* check whether there is enough time and memory left */
977  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
978  	
979  	   if( !success )
980  	      return SCIP_OKAY;
981  	
982  	   *result = SCIP_DIDNOTFIND;
983  	
984  	   /* get variable data */
985  	   vars = SCIPgetVars(scip);
986  	   nvars = SCIPgetNVars(scip);
987  	
988  	   /* get buffer memory and initialize it to FALSE */
989  	   SCIP_CALL( SCIPallocClearBufferArray(scip, &tightened, nvars) );
990  	
991  	   SCIP_CALL( SCIPstartProbing(scip) );
992  	
993  	   SCIP_CALL( tightenVariables(scip, heurdata, vars, nvars, partialsol, tightened, &infeasible) );
994  	
995  	   if( infeasible )
996  	   {
997  	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n");
998  	      goto ENDPROBING;
999  	   }
1000 	
1001 	   /* initialize the subproblem */
1002 	   SCIP_CALL( SCIPcreate(&subscip) );
1003 	
1004 	   retcode = setupAndSolve(scip, subscip, heur, heurdata, result, nstallnodes, partialsol, tightened);
1005 	
1006 	   /* free subproblem */
1007 	   SCIP_CALL( SCIPfree(&subscip) );
1008 	
1009 	   SCIP_CALL( retcode );
1010 	
1011 	  ENDPROBING:
1012 	   SCIPfreeBufferArray(scip, &tightened);
1013 	   SCIP_CALL( SCIPendProbing(scip) );
1014 	
1015 	   return SCIP_OKAY;
1016 	}
1017 	
1018 	
1019 	/*
1020 	 * Callback methods of primal heuristic
1021 	 */
1022 	
1023 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1024 	static
1025 	SCIP_DECL_HEURCOPY(heurCopyCompletesol)
1026 	{  /*lint --e{715}*/
1027 	   assert(scip != NULL);
1028 	   assert(heur != NULL);
1029 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1030 	
1031 	   /* call inclusion method of primal heuristic */
1032 	   SCIP_CALL( SCIPincludeHeurCompletesol(scip) );
1033 	
1034 	   return SCIP_OKAY;
1035 	}
1036 	
1037 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1038 	static
1039 	SCIP_DECL_HEURFREE(heurFreeCompletesol)
1040 	{  /*lint --e{715}*/
1041 	   SCIP_HEURDATA* heurdata;
1042 	
1043 	   assert(heur != NULL);
1044 	   assert(scip != NULL);
1045 	
1046 	   /* get heuristic data */
1047 	   heurdata = SCIPheurGetData(heur);
1048 	   assert(heurdata != NULL);
1049 	
1050 	   /* free heuristic data */
1051 	   SCIPfreeBlockMemory(scip, &heurdata);
1052 	   SCIPheurSetData(heur, NULL);
1053 	
1054 	   return SCIP_OKAY;
1055 	}
1056 	
1057 	/** execution method of primal heuristic */
1058 	static
1059 	SCIP_DECL_HEUREXEC(heurExecCompletesol)
1060 	{/*lint --e{715}*/
1061 	   SCIP_HEURDATA* heurdata;
1062 	   SCIP_VAR** vars;
1063 	   SCIP_SOL** partialsols;
1064 	   SCIP_Longint nstallnodes;
1065 	   int npartialsols;
1066 	   int nunknown;
1067 	   int nfracints;
1068 	   int nvars;
1069 	   int s;
1070 	   int v;
1071 	
1072 	   assert( heur != NULL );
1073 	   assert( scip != NULL );
1074 	   assert( result != NULL );
1075 	
1076 	   *result = SCIP_DELAYED;
1077 	
1078 	   /* do not call heuristic of node was already detected to be infeasible */
1079 	   if( nodeinfeasible )
1080 	      return SCIP_OKAY;
1081 	
1082 	   /* get heuristic data */
1083 	   heurdata = SCIPheurGetData(heur);
1084 	   assert( heurdata != NULL );
1085 	
1086 	   *result = SCIP_DIDNOTRUN;
1087 	
1088 	   if( SCIPisStopped(scip) )
1089 	      return SCIP_OKAY;
1090 	
1091 	   /* do not run after restart */
1092 	   if( SCIPgetNRuns(scip) > 1 )
1093 	      return SCIP_OKAY;
1094 	
1095 	   /* check whether we want to run before presolving */
1096 	   if( (heurtiming & SCIP_HEURTIMING_BEFOREPRESOL) && !heurdata->beforepresol )
1097 	      return SCIP_OKAY;
1098 	
1099 	   /* only run before root node */
1100 	   if( (heurtiming & SCIP_HEURTIMING_BEFORENODE)
1101 	      && (heurdata->beforepresol || SCIPgetCurrentNode(scip) != SCIPgetRootNode(scip)) )
1102 	      return SCIP_OKAY;
1103 	
1104 	   /* get variable data and return of no variables are left in the problem */
1105 	   vars = SCIPgetVars(scip);
1106 	   nvars = SCIPgetNVars(scip);
1107 	
1108 	   if( nvars == 0 )
1109 	      return SCIP_OKAY;
1110 	
1111 	   /* calculate the maximal number of branching nodes until heuristic is aborted */
1112 	   nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1113 	
1114 	   /* reward Completesol if it succeeded often */
1115 	   nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1116 	   nstallnodes -= 100 * SCIPheurGetNCalls(heur);  /* count the setup costs for the sub-SCIP as 100 nodes */
1117 	   nstallnodes += heurdata->nodesofs;
1118 	
1119 	   /* determine the node limit for the current process */
1120 	   nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1121 	
1122 	   /* check whether we have enough nodes left to call subproblem solving */
1123 	   if( nstallnodes < heurdata->minnodes )
1124 	   {
1125 	      SCIPdebugMsg(scip, "skipping Complete: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n",
1126 	         nstallnodes, heurdata->minnodes);
1127 	      return SCIP_OKAY;
1128 	   }
1129 	
1130 	   /* check the number of variables with unknown value and continuous variables with fractional value */
1131 	   nfracints = 0;
1132 	
1133 	   /* get all partial sols */
1134 	   npartialsols = SCIPgetNPartialSols(scip);
1135 	   partialsols = SCIPgetPartialSols(scip);
1136 	
1137 	   /* loop over all partial solutions */
1138 	   for( s = 0; s < npartialsols; s++ )
1139 	   {
1140 	      SCIP_SOL* sol;
1141 	      SCIP_Real solval;
1142 	      SCIP_Real unknownrate;
1143 	
1144 	      sol = partialsols[s];
1145 	      assert(sol != NULL);
1146 	      assert(SCIPsolIsPartial(sol));
1147 	
1148 	      nunknown = 0;
1149 	      /* loop over all variables */
1150 	      for( v = 0; v < nvars; v++ )
1151 	      {
1152 	         assert(SCIPvarIsActive(vars[v]));
1153 	
1154 	         /* skip continuous variables if they should ignored */
1155 	         if( !SCIPvarIsIntegral(vars[v]) && heurdata->ignorecont )
1156 	            continue;
1157 	
1158 	         solval = SCIPgetSolVal(scip, sol, vars[v]);
1159 	
1160 	         /* we only want to count variables that are unfixed after the presolving */
1161 	         if( solval == SCIP_UNKNOWN ) /*lint !e777*/
1162 	            ++nunknown;
1163 	         else if( SCIPvarIsIntegral(vars[v]) && !SCIPisIntegral(scip, solval) )
1164 	            ++nfracints;
1165 	      }
1166 	
1167 	      if( heurdata->ignorecont )
1168 	         unknownrate = nunknown/((SCIP_Real)SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip));
1169 	      else
1170 	         unknownrate = nunknown/((SCIP_Real)nvars);
1171 	      SCIPdebugMsg(scip, "%d (rate %.4f) unknown solution values\n", nunknown, unknownrate);
1172 	
1173 	      /* run the heuristic, if not too many unknown variables exist */
1174 	      if( unknownrate > heurdata->maxunknownrate )
1175 	      {
1176 	         SCIPwarningMessage(scip, "ignore partial solution (%d) because unknown rate is too large (%g > %g)\n", s,
1177 	            unknownrate, heurdata->maxunknownrate);
1178 	         continue;
1179 	      }
1180 	
1181 	      /* all variables have a finite/known solution value all integer variables have an integral solution value,
1182 	       * and there are no continuous variables
1183 	       * in the sub-SCIP, all variables would be fixed, so create a new solution without solving a sub-SCIP
1184 	       */
1185 	      if( nunknown == 0 && nfracints == 0 && SCIPgetNContVars(scip) == 0 && SCIPgetNImplVars(scip) == 0 )
1186 	      {
1187 	         SCIP_SOL* newsol;
1188 	         SCIP_Bool stored;
1189 	
1190 	         assert(vars != NULL);
1191 	         assert(nvars >= 0);
1192 	
1193 	         SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1194 	
1195 	         for( v = 0; v < nvars; v++ )
1196 	         {
1197 	            solval = SCIPgetSolVal(scip, sol, vars[v]);
1198 	            assert(solval != SCIP_UNKNOWN); /*lint !e777*/
1199 	
1200 	            SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], solval) );
1201 	         }
1202 	
1203 	         SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
1204 	         if( stored )
1205 	            *result = SCIP_FOUNDSOL;
1206 	      }
1207 	      else
1208 	      {
1209 	         /* run the heuristic */
1210 	         SCIP_CALL( applyCompletesol(scip, heur, heurdata, result, nstallnodes, sol) );
1211 	      }
1212 	   }
1213 	
1214 	   return SCIP_OKAY;
1215 	}
1216 	
1217 	
1218 	/*
1219 	 * primal heuristic specific interface methods
1220 	 */
1221 	
1222 	/** creates the completesol primal heuristic and includes it in SCIP */
1223 	SCIP_RETCODE SCIPincludeHeurCompletesol(
1224 	   SCIP*                 scip                /**< SCIP data structure */
1225 	   )
1226 	{
1227 	   SCIP_HEURDATA* heurdata;
1228 	   SCIP_HEUR* heur;
1229 	
1230 	   /* create completesol primal heuristic data */
1231 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1232 	   assert(heurdata != NULL);
1233 	
1234 	   /* include primal heuristic */
1235 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1236 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1237 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCompletesol, heurdata) );
1238 	
1239 	   assert(heur != NULL);
1240 	
1241 	   /* set non fundamental callbacks via setter functions */
1242 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCompletesol) );
1243 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCompletesol) );
1244 	
1245 	   /* add completesol primal heuristic parameters */
1246 	
1247 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1248 	         "maximum number of nodes to regard in the subproblem",
1249 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1250 	
1251 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1252 	         "minimum number of nodes required to start the subproblem",
1253 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1254 	
1255 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxunknownrate",
1256 	         "maximal rate of unknown solution values",
1257 	         &heurdata->maxunknownrate, FALSE, DEFAULT_MAXUNKRATE, 0.0, 1.0, NULL, NULL) );
1258 	
1259 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
1260 	         "should all subproblem solutions be added to the original SCIP?",
1261 	         &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
1262 	
1263 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1264 	         "number of nodes added to the contingent of the total nodes",
1265 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1266 	
1267 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1268 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1269 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1270 	
1271 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1272 	         "factor by which the limit on the number of LP depends on the node limit",
1273 	         &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1274 	
1275 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objweight",
1276 	         "weight of the original objective function (1: only original objective)",
1277 	         &heurdata->objweight, TRUE, DEFAULT_OBJWEIGHT, DEFAULT_MINOBJWEIGHT, 1.0, NULL, NULL) );
1278 	
1279 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/boundwidening",
1280 	         "bound widening factor applied to continuous variables (0: fix variables to given solution values, 1: relax to global bounds)",
1281 	         &heurdata->boundwidening, TRUE, DEFAULT_BOUNDWIDENING, 0.0, 1.0, NULL, NULL) );
1282 	
1283 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1284 	         "factor by which the incumbent should be improved at least",
1285 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1286 	
1287 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/ignorecont",
1288 	         "should number of continuous variables be ignored?",
1289 	         &heurdata->ignorecont, FALSE, DEFAULT_IGNORECONT, NULL, NULL) );
1290 	
1291 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solutions",
1292 	         "heuristic stops, if the given number of improving solutions were found (-1: no limit)",
1293 	         &heurdata->bestsols, FALSE, DEFAULT_BESTSOLS, -1, INT_MAX, NULL, NULL) );
1294 	
1295 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1296 	         "maximal number of iterations in propagation (-1: no limit)",
1297 	         &heurdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) );
1298 	
1299 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforepresol",
1300 	         "should the heuristic run before presolving?",
1301 	         &heurdata->beforepresol, FALSE, DEFAULT_BEFOREPRESOL, NULL, NULL) );
1302 	
1303 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiter",
1304 	         "maximal number of LP iterations (-1: no limit)",
1305 	         &heurdata->maxlpiter, FALSE, DEFAULT_MAXLPITER, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1306 	
1307 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcontvars",
1308 	         "maximal number of continuous variables after presolving",
1309 	         &heurdata->maxcontvars, FALSE, DEFAULT_MAXCONTVARS, -1, INT_MAX, NULL, NULL) );
1310 	
1311 	   return SCIP_OKAY;
1312 	}
1313