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_zeroobj.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "Hail Mary"
28   	 * @author Timo Berthold
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_zeroobj.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_var.h"
41   	#include "scip/scip_branch.h"
42   	#include "scip/scip_cons.h"
43   	#include "scip/scip_copy.h"
44   	#include "scip/scip_event.h"
45   	#include "scip/scip_general.h"
46   	#include "scip/scip_heur.h"
47   	#include "scip/scip_lp.h"
48   	#include "scip/scip_mem.h"
49   	#include "scip/scip_message.h"
50   	#include "scip/scip_nodesel.h"
51   	#include "scip/scip_numerics.h"
52   	#include "scip/scip_param.h"
53   	#include "scip/scip_prob.h"
54   	#include "scip/scip_sol.h"
55   	#include "scip/scip_solve.h"
56   	#include "scip/scip_solvingstats.h"
57   	#include "scip/scip_tree.h"
58   	#include "scip/scip_var.h"
59   	#include <string.h>
60   	
61   	#define HEUR_NAME             "zeroobj"
62   	#define HEUR_DESC             "heuristic trying to solve the problem without objective"
63   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
64   	#define HEUR_PRIORITY         100
65   	#define HEUR_FREQ             -1
66   	#define HEUR_FREQOFS          0
67   	#define HEUR_MAXDEPTH         0
68   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL
69   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
70   	
71   	/* event handler properties */
72   	#define EVENTHDLR_NAME         "Zeroobj"
73   	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
74   	
75   	/* default values for zeroobj-specific plugins */
76   	#define DEFAULT_MAXNODES      1000LL    /* maximum number of nodes to regard in the subproblem                       */
77   	#define DEFAULT_MINIMPROVE    0.01      /* factor by which zeroobj should at least improve the incumbent             */
78   	#define DEFAULT_MINNODES      100LL     /* minimum number of nodes to regard in the subproblem                       */
79   	#define DEFAULT_MAXLPITERS    5000LL    /* maximum number of LP iterations to be performed in the subproblem         */
80   	#define DEFAULT_NODESOFS      100LL     /* number of nodes added to the contingent of the total nodes                */
81   	#define DEFAULT_NODESQUOT     0.1       /* subproblem nodes in relation to nodes of the original problem             */
82   	#define DEFAULT_ADDALLSOLS    FALSE     /* should all subproblem solutions be added to the original SCIP?            */
83   	#define DEFAULT_ONLYWITHOUTSOL   TRUE   /**< should heuristic only be executed if no primal solution was found, yet? */
84   	#define DEFAULT_USEUCT        FALSE     /* should uct node selection be used at the beginning of the search?     */
85   	
86   	/*
87   	 * Data structures
88   	 */
89   	
90   	/** primal heuristic data */
91   	struct SCIP_HeurData
92   	{
93   	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem                 */
94   	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem                 */
95   	   SCIP_Longint          maxlpiters;         /**< maximum number of LP iterations to be performed in the subproblem   */
96   	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes          */
97   	   SCIP_Longint          usednodes;          /**< nodes already used by zeroobj in earlier calls                      */
98   	   SCIP_Real             minimprove;         /**< factor by which zeroobj should at least improve the incumbent       */
99   	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem       */
100  	   SCIP_Bool             addallsols;         /**< should all subproblem solutions be added to the original SCIP?      */
101  	   SCIP_Bool             onlywithoutsol;     /**< should heuristic only be executed if no primal solution was found, yet? */
102  	   SCIP_Bool             useuct;             /**< should uct node selection be used at the beginning of the search?  */
103  	};
104  	
105  	
106  	/*
107  	 * Local methods
108  	 */
109  	
110  	/* ---------------- Callback methods of event handler ---------------- */
111  	
112  	/* exec the event handler
113  	 *
114  	 * we interrupt the solution process
115  	 */
116  	static
117  	SCIP_DECL_EVENTEXEC(eventExecZeroobj)
118  	{
119  	   SCIP_HEURDATA* heurdata;
120  	
121  	   assert(eventhdlr != NULL);
122  	   assert(eventdata != NULL);
123  	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
124  	   assert(event != NULL);
125  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_NODESOLVED);
126  	
127  	   heurdata = (SCIP_HEURDATA*)eventdata;
128  	   assert(heurdata != NULL);
129  	
130  	   /* interrupt solution process of sub-SCIP */
131  	   if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
132  	   {
133  	      SCIP_CALL( SCIPinterruptSolve(scip) );
134  	   }
135  	
136  	   return SCIP_OKAY;
137  	}
138  	/* ---------------- Callback methods of primal heuristic ---------------- */
139  	
140  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
141  	static
142  	SCIP_DECL_HEURCOPY(heurCopyZeroobj)
143  	{  /*lint --e{715}*/
144  	   assert(scip != NULL);
145  	   assert(heur != NULL);
146  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
147  	
148  	   /* call inclusion method of primal heuristic */
149  	   SCIP_CALL( SCIPincludeHeurZeroobj(scip) );
150  	
151  	   return SCIP_OKAY;
152  	}
153  	
154  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
155  	static
156  	SCIP_DECL_HEURFREE(heurFreeZeroobj)
157  	{  /*lint --e{715}*/
158  	   SCIP_HEURDATA* heurdata;
159  	
160  	   assert( heur != NULL );
161  	   assert( scip != NULL );
162  	
163  	   /* get heuristic data */
164  	   heurdata = SCIPheurGetData(heur);
165  	   assert( heurdata != NULL );
166  	
167  	   /* free heuristic data */
168  	   SCIPfreeBlockMemory(scip, &heurdata);
169  	   SCIPheurSetData(heur, NULL);
170  	
171  	   return SCIP_OKAY;
172  	}
173  	
174  	
175  	/** initialization method of primal heuristic (called after problem was transformed) */
176  	static
177  	SCIP_DECL_HEURINIT(heurInitZeroobj)
178  	{  /*lint --e{715}*/
179  	   SCIP_HEURDATA* heurdata;
180  	
181  	   assert( heur != NULL );
182  	   assert( scip != NULL );
183  	
184  	   /* get heuristic data */
185  	   heurdata = SCIPheurGetData(heur);
186  	   assert( heurdata != NULL );
187  	
188  	   /* initialize data */
189  	   heurdata->usednodes = 0;
190  	
191  	   return SCIP_OKAY;
192  	}
193  	
194  	
195  	/** execution method of primal heuristic */
196  	static
197  	SCIP_DECL_HEUREXEC(heurExecZeroobj)
198  	{  /*lint --e{715}*/
199  	   SCIP_HEURDATA* heurdata;                  /* heuristic's data                    */
200  	   SCIP_Longint nnodes;                 /* number of stalling nodes for the subproblem */
201  	
202  	   assert( heur != NULL );
203  	   assert( scip != NULL );
204  	   assert( result != NULL );
205  	
206  	   /* get heuristic data */
207  	   heurdata = SCIPheurGetData(heur);
208  	   assert( heurdata != NULL );
209  	
210  	   /* calculate the maximal number of branching nodes until heuristic is aborted */
211  	   nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
212  	
213  	   /* reward zeroobj if it succeeded often */
214  	   nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
215  	   nnodes -= 100 * SCIPheurGetNCalls(heur);  /* count the setup costs for the sub-SCIP as 100 nodes */
216  	   nnodes += heurdata->nodesofs;
217  	
218  	   /* determine the node limit for the current process */
219  	   nnodes -= heurdata->usednodes;
220  	   nnodes = MIN(nnodes, heurdata->maxnodes);
221  	
222  	   /* check whether we have enough nodes left to call subproblem solving */
223  	   if( nnodes < heurdata->minnodes )
224  	   {
225  	      SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
226  	      return SCIP_OKAY;
227  	   }
228  	
229  	   /* do not run zeroobj, if the problem does not have an objective function anyway */
230  	   if( SCIPgetNObjVars(scip) == 0 )
231  	   {
232  	      SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n");
233  	      return SCIP_OKAY;
234  	   }
235  	
236  	   if( SCIPisStopped(scip) )
237  	      return SCIP_OKAY;
238  	
239  	   SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
240  	
241  	   return SCIP_OKAY;
242  	}
243  	
244  	/** setup and solve subscip */
245  	static
246  	SCIP_RETCODE setupAndSolveSubscip(
247  	   SCIP*                 scip,               /**< SCIP data structure */
248  	   SCIP*                 subscip,            /**< SCIP data structure */
249  	   SCIP_HEUR*            heur,               /**< heuristic data structure */
250  	   SCIP_RESULT*          result,             /**< result data structure */
251  	   SCIP_Real             minimprove,         /**< factor by which zeroobj should at least improve the incumbent */
252  	   SCIP_Longint          nnodes              /**< node limit for the subproblem */
253  	   )
254  	{
255  	   SCIP_Real cutoff;                         /* objective cutoff for the subproblem             */
256  	   SCIP_Real large;
257  	   SCIP_HASHMAP*         varmapfw;           /* mapping of SCIP variables to sub-SCIP variables */
258  	   SCIP_VAR**            vars;               /* original problem's variables                    */
259  	   SCIP_VAR**            subvars;            /* subproblem's variables                          */
260  	   SCIP_SOL** subsols;
261  	   SCIP_HEURDATA*        heurdata;           /* heuristic's private data structure              */
262  	   SCIP_EVENTHDLR*       eventhdlr;          /* event handler for LP events                     */
263  	
264  	   int nsubsols;
265  	   int nvars;                                /* number of original problem's variables          */
266  	   int i;
267  	   SCIP_Bool success;
268  	   SCIP_Bool valid;
269  	
270  	   assert(scip != NULL);
271  	   assert(subscip != NULL);
272  	   assert(heur != NULL);
273  	   assert(result != NULL);
274  	
275  	   heurdata = SCIPheurGetData(heur);
276  	   assert(heurdata != NULL);
277  	
278  	   /* get variable data */
279  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
280  	
281  	   /* create the variable mapping hash map */
282  	   SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
283  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
284  	
285  	   /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
286  	   valid = FALSE;
287  	
288  	   /* copy complete SCIP instance */
289  	   SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj",  TRUE, FALSE, FALSE, TRUE, &valid) );
290  	   SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
291  	
292  	   /* create event handler for LP events */
293  	   eventhdlr = NULL;
294  	   SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
295  	   if( eventhdlr == NULL )
296  	   {
297  	      SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
298  	      return SCIP_PLUGINNOTFOUND;
299  	   }
300  	
301  	   /* determine large value to set variables to */
302  	   large = SCIPinfinity(scip);
303  	   if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
304  	      large = 0.1 / SCIPfeastol(scip);
305  	
306  	   /* get variable image and change to 0.0 in sub-SCIP */
307  	   for( i = 0; i < nvars; i++ )
308  	   {
309  	      SCIP_Real adjustedbound;
310  	      SCIP_Real lb;
311  	      SCIP_Real ub;
312  	      SCIP_Real inf;
313  	
314  	      subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
315  	      if( subvars[i] == NULL )
316  	         continue;
317  	
318  	      SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
319  	
320  	      lb = SCIPvarGetLbGlobal(subvars[i]);
321  	      ub = SCIPvarGetUbGlobal(subvars[i]);
322  	      inf = SCIPinfinity(subscip);
323  	
324  	      /* adjust infinite bounds in order to avoid that variables with non-zero objective 
325  	       * get fixed to infinite value in zeroobj subproblem
326  	       */
327  	      if( SCIPisInfinity(subscip, ub ) )
328  	      {
329  	         adjustedbound = MAX(large, lb+large);
330  	         adjustedbound = MIN(adjustedbound, inf);
331  	         SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
332  	      }
333  	      if( SCIPisInfinity(subscip, -lb ) )
334  	      {
335  	         adjustedbound = MIN(-large, ub-large);
336  	         adjustedbound = MAX(adjustedbound, -inf);
337  	         SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
338  	      }
339  	   }
340  	
341  	   /* free hash map */
342  	   SCIPhashmapFree(&varmapfw);
343  	
344  	   /* do not abort subproblem on CTRL-C */
345  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
346  	
347  	#ifdef SCIP_DEBUG
348  	   /* for debugging, enable full output */
349  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
350  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
351  	#else
352  	   /* disable statistic timing inside sub SCIP and output to console */
353  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
354  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
355  	#endif
356  	
357  	   /* set limits for the subproblem */
358  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
359  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
360  	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
361  	
362  	   /* forbid recursive call of heuristics and separators solving sub-SCIPs */
363  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
364  	
365  	   /* disable expensive techniques that merely work on the dual bound */
366  	
367  	   /* disable cutting plane separation */
368  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
369  	
370  	   /* disable expensive presolving */
371  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
372  	   if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
373  	   {
374  	      SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
375  	   }
376  	
377  	   /* use restart dfs node selection */
378  	   if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
379  	   {
380  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
381  	   }
382  	
383  	   /* activate uct node selection at the top of the tree */
384  	   if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
385  	   {
386  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
387  	   }
388  	   /* use least infeasible branching */
389  	   if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
390  	   {
391  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
392  	   }
393  	
394  	   /* disable feaspump and fracdiving */
395  	   if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
396  	   {
397  	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
398  	   }
399  	   if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
400  	   {
401  	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
402  	   }
403  	
404  	   /* speed up sub-SCIP by not checking dual LP feasibility */
405  	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
406  	
407  	   /* restrict LP iterations */
408  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
409  	   SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
410  	
411  	   /* if there is already a solution, add an objective cutoff */
412  	   if( SCIPgetNSols(scip) > 0 )
413  	   {
414  	      SCIP_Real upperbound;
415  	      SCIP_CONS* origobjcons;
416  	#ifndef NDEBUG
417  	      int nobjvars;
418  	      nobjvars = 0;
419  	#endif
420  	
421  	      assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
422  	
423  	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
424  	
425  	      if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
426  	      {
427  	         cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
428  	      }
429  	      else
430  	      {
431  	         if( SCIPgetUpperbound(scip) >= 0 )
432  	            cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
433  	         else
434  	            cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
435  	      }
436  	      cutoff = MIN(upperbound, cutoff);
437  	
438  	      SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
439  	            TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
440  	      for( i = 0; i < nvars; ++i)
441  	      {
442  	         if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
443  	         {
444  	            assert(subvars[i] != NULL);  /* subvars[i] can be NULL for relax-only vars, but they cannot appear in the objective */
445  	            SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
446  	#ifndef NDEBUG
447  	            nobjvars++;
448  	#endif
449  	         }
450  	      }
451  	      SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
452  	      SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
453  	      assert(nobjvars == SCIPgetNObjVars(scip));
454  	   }
455  	
456  	   /* catch LP events of sub-SCIP */
457  	   SCIP_CALL( SCIPtransformProb(subscip) );
458  	   SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
459  	
460  	   SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
461  	
462  	   /* errors in solving the subproblem should not kill the overall solving process;
463  	    * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
464  	    */
465  	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
466  	
467  	   /* drop LP events of sub-SCIP */
468  	   SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
469  	
470  	   /* check, whether a solution was found;
471  	    * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
472  	    */
473  	   nsubsols = SCIPgetNSols(subscip);
474  	   subsols = SCIPgetSols(subscip);
475  	   success = FALSE;
476  	   for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
477  	   {
478  	      SCIP_SOL* newsol;
479  	
480  	      SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
481  	
482  	      SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
483  	      if( success )
484  	         *result = SCIP_FOUNDSOL;
485  	   }
486  	
487  	#ifdef SCIP_DEBUG
488  	   SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
489  	#endif
490  	
491  	   /* free subproblem */
492  	   SCIPfreeBufferArray(scip, &subvars);
493  	
494  	   return SCIP_OKAY;
495  	}
496  	
497  	
498  	/*
499  	 * primal heuristic specific interface methods
500  	 */
501  	
502  	
503  	/** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
504  	SCIP_RETCODE SCIPapplyZeroobj(
505  	   SCIP*                 scip,               /**< original SCIP data structure                                        */
506  	   SCIP_HEUR*            heur,               /**< heuristic data structure                                            */
507  	   SCIP_RESULT*          result,             /**< result data structure                                               */
508  	   SCIP_Real             minimprove,         /**< factor by which zeroobj should at least improve the incumbent      */
509  	   SCIP_Longint          nnodes              /**< node limit for the subproblem                                       */
510  	   )
511  	{
512  	   SCIP*                 subscip;            /* the subproblem created by zeroobj              */
513  	   SCIP_HEURDATA*        heurdata;           /* heuristic's private data structure              */
514  	   SCIP_Bool             success;
515  	   SCIP_RETCODE          retcode;
516  	
517  	   assert(scip != NULL);
518  	   assert(heur != NULL);
519  	   assert(result != NULL);
520  	
521  	   assert(nnodes >= 0);
522  	   assert(0.0 <= minimprove && minimprove <= 1.0);
523  	
524  	   *result = SCIP_DIDNOTRUN;
525  	
526  	   /* only call heuristic once at the root */
527  	   if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
528  	      return SCIP_OKAY;
529  	
530  	   /* get heuristic data */
531  	   heurdata = SCIPheurGetData(heur);
532  	   assert(heurdata != NULL);
533  	
534  	   /* only call the heuristic if we do not have an incumbent  */
535  	   if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
536  	      return SCIP_OKAY;
537  	
538  	   /* check whether there is enough time and memory left */
539  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
540  	
541  	   if( !success )
542  	      return SCIP_OKAY;
543  	
544  	   *result = SCIP_DIDNOTFIND;
545  	
546  	   /* initialize the subproblem */
547  	   SCIP_CALL( SCIPcreate(&subscip) );
548  	
549  	   retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
550  	
551  	   SCIP_CALL( SCIPfree(&subscip) );
552  	
553  	   return retcode;
554  	}
555  	
556  	
557  	/** creates the zeroobj primal heuristic and includes it in SCIP */
558  	SCIP_RETCODE SCIPincludeHeurZeroobj(
559  	   SCIP*                 scip                /**< SCIP data structure */
560  	   )
561  	{
562  	   SCIP_HEURDATA* heurdata;
563  	   SCIP_HEUR* heur;
564  	
565  	   /* create heuristic data */
566  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
567  	
568  	   /* include primal heuristic */
569  	   heur = NULL;
570  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
571  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
572  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
573  	   assert(heur != NULL);
574  	
575  	   /* set non-NULL pointers to callback methods */
576  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
577  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
578  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
579  	
580  	   /* add zeroobj primal heuristic parameters */
581  	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
582  	         "maximum number of nodes to regard in the subproblem",
583  	         &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
584  	
585  	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
586  	         "number of nodes added to the contingent of the total nodes",
587  	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
588  	
589  	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
590  	         "minimum number of nodes required to start the subproblem",
591  	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
592  	
593  	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
594  	         "maximum number of LP iterations to be performed in the subproblem",
595  	         &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
596  	
597  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
598  	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
599  	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
600  	
601  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
602  	         "factor by which zeroobj should at least improve the incumbent",
603  	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
604  	
605  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
606  	         "should all subproblem solutions be added to the original SCIP?",
607  	         &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
608  	
609  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
610  	         "should heuristic only be executed if no primal solution was found, yet?",
611  	         &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
612  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
613  	         "should uct node selection be used at the beginning of the search?",
614  	         &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
615  	
616  	   return SCIP_OKAY;
617  	}
618