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_lpface.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  lpface primal heuristic that searches the optimal LP face inside a sub-MIP
28   	 * @author Gregor Hendel
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/cons_linear.h"
35   	#include "scip/scipdefplugins.h"
36   	#include "scip/heur_lpface.h"
37   	#include "scip/pub_event.h"
38   	#include "scip/pub_heur.h"
39   	#include "scip/pub_lp.h"
40   	#include "scip/pub_message.h"
41   	#include "scip/pub_misc.h"
42   	#include "scip/pub_sol.h"
43   	#include "scip/pub_tree.h"
44   	#include "scip/pub_var.h"
45   	#include "scip/scip_branch.h"
46   	#include "scip/scip_cons.h"
47   	#include "scip/scip_copy.h"
48   	#include "scip/scip_event.h"
49   	#include "scip/scip_general.h"
50   	#include "scip/scip_heur.h"
51   	#include "scip/scip_lp.h"
52   	#include "scip/scip_mem.h"
53   	#include "scip/scip_message.h"
54   	#include "scip/scip_nodesel.h"
55   	#include "scip/scip_numerics.h"
56   	#include "scip/scip_param.h"
57   	#include "scip/scip_prob.h"
58   	#include "scip/scip_sol.h"
59   	#include "scip/scip_solve.h"
60   	#include "scip/scip_solvingstats.h"
61   	#include "scip/scip_timing.h"
62   	#include "scip/scip_tree.h"
63   	#include "scip/scip_var.h"
64   	#include <string.h>
65   	
66   	#define HEUR_NAME             "lpface"
67   	#define HEUR_DESC             "LNS heuristic that searches the optimal LP face inside a sub-MIP"
68   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
69   	#define HEUR_PRIORITY         -1104010
70   	#define HEUR_FREQ             15
71   	#define HEUR_FREQOFS          0
72   	#define HEUR_MAXDEPTH         -1
73   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPNODE
74   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
75   	
76   	#define DEFAULT_MAXNODES      5000LL         /**< maximum number of nodes to regard in the subproblem                   */
77   	#define DEFAULT_MINNODES      50LL           /**< minimum number of nodes to regard in the subproblem                   */
78   	#define DEFAULT_MINFIXINGRATE 0.1            /**< required percentage of fixed integer variables in sub-MIP to run */
79   	#define DEFAULT_NODESOFS      200LL          /**< number of nodes added to the contingent of the total nodes            */
80   	#define DEFAULT_NODESQUOT     0.1            /**< subproblem nodes in relation to nodes of the original problem         */
81   	#define DEFAULT_LPLIMFAC      2.0            /**< factor by which the limit on the number of LP depends on the node limit */
82   	#define DEFAULT_USELPROWS     TRUE           /**< should subproblem be created out of the rows in the LP rows,
83   	                                              *   otherwise, the copy constructors of the constraints handlers are used */
84   	#define DEFAULT_COPYCUTS      TRUE           /**< if uselprows == FALSE, should all active cuts from cutpool be copied
85   	                                              *   to constraints in subproblem?                                     */
86   	#define DEFAULT_DUALBASISEQUATIONS FALSE     /**< should the dually nonbasic rows be turned into equations?        */
87   	#define DEFAULT_KEEPSUBSCIP   FALSE          /**< should the heuristic continue solving the same sub-SCIP? */
88   	#define DEFAULT_MINPATHLEN        5          /**< the minimum active search tree path length along which the lower bound
89   	                                              *   hasn't changed before heuristic becomes active */
90   	/* event handler properties */
91   	#define EVENTHDLR_NAME         "Lpface"
92   	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
93   	
94   	/*
95   	 * Data structures
96   	 */
97   	
98   	/** data structure to keep sub-SCIP across runs */
99   	struct SubscipData
100  	{
101  	   SCIP*                 subscip;            /**< pointer to store sub-SCIP data structure */
102  	   SCIP_VAR**            subvars;            /**< array of variables of the sub-problem */
103  	   int                   nsubvars;           /**< number of sub-problem variables */
104  	   SCIP_Real             objbound;           /**< lower bound on objective for when sub SCIP was created */
105  	};
106  	typedef struct SubscipData SUBSCIPDATA;
107  	
108  	/** primal heuristic data */
109  	struct SCIP_HeurData
110  	{
111  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem               */
112  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem               */
113  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes        */
114  	   SCIP_Longint          usednodes;          /**< nodes already used by lpface in earlier calls                  */
115  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem     */
116  	
117  	   unsigned int          nfailures;          /**< number of failures since last successful call                     */
118  	   SCIP_Longint          nextnodenumber;     /**< number of nodes at which lpface should be called the next time */
119  	   SCIP_Real             lastlpobjinfeas;    /**< last LP objective where the sub-MIP was run to proven infeasibility */
120  	   SCIP_Real             minfixingrate;      /**< required percentage of fixed integer variables in sub-MIP to run     */
121  	   SCIP_Real             nodelimit;          /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
122  	   SCIP_Real             lplimfac;           /**< factor by which the limit on the number of LP depends on the node limit */
123  	   SCIP_Bool             uselprows;          /**< should subproblem be created out of the rows in the LP rows?      */
124  	   SCIP_Bool             copycuts;           /**< if uselprows == FALSE, should all active cuts from cutpool be copied
125  	                                              *   to constraints in subproblem?                                     */
126  	   SCIP_Bool             dualbasisequations; /**< should the dually nonbasic rows be turned into equations?        */
127  	   SCIP_Bool             keepsubscip;        /**< should the heuristic continue solving the same sub-SCIP? */
128  	   char                  subscipobjective;   /**< objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference,
129  	                                              *   (i)nference, LP (f)ractionality, (o)riginal */
130  	
131  	   SCIP_STATUS           submipstatus;       /**< return status of the sub-MIP */
132  	   SCIP_Longint          submipnlpiters;     /**< number of LP iterations of the sub-MIP */
133  	   SCIP_Real             submippresoltime;   /**< time required to presolve the sub-MIP */
134  	   int                   nvarsfixed;         /**< the number of fixed variables by the heuristic */
135  	   int                   minpathlen;         /**< the minimum active search tree path length along which the lower bound
136  	                                              *   hasn't changed before heuristic becomes active */
137  	   SUBSCIPDATA*          subscipdata;        /**< sub-SCIP data structure */
138  	};
139  	
140  	/*
141  	 * Local methods
142  	 */
143  	
144  	/** determine variable fixings for sub-SCIP based on reduced costs */
145  	static
146  	SCIP_RETCODE determineVariableFixings(
147  	   SCIP*                 scip,               /**< SCIP data structure */
148  	   SCIP_HEURDATA*        heurdata,           /**< primal heuristic data */
149  	   SCIP_VAR**            fixvars,            /**< buffer to store variables that should be fixed */
150  	   SCIP_Real*            fixvals,            /**< buffer to store corresponding fixing values */
151  	   int*                  nfixvars,           /**< pointer to store number of variables that should be fixed */
152  	   SCIP_Bool*            success             /**< pointer to store whether enough integer variables were fixed */
153  	   )
154  	{
155  	   SCIP_VAR** vars;                          /* original scip variables                */
156  	   SCIP_Real fixingrate;                     /* percentage of variables that are fixed */
157  	   int nvars;
158  	   int nbinvars;
159  	   int nintvars;
160  	   int i;
161  	   int fixingcounter;
162  	
163  	   /* get required data of the main scip problem */
164  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
165  	
166  	   fixingcounter = 0;
167  	
168  	   assert(nvars >= nbinvars + nintvars);
169  	
170  	   *nfixvars = 0;
171  	   /* loop over problem variables and fix all with nonzero reduced costs to their solution value */
172  	   for( i = 0; i < nvars; i++ )
173  	   {
174  	      SCIP_Real solval;
175  	      SCIP_COL* col;
176  	      SCIP_Real redcost;
177  	      SCIP_Real lbglobal;
178  	      SCIP_Real ubglobal;
179  	      SCIP_VAR* var;
180  	
181  	      var = vars[i];
182  	
183  	      /* skip non-column variables */
184  	      if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
185  	         continue;
186  	
187  	      /* skip relaxation only variables */
188  	      if( SCIPvarIsRelaxationOnly(var) )
189  	         continue;
190  	
191  	      solval = SCIPgetSolVal(scip, NULL, var);
192  	      col = SCIPvarGetCol(vars[i]);
193  	      assert(col != NULL);
194  	      redcost = SCIPgetColRedcost(scip, col);
195  	      lbglobal = SCIPvarGetLbGlobal(var);
196  	      ubglobal = SCIPvarGetUbGlobal(var);
197  	
198  	      /* fix the variable to its solution value if variable is nonbasic (i.e., at one of its bounds)
199  	       *  with nonzero reduced costs
200  	       */
201  	      if( ! SCIPisDualfeasZero(scip, redcost) )
202  	      {
203  	         /* fix variable based on reduced cost information, respecting global bounds */
204  	         if( (redcost > 0 && SCIPisFeasEQ(scip, solval, lbglobal)) ||
205  	                  (redcost < 0 && SCIPisFeasEQ(scip, solval, ubglobal)) )
206  	         {
207  	            assert(! SCIPisInfinity(scip, REALABS(solval)));
208  	
209  	            fixvars[*nfixvars] = var;
210  	            fixvals[*nfixvars] = solval;
211  	
212  	            if( SCIPvarIsIntegral(var) )
213  	               ++fixingcounter;
214  	
215  	            ++(*nfixvars);
216  	         }
217  	      }
218  	   }
219  	
220  	   fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
221  	   heurdata->nvarsfixed = fixingcounter;
222  	
223  	   /* if all variables were fixed or amount of fixed variables is insufficient, skip residual part of
224  	    * subproblem creation and abort immediately
225  	    */
226  	   *success = (fixingcounter < nvars && fixingrate >= heurdata->minfixingrate);
227  	
228  	   SCIPdebugMsg(scip, " LP face heuristic fixed %senough variables (%d out of %d)\n",
229  	      *success ? "": "not ", fixingcounter, nvars);
230  	
231  	   return SCIP_OKAY;
232  	}
233  	
234  	/** creates the rows of the subproblem */
235  	static
236  	SCIP_RETCODE createRows(
237  	   SCIP*                 scip,               /**< original SCIP data structure */
238  	   SCIP*                 subscip,            /**< SCIP data structure for the subproblem */
239  	   SCIP_VAR**            subvars,            /**< the variables of the subproblem */
240  	   SCIP_Bool             dualbasisequations  /**< should the dually nonbasic rows be turned into equations? */
241  	   )
242  	{
243  	   SCIP_ROW** rows;                          /* original scip rows                       */
244  	
245  	   int nrows;
246  	   int i;
247  	
248  	   /* get the rows and their number */
249  	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
250  	
251  	   /* copy all global rows to linear constraints, unless they contain relaxation-only variables */
252  	   for( i = 0; i < nrows; i++ )
253  	   {
254  	      SCIP_VAR** consvars;                   /* new constraint's variables               */
255  	      SCIP_COL** cols;                       /* original row's columns                   */
256  	      SCIP_CONS* cons;                       /* new constraint                           */
257  	
258  	      SCIP_Real* vals;                       /* variables' coefficient values of the row */
259  	      SCIP_Real constant;                    /* constant added to the row                */
260  	      SCIP_Real lhs;                         /* left hand side of the row                */
261  	      SCIP_Real rhs;                         /* left right side of the row               */
262  	      SCIP_Real dualsol;
263  	      SCIP_Real rowsolactivity;
264  	      int j;
265  	      int nnonz;
266  	
267  	      /* ignore rows that are only locally valid */
268  	      if( SCIProwIsLocal(rows[i]) )
269  	         continue;
270  	
271  	      /* get the row's data */
272  	      constant = SCIProwGetConstant(rows[i]);
273  	      vals = SCIProwGetVals(rows[i]);
274  	      nnonz = SCIProwGetNNonz(rows[i]);
275  	      cols = SCIProwGetCols(rows[i]);
276  	
277  	      /* only subtract constant if left hand side is not infinite */
278  	      lhs = SCIProwGetLhs(rows[i]);
279  	      if( ! SCIPisInfinity(scip, -lhs) )
280  	         lhs -= constant;
281  	
282  	      /* only subtract constant if right hand side is not infinite */
283  	      rhs = SCIProwGetRhs(rows[i]);
284  	      if( ! SCIPisInfinity(scip, rhs) )
285  	         rhs -= constant;
286  	
287  	      assert(lhs <= rhs);
288  	
289  	      /* allocate memory array to be filled with the corresponding subproblem variables */
290  	      SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
291  	      for( j = 0; j < nnonz; j++ )
292  	      {
293  	         consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
294  	         if( consvars[j] == NULL )
295  	            break;
296  	      }
297  	      /* skip row if not all variables are in sub-SCIP, i.e., relaxation-only variables */
298  	      if( j < nnonz )
299  	      {
300  	         SCIPfreeBufferArray(scip, &consvars);
301  	         continue;
302  	      }
303  	
304  	      dualsol = SCIProwGetDualsol(rows[i]);
305  	      rowsolactivity = SCIPgetRowActivity(scip, rows[i]);
306  	
307  	      /* transform into equation if the row is sharp and has a nonzero dual solution */
308  	      if( dualbasisequations && ! SCIPisDualfeasZero(scip, dualsol) )
309  	      {
310  	         if( dualsol > 0.0 && SCIPisFeasEQ(scip, rowsolactivity, lhs) )
311  	            rhs = lhs;
312  	         else if( dualsol < 0.0 && SCIPisFeasEQ(scip, rowsolactivity, rhs) )
313  	            lhs = rhs;
314  	      }
315  	
316  	      /* create a new linear constraint and add it to the subproblem */
317  	      SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
318  	            TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
319  	      SCIP_CALL( SCIPaddCons(subscip, cons) );
320  	      SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
321  	
322  	      /* free temporary memory */
323  	      SCIPfreeBufferArray(scip, &consvars);
324  	   }
325  	
326  	   return SCIP_OKAY;
327  	}
328  	
329  	/** create the LP face subproblem constraints */
330  	static
331  	SCIP_RETCODE setupSubproblem(
332  	   SCIP*                 scip,               /**< original SCIP data structure */
333  	   SCIP*                 subscip,            /**< SCIP data structure for the subproblem */
334  	   SCIP_VAR**            subvars,            /**< the variables of the subproblem */
335  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
336  	   )
337  	{
338  	   SCIP_VAR** vars = SCIPgetVars(scip);
339  	   int nvars = SCIPgetNVars(scip);
340  	   SCIP_Real lowerbound;
341  	   SCIP_CONS* origobjcons;
342  	   int i;
343  	#ifndef NDEBUG
344  	   int nobjvars = 0;
345  	#endif
346  	
347  	   /* we copy the rows of the LP, if enough variables could be fixed and we work on the MIP relaxation of the problem */
348  	   if( heurdata->uselprows )
349  	   {
350  	      SCIP_CALL( createRows(scip, subscip, subvars, heurdata->dualbasisequations) );
351  	   }
352  	
353  	   /* add an equation that the objective function must be equal to the lower bound */
354  	   lowerbound = SCIPgetLowerbound(scip);
355  	
356  	   SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, lowerbound, lowerbound,
357  	         TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
358  	
359  	   for( i = 0; i < nvars; ++i)
360  	   {
361  	      if( ! SCIPisZero(subscip, SCIPvarGetObj(vars[i])) )
362  	      {
363  	         assert(subvars[i] != NULL);  /* a relaxation-only variable cannot have an objective coefficient */
364  	         SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
365  	#ifndef NDEBUG
366  	         nobjvars++;
367  	#endif
368  	      }
369  	   }
370  	   assert(nobjvars == SCIPgetNObjVars(scip));
371  	
372  	   SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
373  	   SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
374  	
375  	   return SCIP_OKAY;
376  	}
377  	
378  	/** updates heurdata after an unsuccessful run of lpface */
379  	static
380  	void updateFailureStatistic(
381  	   SCIP*                 scip,               /**< original SCIP data structure */
382  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
383  	   )
384  	{
385  	   /* increase number of failures, calculate next node at which lpface should be called and update actual solutions */
386  	   heurdata->nfailures++;
387  	   heurdata->nextnodenumber = (heurdata->nfailures <= 25
388  	      ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
389  	      : SCIP_LONGINT_MAX);
390  	}
391  	
392  	/** calculate a node limit based on node limiting parameters of the heuristic */
393  	static
394  	SCIP_Longint calcNodeLimit(
395  	   SCIP*                 scip,               /**< (original) SCIP data structure */
396  	   SCIP_HEUR*            heur,               /**< LP face heuristic */
397  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
398  	   )
399  	{
400  	   SCIP_Longint nodelimit;
401  	
402  	   /* calculate the maximal number of branching nodes until heuristic is aborted */
403  	   nodelimit = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
404  	
405  	   /* count the setup costs for the sub-MIP as 100 nodes */
406  	   nodelimit -= 100 * SCIPheurGetNCalls(heur);
407  	
408  	   /* add the offset */
409  	   nodelimit += heurdata->nodesofs;
410  	
411  	   /* subtract previously used nodes */
412  	   nodelimit -= heurdata->usednodes;
413  	
414  	   /* do not use more than the maximum number of allowed nodes in one run */
415  	   nodelimit = MIN(nodelimit, heurdata->maxnodes);
416  	
417  	   /* if the subscip has been kept from a previous run, add the number of already processed nodes */
418  	   if( heurdata->subscipdata->subscip != NULL )
419  	      nodelimit += SCIPgetNNodes(heurdata->subscipdata->subscip);
420  	
421  	   return nodelimit;
422  	}
423  	
424  	/** sets node, time, and memory limit according to the parameter settings of the heuristic */
425  	static
426  	SCIP_RETCODE setSubscipLimits(
427  	   SCIP*                 scip,               /**< original SCIP data structure */
428  	   SCIP*                 subscip,            /**< data structure of the sub-problem */
429  	   SCIP_HEUR*            heur,               /**< LP face heuristic */
430  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
431  	   SCIP_Bool*            success             /**< did we successfully set all parameters up? */
432  	   )
433  	{
434  	   SCIP_Real timelimit;
435  	   SCIP_Real memorylimit;
436  	   SCIP_Longint nodelimit;
437  	   SCIP_Bool avoidmemout;
438  	
439  	   *success = TRUE;
440  	
441  	   /* check whether there is enough time and memory left */
442  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
443  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
444  	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
445  	
446  	   if( ! SCIPisInfinity(scip, timelimit) )
447  	      timelimit -= SCIPgetSolvingTime(scip);
448  	
449  	   /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
450  	   if( ! SCIPisInfinity(scip, memorylimit) )
451  	   {
452  	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
453  	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
454  	   }
455  	
456  	   /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE)
457  	    * to create a copy of SCIP, including external memory usage */
458  	   if( timelimit <= 0.0 || (avoidmemout && memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0) )
459  	   {
460  	      *success = FALSE;
461  	      return SCIP_OKAY;
462  	   }
463  	
464  	   /* calculate node limit for the subproblem */
465  	   nodelimit = calcNodeLimit(scip, heur, heurdata);
466  	
467  	   /* we should have aborted the sub-SCIP procedure earlier if no additional nodes are allowed
468  	    * with the current parameter settings
469  	    */
470  	   assert(nodelimit > SCIPgetNNodes(subscip));
471  	
472  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
473  	   heurdata->nodelimit = nodelimit;
474  	
475  	   /* set also the other two limits */
476  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
477  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
478  	
479  	   return SCIP_OKAY;
480  	}
481  	
482  	/** sets all one-time parameter settings like search strategy, but no limits */
483  	static
484  	SCIP_RETCODE setSubscipParameters(
485  	   SCIP*                 subscip             /**< data structure of the sub-problem */
486  	   )
487  	{
488  	   /* do not abort subproblem on CTRL-C */
489  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
490  	
491  	   /* for debugging lpface, enable MIP output */
492  	#ifdef SCIP_DEBUG
493  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
494  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
495  	#endif
496  	
497  	   /* disable statistic timing inside sub SCIP */
498  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
499  	
500  	   /* forbid recursive call of heuristics and separators solving subMIPs */
501  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
502  	
503  	   /* disable expensive cutting plane separation */
504  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
505  	
506  	   /* disable expensive presolving */
507  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
508  	
509  	   /* use restart depth first node selection */
510  	   if( SCIPfindNodesel(subscip, "restartdfs") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
511  	   {
512  	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
513  	   }
514  	
515  	   /* use inference branching */
516  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
517  	   {
518  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
519  	   }
520  	
521  	   /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
522  	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
523  	   {
524  	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
525  	   }
526  	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
527  	   {
528  	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
529  	   }
530  	   if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
531  	   {
532  	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
533  	   }
534  	
535  	   return SCIP_OKAY;
536  	}
537  	
538  	/** reset the sub-SCIP data to its default values */
539  	static
540  	void subscipdataReset(
541  	   SUBSCIPDATA*          subscipdata         /**< data structure of the sub-problem */
542  	   )
543  	{
544  	   subscipdata->subscip = NULL;
545  	   subscipdata->subvars = NULL;
546  	   subscipdata->nsubvars = 0;
547  	   subscipdata->objbound = SCIP_INVALID;
548  	}
549  	
550  	/** free the stored sub-SCIP information */
551  	static
552  	SCIP_RETCODE subscipdataFreeSubscip(
553  	   SCIP*                 scip,               /**< original SCIP data structure */
554  	   SUBSCIPDATA*          subscipdata         /**< data structure of the sub-problem */
555  	   )
556  	{
557  	   assert(subscipdata != NULL);
558  	
559  	   /* free the subscipdata's scip */
560  	   if( subscipdata->subscip != NULL )
561  	   {
562  	      SCIP_CALL( SCIPfree(&subscipdata->subscip) );
563  	   }
564  	
565  	   subscipdata->subscip = NULL;
566  	
567  	   /* free the subscip variables */
568  	   if( subscipdata->subvars != NULL )
569  	   {
570  	      assert(subscipdata->nsubvars > 0);
571  	      SCIPfreeBlockMemoryArray(scip, &subscipdata->subvars, subscipdata->nsubvars);
572  	   }
573  	
574  	   subscipdataReset(subscipdata);
575  	
576  	   return SCIP_OKAY;
577  	}
578  	
579  	/** store the sub-SCIP to the data structure */
580  	static
581  	SCIP_RETCODE subscipdataCopySubscip(
582  	   SCIP*                 scip,               /**< original SCIP data structure */
583  	   SUBSCIPDATA*          subscipdata,        /**< data structure of the sub-problem */
584  	   SCIP*                 subscip,            /**< sub scip data structure to keep */
585  	   SCIP_VAR**            subvars,            /**< sub scip variable array in the order of the main SCIP variables */
586  	   int                   nvars               /**< number of sub SCIP variables */
587  	   )
588  	{
589  	   assert(scip != NULL);
590  	   assert(subscipdata != NULL);
591  	   assert(subscip != NULL);
592  	   assert(subvars != NULL);
593  	   assert(nvars == SCIPgetNVars(scip));
594  	
595  	   assert(subscipdata->subscip == NULL);
596  	   assert(subscipdata->subvars == NULL);
597  	
598  	   subscipdata->subscip = subscip;
599  	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &subscipdata->subvars, subvars, nvars) );
600  	   subscipdata->nsubvars = nvars;
601  	
602  	   subscipdata->objbound = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip));
603  	
604  	   return SCIP_OKAY;
605  	}
606  	
607  	#ifdef SCIP_DEBUG
608  	/** print debug message listing solving time, nodes, and status of sub-SCIP */
609  	static
610  	SCIP_RETCODE subscipGetInfo(
611  	   SCIP*                 scip,               /**< SCIP data structure */
612  	   SCIP*                 subscip             /**< sub SCIP data */
613  	   )
614  	{
615  	   SCIP_Real timelimit;
616  	   SCIP_Real memorylimit;
617  	   SCIP_Longint nodelimit;
618  	   SCIP_Real time;
619  	   SCIP_Longint nodes;
620  	   SCIP_STATUS status;
621  	
622  	   SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &timelimit) );
623  	   SCIP_CALL( SCIPgetRealParam(subscip, "limits/memory", &memorylimit) );
624  	   SCIP_CALL( SCIPgetLongintParam(subscip, "limits/nodes", &nodelimit) );
625  	
626  	   time = SCIPgetSolvingTime(subscip);
627  	   nodes = SCIPgetNNodes(subscip);
628  	   status = SCIPgetStatus(subscip);
629  	
630  	   SCIPdebugMsg(scip, "SCIP info: Time: %.1f (Limit: %.1f) Nodes: %"SCIP_LONGINT_FORMAT" (Limit: %"SCIP_LONGINT_FORMAT") Status: %d\n",
631  	         time, timelimit, nodes, nodelimit, status);
632  	
633  	   return SCIP_OKAY;
634  	}
635  	#endif
636  	
637  	/** create the objective function based on the user selection */
638  	static
639  	SCIP_RETCODE changeSubvariableObjective(
640  	   SCIP*                 scip,               /**< SCIP data structure */
641  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
642  	   SCIP_VAR*             var,                /**< SCIP variable */
643  	   SCIP_VAR*             subvar,             /**< sub-SCIP variable whose objective coefficient is changed */
644  	   SCIP_HEURDATA*        heurdata            /**< heuristic data structure to control how the objective is changed */
645  	   )
646  	{
647  	   SCIP_Real objcoeff;
648  	   SCIP_Real upfrac;
649  	   SCIP_Real downfrac;
650  	   SCIP_Real lpsolval;
651  	   SCIP_Real rootlpsolval;
652  	
653  	   /* create the objective value based on the choice of the sub-SCIP objective */
654  	   switch( heurdata->subscipobjective )
655  	   {
656  	      /* use zero as objective function */
657  	      case 'z':
658  	         objcoeff = 0.0;
659  	         break;
660  	
661  	      /* use current LP fractionality as objective */
662  	      case 'f':
663  	         lpsolval = SCIPvarGetLPSol(var);
664  	         downfrac = SCIPfrac(scip, lpsolval);
665  	         upfrac = 1.0 - downfrac;
666  	
667  	         objcoeff = downfrac - upfrac;
668  	         break;
669  	
670  	      /* use root LP solution difference */
671  	      case 'r':
672  	         lpsolval = SCIPvarGetLPSol(var);
673  	         rootlpsolval = SCIPvarGetRootSol(var);
674  	         objcoeff = rootlpsolval - lpsolval;
675  	         break;
676  	
677  	      /* use average inferences */
678  	      case 'i':
679  	         objcoeff = SCIPgetVarAvgInferences(scip, var, SCIP_BRANCHDIR_DOWNWARDS)
680  	            - SCIPgetVarAvgInferences(scip, var, SCIP_BRANCHDIR_UPWARDS);
681  	         break;
682  	
683  	      /* use original objective function */
684  	      case 'o':
685  	         objcoeff = SCIPvarGetObj(var);
686  	         break;
687  	      default:
688  	         objcoeff = 0.0;
689  	         break;
690  	   }
691  	
692  	   SCIP_CALL( SCIPchgVarObj(subscip, subvar, objcoeff) );
693  	
694  	   return SCIP_OKAY;
695  	}
696  	
697  	/* ---------------- Callback methods of event handler ---------------- */
698  	
699  	/** execution callback of the event handler for Lpface sub-SCIP
700  	 *
701  	 * we interrupt the solution process if we hit the LP iteration limit per node
702  	 */
703  	static
704  	SCIP_DECL_EVENTEXEC(eventExecLpface)
705  	{
706  	   SCIP_HEURDATA* heurdata;
707  	
708  	   assert(eventhdlr != NULL);
709  	   assert(eventdata != NULL);
710  	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
711  	   assert(event != NULL);
712  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
713  	
714  	   heurdata = (SCIP_HEURDATA*)eventdata;
715  	   assert(heurdata != NULL);
716  	
717  	   /* interrupt solution process of sub-SCIP */
718  	   if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
719  	   {
720  	      SCIPdebugMsg(scip, "interrupt after  %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
721  	      SCIP_CALL( SCIPinterruptSolve(scip) );
722  	   }
723  	
724  	   return SCIP_OKAY;
725  	}
726  	
727  	/** setup and solve the subproblem and catch the return code */
728  	static
729  	SCIP_RETCODE setupSubscipLpface(
730  	   SCIP*                 scip,               /**< SCIP data structure */
731  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
732  	   SCIP_HEURDATA*        heurdata,           /**< heuristics data */
733  	   SCIP_VAR**            subvars,            /**< subproblem's variables */
734  	   SCIP_VAR**            vars,               /**< original problem's variables */
735  	   SCIP_VAR**            fixvars,            /**< variables that should be fixed */
736  	   SCIP_Real*            fixvals,            /**< corresponding fixing values */
737  	   int                   nfixvars,           /**< number of variables that should be fixed */
738  	   int                   nvars               /**< number of original problem's variables */
739  	   )
740  	{
741  	   SCIP_HASHMAP* varmapfw = NULL;            /* mapping of SCIP variables to sub-SCIP variables */
742  	   SCIP_Bool success;
743  	   int i;
744  	
745  	   assert( subscip != NULL );
746  	   assert( heurdata != NULL );
747  	   assert( vars != NULL );
748  	
749  	   /* create the variable hash map */
750  	   SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
751  	   success = FALSE;
752  	
753  	   if( heurdata->uselprows )
754  	   {
755  	      SCIP_Bool valid;
756  	      char probname[SCIP_MAXSTRLEN];
757  	
758  	      /* copy all plugins */
759  	      SCIP_CALL( SCIPcopyPlugins(scip, subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE,
760  	            TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, &valid) );
761  	      /* get name of the original problem and add the string "_lpfacesub" */
762  	      (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_lpfacesub", SCIPgetProbName(scip));
763  	
764  	      /* create the subproblem */
765  	      SCIP_CALL( SCIPcreateProbBasic(subscip, probname) );
766  	      SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(scip) + 1);
767  	
768  	      /* copy all variables */
769  	      SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, fixvars, fixvals, nfixvars, TRUE) );
770  	
771  	      /* copy parameter settings */
772  	      SCIP_CALL( SCIPcopyParamSettings(scip, subscip) );
773  	   }
774  	   else
775  	   {
776  	      SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapfw, NULL, "lpface", fixvars, fixvals, nfixvars, TRUE, FALSE, FALSE, TRUE, &success) );
777  	
778  	      if( heurdata->copycuts )
779  	      {
780  	         /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
781  	         SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
782  	      }
783  	   }
784  	
785  	   /* fill subvars array with mapping from original variables and set the objective coefficient to the desired value */
786  	   for( i = 0; i < nvars; i++ )
787  	   {
788  	      subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
789  	
790  	      if( subvars[i] != NULL )
791  	      {
792  	         SCIP_CALL( changeSubvariableObjective(scip, subscip, vars[i], subvars[i], heurdata) );
793  	      }
794  	   }
795  	
796  	   /* free hash map */
797  	   SCIPhashmapFree(&varmapfw);
798  	
799  	   /* disable output to console */
800  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
801  	
802  	   /* fix variables that are at their bounds and have nonzero reduced costs  */
803  	   SCIP_CALL( setupSubproblem(scip, subscip, subvars, heurdata) );
804  	
805  	   /* set up sub-SCIP parameters */
806  	   SCIP_CALL( setSubscipParameters(subscip) );
807  	
808  	   return SCIP_OKAY;
809  	}
810  	
811  	/** setup and solve the subproblem and catch the return code */
812  	static
813  	SCIP_RETCODE solveSubscipLpface(
814  	   SCIP*                 scip,               /**< SCIP data structure */
815  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
816  	   SCIP_HEUR*            heur,               /**< mutation heuristic */
817  	   SCIP_HEURDATA*        heurdata,           /**< heuristics data */
818  	   SCIP_VAR**            subvars,            /**< subproblem's variables */
819  	   SCIP_RESULT*          result,             /**< pointer to store the result */
820  	   SCIP_Real             focusnodelb,        /**< lower bound of the focus node */
821  	   SCIP_Bool*            keepthisscip        /**< should the subscip be kept or deleted? */
822  	   )
823  	{
824  	   SCIP_EVENTHDLR* eventhdlr;
825  	   SCIP_Bool success;
826  	
827  	   assert( scip != NULL );
828  	   assert( subscip != NULL );
829  	   assert( heur != NULL );
830  	   assert( heurdata != NULL );
831  	   assert( subvars != NULL );
832  	
833  	   /* create event handler for LP events */
834  	   SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLpface, NULL) );
835  	   if( eventhdlr == NULL )
836  	   {
837  	      SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
838  	      return SCIP_PLUGINNOTFOUND;
839  	   }
840  	
841  	   /* determine node, memory, and time limits for the sub-SCIP. Both node and time limit change with every call to
842  	    * the heuristic
843  	    */
844  	   SCIP_CALL( setSubscipLimits(scip, subscip, heur, heurdata, &success) );
845  	
846  	   /* if we did not succeed to set the limits of the subscip to let it run, we won't keep it any longer */
847  	   if( !success )
848  	   {
849  	      *keepthisscip = FALSE;
850  	
851  	      return SCIP_OKAY;
852  	   }
853  	
854  	   /* catch LP events of sub-SCIP */
855  	   SCIP_CALL( SCIPtransformProb(subscip) );
856  	   SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
857  	
858  	#ifdef WRITELPFACEPROB
859  	   {
860  	      char probfilename[] = "./lpface_prob.mps";
861  	      char paramfilename[] = "./lpface_prob.set";
862  	      SCIPinfoMessage(scip, NULL, "Writing problem and parameters to file: <%s> <%s>\n", probfilename, paramfilename);
863  	      SCIP_CALL( SCIPwriteOrigProblem(subscip, probfilename, NULL, FALSE) );
864  	      SCIP_CALL( SCIPwriteParams(subscip, paramfilename, TRUE, TRUE) );
865  	   }
866  	#endif
867  	
868  	   /* we must not be infeasible at this stage */
869  	   assert(SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE);
870  	
871  	   /* solve the subproblem */
872  	   SCIPdebugMsg(scip, "Solve Lpface subMIP\n");
873  	   SCIPdebug(
874  	      SCIP_CALL( subscipGetInfo(scip, subscip) );
875  	   )
876  	
877  	   /* Errors in solving the subproblem should not kill the overall solving process.
878  	    * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
879  	    */
880  	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
881  	
882  	   /* print solving statistics of subproblem if we are in SCIP's debug mode */
883  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
884  	
885  	   /* save useful information regarding the subscip runs */
886  	   heurdata->usednodes += SCIPgetNNodes(subscip);
887  	   heurdata->submipnlpiters += SCIPgetNLPIterations(subscip);
888  	   heurdata->submippresoltime += SCIPgetPresolvingTime(subscip);
889  	   heurdata->submipstatus = SCIPgetStatus(subscip);
890  	
891  	   /* store the focus node lower bound as infeasible to avoid running on this face again */
892  	   if( heurdata->submipstatus == SCIP_STATUS_INFEASIBLE )
893  	   {
894  	      heurdata->lastlpobjinfeas = focusnodelb;
895  	      *keepthisscip = FALSE;
896  	   }
897  	   else if( SCIPgetNSols(subscip) > 0 )
898  	   {
899  	      int solindex;
900  	
901  	      /* check, whether a solution was found;
902  	       * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one is accepted
903  	       */
904  	      SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, &solindex) );
905  	      SCIPdebugMsg(scip, "Transfer was %s successful\n", success ? "" : "not");
906  	
907  	      /* we found an optimal solution and are done. Thus, we free the subscip immediately */
908  	      if( success )
909  	      {
910  	         *keepthisscip = FALSE;
911  	         *result = SCIP_FOUNDSOL;
912  	      }
913  	
914  	      /* if solution could not be added to problem => run is counted as a failure */
915  	      if( ! success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) )
916  	         updateFailureStatistic(scip, heurdata);
917  	   }
918  	   else
919  	   {
920  	      /* if no new solution was found, run was a failure */
921  	      updateFailureStatistic(scip, heurdata);
922  	   }
923  	
924  	   return SCIP_OKAY;
925  	}
926  	
927  	/*
928  	 * Callback methods of primal heuristic
929  	 */
930  	
931  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
932  	static
933  	SCIP_DECL_HEURCOPY(heurCopyLpface)
934  	{  /*lint --e{715}*/
935  	   assert(scip != NULL);
936  	   assert(heur != NULL);
937  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
938  	
939  	   /* call inclusion method of primal heuristic */
940  	   SCIP_CALL( SCIPincludeHeurLpface(scip) );
941  	
942  	   return SCIP_OKAY;
943  	}
944  	
945  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
946  	static
947  	SCIP_DECL_HEURFREE(heurFreeLpface)
948  	{  /*lint --e{715}*/
949  	   SCIP_HEURDATA* heurdata;
950  	
951  	   assert(heur != NULL);
952  	   assert(scip != NULL);
953  	
954  	   /* get heuristic data */
955  	   heurdata = SCIPheurGetData(heur);
956  	   assert(heurdata != NULL);
957  	
958  	   /* free heuristic data */
959  	   SCIPfreeBlockMemory(scip, &heurdata);
960  	   SCIPheurSetData(heur, NULL);
961  	
962  	   return SCIP_OKAY;
963  	}
964  	
965  	/** initialization method of primal heuristic (called after problem was transformed) */
966  	static
967  	SCIP_DECL_HEURINIT(heurInitLpface)
968  	{  /*lint --e{715}*/
969  	   SCIP_HEURDATA* heurdata;
970  	
971  	   assert(heur != NULL);
972  	   assert(scip != NULL);
973  	
974  	   /* get heuristic's data */
975  	   heurdata = SCIPheurGetData(heur);
976  	   assert(heurdata != NULL);
977  	
978  	   /* initialize data */
979  	   heurdata->usednodes = 0;
980  	   heurdata->nfailures = 0;
981  	   heurdata->nextnodenumber = 0;
982  	
983  	   heurdata->submipstatus = SCIP_STATUS_UNKNOWN;
984  	   heurdata->submipnlpiters = -1;
985  	   heurdata->submippresoltime = 0.0;
986  	   heurdata->nvarsfixed = -1;
987  	
988  	   return SCIP_OKAY;
989  	}
990  	
991  	/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
992  	static
993  	SCIP_DECL_HEURINITSOL(heurInitsolLpface)
994  	{  /*lint --e{715}*/
995  	   SCIP_HEURDATA* heurdata;
996  	
997  	   assert(heur != NULL);
998  	   assert(scip != NULL);
999  	
1000 	   /* get heuristic's data */
1001 	   heurdata = SCIPheurGetData(heur);
1002 	   assert(heurdata != NULL);
1003 	
1004 	   /* reset the last infeasible objective because it lives in transformed space and must be invalidated at every restart */
1005 	   heurdata->lastlpobjinfeas = -SCIPinfinity(scip);
1006 	
1007 	   assert(heurdata->subscipdata == NULL);
1008 	
1009 	   /* variable order might have changed since the last run, reinitialize sub-SCIP data */
1010 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata->subscipdata) );
1011 	   subscipdataReset(heurdata->subscipdata);
1012 	
1013 	   return SCIP_OKAY;
1014 	}
1015 	
1016 	/** solving process deinitialization method of primal heuristic (called before branch and bound process is exiting) */
1017 	static
1018 	SCIP_DECL_HEUREXITSOL(heurExitsolLpface)
1019 	{  /*lint --e{715}*/
1020 	   SCIP_HEURDATA* heurdata;
1021 	
1022 	   assert(heur != NULL);
1023 	   assert(scip != NULL);
1024 	
1025 	   /* get heuristic's data */
1026 	   heurdata = SCIPheurGetData(heur);
1027 	   assert(heurdata != NULL);
1028 	
1029 	   /* variable order might change after restart, free the heuristic subscipdata */
1030 	   assert(heurdata->keepsubscip || heurdata->subscipdata->subscip == NULL);
1031 	   if( heurdata->subscipdata->subscip != NULL )
1032 	   {
1033 	      /* free kept data structures first */
1034 	      SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1035 	   }
1036 	
1037 	   /* free the sub-SCIP data structure */
1038 	   SCIPfreeBlockMemory(scip, &heurdata->subscipdata);
1039 	
1040 	   return SCIP_OKAY;
1041 	}
1042 	
1043 	#ifdef SCIP_STATISTIC
1044 	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
1045 	static
1046 	SCIP_DECL_HEUREXIT(heurExitLpface)
1047 	{  /*lint --e{715}*/
1048 	   SCIP_HEURDATA* heurdata;
1049 	
1050 	   assert(heur != NULL);
1051 	   assert(scip != NULL);
1052 	
1053 	   /* get heuristic's data */
1054 	   heurdata = SCIPheurGetData(heur);
1055 	   assert(heurdata != NULL);
1056 	
1057 	   SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1058 	      "LP Face heuristic stats: Status: %d Nodes: %d LP iters: %d Fixed: %d Presolving time: %.2f\n",
1059 	      heurdata->submipstatus, heurdata->usednodes, heurdata->submipnlpiters, heurdata->nvarsfixed, heurdata->submippresoltime);
1060 	
1061 	   return SCIP_OKAY;
1062 	}
1063 	#else
1064 	#define heurExitLpface NULL
1065 	#endif
1066 	
1067 	/** execution method of primal heuristic */
1068 	static
1069 	SCIP_DECL_HEUREXEC(heurExecLpface)
1070 	{  /*lint --e{715}*/
1071 	   SCIP* subscip;                            /* the subproblem created by lpface       */
1072 	   SCIP_HEURDATA* heurdata;                  /* primal heuristic data                  */
1073 	   SCIP_VAR** vars;                          /* original problem's variables           */
1074 	   SCIP_VAR** subvars;                       /* subproblem's variables                 */
1075 	   SCIP_RETCODE retcode;
1076 	   SCIP_Bool keepthisscip;
1077 	   SCIP_Real focusnodelb;
1078 	   SCIP_Real rootlb;
1079 	   SCIP_Longint nodelimit;                   /* node limit for the subproblem          */
1080 	   int nvars;                                /* number of original problem's variables */
1081 	   int nbinvars;
1082 	   int nintvars;
1083 	
1084 	   assert(heur != NULL);
1085 	   assert(scip != NULL);
1086 	   assert(result != NULL);
1087 	
1088 	   /* get heuristic's data */
1089 	   heurdata = SCIPheurGetData(heur);
1090 	   assert(heurdata != NULL);
1091 	
1092 	   *result = SCIP_DELAYED;
1093 	
1094 	   /* we skip infeasible nodes */
1095 	   if( nodeinfeasible )
1096 	      return SCIP_OKAY;
1097 	
1098 	   /* the node number to run the heuristic again was not yet reached */
1099 	   if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1100 	      return SCIP_OKAY;
1101 	
1102 	   /* do not run heuristic on nodes that were not solved to optimality */
1103 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1104 	      return SCIP_OKAY;
1105 	
1106 	   /* LP face requires that the LP defines a valid lower bound for the current node */
1107 	   if( ! SCIPisLPRelax(scip) || ! SCIPallColsInLP(scip) )
1108 	      return SCIP_OKAY;
1109 	
1110 	   assert(SCIPgetCurrentNode(scip) != NULL);
1111 	   focusnodelb = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip));
1112 	
1113 	   /* from the checked conditions, the LP objective should be a valid lower bound for the current node */
1114 	   assert(SCIPisGE(scip, focusnodelb, SCIPgetLPObjval(scip)));
1115 	
1116 	   /* do not run if the current focus node already has a lower bound higher than the LP value at the node,
1117 	    * for example, due to strong branching
1118 	    */
1119 	   if( SCIPisGT(scip, focusnodelb, SCIPgetLPObjval(scip)) )
1120 	      return SCIP_OKAY;
1121 	
1122 	   /* delay heuristic if the active search tree path is not deep enough */
1123 	   if( SCIPgetDepth(scip) < heurdata->minpathlen - 1 )
1124 	      return SCIP_OKAY;
1125 	
1126 	   /* only run at lower bound defining nodes */
1127 	   if( SCIPisGT(scip, focusnodelb, SCIPgetLowerbound(scip)) )
1128 	      return SCIP_OKAY;
1129 	
1130 	   /* only run if lower bound has increased since last LP objective where the sub-MIP was solved to infeasibility */
1131 	   if( SCIPisEQ(scip, heurdata->lastlpobjinfeas, focusnodelb) )
1132 	      return SCIP_OKAY;
1133 	
1134 	   /* make the reasoning stronger if the objective value must be integral */
1135 	   if( SCIPisObjIntegral(scip)
1136 	         && (! SCIPisIntegral(scip, focusnodelb) || SCIPisLT(scip, focusnodelb, heurdata->lastlpobjinfeas + 1.0)) )
1137 	      return SCIP_OKAY;
1138 	
1139 	   rootlb = SCIPgetLowerboundRoot(scip);
1140 	   assert(SCIPisLE(scip, rootlb, focusnodelb));
1141 	
1142 	   /* if the lower bound hasn't changed since the root node, we want to run anyway, otherwise we base our decision on the
1143 	    * total path length of the active search tree along which the lower bound did not change anymore.
1144 	    */
1145 	   if( SCIPisLT(scip, rootlb, focusnodelb) )
1146 	   {
1147 	      SCIP_NODE* parent;
1148 	      int nonimprovingpathlen = 0; /* the length of the current path (in edges) along which the lower bound stayed the same */
1149 	
1150 	      parent = SCIPnodeGetParent(SCIPgetCurrentNode(scip));
1151 	
1152 	      /* count the path length along which the dual bound has not changed */
1153 	      while( SCIPisEQ(scip, SCIPnodeGetLowerbound(parent), focusnodelb) && nonimprovingpathlen < heurdata->minpathlen )
1154 	      {
1155 	         ++nonimprovingpathlen;
1156 	
1157 	         /* we cannot hit the root node because the root lower bound is strictly smaller */
1158 	         assert(SCIPnodeGetParent(parent) != NULL);
1159 	         parent = SCIPnodeGetParent(parent);
1160 	      }
1161 	
1162 	      /* we return if the nonimproving path is too short measured by the heuristic frequency */
1163 	      if( nonimprovingpathlen < heurdata->minpathlen )
1164 	      {
1165 	         /* we do not delay the heuristic if the path has length zero, otherwise it may be called at children so that
1166 	          * the path length is sufficient
1167 	          */
1168 	         if( nonimprovingpathlen == 0 )
1169 	            *result = SCIP_DIDNOTRUN;
1170 	
1171 	         return SCIP_OKAY;
1172 	      }
1173 	   }
1174 	
1175 	   *result = SCIP_DIDNOTRUN;
1176 	
1177 	   /* calculate the maximal number of branching nodes until heuristic is aborted */
1178 	   nodelimit = calcNodeLimit(scip, heur, heurdata);
1179 	
1180 	   /* check whether we have enough nodes left to call subproblem solving */
1181 	   if( nodelimit < heurdata->minnodes )
1182 	      return SCIP_OKAY;
1183 	
1184 	   if( SCIPisStopped(scip) )
1185 	     return SCIP_OKAY;
1186 	
1187 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1188 	   assert(nvars > 0);
1189 	
1190 	   /* check whether discrete variables are present */
1191 	   if( nbinvars == 0 && nintvars == 0 )
1192 	      return SCIP_OKAY;
1193 	
1194 	   *result = SCIP_DIDNOTFIND;
1195 	
1196 	   keepthisscip = heurdata->keepsubscip;
1197 	
1198 	   /* check if variable number increased since last call to the sub-SCIP */
1199 	   if( heurdata->subscipdata->subscip != NULL && heurdata->subscipdata->nsubvars != nvars )
1200 	   {
1201 	      SCIPdebugMsg(scip, "Free subscip of LP face heuristic because variable number %d changed since last call (was %d)\n",
1202 	         nvars, heurdata->subscipdata->nsubvars);
1203 	
1204 	      SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1205 	   }
1206 	   else if( heurdata->subscipdata->subscip != NULL && SCIPisGT(scip, focusnodelb, heurdata->subscipdata->objbound) )
1207 	   {
1208 	      SCIPdebugMsg(scip, "Free subscip of LP face heuristic because of different dual bound: %16.9g > %16.9g\n",
1209 	         SCIPretransformObj(scip, focusnodelb), SCIPretransformObj(scip, heurdata->subscipdata->objbound));
1210 	
1211 	      SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1212 	   }
1213 	
1214 	   /* retrieve the sub-SCIP from the heuristic data structure */
1215 	   if( heurdata->subscipdata->subscip != NULL )
1216 	   {
1217 	      subscip = heurdata->subscipdata->subscip;
1218 	      subvars = heurdata->subscipdata->subvars;
1219 	      nvars = heurdata->subscipdata->nsubvars;
1220 	
1221 	      SCIPdebug(
1222 	         SCIPdebugMsg(scip, "Loaded sub-SCIP from previous run:\n");
1223 	         SCIP_CALL( subscipGetInfo(scip, subscip) );
1224 	         )
1225 	   }
1226 	   else
1227 	   {
1228 	      SCIP_VAR** fixvars;
1229 	      SCIP_Real* fixvals;
1230 	      int nfixvars;
1231 	      SCIP_Bool success;
1232 	
1233 	      assert(heurdata->subscipdata->subscip == NULL);
1234 	
1235 	      /* allocate memory to hold sub-SCIP variables */
1236 	      SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1237 	
1238 	      SCIP_CALL( SCIPallocBufferArray(scip, &fixvars, nvars) );
1239 	      SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) );
1240 	
1241 	      SCIP_CALL( determineVariableFixings(scip, heurdata, fixvars, fixvals, &nfixvars, &success) );
1242 	
1243 	      if( ! success )
1244 	      {
1245 	         SCIPfreeBufferArray(scip, &fixvals);
1246 	         SCIPfreeBufferArray(scip, &fixvars);
1247 	         SCIPfreeBufferArray(scip, &subvars);
1248 	
1249 	         *result = SCIP_DIDNOTRUN;
1250 	         return SCIP_OKAY;
1251 	      }
1252 	
1253 	      SCIPdebugMsg(scip, "Creating new sub-Problem for LP face heuristic\n");
1254 	
1255 	      /* initialize the subproblem */
1256 	      SCIP_CALL( SCIPcreate(&subscip) );
1257 	
1258 	      SCIP_CALL( setupSubscipLpface(scip, subscip, heurdata, subvars, vars, fixvars, fixvals, nfixvars, nvars) );
1259 	
1260 	      SCIPfreeBufferArray(scip, &fixvals);
1261 	      SCIPfreeBufferArray(scip, &fixvars);
1262 	   }
1263 	
1264 	   retcode = solveSubscipLpface(scip, subscip, heur, heurdata, subvars, result, focusnodelb, &keepthisscip);
1265 	
1266 	   SCIP_CALL( retcode );
1267 	
1268 	   /* free subproblem or store it for the next run of the heuristic */
1269 	   if( ! keepthisscip )
1270 	   {
1271 	      /* we only allocated buffer memory if no previous subscip was reinstalled */
1272 	      if( heurdata->subscipdata->subscip == NULL )
1273 	      {
1274 	         SCIPfreeBufferArray(scip, &subvars);
1275 	         SCIP_CALL( SCIPfree(&subscip) );
1276 	      }
1277 	      else
1278 	         SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) );
1279 	
1280 	      subscipdataReset(heurdata->subscipdata);
1281 	   }
1282 	   else
1283 	   {
1284 	      /* if the subscip has not yet been stored, we copy the subscip into the heuristic data to keep it for the next run */
1285 	      if( heurdata->subscipdata->subscip == NULL )
1286 	      {
1287 	         SCIP_CALL( subscipdataCopySubscip(scip, heurdata->subscipdata, subscip, subvars, nvars) );
1288 	         SCIPfreeBufferArray(scip, &subvars);
1289 	      }
1290 	      else
1291 	      {
1292 	         assert(heurdata->subscipdata->subscip == subscip);
1293 	         assert(heurdata->subscipdata->subvars == subvars);
1294 	         assert(heurdata->subscipdata->nsubvars == nvars);
1295 	      }
1296 	   }
1297 	
1298 	   return SCIP_OKAY;
1299 	}
1300 	
1301 	/*
1302 	 * primal heuristic specific interface methods
1303 	 */
1304 	
1305 	/** creates the lpface primal heuristic and includes it in SCIP */
1306 	SCIP_RETCODE SCIPincludeHeurLpface(
1307 	   SCIP*                 scip                /**< SCIP data structure */
1308 	   )
1309 	{
1310 	   SCIP_HEURDATA* heurdata;
1311 	   SCIP_HEUR* heur;
1312 	
1313 	   /* create Lpface primal heuristic data */
1314 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1315 	
1316 	   heurdata->subscipdata = NULL;
1317 	
1318 	   /* include primal heuristic */
1319 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1320 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1321 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLpface, heurdata) );
1322 	
1323 	   assert(heur != NULL);
1324 	
1325 	   /* set non-NULL pointers to callback methods */
1326 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLpface) );
1327 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLpface) );
1328 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLpface) );
1329 	   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolLpface) );
1330 	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolLpface) );
1331 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLpface) );
1332 	
1333 	   /* add lpface primal heuristic parameters */
1334 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1335 	         "number of nodes added to the contingent of the total nodes",
1336 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1337 	
1338 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1339 	         "maximum number of nodes to regard in the subproblem",
1340 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1341 	
1342 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1343 	         "minimum number of nodes required to start the subproblem",
1344 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1345 	
1346 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1347 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1348 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1349 	
1350 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1351 	         "required percentage of fixed integer variables in sub-MIP to run",
1352 	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1353 	
1354 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
1355 	         "factor by which the limit on the number of LP depends on the node limit",
1356 	         &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1357 	
1358 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1359 	         "should subproblem be created out of the rows in the LP rows?",
1360 	         &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1361 	
1362 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dualbasisequations",
1363 	         "should dually nonbasic rows be turned into equations?",
1364 	         &heurdata->dualbasisequations, TRUE, DEFAULT_DUALBASISEQUATIONS, NULL, NULL) );
1365 	
1366 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/keepsubscip",
1367 	         "should the heuristic continue solving the same sub-SCIP?",
1368 	         &heurdata->keepsubscip, TRUE, DEFAULT_KEEPSUBSCIP, NULL, NULL) );
1369 	
1370 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1371 	         "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1372 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1373 	
1374 	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/subscipobjective",
1375 	         "objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference, (i)nference, LP (f)ractionality, (o)riginal",
1376 	         &heurdata->subscipobjective, TRUE, 'z', "forzi", NULL, NULL) );
1377 	
1378 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minpathlen",
1379 	         "the minimum active search tree path length along which lower bound hasn't changed before heuristic becomes active",
1380 	         &heurdata->minpathlen, TRUE, DEFAULT_MINPATHLEN, 0, 65531, NULL, NULL) );
1381 	
1382 	   return SCIP_OKAY;
1383 	}
1384