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_undercover.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  Undercover primal heuristic for MINLPs
28   	 * @author Timo Berthold
29   	 * @author Ambros Gleixner
30   	 *
31   	 * The undercover heuristic is designed for mixed-integer nonlinear programs and tries to fix a subset of variables such
32   	 * as to make each constraint linear or convex. For this purpose it solves a binary program to automatically determine
33   	 * the minimum number of variable fixings necessary. As fixing values, we use values from the LP relaxation, the NLP
34   	 * relaxation, or the incumbent solution.
35   	 *
36   	 * @todo use the conflict analysis to analyze the infeasibility which arise after the probing of the cover worked and
37   	 *       solve returned infeasible, instead of adding the Nogood/Conflict by hand; that has the advantage that the SCIP
38   	 *       takes care of creating the conflict and might shrink the initial reason
39   	 *
40   	 * @todo do not use LP and NLP fixing values in the same run, e.g., fixingalts = "lni", but start a second dive if LP
41   	 *       values fail
42   	 */
43   	
44   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
45   	
46   	#include "blockmemshell/memory.h"
47   	#include "scip/cons_and.h"
48   	#include "scip/cons_bounddisjunction.h"
49   	#include "scip/cons_nonlinear.h"
50   	#include "scip/cons_indicator.h"
51   	#include "scip/cons_linear.h"
52   	#include "scip/cons_logicor.h"
53   	#include "scip/cons_setppc.h"
54   	#include "scip/heur_subnlp.h"
55   	#include "scip/heur_undercover.h"
56   	#include "scip/pub_cons.h"
57   	#include "scip/pub_expr.h"
58   	#include "scip/pub_heur.h"
59   	#include "scip/pub_message.h"
60   	#include "scip/pub_misc.h"
61   	#include "scip/pub_misc_sort.h"
62   	#include "scip/pub_nlp.h"
63   	#include "scip/pub_var.h"
64   	#include "scip/scip_branch.h"
65   	#include "scip/scip_cons.h"
66   	#include "scip/scip_copy.h"
67   	#include "scip/scipdefplugins.h"
68   	#include "scip/scip_general.h"
69   	#include "scip/scip_heur.h"
70   	#include "scip/scip_lp.h"
71   	#include "scip/scip_mem.h"
72   	#include "scip/scip_message.h"
73   	#include "scip/scip_nlp.h"
74   	#include "scip/scip_numerics.h"
75   	#include "scip/scip_param.h"
76   	#include "scip/scip_prob.h"
77   	#include "scip/scip_probing.h"
78   	#include "scip/scip_randnumgen.h"
79   	#include "scip/scip_sol.h"
80   	#include "scip/scip_solve.h"
81   	#include "scip/scip_solvingstats.h"
82   	#include "scip/scip_timing.h"
83   	#include "scip/scip_tree.h"
84   	#include "scip/scip_var.h"
85   	#include <string.h>
86   	
87   	#define HEUR_NAME               "undercover"
88   	#define HEUR_DESC               "solves a sub-CIP determined by a set covering approach"
89   	#define HEUR_DISPCHAR           SCIP_HEURDISPCHAR_LNS
90   	#define HEUR_PRIORITY           -1110000
91   	#define HEUR_FREQ               0
92   	#define HEUR_FREQOFS            0
93   	#define HEUR_MAXDEPTH           -1
94   	#define HEUR_TIMING             SCIP_HEURTIMING_AFTERNODE
95   	#define HEUR_USESSUBSCIP        TRUE         /**< does the heuristic use a secondary SCIP instance? */
96   	
97   	/* default values for user parameters, grouped by parameter type */
98   	#define DEFAULT_FIXINGALTS      "li"         /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
99   	
100  	#define DEFAULT_MAXNODES        (SCIP_Longint)500/**< maximum number of nodes to regard in the subproblem */
101  	#define DEFAULT_MINNODES        (SCIP_Longint)500/**< minimum number of nodes to regard in the subproblem */
102  	#define DEFAULT_NODESOFS        (SCIP_Longint)500/**< number of nodes added to the contingent of the total nodes */
103  	
104  	#define DEFAULT_CONFLICTWEIGHT  1000.0       /**< weight for conflict score in fixing order */
105  	#define DEFAULT_CUTOFFWEIGHT    1.0          /**< weight for cutoff score in fixing order */
106  	#define DEFAULT_INFERENCEWEIGHT 1.0          /**< weight for inference score in fixing order */
107  	#define DEFAULT_MAXCOVERSIZEVARS  1.0           /**< maximum coversize (as fraction of total number of variables) */
108  	#define DEFAULT_MAXCOVERSIZECONSS SCIP_REAL_MAX /**< maximum coversize (as ratio to the percentage of non-affected constraints) */
109  	#define DEFAULT_MINCOVEREDREL   0.15         /**< minimum percentage of nonlinear constraints in the original problem */
110  	#define DEFAULT_MINCOVEREDABS   5            /**< minimum number of nonlinear constraints in the original problem */
111  	#define DEFAULT_MINIMPROVE      0.0          /**< factor by which heuristic should at least improve the incumbent */
112  	#define DEFAULT_NODESQUOT       0.1          /**< subproblem nodes in relation to nodes of the original problem */
113  	#define DEFAULT_RECOVERDIV      0.9          /**< fraction of covering variables in the last cover which need to change their value when recovering */
114  	
115  	#define DEFAULT_MAXBACKTRACKS   6            /**< maximum number of backtracks */
116  	#define DEFAULT_MAXRECOVERS     0            /**< maximum number of recoverings */
117  	#define DEFAULT_MAXREORDERS     1            /**< maximum number of reorderings of the fixing order */
118  	
119  	#define DEFAULT_COVERINGOBJ     'u'          /**< objective function of the covering problem */
120  	#define DEFAULT_FIXINGORDER     'v'          /**< order in which variables should be fixed */
121  	
122  	#define DEFAULT_BEFORECUTS      TRUE         /**< should undercover called at root node before cut separation? */
123  	#define DEFAULT_FIXINTFIRST     FALSE        /**< should integer variables in the cover be fixed first? */
124  	#define DEFAULT_LOCKSROUNDING   TRUE         /**< shall LP values for integer vars be rounded according to locks? */
125  	#define DEFAULT_ONLYCONVEXIFY   FALSE        /**< should we only fix/dom.red. variables creating nonconvexity? */
126  	#define DEFAULT_POSTNLP         TRUE         /**< should the NLP heuristic be called to polish a feasible solution? */
127  	#define DEFAULT_COVERAND        TRUE         /**< should and constraints be covered (or just copied)? */
128  	#define DEFAULT_COVERBD         FALSE        /**< should bounddisjunction constraints be covered (or just copied)? */
129  	#define DEFAULT_COVERIND        FALSE        /**< should indicator constraints be covered (or just copied)? */
130  	#define DEFAULT_COVERNL         TRUE         /**< should nonlinear constraints be covered (or just copied)? */
131  	#define DEFAULT_REUSECOVER      FALSE        /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
132  	#define DEFAULT_COPYCUTS        TRUE         /**< should all active cuts from the cutpool of the original scip be copied
133  	                                              *   to constraints of the subscip
134  	                                              */
135  	#define DEFAULT_RANDSEED        43           /* initial random seed */
136  	
137  	/* local defines */
138  	#define COVERINGOBJS            "cdlmtu"     /**< list of objective functions of the covering problem */
139  	#define FIXINGORDERS            "CcVv"       /**< list of orders in which variables can be fixed */
140  	#define MAXNLPFAILS             1            /**< maximum number of fails after which we give up solving the NLP relaxation */
141  	#define MAXPOSTNLPFAILS         1            /**< maximum number of fails after which we give up calling NLP local search */
142  	#define MINTIMELEFT             1.0          /**< don't start expensive parts of the heuristics if less than this amount of time left */
143  	#define SUBMIPSETUPCOSTS        200          /**< number of nodes equivalent for the costs for setting up the sub-CIP */
144  	
145  	
146  	/*
147  	 * Data structures
148  	 */
149  	
150  	/** primal heuristic data */
151  	struct SCIP_HeurData
152  	{
153  	   SCIP_CONSHDLR**       nlconshdlrs;        /**< array of nonlinear constraint handlers */
154  	   SCIP_HEUR*            nlpheur;            /**< pointer to NLP local search heuristics */
155  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
156  	   char*                 fixingalts;         /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
157  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem */
158  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem */
159  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes */
160  	   SCIP_Longint          nusednodes;         /**< nodes already used by heuristic in earlier calls */
161  	   SCIP_Real             conflictweight;     /**< weight for conflict score in fixing order */
162  	   SCIP_Real             cutoffweight;       /**< weight for cutoff score in fixing order */
163  	   SCIP_Real             inferenceweight;    /**< weight for inference score in foxing order */
164  	   SCIP_Real             maxcoversizevars;   /**< maximum coversize (as fraction of total number of variables) */
165  	   SCIP_Real             maxcoversizeconss;  /**< maximum coversize (as ratio to the percentage of non-affected constraints) */
166  	   SCIP_Real             mincoveredrel;      /**< minimum percentage of nonlinear constraints in the original problem */
167  	   SCIP_Real             minimprove;         /**< factor by which heuristic should at least improve the incumbent */
168  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
169  	   SCIP_Real             recoverdiv;         /**< fraction of covering variables in the last cover which need to change their value when recovering */
170  	   int                   mincoveredabs;      /**< minimum number of nonlinear constraints in the original problem */
171  	   int                   maxbacktracks;      /**< maximum number of backtracks */
172  	   int                   maxrecovers;        /**< maximum number of recoverings */
173  	   int                   maxreorders;        /**< maximum number of reorderings of the fixing order */
174  	   int                   nfixingalts;        /**< number of fixing alternatives */
175  	   int                   nnlpfails;          /**< number of fails when solving the NLP relaxation after last success */
176  	   int                   npostnlpfails;      /**< number of fails of the NLP local search after last success */
177  	   int                   nnlconshdlrs;       /**< number of nonlinear constraint handlers */
178  	   char                  coveringobj;        /**< objective function of the covering problem */
179  	   char                  fixingorder;        /**< order in which variables should be fixed */
180  	   SCIP_Bool             beforecuts;         /**< should undercover be called at root node before cut separation? */
181  	   SCIP_Bool             fixintfirst;        /**< should integer variables in the cover be fixed first? */
182  	   SCIP_Bool             globalbounds;       /**< should global bounds on variables be used instead of local bounds at focus node? */
183  	   SCIP_Bool             locksrounding;      /**< shall LP values for integer vars be rounded according to locks? */
184  	   SCIP_Bool             nlpsolved;          /**< has current NLP relaxation already been solved successfully? */
185  	   SCIP_Bool             nlpfailed;          /**< has solving the NLP relaxation failed? */
186  	   SCIP_Bool             onlyconvexify;      /**< should we only fix/dom.red. variables creating nonconvexity? */
187  	   SCIP_Bool             postnlp;            /**< should the NLP heuristic be called to polish a feasible solution? */
188  	   SCIP_Bool             coverand;           /**< should and constraints be covered (or just copied)? */
189  	   SCIP_Bool             coverbd;            /**< should bounddisjunction constraints be covered (or just copied)? */
190  	   SCIP_Bool             coverind;           /**< should indicator constraints be covered (or just copied)? */
191  	   SCIP_Bool             covernl;            /**< should nonlinear constraints be covered (or just copied)? */
192  	   SCIP_Bool             reusecover;         /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
193  	   SCIP_Bool             copycuts;           /**< should all active cuts from cutpool be copied to constraints in
194  	                                              *   subproblem? */
195  	};
196  	
197  	/*
198  	 * Local methods
199  	 */
200  	
201  	
202  	/** determines, whether a variable is fixed to the given value */
203  	static
204  	SCIP_Bool varIsFixed(
205  	   SCIP*                 scip,               /**< SCIP data structure */
206  	   SCIP_VAR*             var,                /**< variable to check */
207  	   SCIP_Real             val,                /**< value to check */
208  	   SCIP_Bool             global              /**< should global bounds be used? */
209  	   )
210  	{
211  	   SCIP_Bool isfixed;
212  	
213  	   if( global )
214  	      isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbGlobal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbGlobal(var));
215  	   else
216  	      isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbLocal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbLocal(var));
217  	
218  	   return isfixed;
219  	}
220  	
221  	
222  	/** determines, whether a term is already constant, because the variable is fixed or the coefficient is zero */
223  	static
224  	SCIP_Bool termIsConstant(
225  	   SCIP*                 scip,               /**< SCIP data structure */
226  	   SCIP_VAR*             var,                /**< variable to check */
227  	   SCIP_Real             coeff,              /**< coefficient to check */
228  	   SCIP_Bool             global              /**< should global bounds be used? */
229  	   )
230  	{
231  	   /* if the variable has zero coefficient in the original problem, the term is linear */
232  	   if( SCIPisZero(scip, coeff) )
233  	      return TRUE;
234  	
235  	   /* if the variable is fixed in the original problem, the term is linear */
236  	   if( global )
237  	      return SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
238  	   else
239  	      return SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
240  	}
241  	
242  	
243  	/** determines, whether a term is convex */
244  	static
245  	SCIP_Bool termIsConvex(
246  	   SCIP*                 scip,               /**< SCIP data structure */
247  	   SCIP_Real             lhs,                /**< left hand side of the constraint */
248  	   SCIP_Real             rhs,                /**< right hand side of the constraint */
249  	   SCIP_Bool             sign                /**< signature of the term */
250  	   )
251  	{
252  	   return sign ? SCIPisInfinity(scip, -lhs) : SCIPisInfinity(scip, rhs);
253  	}
254  	
255  	
256  	/** increases counters */
257  	static
258  	void  incCounters(
259  	   int*                  termcounter,        /**< array to count in how many nonlinear terms a variable appears */
260  	   int*                  conscounter,        /**< array to count in how many constraints a variable appears */
261  	   SCIP_Bool*            consmarker,         /**< was this variable already counted for this constraint? */
262  	   int                   idx                 /**< problem index of the variable */
263  	   )
264  	{
265  	   termcounter[idx]++;
266  	   if( !consmarker[idx] )
267  	   {
268  	      conscounter[idx]++;
269  	      consmarker[idx] = TRUE;
270  	   }
271  	   return;
272  	}
273  	
274  	
275  	/** update time limit */
276  	static
277  	SCIP_RETCODE updateTimelimit(
278  	   SCIP*                 scip,               /**< SCIP data structure */
279  	   SCIP_CLOCK*           clck,               /**< clock timer */
280  	   SCIP_Real*            timelimit           /**< time limit */
281  	   )
282  	{
283  	   *timelimit -= SCIPgetClockTime(scip, clck);
284  	   SCIP_CALL( SCIPresetClock(scip, clck) );
285  	   SCIP_CALL( SCIPstartClock(scip, clck) );
286  	
287  	   return SCIP_OKAY;
288  	}
289  	
290  	
291  	/** analyzes a nonlinear row and adds constraints and fixings to the covering problem */
292  	static
293  	SCIP_RETCODE processNlRow(
294  	   SCIP*                 scip,               /**< original SCIP data structure */
295  	   SCIP_NLROW*           nlrow,              /**< nonlinear row representation of a nonlinear constraint */
296  	   SCIP*                 coveringscip,       /**< SCIP data structure for the covering problem */
297  	   int                   nvars,              /**< number of variables */
298  	   SCIP_VAR**            coveringvars,       /**< array to store the covering problem's variables */
299  	   int*                  termcounter,        /**< counter array for number of nonlinear nonzeros per variable */
300  	   int*                  conscounter,        /**< counter array for number of nonlinear constraints per variable */
301  	   SCIP_Bool*            consmarker,         /**< marker array if constraint has been counted in conscounter */
302  	   SCIP_Bool             globalbounds,       /**< should global bounds on variables be used instead of local bounds at focus node? */
303  	   SCIP_Bool             onlyconvexify,      /**< should we only fix/dom.red. variables creating nonconvexity? */
304  	   SCIP_Bool*            success             /**< pointer to store whether row was processed successfully */
305  	   )
306  	{
307  	   SCIP_EXPR* expr;
308  	   SCIP_Bool infeas;
309  	   SCIP_Bool fixed;
310  	   int t;
311  	   char name[SCIP_MAXSTRLEN];
312  	
313  	   assert(scip != NULL);
314  	   assert(nlrow != NULL);
315  	   assert(coveringscip != NULL);
316  	   assert(nvars >= 1);
317  	   assert(coveringvars != NULL);
318  	   assert(termcounter != NULL);
319  	   assert(conscounter != NULL);
320  	   assert(consmarker != NULL);
321  	   assert(success != NULL);
322  	
323  	   *success = FALSE;
324  	
325  	   /* if we only want to convexify and curvature and bounds prove already convexity, nothing to do */
326  	   if( onlyconvexify
327  	         && ( SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_LINEAR
328  	            || (SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONVEX )
329  	            || (SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONCAVE)) )
330  	   {
331  	      *success = TRUE;
332  	      return SCIP_OKAY;
333  	   }
334  	
335  	   BMSclearMemoryArray(consmarker, nvars);
336  	
337  	   /* go through expression */
338  	   expr = SCIPnlrowGetExpr(nlrow);
339  	   if( expr != NULL )
340  	   {
341  	      SCIP_Bool isquadratic;
342  	
343  	      SCIP_CALL( SCIPcheckExprQuadratic(scip, expr, &isquadratic) );
344  	      if( isquadratic && SCIPexprAreQuadraticExprsVariables(expr) )
345  	      {
346  	         int nquadexprs;
347  	         int nbilinexprs;
348  	
349  	         SCIPexprGetQuadraticData(expr, NULL, NULL, NULL, NULL, &nquadexprs, &nbilinexprs, NULL, NULL);
350  	
351  	         /* go through all quadratic terms */
352  	         for( t = 0; t < nquadexprs; ++t )
353  	         {
354  	            SCIP_EXPR* varexpr;
355  	            SCIP_Real sqrcoef;
356  	            int probidx;
357  	
358  	            SCIPexprGetQuadraticQuadTerm(expr, t, &varexpr, NULL, &sqrcoef, 0, NULL, NULL);
359  	
360  	            /* term is constant, nothing to do */
361  	            if( termIsConstant(scip, SCIPgetVarExprVar(varexpr), sqrcoef, globalbounds) )
362  	               continue;
363  	
364  	            /* if we only convexify and term is convex considering the bounds of the nlrow, nothing to do */
365  	            if( onlyconvexify && termIsConvex(scip, SCIPnlrowGetLhs(nlrow), SCIPnlrowGetRhs(nlrow), sqrcoef >= 0) )
366  	               continue;
367  	
368  	            probidx = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr));
369  	            if( probidx == -1 )
370  	            {
371  	               SCIPdebugMsg(scip, "inactive variable detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
372  	               return SCIP_OKAY;
373  	            }
374  	            assert(coveringvars[probidx] != NULL);
375  	
376  	            /* otherwise variable has to be in the cover */
377  	            SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx], 1.0, &infeas, &fixed) );
378  	            assert(!infeas);
379  	            assert(fixed);
380  	
381  	            /* update counters */
382  	            incCounters(termcounter, conscounter, consmarker, probidx);
383  	
384  	            SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx]));
385  	         }
386  	
387  	         /* go through all bilinear terms */
388  	         for( t = 0; t < nbilinexprs; ++t )
389  	         {
390  	            SCIP_EXPR* varexpr1;
391  	            SCIP_EXPR* varexpr2;
392  	            SCIP_Real bilincoef;
393  	            int probidx1;
394  	            int probidx2;
395  	            SCIP_CONS* coveringcons;
396  	            SCIP_VAR* coveringconsvars[2];
397  	
398  	            SCIPexprGetQuadraticBilinTerm(expr, t, &varexpr1, &varexpr2, &bilincoef, NULL, NULL);
399  	
400  	            /* if the term is linear because one of the variables is fixed or the coefficient is zero, nothing to do */
401  	            if( termIsConstant(scip, SCIPgetVarExprVar(varexpr1), bilincoef, globalbounds)
402  	               || termIsConstant(scip, SCIPgetVarExprVar(varexpr2), bilincoef, globalbounds) )
403  	               continue;
404  	
405  	            probidx1 = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr1));
406  	            probidx2 = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr2));
407  	            if( probidx1 == -1 || probidx2 == -1 )
408  	            {
409  	               SCIPdebugMsg(scip, "inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
410  	               return SCIP_OKAY;
411  	            }
412  	            assert(coveringvars[probidx1] != NULL);
413  	            assert(coveringvars[probidx2] != NULL);
414  	
415  	            /* create covering constraint */
416  	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering%d", SCIPnlrowGetName(nlrow), t);
417  	            coveringconsvars[0] = coveringvars[probidx1];
418  	            coveringconsvars[1] = coveringvars[probidx2];
419  	            SCIP_CALL( SCIPcreateConsSetcover(coveringscip, &coveringcons, name, 2, coveringconsvars,
420  	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
421  	
422  	            if( coveringcons == NULL )
423  	            {
424  	               SCIPdebugMsg(scip, "failed to create set covering constraint <%s>\n", name);
425  	               return SCIP_OKAY;
426  	            }
427  	
428  	            /* add and release covering constraint */
429  	            SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
430  	            SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
431  	
432  	            /* update counters for both variables */
433  	            incCounters(termcounter, conscounter, consmarker, probidx1);
434  	            incCounters(termcounter, conscounter, consmarker, probidx2);
435  	         }
436  	      }
437  	      else
438  	      {
439  	         /* fix all variables contained in the expression */
440  	         SCIP_EXPRITER* it;
441  	         int probidx;
442  	
443  	         SCIP_CALL( SCIPcreateExpriter(scip, &it) );
444  	         SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
445  	         for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) /*lint !e441*/ /*lint !e440*/
446  	         {
447  	            if( !SCIPisExprVar(scip, expr) )
448  	               continue;
449  	
450  	            /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
451  	            probidx = SCIPvarGetProbindex(SCIPgetVarExprVar(expr));
452  	            if( probidx == -1 )
453  	            {
454  	               SCIPdebugMsg(scip, "strange: inactive variable <%s> detected in nonlinear row <%s>\n",
455  	                  SCIPvarGetName(SCIPgetVarExprVar(expr)), SCIPnlrowGetName(nlrow));
456  	               return SCIP_OKAY;
457  	            }
458  	            assert(coveringvars[probidx] != NULL);
459  	
460  	            /* term is constant, nothing to do */
461  	            if( termIsConstant(scip, SCIPgetVarExprVar(expr), 1.0, globalbounds) )
462  	               continue;
463  	
464  	            /* otherwise fix variable */
465  	            SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx], 1.0, &infeas, &fixed) );
466  	            assert(!infeas);
467  	            assert(fixed);
468  	
469  	            /* update counters */
470  	            incCounters(termcounter, conscounter, consmarker, probidx);
471  	
472  	            SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx]));
473  	         }
474  	         SCIPfreeExpriter(&it);
475  	      }
476  	   }
477  	   *success = TRUE;
478  	
479  	   return SCIP_OKAY;
480  	}
481  	
482  	
483  	/** creates the covering problem to determine a number of variables to be fixed */
484  	static
485  	SCIP_RETCODE createCoveringProblem(
486  	   SCIP*                 scip,               /**< original SCIP data structure */
487  	   SCIP*                 coveringscip,       /**< SCIP data structure for the covering problem */
488  	   SCIP_VAR**            coveringvars,       /**< array to store the covering problem's variables */
489  	   SCIP_Bool             globalbounds,       /**< should global bounds on variables be used instead of local bounds at focus node? */
490  	   SCIP_Bool             onlyconvexify,      /**< should we only fix/dom.red. variables creating nonconvexity? */
491  	   SCIP_Bool             coverand,           /**< should and constraints be covered (or just copied)? */
492  	   SCIP_Bool             coverbd,            /**< should bounddisjunction constraints be covered (or just copied)? */
493  	   SCIP_Bool             coverind,           /**< should indicator constraints be covered (or just copied)? */
494  	   SCIP_Bool             covernl,            /**< should nonlinear constraints be covered (or just copied)? */
495  	   char                  coveringobj,        /**< objective function of the covering problem */
496  	   SCIP_Bool*            success             /**< pointer to store whether the problem was created successfully */
497  	   )
498  	{
499  	   SCIP_VAR** vars;
500  	   SCIP_CONSHDLR* conshdlr;
501  	   SCIP_Bool* consmarker;
502  	   int* conscounter;
503  	   int* termcounter;
504  	
505  	   int nlocksup;
506  	   int nlocksdown;
507  	   int nvars;
508  	   int i;
509  	   int probindex;
510  	   char name[SCIP_MAXSTRLEN];
511  	
512  	   assert(scip != NULL);
513  	   assert(coveringscip != NULL);
514  	   assert(coveringvars != NULL);
515  	   assert(success != NULL);
516  	
517  	   *success = FALSE;
518  	
519  	   /* get required data of the original problem */
520  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
521  	
522  	   /* create problem data structure */
523  	   (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPgetProbName(scip));
524  	   SCIP_CALL( SCIPcreateProb(coveringscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
525  	   SCIPsetSubscipDepth(coveringscip, SCIPgetSubscipDepth(scip) + 1);
526  	
527  	   /* allocate and initialize to zero counter arrays for weighted objectives */
528  	   SCIP_CALL( SCIPallocBufferArray(scip, &consmarker, nvars) );
529  	   SCIP_CALL( SCIPallocBufferArray(scip, &conscounter, nvars) );
530  	   SCIP_CALL( SCIPallocBufferArray(scip, &termcounter, nvars) );
531  	   BMSclearMemoryArray(conscounter, nvars);
532  	   BMSclearMemoryArray(termcounter, nvars);
533  	
534  	   /* create covering variable for each variable in the original problem (fix it or not?) in the same order as in the
535  	    * original problem
536  	    */
537  	   for( i = 0; i < nvars; i++ )
538  	   {
539  	      SCIP_Real ub = 1.0;
540  	
541  	      if( SCIPvarIsRelaxationOnly(vars[i]) )
542  	      {
543  	         /* skip relaxation-only variables; they cannot appear in constraints */
544  	         coveringvars[i] = NULL;
545  	         continue;
546  	      }
547  	
548  	      /* if the variable in the original problem is fixed, then the corresponding cover variable cannot be 1 in any
549  	       * optimal solution of the covering problem (see special termIsConstant treatment below)
550  	       * since some calling code may assume that no fixed variables will appear in the cover (see #1845), but we
551  	       * might not compute an optimal cover here, we fix these variable to 0 here
552  	       */
553  	      if( globalbounds )
554  	      {
555  	         if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i])) )
556  	            ub = 0.0;
557  	      }
558  	      else
559  	      {
560  	         if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
561  	            ub = 0.0;
562  	      }
563  	
564  	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPvarGetName(vars[i]));
565  	      SCIP_CALL( SCIPcreateVar(coveringscip, &coveringvars[i], name, 0.0, ub, 1.0, SCIP_VARTYPE_BINARY,
566  	            TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
567  	      assert(coveringvars[i] != NULL);
568  	      SCIP_CALL( SCIPaddVar(coveringscip, coveringvars[i]) );
569  	   }
570  	
571  	   /* go through all AND constraints in the original problem */
572  	   conshdlr = SCIPfindConshdlr(scip, "and");
573  	   if( conshdlr != NULL && coverand )
574  	   {
575  	      int c;
576  	
577  	      for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
578  	      {
579  	         SCIP_CONS* andcons;
580  	         SCIP_CONS* coveringcons;
581  	         SCIP_VAR** andvars;
582  	         SCIP_VAR* andres;
583  	         SCIP_VAR** coveringconsvars;
584  	         SCIP_Real* coveringconsvals;
585  	         SCIP_Bool negated;
586  	
587  	         int ntofix;
588  	         int v;
589  	
590  	         /* get constraint and variables */
591  	         andcons = SCIPconshdlrGetConss(conshdlr)[c];
592  	         assert(andcons != NULL);
593  	         andvars = SCIPgetVarsAnd(scip, andcons);
594  	         assert(andvars != NULL);
595  	
596  	         /* allocate memory for covering constraint */
597  	         SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNVarsAnd(scip, andcons)+1) );
598  	         SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, SCIPgetNVarsAnd(scip, andcons)+1) );
599  	
600  	         /* collect unfixed variables */
601  	         BMSclearMemoryArray(consmarker, nvars);
602  	         ntofix = 0;
603  	         for( v = SCIPgetNVarsAnd(scip, andcons)-1; v >= 0; v-- )
604  	         {
605  	            assert(andvars[v] != NULL);
606  	            negated = FALSE;
607  	
608  	            /* if variable is fixed to 0, entire constraint can be linearized */
609  	            if( varIsFixed(scip, andvars[v], 0.0, globalbounds) )
610  	            {
611  	               ntofix = 0;
612  	               break;
613  	            }
614  	
615  	            /* if variable is fixed, nothing to do */
616  	            if( termIsConstant(scip, andvars[v], 1.0, globalbounds) )
617  	            {
618  	               continue;
619  	            }
620  	
621  	            /* if constraints with inactive variables are present, we have to find the corresponding active variable */
622  	            probindex = SCIPvarGetProbindex(andvars[v]);
623  	            if( probindex == -1 )
624  	            {
625  	               SCIP_VAR* repvar;
626  	
627  	               /* get binary representative of variable */
628  	               SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[v], &repvar, &negated) );
629  	               assert(repvar != NULL);
630  	               assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
631  	
632  	               if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
633  	               {
634  	                  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(andvars[v]));
635  	                  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
636  	                  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
637  	                  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
638  	                  goto TERMINATE;
639  	               }
640  	
641  	               /* check for negation */
642  	               if( SCIPvarIsNegated(repvar) )
643  	               {
644  	                  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
645  	                  negated = TRUE;
646  	               }
647  	               else
648  	               {
649  	                  assert(SCIPvarIsActive(repvar));
650  	                  probindex = SCIPvarGetProbindex(repvar);
651  	                  negated = FALSE;
652  	               }
653  	            }
654  	            assert(probindex >= 0);
655  	            assert(coveringvars[probindex] != NULL);
656  	
657  	            /* add covering variable for unfixed original variable */
658  	            if( negated )
659  	            {
660  	               SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
661  	            }
662  	            else
663  	               coveringconsvars[ntofix] = coveringvars[probindex];
664  	            coveringconsvals[ntofix] = 1.0;
665  	            ntofix++;
666  	         }
667  	         negated = FALSE;
668  	
669  	         /* if constraints with inactive variables are present, we have to find the corresponding active variable */
670  	         andres = SCIPgetResultantAnd(scip, andcons);
671  	         assert(andres != NULL);
672  	         probindex = SCIPvarGetProbindex(andres);
673  	
674  	         /* if resultant is fixed this constraint can be either linearized or is redundant because all operands can be fixed */
675  	         if( termIsConstant(scip, andres, 1.0, globalbounds) )
676  	         {
677  	            /* free memory for covering constraint */
678  	            SCIPfreeBufferArray(coveringscip, &coveringconsvals);
679  	            SCIPfreeBufferArray(coveringscip, &coveringconsvars);
680  	
681  	            continue;
682  	         }
683  	
684  	         if( probindex == -1 )
685  	         {
686  	            SCIP_VAR* repvar;
687  	
688  	            /* get binary representative of variable */
689  	            SCIP_CALL( SCIPgetBinvarRepresentative(scip, SCIPgetResultantAnd(scip, andcons), &repvar, &negated) );
690  	            assert(repvar != NULL);
691  	            assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
692  	
693  	            if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
694  	            {
695  	               SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(SCIPgetResultantAnd(scip, andcons)));
696  	               SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
697  	               SCIPfreeBufferArray(coveringscip, &coveringconsvals);
698  	               SCIPfreeBufferArray(coveringscip, &coveringconsvars);
699  	               goto TERMINATE;
700  	            }
701  	
702  	            /* check for negation */
703  	            if( SCIPvarIsNegated(repvar) )
704  	            {
705  	               probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
706  	               negated = TRUE;
707  	            }
708  	            else
709  	            {
710  	               assert(SCIPvarIsActive(repvar));
711  	               probindex = SCIPvarGetProbindex(repvar);
712  	               negated = FALSE;
713  	            }
714  	         }
715  	         else if( SCIPvarGetLbGlobal(andres) > 0.5 || SCIPvarGetUbGlobal(andres) < 0.5 )
716  	         {
717  	            /* free memory for covering constraint */
718  	            SCIPfreeBufferArray(coveringscip, &coveringconsvals);
719  	            SCIPfreeBufferArray(coveringscip, &coveringconsvars);
720  	
721  	            continue;
722  	         }
723  	         assert(probindex >= 0);
724  	         assert(coveringvars[probindex] != NULL);
725  	         assert(!termIsConstant(scip, (negated ? SCIPvarGetNegatedVar(vars[probindex]) : vars[probindex]), 1.0, globalbounds));
726  	
727  	         /* if less than two variables are unfixed or the resultant variable is fixed, the entire constraint can be linearized anyway */
728  	         if( ntofix >= 2 )
729  	         {
730  	            assert(ntofix <= SCIPgetNVarsAnd(scip, andcons));
731  	
732  	            /* add covering variable for unfixed resultant */
733  	            if( negated )
734  	            {
735  	               SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
736  	            }
737  	            else
738  	               coveringconsvars[ntofix] = coveringvars[probindex];
739  	            coveringconsvals[ntofix] = (SCIP_Real)(ntofix - 1);
740  	            ntofix++;
741  	
742  	            /* create covering constraint */
743  	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(andcons));
744  	            SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
745  	                  (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
746  	                  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
747  	
748  	            if( coveringcons == NULL )
749  	            {
750  	               SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
751  	               SCIPfreeBufferArray(coveringscip, &coveringconsvals);
752  	               SCIPfreeBufferArray(coveringscip, &coveringconsvars);
753  	               goto TERMINATE;
754  	            }
755  	
756  	            /* add and release covering constraint */
757  	            SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
758  	            SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
759  	
760  	            /* update counters */
761  	            for( v = ntofix-1; v >= 0; v-- )
762  	               if( SCIPvarIsNegated(coveringconsvars[v]) )
763  	                  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
764  	               else
765  	                  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
766  	         }
767  	
768  	         /* free memory for covering constraint */
769  	         SCIPfreeBufferArray(coveringscip, &coveringconsvals);
770  	         SCIPfreeBufferArray(coveringscip, &coveringconsvars);
771  	      }
772  	   }
773  	
774  	   /* go through all bounddisjunction constraints in the original problem */
775  	   conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
776  	   if( conshdlr != NULL && coverbd )
777  	   {
778  	      int c;
779  	
780  	      for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
781  	      {
782  	         SCIP_CONS* bdcons;
783  	         SCIP_CONS* coveringcons;
784  	         SCIP_VAR** bdvars;
785  	         SCIP_VAR** coveringconsvars;
786  	         SCIP_Real* coveringconsvals;
787  	
788  	         int nbdvars;
789  	         int ntofix;
790  	         int v;
791  	
792  	         /* get constraint and variables */
793  	         bdcons = SCIPconshdlrGetConss(conshdlr)[c];
794  	         assert(bdcons != NULL);
795  	         bdvars = SCIPgetVarsBounddisjunction(scip, bdcons);
796  	         assert(bdvars != NULL);
797  	         nbdvars = SCIPgetNVarsBounddisjunction(scip, bdcons);
798  	
799  	         /* bounddisjunction constraints are not passed to the NLP, hence nothing to store in the hash map */
800  	
801  	         /* allocate memory for covering constraint */
802  	         SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, nbdvars) );
803  	         SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, nbdvars) );
804  	
805  	         /* collect unfixed variables */
806  	         BMSclearMemoryArray(consmarker, nvars);
807  	         ntofix = 0;
808  	         for( v = nbdvars-1; v >= 0; v-- )
809  	         {
810  	            SCIP_Bool negated;
811  	
812  	            assert(bdvars[v] != NULL);
813  	            negated = FALSE;
814  	
815  	            /* if variable is fixed, nothing to do */
816  	            if( varIsFixed(scip, bdvars[v], globalbounds ? SCIPvarGetLbGlobal(bdvars[v]) : SCIPvarGetLbLocal(bdvars[v]),
817  	                  globalbounds) )
818  	            {
819  	               continue;
820  	            }
821  	
822  	            /* if constraints with inactive variables are present, we have to find the corresponding active variable */
823  	            probindex = SCIPvarGetProbindex(bdvars[v]);
824  	            if( probindex == -1 )
825  	            {
826  	               SCIP_VAR* repvar;
827  	
828  	               /* get binary representative of variable */
829  	               SCIP_CALL( SCIPgetBinvarRepresentative(scip, bdvars[v], &repvar, &negated) );
830  	               assert(repvar != NULL);
831  	               assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
832  	
833  	               if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
834  	               {
835  	                  SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(bdvars[v]));
836  	                  SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(bdcons));
837  	                  SCIPfreeBufferArray(coveringscip, &coveringconsvals);
838  	                  SCIPfreeBufferArray(coveringscip, &coveringconsvars);
839  	                  goto TERMINATE;
840  	               }
841  	
842  	               /* check for negation */
843  	               if( SCIPvarIsNegated(repvar) )
844  	               {
845  	                  probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
846  	                  negated = TRUE;
847  	               }
848  	               else
849  	               {
850  	                  assert(SCIPvarIsActive(repvar));
851  	                  probindex = SCIPvarGetProbindex(repvar);
852  	                  negated = FALSE;
853  	               }
854  	            }
855  	            assert(probindex >= 0);
856  	            assert(coveringvars[probindex] != NULL);
857  	
858  	            /* add covering variable for unfixed original variable */
859  	            if( negated )
860  	            {
861  	               SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) );
862  	            }
863  	            else
864  	               coveringconsvars[ntofix] = coveringvars[probindex];
865  	            coveringconsvals[ntofix] = 1.0;
866  	            ntofix++;
867  	         }
868  	
869  	         /* if less than two variables are unfixed, the entire constraint can be linearized anyway */
870  	         if( ntofix >= 2 )
871  	         {
872  	            assert(ntofix <= nbdvars);
873  	
874  	            /* create covering constraint */
875  	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(bdcons));
876  	            SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals,
877  	                  (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
878  	                  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
879  	
880  	            if( coveringcons == NULL )
881  	            {
882  	               SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
883  	               SCIPfreeBufferArray(coveringscip, &coveringconsvals);
884  	               SCIPfreeBufferArray(coveringscip, &coveringconsvars);
885  	               goto TERMINATE;
886  	            }
887  	
888  	            /* add and release covering constraint */
889  	            SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) );
890  	            SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) );
891  	
892  	            /* update counters */
893  	            for( v = ntofix-1; v >= 0; v-- )
894  	               if( SCIPvarIsNegated(coveringconsvars[v]) )
895  	                  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v])));
896  	               else
897  	                  incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v]));
898  	         }
899  	
900  	         /* free memory for covering constraint */
901  	         SCIPfreeBufferArray(coveringscip, &coveringconsvals);
902  	         SCIPfreeBufferArray(coveringscip, &coveringconsvars);
903  	      }
904  	   }
905  	
906  	   /* go through all indicator constraints in the original problem; fix the binary variable */
907  	   conshdlr = SCIPfindConshdlr(scip, "indicator");
908  	   if( conshdlr != NULL && coverind )
909  	   {
910  	      int c;
911  	
912  	      for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
913  	      {
914  	         SCIP_CONS* indcons;
915  	         SCIP_VAR* binvar;
916  	         SCIP_VAR* coveringvar;
917  	
918  	         /* get constraint and variables */
919  	         indcons = SCIPconshdlrGetConss(conshdlr)[c];
920  	         assert(indcons != NULL);
921  	         binvar = SCIPgetBinaryVarIndicator(indcons);
922  	         assert(binvar != NULL);
923  	
924  	         /* indicator constraints are not passed to the NLP, hence nothing to store in the hash map */
925  	
926  	         /* if variable is fixed, nothing to do */
927  	         if( varIsFixed(scip, binvar, globalbounds ? SCIPvarGetLbGlobal(binvar) : SCIPvarGetLbLocal(binvar), globalbounds) )
928  	         {
929  	            continue;
930  	         }
931  	
932  	         /* if constraints with inactive variables are present, we have to find the corresponding active variable */
933  	         probindex = SCIPvarGetProbindex(binvar);
934  	         if( probindex == -1 )
935  	         {
936  	            SCIP_VAR* repvar;
937  	            SCIP_Bool negated;
938  	
939  	            /* get binary representative of variable */
940  	            negated = FALSE;
941  	            SCIP_CALL( SCIPgetBinvarRepresentative(scip, binvar, &repvar, &negated) );
942  	            assert(repvar != NULL);
943  	            assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
944  	
945  	            if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR )
946  	            {
947  	               SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(binvar));
948  	               SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(indcons));
949  	               goto TERMINATE;
950  	            }
951  	
952  	            /* check for negation */
953  	            if( SCIPvarIsNegated(repvar) )
954  	               probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
955  	            else
956  	            {
957  	               assert(SCIPvarIsActive(repvar));
958  	               probindex = SCIPvarGetProbindex(repvar);
959  	            }
960  	         }
961  	         assert(probindex >= 0);
962  	         assert(coveringvars[probindex] != NULL);
963  	
964  	         /* get covering variable for unfixed binary variable in indicator constraint */
965  	         coveringvar = coveringvars[probindex];
966  	
967  	         /* require covering variable to be fixed such that indicator is linearized */
968  	         SCIP_CALL( SCIPchgVarLb(coveringscip, coveringvar, 1.0) );
969  	
970  	         /* update counters */
971  	         BMSclearMemoryArray(consmarker, nvars);
972  	         incCounters(termcounter, conscounter, consmarker, probindex);
973  	      }
974  	   }
975  	
976  	   /* go through all nonlinear constraints in the original problem
977  	    * @todo: some expr constraints might be SOC and these only need to have all but one variable fixed in order to be
978  	    * linear; however, by just looking at the nlrow representation of a soc constraint, processNlRow doesn't realize
979  	    * this. if more specific information is accessible from expr constrains, then this can be improved
980  	    */
981  	   conshdlr = SCIPfindConshdlr(scip, "nonlinear");
982  	   if( conshdlr != NULL && covernl )
983  	   {
984  	      int c;
985  	
986  	      for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
987  	      {
988  	         SCIP_CONS* exprcons;
989  	         SCIP_NLROW* nlrow;
990  	
991  	         /* get constraint */
992  	         exprcons = SCIPconshdlrGetConss(conshdlr)[c];
993  	         assert(exprcons != NULL);
994  	
995  	         /* get nlrow representation and store it in hash map */
996  	         SCIP_CALL( SCIPgetNlRowNonlinear(scip, exprcons, &nlrow) );
997  	         assert(nlrow != NULL);
998  	
999  	         /* process nlrow */
1000 	         *success = FALSE;
1001 	         SCIP_CALL( processNlRow(scip, nlrow, coveringscip, nvars, coveringvars,
1002 	               termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
1003 	
1004 	         if( *success == FALSE )
1005 	            goto TERMINATE;
1006 	      }
1007 	
1008 	      *success = FALSE;
1009 	   }
1010 	
1011 	   /* set objective function of covering problem */
1012 	   switch( coveringobj )
1013 	   {
1014 	   case 'c': /* number of influenced nonlinear constraints */
1015 	      for( i = nvars-1; i >= 0; i-- )
1016 	      {
1017 	         if( coveringvars[i] == NULL )
1018 	            continue;
1019 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) conscounter[i]) );
1020 	      }
1021 	      break;
1022 	   case 'd': /* domain size */
1023 	      for( i = nvars-1; i >= 0; i-- )
1024 	      {
1025 	         if( coveringvars[i] == NULL )
1026 	            continue;
1027 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i],
1028 	               (globalbounds ? SCIPvarGetUbGlobal(vars[i]) - SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbLocal(vars[i]) - SCIPvarGetLbLocal(vars[i]))) );
1029 	      }
1030 	      break;
1031 	   case 'l': /* number of locks */
1032 	      for( i = nvars-1; i >= 0; i-- )
1033 	      {
1034 	         if( coveringvars[i] == NULL )
1035 	            continue;
1036 	         nlocksup = SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL);
1037 	         nlocksdown = SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL);
1038 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (nlocksup+nlocksdown+1)) );
1039 	      }
1040 	      break;
1041 	   case 'm': /* min(up locks, down locks)+1 */
1042 	      for( i = nvars-1; i >= 0; i-- )
1043 	      {
1044 	         if( coveringvars[i] == NULL )
1045 	            continue;
1046 	         nlocksup = SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL);
1047 	         nlocksdown = SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL);
1048 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (MIN(nlocksup, nlocksdown)+1)) );
1049 	      }
1050 	      break;
1051 	   case 't': /* number of influenced nonlinear terms */
1052 	      for( i = nvars-1; i >= 0; i-- )
1053 	      {
1054 	         if( coveringvars[i] == NULL )
1055 	            continue;
1056 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) termcounter[i]) );
1057 	      }
1058 	      break;
1059 	   case 'u': /* unit penalties */
1060 	      for( i = nvars-1; i >= 0; i-- )
1061 	      {
1062 	         if( coveringvars[i] == NULL )
1063 	            continue;
1064 	         SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], 1.0) );
1065 	      }
1066 	      break;
1067 	   default:
1068 	      SCIPerrorMessage("invalid choice <%c> for covering objective\n", coveringobj);
1069 	      goto TERMINATE;
1070 	   }
1071 	
1072 	   /* covering problem successfully set up */
1073 	   *success = TRUE;
1074 	
1075 	 TERMINATE:
1076 	   SCIPstatistic(
1077 	      {
1078 		 int nnonzs;
1079 		 nnonzs = 0;
1080 		 for( i = 0; i < nvars; ++i)
1081 		    nnonzs += termcounter[i];
1082 		 SCIPstatisticPrintf("UCstats nnz/var: %9.6f\n", nnonzs/(SCIP_Real)nvars);
1083 		 nnonzs = 0;
1084 		 for( i = 0; i < nvars; ++i)
1085 		    if( conscounter[i] > 0 )
1086 		       nnonzs++;
1087 		 SCIPstatisticPrintf("UCstats nlvars: %6d\n", nnonzs);
1088 	      }
1089 	      );
1090 	
1091 	   /* free counter arrays for weighted objectives */
1092 	   SCIPfreeBufferArray(scip, &termcounter);
1093 	   SCIPfreeBufferArray(scip, &conscounter);
1094 	   SCIPfreeBufferArray(scip, &consmarker);
1095 	
1096 	   return SCIP_OKAY;
1097 	}
1098 	
1099 	
1100 	/** adds a constraint to the covering problem to forbid the given cover */
1101 	static
1102 	SCIP_RETCODE forbidCover(
1103 	   SCIP*                 scip,               /**< SCIP data structure of the covering problem */
1104 	   int                   nvars,              /**< number of variables */
1105 	   SCIP_VAR**            vars,               /**< variable array */
1106 	   int                   coversize,          /**< size of the cover */
1107 	   int*                  cover,              /**< problem indices of the variables in the cover */
1108 	   int                   diversification,    /**< how many unfixed variables have to change their value? */
1109 	   SCIP_Bool*            success,            /**< pointer to store whether the cutoff constraint was created successfully */
1110 	   SCIP_Bool*            infeas              /**< pointer to store whether the cutoff proves (local or global) infeasibility */
1111 	   )
1112 	{
1113 	   SCIP_CONS* cons;
1114 	   SCIP_VAR** consvars;
1115 	
1116 	   char name[SCIP_MAXSTRLEN];
1117 	   int nconsvars;
1118 	   int i;
1119 	
1120 	   assert(scip != NULL);
1121 	   assert(vars != NULL);
1122 	   assert(nvars >= 1);
1123 	   assert(cover != NULL);
1124 	   assert(coversize >= 1);
1125 	   assert(coversize <= nvars);
1126 	   assert(diversification >= 1);
1127 	   assert(success != NULL);
1128 	   assert(infeas != NULL);
1129 	
1130 	   *success = FALSE;
1131 	   *infeas = FALSE;
1132 	
1133 	   /* allocate memory for constraint variables */
1134 	   SCIP_CALL( SCIPallocBufferArray(scip, &consvars, coversize) );
1135 	   nconsvars = 0;
1136 	   cons = NULL;
1137 	
1138 	   /* create constraint name */
1139 	   (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "forbid_cover_assignment");
1140 	
1141 	   /* if all variables in the cover are binary and we require only one variable to change its value, then we create a
1142 	    * set covering constraint
1143 	    */
1144 	   if( diversification == 1 )
1145 	   {
1146 	      /* build up constraint */
1147 	      for( i = coversize-1; i >= 0; i-- )
1148 	      {
1149 	         if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1150 	         {
1151 	            SCIP_CALL( SCIPgetNegatedVar(scip, vars[cover[i]], &consvars[nconsvars]) );
1152 	            nconsvars++;
1153 	         }
1154 	      }
1155 	
1156 	      /* if all covering variables are fixed to one, the constraint cannot be satisfied */
1157 	      if( nconsvars == 0 )
1158 	      {
1159 	         *infeas = TRUE;
1160 	      }
1161 	      else
1162 	      {
1163 	         /* create constraint */
1164 	         SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars,
1165 	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1166 	      }
1167 	   }
1168 	   /* if all variables in the cover are binary and we require more variables to change their value, then we create a
1169 	    * linear constraint
1170 	    */
1171 	   else
1172 	   {
1173 	      SCIP_Real* consvals;
1174 	      SCIP_Real rhs;
1175 	
1176 	      /* build up constraint */
1177 	      SCIP_CALL( SCIPallocBufferArray(scip, &consvals, coversize) );
1178 	      for( i = coversize-1; i >= 0; i-- )
1179 	      {
1180 	         if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1181 	         {
1182 	            consvars[nconsvars] = vars[cover[i]];
1183 	            consvals[nconsvars] = 1.0;
1184 	            nconsvars++;
1185 	         }
1186 	      }
1187 	      rhs = (SCIP_Real) (nconsvars-diversification);
1188 	
1189 	      /* if too many covering variables are fixed to 1, the constraint cannot be satisfied */
1190 	      if( rhs < 0 )
1191 	      {
1192 	         *infeas = TRUE;
1193 	      }
1194 	      else
1195 	      {
1196 	         /* create constraint */
1197 	         SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name,
1198 	               nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
1199 	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
1200 	      }
1201 	
1202 	      /* free memory */
1203 	      SCIPfreeBufferArray(scip, &consvals);
1204 	   }
1205 	
1206 	   /* free memory */
1207 	   SCIPfreeBufferArray(scip, &consvars);
1208 	
1209 	   /* if proven infeasible, we do not even add the constraint; otherwise we add and release the constraint if created
1210 	    * successfully 
1211 	    */
1212 	   if( !(*infeas) && cons != NULL )
1213 	   {
1214 	      SCIP_CALL( SCIPaddCons(scip, cons) );
1215 	      SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1216 	      *success = TRUE;
1217 	   }
1218 	
1219 	   return SCIP_OKAY;
1220 	}
1221 	
1222 	
1223 	/** adds a set covering or bound disjunction constraint to the original problem */
1224 	static
1225 	SCIP_RETCODE createConflict(
1226 	   SCIP*                 scip,               /**< SCIP data structure */
1227 	   int                   bdlen,              /**< length of bound disjunction */
1228 	   SCIP_VAR**            bdvars,             /**< array of variables in bound disjunction */
1229 	   SCIP_BOUNDTYPE*       bdtypes,            /**< array of bound types in bound disjunction */
1230 	   SCIP_Real*            bdbounds,           /**< array of bounds in bound disjunction */
1231 	   SCIP_Bool             local,              /**< is constraint valid only locally? */
1232 	   SCIP_Bool             dynamic,            /**< is constraint subject to aging? */
1233 	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup? */
1234 	   SCIP_Bool*            success             /**< pointer to store whether the cutoff constraint was created successfully */
1235 	   )
1236 	{
1237 	   SCIP_CONS* cons;
1238 	   SCIP_VAR** consvars;
1239 	   SCIP_Bool isbinary;
1240 	   char name[SCIP_MAXSTRLEN];
1241 	   int i;
1242 	
1243 	   assert(scip != NULL);
1244 	   assert(bdlen >= 1);
1245 	   assert(bdvars != NULL);
1246 	   assert(bdtypes != NULL);
1247 	   assert(bdbounds != NULL);
1248 	   assert(success != NULL);
1249 	
1250 	   /* initialize */
1251 	   *success = FALSE;
1252 	   cons = NULL;
1253 	   consvars = NULL;
1254 	
1255 	   /* create constraint name */
1256 	   (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "undercover_cutoff");
1257 	
1258 	   /* check if all variables in the cover are binary */
1259 	   isbinary = TRUE;
1260 	   for( i = bdlen-1; i >= 0 && isbinary; i-- )
1261 	   {
1262 	      isbinary = SCIPvarIsBinary(bdvars[i]);
1263 	   }
1264 	
1265 	   /* if all variables in the cover are binary, then we create a logicor constraint */
1266 	   if( isbinary )
1267 	   {
1268 	      /* allocate memory for constraint variables */
1269 	      SCIP_CALL( SCIPallocBufferArray(scip, &consvars, bdlen) );
1270 	
1271 	      /* build up constraint */
1272 	      for( i = bdlen-1; i >= 0; i-- )
1273 	      {
1274 	         assert(bdtypes[i] == SCIP_BOUNDTYPE_LOWER || SCIPisFeasZero(scip, bdbounds[i]));
1275 	         assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER || SCIPisFeasEQ(scip, bdbounds[i], 1.0));
1276 	
1277 	         if( bdtypes[i] == SCIP_BOUNDTYPE_LOWER )
1278 	         {
1279 	            consvars[i] = bdvars[i];
1280 	         }
1281 	         else
1282 	         {
1283 	            assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER);
1284 	            SCIP_CALL( SCIPgetNegatedVar(scip, bdvars[i], &consvars[i]) );
1285 	         }
1286 	      }
1287 	
1288 	      /* create conflict constraint */
1289 	      SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, bdlen, consvars,
1290 	            FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1291 	   }
1292 	   /* otherwise we create a bound disjunction constraint as given */
1293 	   else
1294 	   {
1295 	      /* create conflict constraint */
1296 	      SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, bdlen, bdvars, bdtypes, bdbounds,
1297 	            FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1298 	   }
1299 	
1300 	   /* add and release constraint if created successfully */
1301 	   if( cons != NULL )
1302 	   {
1303 	      if( local )
1304 	      {
1305 	         SCIP_CALL( SCIPaddConsLocal(scip, cons, NULL) );
1306 	      }
1307 	      else
1308 	      {
1309 	         SCIP_CALL( SCIPaddCons(scip, cons) );
1310 	      }
1311 	
1312 	      SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1313 	      *success = TRUE;
1314 	   }
1315 	
1316 	   /* free memory */
1317 	   SCIPfreeBufferArrayNull(scip, &consvars);
1318 	
1319 	   return SCIP_OKAY;
1320 	}
1321 	
1322 	
1323 	/** solve covering problem */
1324 	static
1325 	SCIP_RETCODE solveCoveringProblem(
1326 	   SCIP*                 coveringscip,       /**< SCIP data structure for the covering problem */
1327 	   int                   ncoveringvars,      /**< number of the covering problem's variables */
1328 	   SCIP_VAR**            coveringvars,       /**< array of the covering problem's variables */
1329 	   int*                  coversize,          /**< size of the computed cover */
1330 	   int*                  cover,              /**< array to store indices of the variables in the computed cover
1331 	                                              *   (should be ready to hold ncoveringvars entries) */
1332 	   SCIP_Real             timelimit,          /**< time limit */
1333 	   SCIP_Real             memorylimit,        /**< memory limit */
1334 	   SCIP_Real             objlimit,           /**< upper bound on the cover size */
1335 	   SCIP_Bool*            success             /**< feasible cover found? */
1336 	   )
1337 	{
1338 	   SCIP_Real totalpenalty;
1339 	   SCIP_RETCODE retcode;
1340 	   int i;
1341 	
1342 	   assert(coveringscip != NULL);
1343 	   assert(coveringvars != NULL);
1344 	   assert(cover != NULL);
1345 	   assert(coversize != NULL);
1346 	   assert(timelimit > 0.0);
1347 	   assert(memorylimit > 0.0);
1348 	   assert(success != NULL);
1349 	
1350 	   *success = FALSE;
1351 	
1352 	   /* forbid call of heuristics and separators solving sub-CIPs */
1353 	   SCIP_CALL( SCIPsetSubscipsOff(coveringscip, TRUE) );
1354 	
1355 	   /* set presolving and separation to fast */
1356 	   SCIP_CALL( SCIPsetSeparating(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) );
1357 	   SCIP_CALL( SCIPsetPresolving(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) );
1358 	
1359 	   /* use inference branching */
1360 	   if( SCIPfindBranchrule(coveringscip, "inference") != NULL && !SCIPisParamFixed(coveringscip, "branching/inference/priority") )
1361 	   {
1362 	      SCIP_CALL( SCIPsetIntParam(coveringscip, "branching/inference/priority", INT_MAX/4) );
1363 	   }
1364 	
1365 	   /* only solve root */
1366 	   SCIP_CALL( SCIPsetLongintParam(coveringscip, "limits/nodes", 1LL) );
1367 	
1368 	   SCIPdebugMsg(coveringscip, "timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1369 	
1370 	   /* set time, memory, and objective limit */
1371 	   SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/time", timelimit) );
1372 	   SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/memory", memorylimit) );
1373 	   SCIP_CALL( SCIPsetObjlimit(coveringscip, objlimit) );
1374 	
1375 	   /* do not abort on CTRL-C */
1376 	   SCIP_CALL( SCIPsetBoolParam(coveringscip, "misc/catchctrlc", FALSE) );
1377 	
1378 	   /* disable output to console in optimized mode, enable in SCIP's debug mode */
1379 	#ifdef SCIP_DEBUG
1380 	   SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 5) );
1381 	   SCIP_CALL( SCIPsetIntParam(coveringscip, "display/freq", 100000) );
1382 	#else
1383 	   SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 0) );
1384 	#endif
1385 	
1386 	   /* solve covering problem */
1387 	   retcode = SCIPsolve(coveringscip);
1388 	
1389 	   /* errors in solving the covering problem should not kill the overall solving process;
1390 	    * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1391 	    */
1392 	   if( retcode != SCIP_OKAY )
1393 	   {
1394 	#ifndef NDEBUG
1395 	      SCIP_CALL( retcode );
1396 	#endif
1397 	      SCIPwarningMessage(coveringscip, "Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1398 	      return SCIP_OKAY;
1399 	   }
1400 	
1401 	   /* check, whether a feasible cover was found */
1402 	   if( SCIPgetNSols(coveringscip) == 0 )
1403 	      return SCIP_OKAY;
1404 	
1405 	   /* store solution */
1406 	   *coversize = 0;
1407 	   totalpenalty = 0.0;
1408 	   for( i = 0; i < ncoveringvars; i++ )
1409 	   {
1410 	      if( coveringvars[i] == NULL )
1411 	         continue;
1412 	
1413 	      if( SCIPgetSolVal(coveringscip, SCIPgetBestSol(coveringscip), coveringvars[i]) > 0.5 )
1414 	      {
1415 	         cover[*coversize] = i;
1416 	         (*coversize)++;
1417 	      }
1418 	      totalpenalty += SCIPvarGetObj(coveringvars[i]);
1419 	   }
1420 	
1421 	   /* print solution if we are in SCIP's debug mode */
1422 	   assert(SCIPgetBestSol(coveringscip) != NULL);
1423 	   SCIPdebugMsg(coveringscip, "found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1424 	      *coversize, SCIPgetNOrigVars(coveringscip), SCIPgetSolOrigObj(coveringscip, SCIPgetBestSol(coveringscip))/(totalpenalty+SCIPsumepsilon(coveringscip)));
1425 	   SCIPdebug( SCIP_CALL( SCIPprintSol(coveringscip, SCIPgetBestSol(coveringscip), NULL, FALSE) ) );
1426 	   SCIPdebugMsg(coveringscip, "\r                                                  \n");
1427 	
1428 	   *success = TRUE;
1429 	
1430 	   return SCIP_OKAY;
1431 	}
1432 	
1433 	
1434 	/** computes fixing order and returns whether order has really been changed */
1435 	static
1436 	SCIP_RETCODE computeFixingOrder(
1437 	   SCIP*                 scip,               /**< original SCIP data structure */
1438 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1439 	   int                   nvars,              /**< number of variables in the original problem */
1440 	   SCIP_VAR**            vars,               /**< variables in the original problem */
1441 	   int                   coversize,          /**< size of the cover */
1442 	   int*                  cover,              /**< problem indices of the variables in the cover */
1443 	   int                   lastfailed,         /**< position in cover array of the variable the fixing of which yielded
1444 	                                              *   infeasibility in last dive (or >= coversize, in which case *success
1445 	                                              *   is always TRUE) */
1446 	   SCIP_Bool*            success             /**< has order really been changed? */
1447 	   )
1448 	{
1449 	   SCIP_Real* scores;
1450 	   SCIP_Real bestscore;
1451 	   SCIP_Bool sortdown;
1452 	   int i;
1453 	
1454 	   assert(scip != NULL);
1455 	   assert(heurdata != NULL);
1456 	   assert(nvars >= 1);
1457 	   assert(vars != NULL);
1458 	   assert(coversize >= 1);
1459 	   assert(cover != NULL);
1460 	   assert(lastfailed >= 0);
1461 	
1462 	   *success = FALSE;
1463 	
1464 	   /* if fixing the first variable had failed, do not try with another order */
1465 	   if( lastfailed == 0 )
1466 	      return SCIP_OKAY;
1467 	
1468 	   /* allocate buffer array for score values */
1469 	   SCIP_CALL( SCIPallocBufferArray(scip, &scores, coversize) );
1470 	
1471 	   /* initialize best score to infinite value */
1472 	   sortdown = (heurdata->fixingorder == 'c' || heurdata->fixingorder == 'v' );
1473 	   bestscore = sortdown ? -SCIPinfinity(scip) : +SCIPinfinity(scip);
1474 	
1475 	   /* compute score values */
1476 	   for( i = coversize-1; i >= 0; i-- )
1477 	   {
1478 	      SCIP_VAR* var;
1479 	
1480 	      /* get variable in the cover */
1481 	      assert(cover[i] >= 0);
1482 	      assert(cover[i] < nvars);
1483 	      var = vars[cover[i]];
1484 	
1485 	      if( heurdata->fixingorder == 'C' || heurdata->fixingorder == 'c' )
1486 	      {
1487 	         /* add a small pertubation value to the score to reduce performance variability */
1488 	         scores[i] = heurdata->conflictweight * SCIPgetVarConflictScore(scip, var)
1489 	            + heurdata->inferenceweight * SCIPgetVarAvgInferenceCutoffScore(scip, var, heurdata->cutoffweight)
1490 	            + SCIPrandomGetReal(heurdata->randnumgen, 0.0, SCIPepsilon(scip));
1491 	      }
1492 	      else if( heurdata->fixingorder == 'V' || heurdata->fixingorder == 'v' )
1493 	         scores[i] = cover[i];
1494 	      else
1495 	         return SCIP_PARAMETERWRONGVAL;
1496 	
1497 	      assert(scores[i] >= 0.0);
1498 	
1499 	      /* update best score */
1500 	      if( sortdown )
1501 	         bestscore = MAX(bestscore, scores[i]);
1502 	      else
1503 	         bestscore = MIN(bestscore, scores[i]);
1504 	   }
1505 	
1506 	   /* put integers to the front */
1507 	   if( heurdata->fixintfirst )
1508 	   {
1509 	      for( i = coversize-1; i >= 0; i-- )
1510 	      {
1511 	         if( SCIPvarIsIntegral(vars[cover[i]]) )
1512 	         {
1513 	            if( sortdown )
1514 	               scores[i] += bestscore+1.0;
1515 	            else
1516 	               scores[i] = bestscore - 1.0/(scores[i]+1.0);
1517 	         }
1518 	      }
1519 	   }
1520 	
1521 	   /* put last failed variable to the front */
1522 	   if( lastfailed < coversize )
1523 	   {
1524 	      if( sortdown )
1525 	         scores[lastfailed] += bestscore+2.0;
1526 	      else
1527 	         scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1528 	      i = cover[lastfailed];
1529 	   }
1530 	
1531 	   /* sort by non-decreasing (negative) score */
1532 	   if( sortdown )
1533 	      SCIPsortDownRealInt(scores, cover, coversize);
1534 	   else
1535 	      SCIPsortRealInt(scores, cover, coversize);
1536 	
1537 	   assert(lastfailed >= coversize || cover[0] == i);
1538 	
1539 	   /* free buffer memory */
1540 	   SCIPfreeBufferArray(scip, &scores);
1541 	
1542 	   *success = TRUE;
1543 	
1544 	   return SCIP_OKAY;
1545 	}
1546 	
1547 	
1548 	/** gets fixing value */
1549 	static
1550 	SCIP_RETCODE getFixingValue(
1551 	   SCIP*                 scip,               /**< original SCIP data structure */
1552 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1553 	   SCIP_VAR*             var,                /**< variable in the original problem */
1554 	   SCIP_Real*            val,                /**< buffer for returning fixing value */
1555 	   char                  fixalt,             /**< source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
1556 	   SCIP_Bool*            success,            /**< could value be retrieved successfully? */
1557 	   int                   bdlen,              /**< current length of probing path */
1558 	   SCIP_VAR**            bdvars,             /**< array of variables with bound changes along probing path */
1559 	   SCIP_BOUNDTYPE*       bdtypes,            /**< array of bound types in bound disjunction */
1560 	   SCIP_Real*            oldbounds           /**< array of bounds before fixing */
1561 	   )
1562 	{
1563 	   assert(scip != NULL);
1564 	   assert(heurdata != NULL);
1565 	   assert(var != NULL);
1566 	   assert(val != NULL);
1567 	   assert(success != NULL);
1568 	
1569 	   *success = FALSE;
1570 	
1571 	   switch( fixalt )
1572 	   {
1573 	   case 'l':
1574 	      /* get the last LP solution value */
1575 	      *val = SCIPvarGetLPSol(var);
1576 	      *success = TRUE;
1577 	      break;
1578 	   case 'n':
1579 	      /* only call this function if NLP relaxation is available */
1580 	      assert(SCIPisNLPConstructed(scip));
1581 	
1582 	      /* the solution values are already available */
1583 	      if( heurdata->nlpsolved )
1584 	      {
1585 	         assert(!heurdata->nlpfailed);
1586 	
1587 	         /* retrieve NLP solution value */
1588 	         *val = SCIPvarGetNLPSol(var);
1589 	         *success = TRUE;
1590 	      }
1591 	      /* solve NLP relaxation unless it has not failed too often before */
1592 	      else if( !heurdata->nlpfailed )
1593 	      {  /*lint --e{850}*/
1594 	         SCIP_NLPSOLSTAT stat;
1595 	         int i;
1596 	
1597 	         /* restore bounds at start of probing, since otherwise, if in backtrack mode, NLP solver becomes most likely
1598 	          * locally infeasible 
1599 	          */
1600 	         SCIP_CALL( SCIPstartDiveNLP(scip) );
1601 	
1602 	         for( i = bdlen-1; i >= 0; i-- )
1603 	         {
1604 	            SCIP_VAR* relaxvar;
1605 	            SCIP_Real lb;
1606 	            SCIP_Real ub;
1607 	
1608 	            relaxvar = bdvars[i];
1609 	
1610 	            /* both bounds were tightened */
1611 	            if( i > 0 && bdvars[i-1] == relaxvar )
1612 	            {
1613 	               assert(bdtypes[i] != bdtypes[i-1]);
1614 	
1615 	               lb = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i] : oldbounds[i-1];
1616 	               ub = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i-1] : oldbounds[i];
1617 	               i--;
1618 	            }
1619 	            /* lower bound was tightened */
1620 	            else if( bdtypes[i] == SCIP_BOUNDTYPE_UPPER )
1621 	            {
1622 	               lb = oldbounds[i];
1623 	               ub = SCIPvarGetUbLocal(relaxvar);
1624 	            }
1625 	            /* upper bound was tightened */
1626 	            else
1627 	            {
1628 	               lb = SCIPvarGetLbLocal(relaxvar);
1629 	               ub = oldbounds[i];
1630 	            }
1631 	
1632 	            assert(SCIPisLE(scip, lb, SCIPvarGetLbLocal(relaxvar)));
1633 	            assert(SCIPisGE(scip, ub, SCIPvarGetUbLocal(relaxvar)));
1634 	
1635 	            /* relax bounds */
1636 	            SCIP_CALL( SCIPchgVarBoundsDiveNLP(scip, relaxvar, lb, ub) );
1637 	         }
1638 	
1639 	         /* set starting point to lp solution */
1640 	         SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1641 	
1642 	         /* solve NLP relaxation */
1643 	         SCIP_CALL( SCIPsolveNLP(scip) );  /*lint !e666*/
1644 	         stat = SCIPgetNLPSolstat(scip);
1645 	         *success = stat == SCIP_NLPSOLSTAT_GLOBOPT || stat == SCIP_NLPSOLSTAT_LOCOPT || stat == SCIP_NLPSOLSTAT_FEASIBLE;
1646 	
1647 	         SCIPdebugMsg(scip, "solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ? "successful" : "failed", stat);
1648 	
1649 	         if( *success )
1650 	         {
1651 	            /* solving succeeded */
1652 	            heurdata->nnlpfails = 0;
1653 	            heurdata->nlpsolved = TRUE;
1654 	
1655 	            /* retrieve NLP solution value */
1656 	            *val = SCIPvarGetNLPSol(var);
1657 	         }
1658 	         else
1659 	         {
1660 	            /* solving failed */
1661 	            heurdata->nnlpfails++;
1662 	            heurdata->nlpfailed = TRUE;
1663 	            heurdata->nlpsolved = FALSE;
1664 	
1665 	            SCIPdebugMsg(scip, "solving NLP relaxation failed (%d time%s%s)\n",
1666 	               heurdata->nnlpfails, heurdata->nnlpfails > 1 ? "s" : "", heurdata->nnlpfails >= MAXNLPFAILS ? ", will not be called again" : "");
1667 	         }
1668 	      }
1669 	      break;
1670 	   case 'i':
1671 	      /* only call this function if a feasible solution is available */
1672 	      assert(SCIPgetBestSol(scip) != NULL);
1673 	
1674 	      /* get value in the incumbent solution */
1675 	      *val = SCIPgetSolVal(scip, SCIPgetBestSol(scip), var);
1676 	      *success = TRUE;
1677 	      break;
1678 	   default:
1679 	      break;
1680 	   }
1681 	
1682 	   /* due to propagation (during probing) it might happen that the LP and NLP solution value of var might be outside of
1683 	    * its bounds
1684 	    */
1685 	   *val = MAX(*val, SCIPvarGetLbLocal(var)); /*lint !e666*/
1686 	   *val = MIN(*val, SCIPvarGetUbLocal(var)); /*lint !e666*/
1687 	
1688 	   return SCIP_OKAY;
1689 	}
1690 	
1691 	
1692 	/** calculates up to four alternative values for backtracking, if fixing the variable failed.
1693 	 * The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value.
1694 	 * For infinite bounds, fixval +/- abs(fixval) will be used instead.
1695 	 */
1696 	static
1697 	void calculateAlternatives(
1698 	   SCIP*                 scip,               /**< original SCIP data structure */
1699 	   SCIP_VAR*             var,                /**< variable to calculate alternatives for */
1700 	   SCIP_Real             fixval,             /**< reference fixing value */
1701 	   int*                  nalternatives,      /**< number of fixing values computed */
1702 	   SCIP_Real*            alternatives        /**< array to store the alternative fixing values */
1703 	   )
1704 	{
1705 	   SCIP_Real lb;
1706 	   SCIP_Real ub;
1707 	
1708 	   /* for binary variables, there is only two possible fixing values */
1709 	   if( SCIPvarIsBinary(var) )
1710 	   {
1711 	      if( SCIPisFeasEQ(scip, fixval, 0.0) || SCIPisFeasEQ(scip, fixval, 1.0) )
1712 	      {
1713 	         alternatives[0] = 1.0 - fixval;
1714 	         *nalternatives = 1;
1715 	      }
1716 	      else
1717 	      {
1718 	         alternatives[0] = 0.0;
1719 	         alternatives[1] = 1.0;
1720 	         *nalternatives = 2;
1721 	      }
1722 	      return;
1723 	   }
1724 	
1725 	   /* get bounds */
1726 	   lb = SCIPvarGetLbLocal(var);
1727 	   ub = SCIPvarGetUbLocal(var);
1728 	
1729 	   /* if lower bound is infinite, use x'-|x'|; if x' is zero, use -1.0 instead */
1730 	   if( SCIPisInfinity(scip, -lb) )
1731 	      lb = SCIPisFeasZero(scip, fixval) ? -1.0 : fixval - ABS(fixval);
1732 	
1733 	   /* if upper bound is infinite, use x'+|x'|; if x' is zero, use 1.0 instead */
1734 	   if( SCIPisInfinity(scip, ub) )
1735 	      ub = SCIPisFeasZero(scip, fixval) ? 1.0 : fixval + ABS(fixval);
1736 	
1737 	   assert(!SCIPisEQ(scip, lb, ub));
1738 	
1739 	   /* collect alternatives */
1740 	   *nalternatives = 0;
1741 	
1742 	   /* use lower bound if not equal to x' */
1743 	   if( !SCIPisFeasEQ(scip, lb, fixval) )
1744 	   {
1745 	      alternatives[*nalternatives] = lb;
1746 	      (*nalternatives)++;
1747 	   }
1748 	
1749 	   /* use upper bound if not equal to x' */
1750 	   if( !SCIPisFeasEQ(scip, ub, fixval) )
1751 	   {
1752 	      alternatives[*nalternatives] = ub;
1753 	      (*nalternatives)++;
1754 	   }
1755 	
1756 	   /* use the average of x' and lower bound as alternative value, if this is not equal to any of the other values */
1757 	   if( !SCIPisFeasEQ(scip, lb, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, lb, fixval-1)) )
1758 	   {
1759 	      alternatives[*nalternatives] = (lb+fixval)/2.0;
1760 	      (*nalternatives)++;
1761 	   }
1762 	
1763 	   /* use the average of x' and upper bound as alternative value, if this is not equal to any of the other values */
1764 	   if( !SCIPisFeasEQ(scip, ub, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, ub, fixval+1)) )
1765 	   {
1766 	      alternatives[*nalternatives] = (ub+fixval)/2.0;
1767 	      (*nalternatives)++;
1768 	   }
1769 	
1770 	   assert(*nalternatives <= 4);
1771 	
1772 	   return;
1773 	}
1774 	
1775 	
1776 	/** rounds the given fixing value */
1777 	static
1778 	SCIP_RETCODE roundFixingValue(
1779 	   SCIP*                 scip,               /**< original SCIP data structure */
1780 	   SCIP_Real*            val,                /**< fixing value to be rounded */
1781 	   SCIP_VAR*             var,                /**< corresponding variable */
1782 	   SCIP_Bool             locksrounding       /**< shall we round according to locks? (otherwise to nearest integer) */
1783 	   )
1784 	{
1785 	   SCIP_Real x;
1786 	
1787 	   x = *val;
1788 	
1789 	   /* if integral within feasibility tolerance, only shift to nearest integer */
1790 	   if( SCIPisFeasIntegral(scip, x) )
1791 	      x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
1792 	
1793 	   /* round in the direction of least locks with fractionality as tie breaker */
1794 	   else if( locksrounding )
1795 	   {
1796 	      if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) )
1797 	         x = SCIPfeasFloor(scip, x);
1798 	      else if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) )
1799 	         x = SCIPfeasCeil(scip, x);
1800 	      else
1801 	         x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
1802 	   }
1803 	   /* round in the direction of least fractionality with locks as tie breaker */
1804 	   else
1805 	   {
1806 	      if( SCIPfeasFrac(scip, x) < 0.5)
1807 	         x = SCIPfeasFloor(scip, x);
1808 	      else if( SCIPfeasFrac(scip, x) > 0.5 )
1809 	         x = SCIPfeasCeil(scip, x);
1810 	      else
1811 	         x = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x);
1812 	   }
1813 	
1814 	   /* return rounded fixing value */
1815 	   *val = x;
1816 	
1817 	   return SCIP_OKAY;
1818 	}
1819 	
1820 	/** solve subproblem and pass best feasible solution to original SCIP instance */
1821 	static
1822 	SCIP_RETCODE solveSubproblem(
1823 	   SCIP*                 scip,               /**< SCIP data structure of the original problem */
1824 	   SCIP_HEUR*            heur,               /**< heuristic data structure */
1825 	   int                   coversize,          /**< size of the cover */
1826 	   int*                  cover,              /**< problem indices of the variables in the cover */
1827 	   SCIP_Real*            fixedvals,          /**< fixing values for the variables in the cover */
1828 	   SCIP_Real             timelimit,          /**< time limit */
1829 	   SCIP_Real             memorylimit,        /**< memory limit */
1830 	   SCIP_Longint          nodelimit,          /**< node limit */
1831 	   SCIP_Longint          nstallnodes,        /**< number of stalling nodes for the subproblem */
1832 	   SCIP_Bool*            validsolved,        /**< was problem constructed from a valid copy and solved (proven optimal or infeasible)? */
1833 	   SCIP_SOL**            sol,                /**< best solution found in subproblem (if feasible); *sol must be NULL, solution will be created */
1834 	   SCIP_Longint*         nusednodes          /**< number of nodes used for solving the subproblem */
1835 	   )
1836 	{
1837 	   SCIP_HEURDATA* heurdata;
1838 	   SCIP* subscip;
1839 	   SCIP_VAR** subvars;
1840 	   SCIP_VAR** vars;
1841 	   SCIP_HASHMAP* varmap;
1842 	   SCIP_VAR** fixedvars;
1843 	   int nfixedvars;
1844 	
1845 	   SCIP_RETCODE retcode;
1846 	
1847 	   int nvars;
1848 	   int i;
1849 	
1850 	   assert(scip != NULL);
1851 	   assert(heur != NULL);
1852 	   assert(cover != NULL);
1853 	   assert(fixedvals != NULL);
1854 	   assert(coversize >= 1);
1855 	   assert(timelimit > 0.0);
1856 	   assert(memorylimit > 0.0);
1857 	   assert(nodelimit >= 1);
1858 	   assert(nstallnodes >= 1);
1859 	   assert(validsolved != NULL);
1860 	   assert(sol != NULL);
1861 	   assert(*sol == NULL);
1862 	   assert(nusednodes != NULL);
1863 	
1864 	   *validsolved = FALSE;
1865 	   *nusednodes = 0;
1866 	
1867 	   /* get heuristic data */
1868 	   heurdata = SCIPheurGetData(heur);
1869 	   assert(heurdata != NULL);
1870 	
1871 	   /* get required data of the original problem */
1872 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1873 	
1874 	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, coversize) );
1875 	   nfixedvars = coversize;
1876 	   /* fix subproblem variables in the cover */
1877 	   SCIPdebugMsg(scip, "fixing variables\n");
1878 	   for( i = coversize-1; i >= 0; i-- )
1879 	   {
1880 	      assert(cover[i] >= 0);
1881 	      assert(cover[i] < nvars);
1882 	
1883 	      fixedvars[i] = vars[cover[i]];
1884 	   }
1885 	
1886 	   /* create subproblem */
1887 	   SCIP_CALL( SCIPcreate(&subscip) );
1888 	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1889 	
1890 	   /* create the variable mapping hash map */
1891 	   SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
1892 	
1893 	   /* copy original problem to subproblem; do not copy pricers */
1894 	   SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", fixedvars, fixedvals, nfixedvars,
1895 	         heurdata->globalbounds, FALSE, FALSE, TRUE, validsolved) );
1896 	
1897 	   if( heurdata->copycuts )
1898 	   {
1899 	      /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
1900 	      SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, heurdata->globalbounds, NULL) );
1901 	   }
1902 	
1903 	   SCIPdebugMsg(scip, "problem copied, copy %svalid\n", *validsolved ? "" : "in");
1904 	
1905 	   /* store subproblem variables */
1906 	   for( i = nvars-1; i >= 0; i-- )
1907 	      subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
1908 	
1909 	   /* free variable mapping hash map */
1910 	   SCIPhashmapFree(&varmap);
1911 	
1912 	   /* set the parameters such that good solutions are found fast */
1913 	   SCIPdebugMsg(scip, "setting subproblem parameters\n");
1914 	   SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
1915 	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
1916 	   SCIP_CALL( SCIPsetHeuristics(subscip, SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
1917 	
1918 	   /* deactivate expensive pre-root heuristics, since it may happen that the lp relaxation of the subproblem is already
1919 	    * infeasible; in this case, we do not want to waste time on heuristics before solving the root lp */
1920 	   if( !SCIPisParamFixed(subscip, "heuristics/shiftandpropagate/freq") )
1921 	   {
1922 	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shiftandpropagate/freq", -1) );
1923 	   }
1924 	   if( !SCIPisParamFixed(subscip, "heuristics/zeroobj/freq") )
1925 	   {
1926 	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zeroobj/freq", -1) );
1927 	   }
1928 	
1929 	   /* forbid recursive call of undercover heuristic */
1930 	   if( SCIPisParamFixed(subscip, "heuristics/" HEUR_NAME "/freq") )
1931 	   {
1932 	      SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
1933 	      SCIP_CALL( SCIPunfixParam(subscip, "heuristics/" HEUR_NAME "/freq") );
1934 	   }
1935 	   SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/" HEUR_NAME "/freq", -1) );
1936 	
1937 	   SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
1938 	
1939 	   SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
1940 	
1941 	   /* disable statistic timing inside sub SCIP */
1942 	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1943 	
1944 	   /* set time, memory and node limits */
1945 	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1946 	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1947 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
1948 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
1949 	
1950 	   /* do not abort subproblem on CTRL-C */
1951 	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1952 	
1953 	   /* disable output to console in optimized mode, enable in SCIP's debug mode */
1954 	#ifdef SCIP_DEBUG
1955 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1956 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000) );
1957 	#else
1958 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1959 	#endif
1960 	
1961 	   /* if there is already a solution, add an objective cutoff; note: this does not affect the validity of the subproblem
1962 	    * if we find solutions later, thus we do not set *validsolved to FALSE */
1963 	   if( SCIPgetNSols(scip) > 0 )
1964 	   {
1965 	      SCIP_Real cutoff;
1966 	      SCIP_Real upperbound;
1967 	
1968 	      assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
1969 	      upperbound = SCIPgetUpperbound(scip);
1970 	
1971 	      if( SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) )
1972 	         cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
1973 	      else
1974 	         cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove * SCIPgetLowerbound(scip);
1975 	
1976 	      cutoff = MIN(upperbound, cutoff);
1977 	      SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
1978 	
1979 	      SCIPdebugMsg(scip, "adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
1980 	   }
1981 	
1982 	   /* solve subproblem */
1983 	   SCIPdebugMsg(scip, "solving subproblem started\n");
1984 	   retcode = SCIPsolve(subscip);
1985 	
1986 	   /* Errors in solving the subproblem should not kill the overall solving process
1987 	    * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1988 	    */
1989 	   if( retcode != SCIP_OKAY )
1990 	   {
1991 	#ifndef NDEBUG
1992 	      SCIP_CALL( retcode );
1993 	#endif
1994 	      SCIPwarningMessage(scip, "Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1995 	      /* free array of subproblem variables, and subproblem */
1996 	      SCIPfreeBufferArray(scip, &subvars);
1997 	      SCIPfreeBufferArray(scip, &fixedvars);
1998 	      SCIP_CALL( SCIPfree(&subscip) );
1999 	      return SCIP_OKAY;
2000 	   }
2001 	
2002 	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
2003 	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
2004 	
2005 	   /* store solving status; note: if we proved infeasibility in presence of an objective cutoff beyond the primal bound,
2006 	    * the subproblem was not a valid copy */
2007 	   *validsolved = *validsolved && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL
2008 	      || (SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE && (SCIPgetNSols(scip) == 0 || heurdata->minimprove <= 0.0)));
2009 	   *nusednodes = SCIPgetNNodes(subscip);
2010 	
2011 	   /* if a solution was found for the subproblem, create corresponding solution in the original problem */
2012 	   if( SCIPgetNSols(subscip) > 0 && (SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE || heurdata->minimprove > 0.0) )
2013 	   {
2014 	      SCIP_SOL** subsols;
2015 	      SCIP_Bool success = FALSE;
2016 	      int nsubsols;
2017 	
2018 	      /* check, whether a solution was found;
2019 	       * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
2020 	      nsubsols = SCIPgetNSols(subscip);
2021 	      subsols = SCIPgetSols(subscip);
2022 	      assert(subsols != NULL);
2023 	
2024 	      for( i = 0; i < nsubsols; i++ )
2025 	      {
2026 	         /* transform solution to original problem */
2027 	         SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, sol) );
2028 	
2029 	         /* try to add new solution to scip */
2030 	         SCIP_CALL( SCIPtrySol(scip, *sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2031 	
2032 	         if( success )
2033 	         {
2034 	            SCIPdebugMsg(scip, "heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2035 	            break;
2036 	         }
2037 	         else
2038 	         {
2039 	            /* free solution structure, since SCIPtranslateSubSol would recreate in the next round */
2040 	            SCIP_CALL( SCIPfreeSol(scip, sol) );
2041 	            assert(*sol == NULL);
2042 	         }
2043 	      }
2044 	
2045 	      /* if the best subproblem solution was not accepted in the original problem, then we do not trust the solving status */
2046 	      if( !success || i > 0 )
2047 	         *validsolved = FALSE;
2048 	   }
2049 	
2050 	   if( *validsolved )
2051 	   {
2052 	      SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2053 	   }
2054 	
2055 	   /* free array of subproblem variables, and subproblem */
2056 	   SCIPfreeBufferArray(scip, &subvars);
2057 	   SCIPfreeBufferArray(scip, &fixedvars);
2058 	   SCIP_CALL( SCIPfree(&subscip) );
2059 	
2060 	   return SCIP_OKAY;
2061 	}
2062 	
2063 	
2064 	/** perform fixing of a variable and record bound disjunction information */
2065 	static
2066 	SCIP_RETCODE performFixing(
2067 	   SCIP*                 scip,               /**< SCIP data structure */
2068 	   SCIP_VAR*             var,                /**< variable to fix */
2069 	   SCIP_Real             val,                /**< fixing value */
2070 	   SCIP_Bool*            infeas,             /**< pointer to store whether the fixing lead to infeasibility */
2071 	   int*                  bdlen,              /**< current length of bound disjunction */
2072 	   SCIP_VAR**            bdvars,             /**< array of variables in bound disjunction */
2073 	   SCIP_BOUNDTYPE*       bdtypes,            /**< array of bound types in bound disjunction */
2074 	   SCIP_Real*            bdbounds,           /**< array of bounds in bound disjunction */
2075 	   SCIP_Real*            oldbounds           /**< array of bounds before fixing */
2076 	   )
2077 	{
2078 	   SCIP_Longint ndomredsfound;
2079 	   SCIP_Real oldlb;
2080 	   SCIP_Real oldub;
2081 	   int oldbdlen;
2082 	
2083 	   assert(scip != NULL);
2084 	   assert(var != NULL);
2085 	   assert(val >= SCIPvarGetLbLocal(var));
2086 	   assert(val <= SCIPvarGetUbLocal(var));
2087 	   assert(infeas != NULL);
2088 	   assert(bdlen != NULL);
2089 	   assert(*bdlen >= 0);
2090 	   assert(*bdlen < 2*SCIPgetNVars(scip)-1);
2091 	   assert(bdvars != NULL);
2092 	   assert(bdtypes != NULL);
2093 	   assert(bdbounds != NULL);
2094 	
2095 	   assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2096 	
2097 	   /* remember length of probing path */
2098 	   oldbdlen = *bdlen;
2099 	
2100 	   /* get bounds of the variable to fix */
2101 	   oldlb = SCIPvarGetLbLocal(var);
2102 	   oldub = SCIPvarGetUbLocal(var);
2103 	
2104 	   /* decrease upper bound to fixing value */
2105 	   *infeas = FALSE;
2106 	   if( SCIPisUbBetter(scip, val, oldlb, oldub) )
2107 	   {
2108 	      /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2109 	      if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2110 	      {
2111 	         /* create next probing node */
2112 	         SCIP_CALL( SCIPnewProbingNode(scip) );
2113 	      }
2114 	      SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) );
2115 	
2116 	      SCIPdebugMsg(scip, "tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2117 	         SCIPvarGetName(var), val);
2118 	
2119 	      /* store bound disjunction information */
2120 	      bdvars[*bdlen] = var;
2121 	      bdtypes[*bdlen] = SCIP_BOUNDTYPE_LOWER;
2122 	      bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)+1.0 : val;
2123 	      oldbounds[*bdlen] = oldub;
2124 	      (*bdlen)++;
2125 	
2126 	      /* propagate the bound change; conflict analysis is performed automatically */
2127 	      SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2128 	      SCIPdebugMsg(scip, "  --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2129 	
2130 	      /* if propagation led to a cutoff, we backtrack immediately */
2131 	      if( *infeas )
2132 	      {
2133 	         *bdlen = oldbdlen;
2134 	         return SCIP_OKAY;
2135 	      }
2136 	
2137 	      /* store bound before propagation */
2138 	      oldbounds[*bdlen] = oldlb;
2139 	
2140 	      /* move fixing value into the new domain, since it may be outside due to numerical issues or previous propagation */
2141 	      oldlb = SCIPvarGetLbLocal(var);
2142 	      oldub = SCIPvarGetUbLocal(var);
2143 	      val = MIN(val, oldub);
2144 	      val = MAX(val, oldlb);
2145 	
2146 	      assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val));
2147 	   }
2148 	
2149 	   /* update lower bound to fixing value */
2150 	   *infeas = FALSE;
2151 	   if( SCIPisLbBetter(scip, val, oldlb, oldub) )
2152 	   {
2153 	      /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2154 	      if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
2155 	      {
2156 	         /* create next probing node */
2157 	         SCIP_CALL( SCIPnewProbingNode(scip) );
2158 	      }
2159 	      SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) );
2160 	
2161 	      SCIPdebugMsg(scip, "tentatively increasing lower bound of variable <%s> to %g for probing\n",
2162 	         SCIPvarGetName(var), val);
2163 	
2164 	      /* store bound disjunction information */
2165 	      bdvars[*bdlen] = var;
2166 	      bdtypes[*bdlen] = SCIP_BOUNDTYPE_UPPER;
2167 	      bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)-1.0 : val;
2168 	      (*bdlen)++;
2169 	
2170 	      /* propagate the bound change */
2171 	      SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2172 	      SCIPdebugMsg(scip, "  --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2173 	
2174 	      /* if propagation led to a cutoff, we backtrack immediately */
2175 	      if( *infeas )
2176 	      {
2177 	         *bdlen = oldbdlen;
2178 	         return SCIP_OKAY;
2179 	      }
2180 	   }
2181 	
2182 	   return SCIP_OKAY;
2183 	}
2184 	
2185 	static
2186 	SCIP_RETCODE fixAndPropagate(
2187 	   SCIP*                 scip,               /**< original SCIP data structure */
2188 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
2189 	   int*                  cover,              /**< array with indices of the variables in the computed cover */
2190 	   int                   coversize,          /**< size of the cover */
2191 	   SCIP_Real*            fixingvals,         /**< fixing values for the variables in the cover */
2192 	   int*                  bdlen,              /**< current length of bound disjunction along the probing path */
2193 	   SCIP_VAR**            bdvars,             /**< array of variables in bound disjunction */
2194 	   SCIP_BOUNDTYPE*       bdtypes,            /**< array of bound types in bound disjunction */
2195 	   SCIP_Real*            bdbounds,           /**< array of bounds in bound disjunction */
2196 	   SCIP_Real*            oldbounds,          /**< array of bounds before fixing */
2197 	   int*                  nfixedints,         /**< pointer to store number of fixed integer variables */
2198 	   int*                  nfixedconts,        /**< pointer to store number of fixed continuous variables */
2199 	   int*                  lastfailed,         /**< position in cover array of the variable the fixing of which yielded
2200 	                                              *   infeasibility */
2201 	   SCIP_Bool*            infeas              /**< pointer to store whether fix-and-propagate led to an infeasibility */
2202 	   )
2203 	{
2204 	   SCIP_VAR** vars;                          /* original problem's variables */
2205 	
2206 	   int i;
2207 	   SCIP_Bool lpsolved;
2208 	
2209 	   /* start probing in original problem */
2210 	   lpsolved = SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL;
2211 	   SCIP_CALL( SCIPstartProbing(scip) );
2212 	
2213 	   /* initialize data */
2214 	   *nfixedints = 0;
2215 	   *nfixedconts = 0;
2216 	   *bdlen = 0;
2217 	   vars = SCIPgetVars(scip);
2218 	
2219 	   /* round-fix-propagate-analyze-backtrack for each variable in the cover
2220 	    * TODO doing a fix-and-propagate for one variable at a time can be very expensive for large covers
2221 	    *    (try, e.g., junkturn with maxcoversizevars=1)
2222 	    *    consider splitting the cover into at most, say, 100 batches, and fix a complete batch before propagating
2223 	    */
2224 	   for( i = 0; i < coversize && !(*infeas); i++ )
2225 	   {
2226 	      SCIP_Real* boundalts;
2227 	      SCIP_Real* usedvals;
2228 	      SCIP_Real val;
2229 	      int nbacktracks;
2230 	      int nboundalts;
2231 	      int nfailedvals;
2232 	      int nusedvals;
2233 	      int probingdepth;
2234 	      int idx;
2235 	
2236 	      /* get probindex of next variable in the cover */
2237 	      idx = cover[i];
2238 	
2239 	      /* nothing to do if the variable was already fixed, e.g., by propagation */
2240 	      if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[idx]), SCIPvarGetUbLocal(vars[idx])) )
2241 	      {
2242 	         fixingvals[i] = SCIPvarGetLbLocal(vars[idx]);
2243 	         continue;
2244 	      }
2245 	
2246 	      /* we will store the fixing values already used to avoid try the same value twice */
2247 	      SCIP_CALL( SCIPallocBufferArray(scip, &usedvals, heurdata->maxbacktracks+1) );
2248 	      nusedvals = 0;
2249 	
2250 	      /* backtracking loop */
2251 	      *infeas = TRUE;
2252 	      nfailedvals = 0;
2253 	      nboundalts = 0;
2254 	      boundalts = NULL;
2255 	      val = 0.0;
2256 	      for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2257 	      {
2258 	         SCIP_Real oldlb;
2259 	         SCIP_Real oldub;
2260 	         SCIP_Bool usedbefore;
2261 	         int j;
2262 	
2263 	         probingdepth = SCIPgetProbingDepth(scip);
2264 	
2265 	         /* get fixing value */
2266 	         if( nbacktracks < heurdata->nfixingalts )
2267 	         {
2268 	            SCIP_Bool success;
2269 	
2270 	            /* if the lp relaxation is not solved, we do not even try to retrieve the lp solution value;
2271 	             * if the NLP relaxation is not constructed, we do not even try to retrieve the NLP solution value;
2272 	             * if there is no feasible solution yet, we do not even try to obtain the value in the incumbent */
2273 	            success = FALSE;
2274 	            if( (heurdata->fixingalts[nbacktracks] != 'l' || lpsolved)
2275 	               && (heurdata->fixingalts[nbacktracks] != 'n' || !heurdata->nlpfailed)
2276 	               && (heurdata->fixingalts[nbacktracks] != 'i' || SCIPgetBestSol(scip) != NULL) )
2277 	            {
2278 	               SCIP_CALL( getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2279 	            }
2280 	
2281 	            if( !success )
2282 	            {
2283 	               SCIPdebugMsg(scip, "retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2284 	                  heurdata->fixingalts[nbacktracks], SCIPvarGetName(vars[idx]));
2285 	               nfailedvals++;
2286 	               continue;
2287 	            }
2288 	
2289 	            /* for the first (successfully retrieved) fixing value, compute (at most 4) bound dependent
2290 	             * alternative fixing values */
2291 	            if( boundalts == NULL )
2292 	            {
2293 	               SCIP_CALL( SCIPallocBufferArray(scip, &boundalts, 4) );
2294 	               nboundalts = 0;
2295 	               calculateAlternatives(scip, vars[idx], val, &nboundalts, boundalts);
2296 	               assert(nboundalts >= 0);
2297 	               assert(nboundalts <= 4);
2298 	            }
2299 	         }
2300 	         /* get alternative fixing value */
2301 	         else if( boundalts != NULL && nbacktracks <  heurdata->nfixingalts+nboundalts )
2302 	         {
2303 	            assert(nbacktracks-heurdata->nfixingalts >= 0);
2304 	            val = boundalts[nbacktracks-heurdata->nfixingalts];
2305 	         }
2306 	         else
2307 	            break;
2308 	
2309 	         /* round fixing value */
2310 	         if( SCIPvarIsIntegral(vars[idx]) && !SCIPisIntegral(scip, val) )
2311 	         {
2312 	            SCIP_CALL( roundFixingValue(scip, &val, vars[idx], heurdata->locksrounding) );
2313 	            assert(SCIPisIntegral(scip, val));
2314 	         }
2315 	
2316 	         /* move value into the domain, since it may be outside due to numerical issues or previous propagation */
2317 	         oldlb = SCIPvarGetLbLocal(vars[idx]);
2318 	         oldub = SCIPvarGetUbLocal(vars[idx]);
2319 	         val = MIN(val, oldub);
2320 	         val = MAX(val, oldlb);
2321 	
2322 	         assert(!SCIPvarIsIntegral(vars[idx]) || SCIPisFeasIntegral(scip, val));
2323 	
2324 	         /* check if this fixing value was already used */
2325 	         usedbefore = FALSE;
2326 	         for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2327 	            usedbefore = SCIPisFeasEQ(scip, val, usedvals[j]);
2328 	
2329 	         if( usedbefore )
2330 	         {
2331 	            nfailedvals++;
2332 	            continue;
2333 	         }
2334 	
2335 	         /* store fixing value */
2336 	         assert(nusedvals < heurdata->maxbacktracks);
2337 	         usedvals[nusedvals] = val;
2338 	         nusedvals++;
2339 	
2340 	         /* fix-propagate-analyze */
2341 	         SCIP_CALL( performFixing(scip, vars[idx], val, infeas, bdlen, bdvars, bdtypes, bdbounds, oldbounds) );
2342 	
2343 	         /* if infeasible, backtrack and try alternative fixing value */
2344 	         if( *infeas )
2345 	         {
2346 	            SCIPdebugMsg(scip, "  --> cutoff detected - backtracking\n");
2347 	            SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2348 	         }
2349 	      }
2350 	
2351 	      /* free array of alternative backtracking values */
2352 	      if( boundalts != NULL)
2353 	         SCIPfreeBufferArray(scip, &boundalts);
2354 	      SCIPfreeBufferArray(scip, &usedvals);
2355 	
2356 	      /* backtracking loop unsuccessful */
2357 	      if( *infeas )
2358 	      {
2359 	         SCIPdebugMsg(scip, "no feasible fixing value found for variable <%s> in fixing order\n",
2360 	            SCIPvarGetName(vars[idx]));
2361 	         break;
2362 	      }
2363 	      /* fixing successful */
2364 	      else
2365 	      {
2366 	         /* store successful fixing value */
2367 	         fixingvals[i] = val;
2368 	
2369 	         /* statistics */
2370 	         if( SCIPvarGetType(vars[idx]) == SCIP_VARTYPE_CONTINUOUS )
2371 	            (*nfixedconts)++;
2372 	         else
2373 	            (*nfixedints)++;
2374 	      }
2375 	   }
2376 	   assert(*infeas || i == coversize);
2377 	   assert(!(*infeas) || i < coversize);
2378 	
2379 	   /* end of dive */
2380 	   SCIP_CALL( SCIPendProbing(scip) );
2381 	
2382 	   *lastfailed = i;
2383 	
2384 	   return SCIP_OKAY;
2385 	}
2386 	
2387 	/** main procedure of the undercover heuristic */
2388 	static
2389 	SCIP_RETCODE SCIPapplyUndercover(
2390 	   SCIP*                 scip,               /**< original SCIP data structure */
2391 	   SCIP_HEUR*            heur,               /**< heuristic data structure */
2392 	   SCIP_RESULT*          result,             /**< result data structure */
2393 	   SCIP_Real             timelimit,          /**< time limit */
2394 	   SCIP_Real             memorylimit,        /**< memory limit */
2395 	   SCIP_Longint          nstallnodes         /**< number of stalling nodes for the subproblem */
2396 	   )
2397 	{
2398 	   SCIP_HEURDATA* heurdata;                  /* heuristic data */
2399 	   SCIP_VAR** vars;                          /* original problem's variables */
2400 	   SCIP_CLOCK* clock;                        /* clock for updating time limit */
2401 	
2402 	   SCIP* coveringscip;                       /* SCIP data structure for covering problem */
2403 	   SCIP_VAR** coveringvars;                  /* covering variables */
2404 	   SCIP_Real* fixingvals;                    /* array for storing fixing values used */
2405 	   int* cover;                               /* array to store problem indices of variables in the computed cover */
2406 	
2407 	   SCIP_VAR** bdvars;                        /* array of variables in bound disjunction along the probing path */
2408 	   SCIP_BOUNDTYPE* bdtypes;                  /* array of bound types in bound disjunction along the probing path */
2409 	   SCIP_Real* bdbounds;                      /* array of bounds in bound disjunction along the probing path */
2410 	   SCIP_Real* oldbounds;                     /* array of bounds before fixing along the probing path */
2411 	
2412 	   SCIP_Real maxcoversize;
2413 	
2414 	   int coversize;
2415 	   int nvars;
2416 	   int ncovers;
2417 	   int nunfixeds;
2418 	   int nnlconss;
2419 	   int i;
2420 	
2421 	   SCIP_Bool success;
2422 	   SCIP_Bool reusecover;
2423 	
2424 	   assert(scip != NULL);
2425 	   assert(heur != NULL);
2426 	   assert(result != NULL);
2427 	   assert(*result == SCIP_DIDNOTFIND);
2428 	
2429 	   /* create and start timing */
2430 	   SCIP_CALL( SCIPcreateClock(scip, &clock) );
2431 	   SCIP_CALL( SCIPstartClock(scip, clock) );
2432 	
2433 	   /* initialize */
2434 	   fixingvals = NULL;
2435 	   cover = NULL;
2436 	   bdvars = NULL;
2437 	   bdtypes = NULL;
2438 	   bdbounds = NULL;
2439 	   oldbounds = NULL;
2440 	   coversize = 0;
2441 	
2442 	   /* get heuristic data */
2443 	   heurdata = SCIPheurGetData(heur);
2444 	   assert(heurdata != NULL);
2445 	
2446 	   /* NLP relaxation has not been solved yet (only solve once, not again for each cover or dive, because it is expensive) */
2447 	   heurdata->nlpsolved = FALSE;
2448 	
2449 	   /* if solving the NLP relaxation has failed too often in previous runs, or NLP and NLP solver is not available, we do
2450 	    * not even try 
2451 	    */
2452 	   heurdata->nlpfailed = heurdata->nnlpfails >= MAXNLPFAILS || !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0;
2453 	
2454 	   /* get variable data of original problem */
2455 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2456 	
2457 	   /* get number of nonlinear constraints */
2458 	   nnlconss = 0;
2459 	   for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2460 	      nnlconss += SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[i]);
2461 	   assert(nnlconss >= 0);
2462 	   assert(nnlconss <= SCIPgetNConss(scip));
2463 	
2464 	   /* run only if problem is sufficiently nonlinear */
2465 	   if( nnlconss < (SCIP_Real) SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2466 	   {
2467 	      SCIPdebugMsg(scip, "too few nonlinear constraints present, not running\n");
2468 	
2469 	      /* free clock */
2470 	      SCIP_CALL( SCIPfreeClock(scip, &clock) );
2471 	
2472 	      return SCIP_OKAY;
2473 	   }
2474 	
2475 	   /* calculate upper bound for cover size */
2476 	   if( heurdata->maxcoversizevars < 1.0 )
2477 	   {
2478 	      maxcoversize = 0.0;
2479 	      for( i = 0; i < nvars; ++i )
2480 	         if( !SCIPvarIsRelaxationOnly(vars[i]) )
2481 	            maxcoversize += 1.0;
2482 	      maxcoversize *= heurdata->maxcoversizevars;
2483 	   }
2484 	   else
2485 	   {
2486 	      /* if maxcoversizevars == 1.0, then there is no limit derived from number of variables */
2487 	      maxcoversize = (SCIP_Real)nvars;
2488 	   }
2489 	   if( heurdata->maxcoversizeconss < SCIP_REAL_MAX )
2490 	   {
2491 	      SCIP_Real maxcoversizeconss;
2492 	      maxcoversizeconss = heurdata->maxcoversizeconss * nnlconss / ((SCIP_Real) SCIPgetNConss(scip));
2493 	      maxcoversize = MIN(maxcoversize, maxcoversizeconss);
2494 	   }
2495 	
2496 	   /* create covering problem */
2497 	   success = FALSE;
2498 	   SCIP_CALL( SCIPcreate(&coveringscip) );
2499 	   SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
2500 	   SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
2501 	   SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, heurdata->globalbounds, heurdata->onlyconvexify,
2502 	         heurdata->coverand, heurdata->coverbd, heurdata->coverind, heurdata->covernl, heurdata->coveringobj,
2503 	         &success) );
2504 	
2505 	   if( !success )
2506 	   {
2507 	      SCIPdebugMsg(scip, "creating covering problem failed, terminating\n");
2508 	      goto TERMINATE;
2509 	   }
2510 	   else
2511 	   {
2512 	      SCIPdebugMsg(scip, "covering problem created successfully\n");
2513 	   }
2514 	
2515 	   /* count number of unfixed covering variables */
2516 	   nunfixeds = 0;
2517 	   for( i = nvars-1; i >= 0; i-- )
2518 	   {
2519 	      if( coveringvars[i] != NULL && SCIPisFeasEQ(coveringscip, SCIPvarGetLbGlobal(coveringvars[i]), 1.0) )
2520 	         nunfixeds++;
2521 	   }
2522 	
2523 	   /* update time limit */
2524 	   SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2525 	
2526 	   if( timelimit <= MINTIMELEFT )
2527 	   {
2528 	      SCIPdebugMsg(scip, "time limit hit, terminating\n");
2529 	      goto TERMINATE;
2530 	   }
2531 	
2532 	   /* update memory left */
2533 	   memorylimit -= SCIPgetMemUsed(coveringscip)/1048576.0;
2534 	   memorylimit -= SCIPgetMemExternEstim(coveringscip)/1048576.0;
2535 	
2536 	   /* allocate memory for storing bound disjunction information along probing path */
2537 	   SCIP_CALL( SCIPallocBufferArray(scip, &bdvars, 2*nvars) );
2538 	   SCIP_CALL( SCIPallocBufferArray(scip, &bdtypes, 2*nvars) );
2539 	   SCIP_CALL( SCIPallocBufferArray(scip, &bdbounds, 2*nvars) );
2540 	   SCIP_CALL( SCIPallocBufferArray(scip, &oldbounds, 2*nvars) );
2541 	
2542 	   /* initialize data for recovering loop */
2543 	   SCIP_CALL( SCIPallocBufferArray(scip, &cover, nvars) );
2544 	   SCIP_CALL( SCIPallocBufferArray(scip, &fixingvals, nvars) );
2545 	   ncovers = 0;
2546 	   success = FALSE;
2547 	   reusecover = FALSE;
2548 	
2549 	   heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2550 	   assert(heurdata->nfixingalts >= 1);
2551 	
2552 	   /* recovering loop */
2553 	   while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2554 	   {
2555 	      int lastfailed;
2556 	      int ndives;
2557 	      int nfixedints;
2558 	      int nfixedconts;
2559 	      int bdlen;                                /* current length of bound disjunction along the probing path */
2560 	
2561 	      SCIP_Bool conflictcreated;
2562 	
2563 	      SCIPdebugMsg(scip, "solving covering problem\n\n");
2564 	      success = FALSE;
2565 	      bdlen = 0;
2566 	      conflictcreated = FALSE;
2567 	
2568 	      /* solve covering problem */
2569 	      if( !reusecover )
2570 	      {
2571 	         SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, &coversize, cover,
2572 	               timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, maxcoversize, &success) );
2573 	
2574 	         SCIPstatistic(
2575 	            if( ncovers == 0 && success )
2576 	               SCIPstatisticPrintf("UCstats coversize abs: %6d rel: %9.6f\n", coversize, 100.0*coversize /(SCIP_Real)nvars);
2577 	            );
2578 	
2579 	         assert(coversize >= 0);
2580 	         assert(coversize <= nvars);
2581 	         ncovers++;
2582 	
2583 	         /* free transformed covering problem immediately */
2584 	         SCIP_CALL( SCIPfreeTransform(coveringscip) );
2585 	
2586 	         /* terminate if no feasible cover was found */
2587 	         if( !success )
2588 	         {
2589 	            SCIPdebugMsg(scip, "no feasible cover found in covering problem %d, terminating\n", ncovers);
2590 	            goto TERMINATE;
2591 	         }
2592 	
2593 	         /* terminate, if cover is empty or too large */
2594 	         if( coversize == 0 || coversize > maxcoversize )
2595 	         {
2596 	            SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2597 	            goto TERMINATE;
2598 	         }
2599 	
2600 	         /* terminate, if cover too large for the ratio of nonlinear constraints */
2601 	         if( heurdata->maxcoversizeconss < SCIP_REAL_MAX && coversize > heurdata->maxcoversizeconss * nnlconss / (SCIP_Real) SCIPgetNConss(scip) )
2602 	         {
2603 	            SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2604 	            goto TERMINATE;
2605 	         }
2606 	      }
2607 	
2608 	      /* data setup */
2609 	      ndives = 0;
2610 	      nfixedints = 0;
2611 	      nfixedconts = 0;
2612 	      success = FALSE;
2613 	      lastfailed = reusecover ? MAX(1, coversize-1) : coversize;
2614 	
2615 	      /* round-fix-propagate-analyze-backtrack-reorder loop */
2616 	      while( ndives <= heurdata->maxreorders && !success )
2617 	      {
2618 	         SCIP_Bool reordered;
2619 	         SCIP_Bool infeas;
2620 	
2621 	         /* compute fixing order */
2622 	         SCIP_CALL( computeFixingOrder(scip, heurdata, nvars, vars, coversize, cover, lastfailed, &reordered) );
2623 	         reordered = reordered || ndives == 0;
2624 	         SCIPdebugMsg(scip, "%sordering variables in cover %s\n", ndives == 0 ? "" : "re", reordered ? "" : "failed");
2625 	
2626 	         /* stop if order has not changed */
2627 	         if( !reordered )
2628 	            break;
2629 	
2630 	         infeas = FALSE;
2631 	         SCIP_CALL( fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds,
2632 	               &nfixedints, &nfixedconts, &lastfailed, &infeas) );
2633 	         ndives++;
2634 	         success = !infeas;
2635 	      }
2636 	
2637 	      /* update time limit */
2638 	      SCIPdebugMsg(scip, "%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ? "s" : "", ncovers, SCIPgetClockTime(scip, clock));
2639 	      SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2640 	
2641 	      if( timelimit <= MINTIMELEFT )
2642 	      {
2643 	         SCIPdebugMsg(scip, "time limit hit, terminating\n");
2644 	         goto TERMINATE;
2645 	      }
2646 	
2647 	      /* no feasible fixing could be found for the current cover */
2648 	      if( !success )
2649 	      {
2650 	         SCIPdebugMsg(scip, "no feasible fixing values found for cover %d\n", ncovers);
2651 	      }
2652 	      else
2653 	      {
2654 	         SCIP_SOL* sol;
2655 	         SCIP_Longint nsubnodes;
2656 	         SCIP_Bool validsolved;
2657 	
2658 	         SCIPdebugMsg(scip, "heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2659 	            nfixedints+nfixedconts, nfixedints, nfixedconts); /*lint !e771*/
2660 	
2661 	         /* solve sub-CIP and pass feasible solutions to original problem */
2662 	         success = FALSE;
2663 	         validsolved = FALSE;
2664 	         sol = NULL;
2665 	         nsubnodes = 0;
2666 	
2667 	         SCIP_CALL( solveSubproblem(scip, heur, coversize, cover, fixingvals,
2668 	               timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2669 	
2670 	         /* update number of sub-CIP nodes used by heuristic so far */
2671 	         heurdata->nusednodes += nsubnodes;
2672 	
2673 	         /* if the subproblem was constructed from a valid copy and solved, try to forbid the assignment of fixing
2674 	          * values to variables in the cover
2675 	          */
2676 	         if( validsolved )
2677 	         {
2678 	            SCIP_Real maxvarsfac;
2679 	            SCIP_Bool useconf;
2680 	            int minmaxvars;
2681 	
2682 	            SCIP_CALL( SCIPgetIntParam(scip, "conflict/minmaxvars", &minmaxvars) );
2683 	            SCIP_CALL( SCIPgetRealParam(scip, "conflict/maxvarsfac", &maxvarsfac) );
2684 	
2685 	            useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2686 	
2687 	            if( useconf )
2688 	            {
2689 	               /* even if we had reset the global bounds at start of probing, the constraint might be only locally valid due to local constraints/cuts */
2690 	               SCIP_CALL( createConflict(scip, bdlen, bdvars, bdtypes, bdbounds, SCIPgetDepth(scip) > 0, TRUE, TRUE, &success) );
2691 	               conflictcreated = success;
2692 	            }
2693 	
2694 	            SCIPdebugMsg(scip, "subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2695 	               sol == NULL ? "infeasible" : "optimal",
2696 	               success ? "successful" : "failed", useconf ? "" : "skipped due to ", bdlen);
2697 	         }
2698 	
2699 	         /* heuristic succeeded */
2700 	         success = (sol != NULL);
2701 	         if( success )
2702 	         {
2703 	            *result = SCIP_FOUNDSOL;
2704 	            success = TRUE;
2705 	
2706 	            /* call NLP local search heuristic unless it has failed too often */
2707 	            if( heurdata->postnlp && heurdata->npostnlpfails < MAXPOSTNLPFAILS )
2708 	            {
2709 	               if( nfixedconts == 0 && validsolved )
2710 	               {
2711 	                  SCIPdebugMsg(scip, "subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
2712 	               }
2713 	               else if( heurdata->nlpheur == NULL )
2714 	               {
2715 	                  SCIPdebugMsg(scip, "NLP heuristic not found, skipping NLP local search\n");
2716 	               }
2717 	               else
2718 	               {
2719 	                  SCIP_RESULT nlpresult;
2720 	
2721 	                  SCIP_CALL( SCIPapplyHeurSubNlp(scip, heurdata->nlpheur, &nlpresult, sol, NULL) );
2722 	                  SCIPdebugMsg(scip, "NLP local search %s\n", nlpresult == SCIP_FOUNDSOL ? "successful" : "failed");
2723 	
2724 	                  if( nlpresult == SCIP_FOUNDSOL )
2725 	                     heurdata->npostnlpfails = 0;
2726 	                  else
2727 	                     heurdata->npostnlpfails++;
2728 	               }
2729 	            }
2730 	
2731 	            /* free solution */
2732 	            SCIP_CALL( SCIPfreeSol(scip, &sol) );
2733 	         }
2734 	      }
2735 	
2736 	      /* heuristic failed but we have another recovering try, hence we forbid the current cover in the covering problem */
2737 	      if( !success && ncovers <= heurdata->maxrecovers )
2738 	      {
2739 	         SCIP_Bool infeas;
2740 	         int diversification;
2741 	
2742 	         /* compute minimal number of unfixed covering variables (in the cover) which have to change their value */
2743 	         diversification = (int) SCIPfeasCeil(scip, (heurdata->recoverdiv) * (SCIP_Real) nunfixeds);
2744 	         diversification = MAX(diversification, 1);
2745 	
2746 	         /* forbid unsuccessful cover globally in covering problem */
2747 	         SCIP_CALL( forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) );
2748 	
2749 	         if( infeas )
2750 	         {
2751 	            SCIPdebugMsg(scip, "recovering problem infeasible (diversification=%d), terminating\n", diversification);
2752 	            goto TERMINATE;
2753 	         }
2754 	         else if( !success )
2755 	         {
2756 	            SCIPdebugMsg(scip, "failed to forbid current cover in the covering problem, terminating\n");
2757 	            goto TERMINATE;
2758 	         }
2759 	         else
2760 	         {
2761 	            SCIPdebugMsg(scip, "added constraint to the covering problem in order to forbid current cover\n");
2762 	            success = FALSE;
2763 	         }
2764 	      }
2765 	
2766 	      /* try to re-use the same cover at most once */
2767 	      if( heurdata->reusecover && !reusecover && conflictcreated )
2768 	         reusecover = TRUE;
2769 	      else
2770 	         reusecover = FALSE;
2771 	   }
2772 	
2773 	 TERMINATE:
2774 	   if( *result != SCIP_FOUNDSOL && *result != SCIP_DELAYED )
2775 	   {
2776 	      SCIPdebugMsg(scip, "heuristic terminating unsuccessfully\n");
2777 	   }
2778 	
2779 	   /* we must remain in NLP diving mode until here to be able to retrieve NLP solution values easily */
2780 	   /* assert((SCIPisNLPConstructed(scip) == FALSE && heurdata->nlpsolved == FALSE) ||
2781 	    * (SCIPisNLPConstructed(scip) == TRUE && heurdata->nlpsolved == SCIPnlpIsDiving(SCIPgetNLP(scip))));
2782 	    */
2783 	   if( heurdata->nlpsolved )
2784 	   {
2785 	      SCIP_CALL( SCIPendDiveNLP(scip) );
2786 	   }
2787 	
2788 	   /* free arrays for storing the cover */
2789 	   SCIPfreeBufferArrayNull(scip, &fixingvals);
2790 	   SCIPfreeBufferArrayNull(scip, &cover);
2791 	
2792 	   /* free arrays for storing bound disjunction information along probing path */
2793 	   SCIPfreeBufferArrayNull(scip, &oldbounds);
2794 	   SCIPfreeBufferArrayNull(scip, &bdbounds);
2795 	   SCIPfreeBufferArrayNull(scip, &bdtypes);
2796 	   SCIPfreeBufferArrayNull(scip, &bdvars);
2797 	
2798 	   /* free covering problem */
2799 	   for( i = nvars-1; i >= 0; i-- )
2800 	   {
2801 	      if( coveringvars[i] == NULL )
2802 	         continue;
2803 	      SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
2804 	   }
2805 	   SCIPfreeBufferArray(scip, &coveringvars);
2806 	   SCIP_CALL( SCIPfree(&coveringscip) );
2807 	
2808 	   /* free clock */
2809 	   SCIP_CALL( SCIPfreeClock(scip, &clock) );
2810 	
2811 	   return SCIP_OKAY;
2812 	}
2813 	
2814 	
2815 	/*
2816 	 * Callback methods of primal heuristic
2817 	 */
2818 	
2819 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2820 	static
2821 	SCIP_DECL_HEURCOPY(heurCopyUndercover)
2822 	{  /*lint --e{715}*/
2823 	   assert(scip != NULL);
2824 	   assert(heur != NULL);
2825 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2826 	
2827 	   /* call inclusion method of primal heuristic */
2828 	   SCIP_CALL( SCIPincludeHeurUndercover(scip) );
2829 	
2830 	   return SCIP_OKAY;
2831 	}
2832 	
2833 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2834 	static
2835 	SCIP_DECL_HEURFREE(heurFreeUndercover)
2836 	{  /*lint --e{715}*/
2837 	   SCIP_HEURDATA* heurdata;
2838 	
2839 	   assert(scip != NULL);
2840 	   assert(heur != NULL);
2841 	
2842 	   /* get heuristic data */
2843 	   heurdata = SCIPheurGetData(heur);
2844 	   assert(heurdata != NULL);
2845 	
2846 	   /* free heuristic data */
2847 	   SCIPfreeBlockMemory(scip, &heurdata);
2848 	   SCIPheurSetData(heur, NULL);
2849 	
2850 	   return SCIP_OKAY;
2851 	}
2852 	
2853 	/** initialization method of primal heuristic (called after problem was transformed) */
2854 	static
2855 	SCIP_DECL_HEURINIT(heurInitUndercover)
2856 	{  /*lint --e{715}*/
2857 	   SCIP_HEURDATA* heurdata;
2858 	
2859 	   assert(heur != NULL);
2860 	   assert(scip != NULL);
2861 	
2862 	   /* get heuristic's data */
2863 	   heurdata = SCIPheurGetData(heur);
2864 	   assert(heurdata != NULL);
2865 	
2866 	   /* create random number generator */
2867 	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
2868 	         DEFAULT_RANDSEED, TRUE) );
2869 	
2870 	   return SCIP_OKAY;
2871 	}
2872 	
2873 	/** deinitialization method of primal heuristic */
2874 	static
2875 	SCIP_DECL_HEUREXIT(heurExitUndercover)
2876 	{  /*lint --e{715}*/
2877 	   SCIP_HEURDATA* heurdata;
2878 	
2879 	   assert(heur != NULL);
2880 	   assert(scip != NULL);
2881 	
2882 	   /* get heuristic's data */
2883 	   heurdata = SCIPheurGetData(heur);
2884 	   assert(heurdata != NULL);
2885 	
2886 	   /* free random number generator */
2887 	   SCIPfreeRandom(scip, &heurdata->randnumgen);
2888 	
2889 	   return SCIP_OKAY;
2890 	}
2891 	
2892 	/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2893 	static
2894 	SCIP_DECL_HEURINITSOL(heurInitsolUndercover)
2895 	{  /*lint --e{715}*/
2896 	   SCIP_HEURDATA* heurdata;
2897 	   int h;
2898 	
2899 	   assert(heur != NULL);
2900 	   assert(scip != NULL);
2901 	
2902 	   /* get heuristic's data */
2903 	   heurdata = SCIPheurGetData(heur);
2904 	   assert(heurdata != NULL);
2905 	
2906 	   /* initialize counters to zero */
2907 	   heurdata->nusednodes = 0;
2908 	   heurdata->npostnlpfails = 0;
2909 	   heurdata->nnlpfails = 0;
2910 	
2911 	   /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */
2912 	   if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 )
2913 	      SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP);
2914 	
2915 	   /* find nonlinear constraint handlers */
2916 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4) );/*lint !e506*/
2917 	   h = 0;
2918 	
2919 	   if( heurdata->coverand )
2920 	   {
2921 	      heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "and");
2922 	      if( heurdata->nlconshdlrs[h] != NULL )
2923 	         h++;
2924 	   }
2925 	   if( heurdata->coverbd )
2926 	   {
2927 	      heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "bounddisjunction");
2928 	      if( heurdata->nlconshdlrs[h] != NULL )
2929 	         h++;
2930 	   }
2931 	   if( heurdata->coverind )
2932 	   {
2933 	      heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "indicator");
2934 	      if( heurdata->nlconshdlrs[h] != NULL )
2935 	         h++;
2936 	   }
2937 	   if( heurdata->covernl )
2938 	   {
2939 	      heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "nonlinear");
2940 	      if( heurdata->nlconshdlrs[h] != NULL )
2941 	         h++;
2942 	   }
2943 	   heurdata->nnlconshdlrs = h;
2944 	   assert( heurdata->nnlconshdlrs <= 4 );
2945 	
2946 	   /* find NLP local search heuristic */
2947 	   heurdata->nlpheur = SCIPfindHeur(scip, "subnlp");
2948 	
2949 	   return SCIP_OKAY;
2950 	}
2951 	
2952 	/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2953 	static
2954 	SCIP_DECL_HEUREXITSOL(heurExitsolUndercover)
2955 	{
2956 	   SCIP_HEURDATA* heurdata;
2957 	
2958 	   assert(heur != NULL);
2959 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2960 	
2961 	   /* get heuristic's data */
2962 	   heurdata = SCIPheurGetData(heur);
2963 	   assert(heurdata != NULL);
2964 	
2965 	   /* free array of nonlinear constraint handlers */
2966 	   SCIPfreeBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4);
2967 	
2968 	   /* reset timing, if it was changed temporary (at the root node) */
2969 	   SCIPheurSetTimingmask(heur, HEUR_TIMING);
2970 	
2971 	   return SCIP_OKAY;
2972 	}
2973 	
2974 	/** execution method of primal heuristic */
2975 	static
2976 	SCIP_DECL_HEUREXEC(heurExecUndercover)
2977 	{  /*lint --e{715}*/
2978 	   SCIP_HEURDATA* heurdata;                  /* heuristic data */
2979 	   SCIP_Real timelimit;                      /* time limit for the subproblem */
2980 	   SCIP_Real memorylimit;                    /* memory limit for the subproblem */
2981 	   SCIP_Longint nstallnodes;                 /* number of stalling nodes for the subproblem */
2982 	   SCIP_Bool run;
2983 	   SCIP_Bool avoidmemout;
2984 	
2985 	   int h;
2986 	
2987 	   assert(heur != NULL);
2988 	   assert(scip != NULL);
2989 	   assert(result != NULL);
2990 	
2991 	   *result = SCIP_DIDNOTRUN;
2992 	
2993 	   /* do not call heuristic of node was already detected to be infeasible */
2994 	   if( nodeinfeasible )
2995 	      return SCIP_OKAY;
2996 	
2997 	   /* get heuristic's data */
2998 	   heurdata = SCIPheurGetData(heur);
2999 	   assert(heurdata != NULL);
3000 	
3001 	   /* only call heuristic once at the root */
3002 	   if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 )
3003 	      return SCIP_OKAY;
3004 	
3005 	   /* if we want to use NLP fixing values exclusively and no NLP solver is available, we cannot run */
3006 	   if( strcmp(heurdata->fixingalts, "n") == 0 && SCIPgetNNlpis(scip) == 0 )
3007 	   {
3008 	      SCIPdebugMsg(scip, "skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
3009 	      return SCIP_OKAY;
3010 	   }
3011 	
3012 	   /* calculate stallnode limit */
3013 	   nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
3014 	
3015 	   /* reward heuristic if it succeeded often */
3016 	   nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0));
3017 	   nstallnodes -= SUBMIPSETUPCOSTS * SCIPheurGetNCalls(heur);  /* account for the setup costs of the sub-CIP */
3018 	   nstallnodes += heurdata->nodesofs;
3019 	
3020 	   /* determine the node limit for the current process */
3021 	   nstallnodes -= heurdata->nusednodes;
3022 	   nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
3023 	   nstallnodes = MAX(nstallnodes, 1);
3024 	
3025 	   /* only call heuristics if we have enough nodes left to call sub-CIP solving */
3026 	   if( nstallnodes < heurdata->minnodes )
3027 	   {
3028 	      SCIPdebugMsg(scip, "skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
3029 	      return SCIP_OKAY;
3030 	   }
3031 	
3032 	   /* only call heuristics if we have enough time left */
3033 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3034 	   if( !SCIPisInfinity(scip, timelimit) )
3035 	      timelimit -= SCIPgetSolvingTime(scip);
3036 	   if( timelimit <= 2*MINTIMELEFT )
3037 	   {
3038 	      SCIPdebugMsg(scip, "skipping undercover heuristic: time left=%g\n", timelimit);
3039 	      return SCIP_OKAY;
3040 	   }
3041 	
3042 	   /* only call heuristics if we have enough memory left */
3043 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3044 	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
3045 	   if( !SCIPisInfinity(scip, memorylimit) )
3046 	   {
3047 	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3048 	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3049 	   }
3050 	
3051 	   if( avoidmemout && memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
3052 	   {
3053 	      SCIPdebugMsg(scip, "skipping undercover heuristic: too little memory\n");
3054 	      return SCIP_OKAY;
3055 	   }
3056 	
3057 	   /* only call heuristic if nonlinear constraints are present */
3058 	   run = FALSE;
3059 	   for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3060 	   {
3061 	      run = (SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[h]) > 0);
3062 	   }
3063 	
3064 	   /* go through all nlrows and check for general nonlinearities */
3065 	   if( !run && SCIPisNLPConstructed(scip) )
3066 	   {
3067 	      SCIP_NLROW** nlrows;
3068 	      int nnlrows;
3069 	      int i;
3070 	
3071 	      /* get nlrows */
3072 	      nnlrows = SCIPgetNNLPNlRows(scip);
3073 	      nlrows = SCIPgetNLPNlRows(scip);
3074 	
3075 	      /* check for a nonlinear nlrow; start from the end since we expect the linear nlrows at the end */
3076 	      for( i = nnlrows-1; i >= 0 && !run; i-- )
3077 	      {
3078 	         assert(nlrows[i] != NULL);
3079 	         run = SCIPnlrowGetExpr(nlrows[i]) != NULL;
3080 	      }
3081 	   }
3082 	
3083 	   if( !run )
3084 	   {
3085 	      SCIPdebugMsg(scip, "skipping undercover heuristic: no nonlinear constraints found\n");
3086 	      return SCIP_OKAY;
3087 	   }
3088 	
3089 	   /* only call heuristics if solving has not stopped yet */
3090 	   if( SCIPisStopped(scip) )
3091 	      return SCIP_OKAY;
3092 	
3093 	   /* reset timing, if it was changed temporary (at the root node) */
3094 	   if( heurtiming != HEUR_TIMING )
3095 	      SCIPheurSetTimingmask(heur, HEUR_TIMING);
3096 	
3097 	   /* call heuristic */
3098 	   *result = SCIP_DIDNOTFIND;
3099 	   SCIPdebugMsg(scip, "calling undercover heuristic for <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3100 	
3101 	   SCIP_CALL( SCIPapplyUndercover(scip, heur, result, timelimit, memorylimit, nstallnodes) );
3102 	
3103 	   return SCIP_OKAY;
3104 	}
3105 	
3106 	
3107 	/*
3108 	 * primal heuristic specific interface methods
3109 	 */
3110 	
3111 	/** creates the undercover primal heuristic and includes it in SCIP */
3112 	SCIP_RETCODE SCIPincludeHeurUndercover(
3113 	   SCIP*                 scip                /**< SCIP data structure */
3114 	   )
3115 	{
3116 	   SCIP_HEURDATA* heurdata;
3117 	   SCIP_HEUR* heur;
3118 	
3119 	   /* create undercover primal heuristic data */
3120 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
3121 	
3122 	   /* always use local bounds */
3123 	   heurdata->globalbounds = FALSE;
3124 	
3125 	   /* include primal heuristic */
3126 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
3127 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
3128 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecUndercover, heurdata) );
3129 	
3130 	   assert(heur != NULL);
3131 	
3132 	   /* set non-NULL pointers to callback methods */
3133 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyUndercover) );
3134 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeUndercover) );
3135 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitUndercover) );
3136 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitUndercover) );
3137 	   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolUndercover) );
3138 	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolUndercover) );
3139 	
3140 	   /* add string parameters */
3141 	   heurdata->fixingalts = NULL;
3142 	   SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/fixingalts",
3143 	         "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3144 	         &heurdata->fixingalts, FALSE, DEFAULT_FIXINGALTS, NULL, NULL) );
3145 	
3146 	   /* add longint parameters */
3147 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
3148 	         "maximum number of nodes to regard in the subproblem",
3149 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3150 	
3151 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
3152 	         "minimum number of nodes required to start the subproblem",
3153 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3154 	
3155 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
3156 	         "number of nodes added to the contingent of the total nodes",
3157 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3158 	
3159 	   /* add real parameters */
3160 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictweight",
3161 	         "weight for conflict score in fixing order",
3162 	         &heurdata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3163 	
3164 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/cutoffweight",
3165 	         "weight for cutoff score in fixing order",
3166 	         &heurdata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3167 	
3168 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inferenceweight",
3169 	         "weight for inference score in fixing order",
3170 	         &heurdata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3171 	
3172 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizevars",
3173 	         "maximum coversize (as fraction of total number of variables)",
3174 	         &heurdata->maxcoversizevars, TRUE, DEFAULT_MAXCOVERSIZEVARS, 0.0, 1.0, NULL, NULL) );
3175 	
3176 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizeconss",
3177 	         "maximum coversize (as ratio to the percentage of non-affected constraints)",
3178 	         &heurdata->maxcoversizeconss, TRUE, DEFAULT_MAXCOVERSIZECONSS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3179 	
3180 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mincoveredrel",
3181 	         "minimum percentage of nonlinear constraints in the original problem",
3182 	         &heurdata->mincoveredrel, TRUE, DEFAULT_MINCOVEREDREL, 0.0, 1.0, NULL, NULL) );
3183 	
3184 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
3185 	         "factor by which the heuristic should at least improve the incumbent",
3186 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, -1.0, 1.0, NULL, NULL) );
3187 	
3188 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
3189 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3190 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
3191 	
3192 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/recoverdiv",
3193 	         "fraction of covering variables in the last cover which need to change their value when recovering",
3194 	         &heurdata->recoverdiv, TRUE, DEFAULT_RECOVERDIV, 0.0, 1.0, NULL, NULL) );
3195 	
3196 	   /* add int parameters */
3197 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/mincoveredabs",
3198 	         "minimum number of nonlinear constraints in the original problem",
3199 	         &heurdata->mincoveredabs, TRUE, DEFAULT_MINCOVEREDABS, 0, INT_MAX, NULL, NULL) );
3200 	
3201 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
3202 	         "maximum number of backtracks in fix-and-propagate",
3203 	         &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, 0, INT_MAX, NULL, NULL) );
3204 	
3205 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxrecovers",
3206 	         "maximum number of recoverings",
3207 	         &heurdata->maxrecovers, TRUE, DEFAULT_MAXRECOVERS, 0, INT_MAX, NULL, NULL) );
3208 	
3209 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxreorders",
3210 	         "maximum number of reorderings of the fixing order",
3211 	         &heurdata->maxreorders, TRUE, DEFAULT_MAXREORDERS, 0, INT_MAX, NULL, NULL) );
3212 	
3213 	   /* add char parameters */
3214 	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/coveringobj",
3215 	         "objective function of the covering problem (influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties)",
3216 	         &heurdata->coveringobj, TRUE, DEFAULT_COVERINGOBJ, COVERINGOBJS, NULL, NULL) );
3217 	
3218 	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/fixingorder",
3219 	         "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3220 	         &heurdata->fixingorder, TRUE, DEFAULT_FIXINGORDER, FIXINGORDERS, NULL, NULL) );
3221 	
3222 	   /* add bool parameters */
3223 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforecuts",
3224 	         "should the heuristic be called at root node before cut separation?",
3225 	         &heurdata->beforecuts, TRUE, DEFAULT_BEFORECUTS, NULL, NULL) );
3226 	
3227 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixintfirst",
3228 	         "should integer variables in the cover be fixed first?",
3229 	         &heurdata->fixintfirst, TRUE, DEFAULT_FIXINTFIRST, NULL, NULL) );
3230 	
3231 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/locksrounding",
3232 	         "shall LP values for integer vars be rounded according to locks?",
3233 	         &heurdata->locksrounding, TRUE, DEFAULT_LOCKSROUNDING, NULL, NULL) );
3234 	
3235 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyconvexify",
3236 	         "should we only fix variables in order to obtain a convex problem?",
3237 	         &heurdata->onlyconvexify, FALSE, DEFAULT_ONLYCONVEXIFY, NULL, NULL) );
3238 	
3239 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/postnlp",
3240 	         "should the NLP heuristic be called to polish a feasible solution?",
3241 	         &heurdata->postnlp, FALSE, DEFAULT_POSTNLP, NULL, NULL) );
3242 	
3243 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverand",
3244 	         "should and constraints be covered (or just copied)?",
3245 	         &heurdata->coverand, TRUE, DEFAULT_COVERAND, NULL, NULL) );
3246 	
3247 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverbd",
3248 	         "should bounddisjunction constraints be covered (or just copied)?",
3249 	         &heurdata->coverbd, TRUE, DEFAULT_COVERBD, NULL, NULL) );
3250 	
3251 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverind",
3252 	         "should indicator constraints be covered (or just copied)?",
3253 	         &heurdata->coverind, TRUE, DEFAULT_COVERIND, NULL, NULL) );
3254 	
3255 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/covernl",
3256 	         "should nonlinear constraints be covered (or just copied)?",
3257 	         &heurdata->covernl, TRUE, DEFAULT_COVERNL, NULL, NULL) );
3258 	
3259 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
3260 	         "should all active cuts from cutpool be copied to constraints in subproblem?",
3261 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
3262 	
3263 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reusecover",
3264 	         "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3265 	         &heurdata->reusecover, TRUE, DEFAULT_REUSECOVER, NULL, NULL) );
3266 	
3267 	   return SCIP_OKAY;
3268 	}
3269 	
3270 	/** create and solve covering problem */
3271 	static
3272 	SCIP_RETCODE computeCoverUndercover(
3273 	   SCIP*                 scip,               /**< SCIP data structure */
3274 	   SCIP*                 coveringscip,       /**< SCIP instance for covering problem */
3275 	   int*                  coversize,          /**< buffer for the size of the computed cover */
3276 	   SCIP_VAR**            cover,              /**< pointer to store the variables (of the original SCIP) in the computed cover
3277 	                                              *   (should be ready to hold SCIPgetNVars(scip) entries) */
3278 	   SCIP_Real             timelimit,          /**< time limit */
3279 	   SCIP_Real             memorylimit,        /**< memory limit */
3280 	   SCIP_Real             objlimit,           /**< objective limit: upper bound on coversize */
3281 	   SCIP_Bool             globalbounds,       /**< should global bounds on variables be used instead of local bounds at focus node? */
3282 	   SCIP_Bool             onlyconvexify,      /**< should we only fix/dom.red. variables creating nonconvexity? */
3283 	   SCIP_Bool             coverand,           /**< should and constraints be covered (or just copied)? */
3284 	   SCIP_Bool             coverbd,            /**< should bounddisjunction constraints be covered (or just copied)? */
3285 	   SCIP_Bool             coverind,           /**< should indicator constraints be covered (or just copied)? */
3286 	   SCIP_Bool             covernl,            /**< should nonlinear constraints be covered (or just copied)? */
3287 	   char                  coveringobj,        /**< objective function of the covering problem ('b'ranching status,
3288 	                                              *   influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3289 	                                              *   'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3290 	   SCIP_Bool*            success             /**< feasible cover found? */
3291 	   )
3292 	{
3293 	   SCIP_VAR** coveringvars;                  /* covering variables */
3294 	   SCIP_VAR** vars;                          /* original variables */
3295 	   int* coverinds;                           /* indices of variables in the cover */
3296 	   int nvars;                                /* number of original variables */
3297 	   int i;
3298 	
3299 	   assert(scip != NULL);
3300 	   assert(coveringscip != NULL);
3301 	
3302 	   SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) );
3303 	
3304 	   /* allocate memory for variables of the covering problem */
3305 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL ) );
3306 	   SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) );
3307 	   SCIP_CALL( SCIPallocBufferArray(scip, &coverinds, nvars) );
3308 	
3309 	   SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, globalbounds, onlyconvexify,
3310 	         coverand, coverbd, coverind, covernl, coveringobj, success) );
3311 	
3312 	   if( *success )
3313 	   {
3314 	      /* solve covering problem */
3315 	      SCIPdebugMsg(scip, "solving covering problem\n\n");
3316 	
3317 	      SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, coversize, coverinds,
3318 	            timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, objlimit, success) );
3319 	
3320 	      if( *success )
3321 	      {
3322 	         assert(*coversize >= 0);
3323 	         assert(*coversize <= nvars);
3324 	
3325 	         /* return original variables in the cover */
3326 	         for( i = *coversize-1; i >= 0; i-- )
3327 	         {
3328 	            assert(coverinds[i] >= 0);
3329 	            assert(coverinds[i] < nvars);
3330 	            cover[i] = vars[coverinds[i]];
3331 	         }
3332 	      }
3333 	   }
3334 	   else
3335 	   {
3336 	      SCIPdebugMsg(scip, "failure: covering problem could not be created\n");
3337 	   }
3338 	
3339 	   /* free covering problem */
3340 	   for( i = nvars-1; i >= 0; i-- )
3341 	   {
3342 	      if( coveringvars[i] == NULL )
3343 	         continue;
3344 	      SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) );
3345 	   }
3346 	   SCIPfreeBufferArray(scip, &coverinds);
3347 	   SCIPfreeBufferArray(scip, &coveringvars);
3348 	
3349 	   return SCIP_OKAY;
3350 	}
3351 	
3352 	/** computes a minimal set of covering variables */
3353 	SCIP_RETCODE SCIPcomputeCoverUndercover(
3354 	   SCIP*                 scip,               /**< SCIP data structure */
3355 	   int*                  coversize,          /**< buffer for the size of the computed cover */
3356 	   SCIP_VAR**            cover,              /**< pointer to store the variables (of the original SCIP) in the computed cover
3357 	                                              *   (should be ready to hold SCIPgetNVars(scip) entries) */
3358 	   SCIP_Real             timelimit,          /**< time limit */
3359 	   SCIP_Real             memorylimit,        /**< memory limit */
3360 	   SCIP_Real             objlimit,           /**< objective limit: upper bound on coversize */
3361 	   SCIP_Bool             globalbounds,       /**< should global bounds on variables be used instead of local bounds at focus node? */
3362 	   SCIP_Bool             onlyconvexify,      /**< should we only fix/dom.red. variables creating nonconvexity? */
3363 	   SCIP_Bool             coverand,           /**< should and constraints be covered (or just copied)? */
3364 	   SCIP_Bool             coverbd,            /**< should bounddisjunction constraints be covered (or just copied)? */
3365 	   SCIP_Bool             coverind,           /**< should indicator constraints be covered (or just copied)? */
3366 	   SCIP_Bool             covernl,            /**< should nonlinear constraints be covered (or just copied)? */
3367 	   char                  coveringobj,        /**< objective function of the covering problem ('b'ranching status,
3368 	                                              *   influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3369 	                                              *   'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3370 	   SCIP_Bool*            success             /**< feasible cover found? */
3371 	   )
3372 	{
3373 	   SCIP* coveringscip;                       /* SCIP instance for covering problem */
3374 	   SCIP_RETCODE retcode;
3375 	
3376 	   assert(scip != NULL);
3377 	   assert(coversize != NULL);
3378 	   assert(success != NULL);
3379 	
3380 	   *success = FALSE;
3381 	
3382 	   /* create covering problem */
3383 	   SCIP_CALL( SCIPcreate(&coveringscip) );
3384 	
3385 	   retcode = computeCoverUndercover(scip, coveringscip, coversize, cover,
3386 	      timelimit, memorylimit, objlimit,
3387 	      globalbounds, onlyconvexify, coverand, coverbd, coverind, covernl,
3388 	      coveringobj, success);
3389 	
3390 	   /* free the covering problem scip instance before reacting on potential errors */
3391 	   SCIP_CALL( SCIPfree(&coveringscip) );
3392 	
3393 	   SCIP_CALL( retcode );
3394 	
3395 	   return SCIP_OKAY;
3396 	}
3397