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_repair.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  repair primal heuristic
28   	 * @author Gregor Hendel
29   	 * @author Thomas Nagel
30   	 *
31   	 */
32   	
33   	/* This heuristic takes an infeasible solution and tries to repair it.
34   	 * This can happen by variable fixing as long as the sum of all potential possible shiftings
35   	 * is higher than alpha*slack or slack variables with a strong penalty on the objective function.
36   	 * This heuristic cannot run if variable fixing and slack variables are turned off.
37   	 */
38   	
39   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40   	
41   	#include "blockmemshell/memory.h"
42   	#include "scip/cons_linear.h"
43   	#include "scip/cons_varbound.h"
44   	#include "scip/heur_repair.h"
45   	#include "scip/pub_heur.h"
46   	#include "scip/pub_lp.h"
47   	#include "scip/pub_message.h"
48   	#include "scip/pub_misc.h"
49   	#include "scip/pub_misc_sort.h"
50   	#include "scip/pub_var.h"
51   	#include "scip/scip_branch.h"
52   	#include "scip/scip_cons.h"
53   	#include "scip/scip_copy.h"
54   	#include "scip/scip_general.h"
55   	#include "scip/scip_heur.h"
56   	#include "scip/scip_lp.h"
57   	#include "scip/scip_mem.h"
58   	#include "scip/scip_message.h"
59   	#include "scip/scip_numerics.h"
60   	#include "scip/scip_param.h"
61   	#include "scip/scip_prob.h"
62   	#include "scip/scip_sol.h"
63   	#include "scip/scip_solve.h"
64   	#include "scip/scip_solvingstats.h"
65   	#include "scip/scip_timing.h"
66   	#include "scip/scip_tree.h"
67   	#include "scip/scip_var.h"
68   	#include "scip/scipdefplugins.h"
69   	#include <string.h>
70   	
71   	#define HEUR_NAME             "repair"
72   	#define HEUR_DESC             "tries to repair a primal infeasible solution"
73   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
74   	#define HEUR_PRIORITY         -20
75   	#define HEUR_FREQ             -1
76   	#define HEUR_FREQOFS          0
77   	#define HEUR_MAXDEPTH         -1
78   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
79   	#define HEUR_USESSUBSCIP      TRUE      /**< does the heuristic use a secondary SCIP instance? */
80   	#define DEFAULT_MINFIXINGRATE 0.3       /* minimum percentage of integer variables that have to be fixed */
81   	
82   	#define DEFAULT_NODESOFS      500       /* number of nodes added to the contingent of the total nodes */
83   	#define DEFAULT_MAXNODES      5000      /* maximum number of nodes to regard in the subproblem */
84   	#define DEFAULT_MINNODES      50        /* minimum number of nodes to regard in the subproblem */
85   	#define DEFAULT_NODESQUOT     0.1       /* subproblem nodes in relation to nodes of the original problem */
86   	
87   	#define DEFAULT_FILENAME      "-"       /**< file name of a solution to be used as infeasible starting point */
88   	#define DEFAULT_ROUNDIT       TRUE      /**< if it is TRUE : fractional variables which are not fractional in the given
89   	                                         *   solution are rounded, if it is FALSE : solving process of this heuristic
90   	                                         *   is stopped
91   	                                         */
92   	#define DEFAULT_USEOBJFACTOR  FALSE     /**< should a scaled objective function for original variables be used in repair
93   	                                         *   subproblem?
94   	                                         */
95   	#define DEFAULT_USEVARFIX     TRUE      /**< should variable fixings be used in repair subproblem? */
96   	#define DEFAULT_USESLACKVARS  FALSE     /**< should slack variables be used in repair subproblem? */
97   	#define DEFAULT_ALPHA         2.0       /**< how many times the potential should be bigger than the slack? */
98   	
99   	/*
100  	 * Data structures
101  	 */
102  	
103  	
104  	/** primal heuristic data */
105  	struct SCIP_HeurData
106  	{
107  	   SCIP_SOL*             infsol;             /**< infeasible solution to start with */
108  	   char*                 filename;           /**< file name of a solution to be used as infeasible starting point */
109  	   SCIP_Longint          usednodes;          /**< number of already used nodes by repair */
110  	   SCIP_Longint          subnodes;           /**< number of nodes which were necessary to solve the sub-SCIP */
111  	   SCIP_Longint          subiters;           /**< contains total number of iterations used in primal and dual simplex
112  	                                              *   and barrier algorithm to solve the sub-SCIP
113  	                                              */
114  	   SCIP_Real             relvarfixed;        /**< relative number of fixed variables */
115  	   SCIP_Real             alpha;              /**< how many times the potential should be bigger than the slack? */
116  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
117  	   SCIP_Real             minfixingrate;      /**< minimum percentage of integer variables that have to be fixed */
118  	#ifdef SCIP_STATISTIC
119  	   SCIP_Real             relviolatedvars;    /**< relative number of violated variables */
120  	   SCIP_Real             subpresoltime;      /**< time for presolving the sub-SCIP */
121  	   SCIP_Real             relviolatedcons;    /**< relative number of violated cons */
122  	   SCIP_Real             originalsolval;     /**< value of the solution find by repair, in the original Problem*/
123  	   SCIP_Real             improvedoldsol;     /**< value of the given solution after being improved by SCIP */
124  	   int                   nviolatedvars;      /**< number of violated variables in the given solution */
125  	   int                   norigvars;          /**< number of all variables in the given problem */
126  	   int                   nviolatedcons;      /**< number of violated cons in the given solution */
127  	   int                   norcons;            /**< number of all cons in the given problem */
128  	#endif
129  	   int                   nvarfixed;          /**< number of all variables fixed in the sub problem */
130  	   int                   runs;               /**< number of branch and bound runs performed to solve the sub-SCIP */
131  	   int                   nodesofs;           /**< number of nodes added to the contingent of the total nodes */
132  	   int                   maxnodes;           /**< maximum number of nodes to regard in the subproblem */
133  	   int                   minnodes;           /**< minimum number of nodes to regard in the subproblem */
134  	   SCIP_Bool             roundit;            /**< if it is TRUE : fractional variables which are not fractional in the
135  	                                              *   given solution are rounded, if it is FALSE : solving process of this
136  	                                              *   heuristic is stopped.
137  	                                              */
138  	   SCIP_Bool             useobjfactor;       /**< should a scaled objective function for original variables be used in
139  	                                              *   repair subproblem?
140  	                                              */
141  	   SCIP_Bool             usevarfix;          /**< should variable fixings be used in repair subproblem? */
142  	   SCIP_Bool             useslackvars;       /**< should slack variables be used in repair subproblem? */
143  	};
144  	
145  	
146  	/*
147  	 * Local methods
148  	 */
149  	
150  	/** computes a factor, so that (factor) * (original objective upper bound) <= 1.*/
151  	static
152  	SCIP_RETCODE getObjectiveFactor(
153  	   SCIP*                 scip,               /**< SCIP data structure */
154  	   SCIP*                 subscip,            /**< SCIP data structure */
155  	   SCIP_Real*            factor,             /**< SCIP_Real to save the factor for the old objective function*/
156  	   SCIP_Bool*            success             /**< SCIP_Bool: Is the factor real?*/
157  	   )
158  	{
159  	   SCIP_VAR** vars;
160  	   SCIP_Real lprelaxobj;
161  	   SCIP_Real upperbound;
162  	   SCIP_Real objoffset;
163  	   int nvars;
164  	   int i;
165  	
166  	   *success = TRUE;
167  	   *factor = 0.0;
168  	   upperbound = 0.0;
169  	
170  	   lprelaxobj = SCIPgetLowerbound(scip);
171  	
172  	   if( SCIPisInfinity(scip, -lprelaxobj) )
173  	   {
174  	      return SCIP_OKAY;
175  	   }
176  	
177  	   if( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
178  	   {
179  	      upperbound = SCIPgetUpperbound(scip);
180  	   }
181  	   else
182  	   {
183  	      SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
184  	
185  	      /* tries to find an upper bound for the original objective function, by compute the worst objective value of the
186  	       * LP-relaxation, which holds all variable bounds
187  	       */
188  	      for (i = 0; i < nvars; ++i)
189  	      {
190  	         upperbound = SCIPvarGetObj(vars[i]);
191  	         if( SCIPisInfinity(scip, upperbound) || SCIPisInfinity(scip, -upperbound) )
192  	         {
193  	            /* TODO fancy diving function to find a solution for the max problem */
194  	            *factor = 1 / SCIPinfinity(scip);
195  	            return SCIP_OKAY;
196  	         }
197  	         else if( SCIPisZero(scip, upperbound) )
198  	         {
199  	            continue;
200  	         }
201  	         else if( SCIPisGT(scip, 0.0, upperbound) )
202  	         {
203  	            *factor += upperbound * SCIPvarGetLbGlobal(vars[i]);
204  	         }
205  	         else
206  	         {
207  	            *factor += upperbound * SCIPvarGetUbGlobal(vars[i]);
208  	         }
209  	      }
210  	   }
211  	
212  	   /* Ending-sequence */
213  	   *factor = upperbound - lprelaxobj;
214  	   if( !SCIPisZero(scip, *factor) )
215  	   {
216  	      *factor = 1.0 / *factor;
217  	   }
218  	
219  	   /* set an offset which guarantees positive objective values */
220  	   objoffset = -lprelaxobj * (*factor);
221  	   SCIP_CALL( SCIPaddOrigObjoffset(subscip, -objoffset) );
222  	
223  	   return SCIP_OKAY;
224  	}
225  	
226  	/** returns the contributed potential for a variable */
227  	static
228  	SCIP_Real getPotentialContributed(
229  	   SCIP*             scip,                   /**< SCIP data structure */
230  	   SCIP_SOL*         sol,                    /**< infeasible solution */
231  	   SCIP_VAR*         var,                    /**< variable, which potential should be returned */
232  	   SCIP_Real         coefficient,            /**< variables coefficient in corresponding row */
233  	   int               sgn                     /**< sign of the slack */
234  	   )
235  	{
236  	   SCIP_Real potential;
237  	
238  	   assert(NULL != scip);
239  	   assert(NULL != var);
240  	
241  	   if( 0 > sgn * coefficient )
242  	   {
243  	      if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) )
244  	      {
245  	         potential = SCIPinfinity(scip);
246  	      }
247  	      else
248  	      {
249  	         potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetLbGlobal(var));
250  	      }
251  	   }
252  	   else
253  	   {
254  	      if( SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
255  	      {
256  	         potential = -SCIPinfinity(scip);
257  	      }
258  	      else
259  	      {
260  	         potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetUbGlobal(var));
261  	      }
262  	   }
263  	
264  	   if( SCIPisZero(scip, potential) )
265  	   {
266  	      potential = 0.0;
267  	   }
268  	   return potential;
269  	}
270  	
271  	/** finds out if a variable can be fixed with respect to the potentials of all rows, if it is possible, the potentials
272  	 *  of rows are adapted and TRUE is returned.
273  	 */
274  	static
275  	SCIP_RETCODE tryFixVar(
276  	   SCIP*                 scip,               /**< SCIP data structure */
277  	   SCIP*                 subscip,            /**< sub-SCIP data structure */
278  	   SCIP_SOL*             sol,                /**< solution data structure */
279  	   SCIP_Real*            potential,          /**< array with all potential values */
280  	   SCIP_Real*            slack,              /**< array with all slack values */
281  	   SCIP_VAR*             var,                /**< variable to be fixed? */
282  	   SCIP_VAR*             subvar,             /**< representative variable for var in the sub-SCIP */
283  	   int*                  inftycounter,       /**< counters how many variables have an infinity potential in a row */
284  	   SCIP_HEURDATA*        heurdata,           /**< repairs heuristic data */
285  	   SCIP_Bool*            fixed               /**< pointer to store whether the fixing was performed (variable was unfixed) */
286  	   )
287  	{
288  	   SCIP_ROW** rows;
289  	   SCIP_COL* col;
290  	   SCIP_Real* vals;
291  	   SCIP_Real alpha;
292  	   SCIP_Real solval;
293  	   SCIP_Bool infeasible;
294  	   int nrows;
295  	   int i;
296  	   int sgn;
297  	   int rowindex;
298  	
299  	   assert(NULL != scip);
300  	   assert(NULL != potential);
301  	   assert(NULL != slack);
302  	   assert(NULL != var);
303  	   assert(NULL != inftycounter);
304  	   assert(NULL != heurdata);
305  	
306  	   alpha = heurdata->alpha;
307  	   infeasible = TRUE;
308  	   *fixed = FALSE;
309  	
310  	   solval = SCIPgetSolVal(scip, sol, var);
311  	
312  	   if( SCIPisFeasLT(scip, solval, SCIPvarGetLbGlobal(var)) )
313  	   {
314  	      return SCIP_OKAY;
315  	   }
316  	   if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) )
317  	   {
318  	      return SCIP_OKAY;
319  	   }
320  	
321  	   col = SCIPvarGetCol(var);
322  	   rows = SCIPcolGetRows(col);
323  	   nrows = SCIPcolGetNLPNonz(col);
324  	   vals = SCIPcolGetVals(col);
325  	
326  	   if( NULL == rows )
327  	   {
328  	      SCIP_CALL( SCIPfixVar(subscip, subvar, solval,
329  	               &infeasible, fixed) );
330  	      assert(!infeasible && *fixed);
331  	      heurdata->nvarfixed++;
332  	      SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var), solval);
333  	      return SCIP_OKAY;
334  	   }
335  	   assert(NULL != rows);
336  	
337  	   /* iterate over rows, where the variable coefficient is nonzero */
338  	   for( i = 0; i < nrows; ++i )
339  	   {
340  	      SCIP_Real contribution;
341  	      rowindex = SCIProwGetLPPos(rows[i]);
342  	      assert(rowindex >= 0);
343  	
344  	      sgn = 1;
345  	
346  	      if( SCIPisFeasZero(scip, slack[rowindex]) )
347  	      {
348  	         continue;
349  	      }
350  	      else if( SCIPisFeasGT(scip, 0.0 , slack[rowindex]) )
351  	      {
352  	         sgn = -1;
353  	      }
354  	
355  	      contribution = getPotentialContributed(scip, sol, var, vals[i], sgn);
356  	
357  	      if( !SCIPisInfinity(scip, REALABS(contribution)) )
358  	      {
359  	         potential[rowindex] -= contribution;
360  	      }
361  	      else
362  	      {
363  	         inftycounter[rowindex]--;
364  	      }
365  	
366  	      assert(0 <= inftycounter[rowindex]);
367  	      if( 0 == inftycounter[rowindex] && REALABS(potential[rowindex]) < alpha * REALABS(slack[rowindex]) )
368  	      {
369  	         /* revert the changes before */
370  	         int j = i;
371  	         for( ; j >= 0; --j )
372  	         {
373  	            sgn = 1;
374  	            if( 0 == slack[rowindex] )
375  	            {
376  	               continue;
377  	            }
378  	            rowindex = SCIProwGetLPPos(rows[j]);
379  	            if( 0 > slack[rowindex])
380  	            {
381  	               sgn = -1;
382  	            }
383  	            contribution = getPotentialContributed(scip, sol, var, vals[j], sgn);
384  	            if( !SCIPisInfinity(scip, REALABS(contribution)) )
385  	            {
386  	               potential[rowindex] += contribution;
387  	            }
388  	            else
389  	            {
390  	               inftycounter[rowindex]++;
391  	            }
392  	         }
393  	         return SCIP_OKAY;
394  	      }
395  	   }
396  	
397  	   SCIP_CALL( SCIPfixVar(subscip, subvar, solval, &infeasible, fixed) );
398  	   assert(!infeasible && *fixed);
399  	   heurdata->nvarfixed++;
400  	   SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var),
401  	         SCIPgetSolVal(scip, sol, var));
402  	
403  	   return SCIP_OKAY;
404  	}
405  	
406  	/** checks if all integral variables in the given solution are integral. */
407  	static
408  	SCIP_RETCODE checkCands(
409  	   SCIP*                 scip,               /**< SCIP data structure */
410  	   SCIP_SOL*             sol,                /**< solution pointer to the to be checked solution */
411  	   SCIP_Bool             roundit,            /**< round fractional solution values of integer variables */
412  	   SCIP_Bool*            success             /**< pointer to store if all integral variables are integral or could
413  	                                              *   be rounded
414  	                                              */
415  	   )
416  	{
417  	   SCIP_VAR** vars;
418  	   int nvars;
419  	   int nfracvars;
420  	   int nbinvars;
421  	   int nintvars;
422  	   int i;
423  	
424  	   assert(NULL != success);
425  	   assert(NULL != sol);
426  	
427  	   *success = TRUE;
428  	
429  	   /* get variable data */
430  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
431  	
432  	   /* check if the candidates are fractional and round them if necessary */
433  	   nfracvars = nbinvars + nintvars;
434  	   for( i = 0; i < nfracvars; ++i)
435  	   {
436  	      SCIP_Real value = SCIPgetSolVal(scip, sol, vars[i]);
437  	
438  	      if( SCIPisInfinity(scip, REALABS(value)) )
439  	      {
440  	         *success = FALSE;
441  	         SCIPdebugMsg(scip, "Variable with infinite solution value");
442  	
443  	         return SCIP_OKAY;
444  	      }
445  	      if( !SCIPisFeasIntegral(scip, value) )
446  	      {
447  	         if( roundit )
448  	         {
449  	            SCIP_Real roundedvalue;
450  	
451  	            if( SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) )
452  	            {
453  	               roundedvalue = SCIPceil(scip, value - 1.0);
454  	            }
455  	            else
456  	            {
457  	               roundedvalue = SCIPfloor(scip, value + 1.0);
458  	            }
459  	
460  	            SCIP_CALL( SCIPsetSolVal(scip, sol, vars[i], roundedvalue) );
461  	         }
462  	         else
463  	         {
464  	            *success = FALSE;
465  	            SCIPdebugMsg(scip, "Repair: All variables are integral.\n");
466  	            return SCIP_OKAY;
467  	         }
468  	      }
469  	   }
470  	
471  	   /* ensure that no other variables have infinite LP solution values */
472  	   for( ; i < nvars; ++i )
473  	   {
474  	      if( SCIPisInfinity(scip, REALABS(SCIPgetSolVal(scip, sol, vars[i]))) )
475  	      {
476  	         *success = FALSE;
477  	         SCIPdebugMsg(scip, "Variable with infinite solution value");
478  	
479  	         return SCIP_OKAY;
480  	      }
481  	   }
482  	
483  	   SCIPdebugMsg(scip, "All variables rounded.\n");
484  	   return SCIP_OKAY;
485  	}
486  	
487  	/** creates a new solution for the original problem by copying the solution of the subproblem */
488  	static
489  	SCIP_RETCODE createNewSol(
490  	   SCIP*                 scip,               /**< original SCIP data structure                        */
491  	   SCIP*                 subscip,            /**< SCIP structure of the subproblem                    */
492  	   SCIP_VAR**            subvars,            /**< the variables of the subproblem                     */
493  	   SCIP_HEUR*            heur,               /**< Repair heuristic structure                          */
494  	   SCIP_SOL*             subsol,             /**< solution of the subproblem                          */
495  	   SCIP_Bool*            success             /**< used to store whether new solution was found or not */
496  	   )
497  	{
498  	   SCIP_SOL*  newsol;                        /* solution to be created for the original problem */
499  	
500  	   assert(scip != NULL);
501  	   assert(subscip != NULL);
502  	   assert(subvars != NULL);
503  	   assert(subsol != NULL);
504  	
505  	   SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsol, heur, subvars, &newsol) );
506  	
507  	   /* try to add new solution to SCIP and free it immediately */
508  	   SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
509  	
510  	#ifdef SCIP_STATISTIC
511  	   {
512  	      SCIP_HEURDATA* heurdata;
513  	      heurdata = SCIPheurGetData(heur);
514  	
515  	      if( *success )
516  	      {
517  	         heurdata->originalsolval = SCIPgetSolOrigObj(scip, newsol);
518  	      }
519  	   }
520  	#endif
521  	
522  	   return SCIP_OKAY;
523  	}
524  	
525  	/** tries to fix variables as an approach to repair a solution. */
526  	static
527  	SCIP_RETCODE applyRepair(
528  	   SCIP*                 scip,               /**< SCIP data structure of the problem */
529  	   SCIP_HEUR*            heur,               /**< pointer to this heuristic instance */
530  	   SCIP_RESULT*          result,             /**< pointer to return the result status */
531  	   SCIP_Longint          nnodes              /**< nodelimit for sub-SCIP */
532  	   )
533  	{
534  	   SCIP* subscip = NULL;
535  	   SCIP_VAR** vars = NULL;
536  	   SCIP_VAR** subvars = NULL;
537  	   SCIP_ROW** rows;
538  	   SCIP_CONS** subcons = NULL;
539  	   int* nviolatedrows = NULL;
540  	   int* permutation = NULL;
541  	   int* inftycounter = NULL;
542  	   SCIP_SOL* sol;
543  	   SCIP_SOL* subsol = NULL;
544  	   SCIP_HEURDATA* heurdata;
545  	   SCIP_Real* potential = NULL;
546  	   SCIP_Real* slacks = NULL;
547  	   SCIP_RETCODE retcode = SCIP_OKAY;
548  	   SCIP_Real timelimit;
549  	   SCIP_Real memorylimit;
550  	   SCIP_Real factor;
551  	   char probname[SCIP_MAXSTRLEN];
552  	   int i;
553  	   int nbinvars;
554  	   int nintvars;
555  	   int nvars;
556  	   int nrows;
557  	   int ndiscvars;
558  	   int nfixeddiscvars;
559  	   SCIP_Bool success;
560  	   SCIP_Bool avoidmemout;
561  	
562  	   heurdata = SCIPheurGetData(heur);
563  	   sol = heurdata->infsol;
564  	
565  	   /* initializes the sub-SCIP */
566  	   SCIP_CALL( SCIPcreate(&subscip) );
567  	   SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
568  	   SCIP_CALL( SCIPcopyParamSettings(scip, subscip) );
569  	
570  	   /* use inference branching */
571  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
572  	   {
573  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
574  	   }
575  	
576  	   /* get name of the original problem and add the string "_repairsub" */
577  	   (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_repairsub", SCIPgetProbName(scip));
578  	
579  	   SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
580  	
581  	   /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
582  	   if( heurdata->useslackvars )
583  	   {
584  	      SCIP_CALL( SCIPcreateSol(subscip, &subsol, heur) );
585  	   }
586  	
587  	   /* gets all original variables */
588  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
589  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
590  	   SCIP_CALL( SCIPallocBufferArray(scip, &nviolatedrows, nvars) );
591  	   SCIP_CALL( SCIPallocBufferArray(scip, &permutation, nvars) );
592  	
593  	   SCIPdebugMsg(scip,"\n\n Calling objective factor calculation \n\n");
594  	   if( heurdata->useobjfactor )
595  	   {
596  	      SCIP_CALL( getObjectiveFactor(scip, subscip, &factor, &success) );
597  	   }
598  	   else
599  	   {
600  	      factor = 0.0;
601  	   }
602  	
603  	   /* adds all original variables */
604  	   ndiscvars = 0;
605  	   for( i = 0; i < nvars; ++i )
606  	   {
607  	      SCIP_CONS* cons;
608  	      SCIP_Real lb;
609  	      SCIP_Real ub;
610  	      SCIP_Real lborig;
611  	      SCIP_Real uborig;
612  	      SCIP_Real varslack;
613  	      SCIP_Real objval;
614  	      SCIP_Real value;
615  	      SCIP_VARTYPE vartype;
616  	      char varname[SCIP_MAXSTRLEN];
617  	      char slackvarname[SCIP_MAXSTRLEN];
618  	      char consvarname[SCIP_MAXSTRLEN];
619  	
620  	#ifdef SCIP_STATISTIC
621  	      heurdata->norigvars++;
622  	#endif
623  	
624  	      varslack = 0.0;
625  	      lborig = SCIPvarGetLbGlobal(vars[i]);
626  	      uborig = SCIPvarGetUbGlobal(vars[i]);
627  	      value = SCIPgetSolVal(scip, sol, vars[i]);
628  	      vartype = SCIPvarGetType(vars[i]);
629  	
630  	      nviolatedrows[i] = 0;
631  	
632  	      /* if the value of x is lower than the variables lower bound, sets the slack to a correcting value */
633  	      if( heurdata->useslackvars && SCIPisFeasLT(scip, value, lborig) )
634  	      {
635  	         lb = value;
636  	         varslack = lborig - value;
637  	      }
638  	      else
639  	      {
640  	         lb = lborig;
641  	      }
642  	
643  	      /* if the value of x is bigger than the variables upper bound, sets the slack to a correcting value */
644  	      if( heurdata->useslackvars && SCIPisFeasGT(scip, value, uborig) )
645  	      {
646  	         ub = value;
647  	         varslack = uborig - value;
648  	      }
649  	      else
650  	      {
651  	         ub = uborig;
652  	      }
653  	
654  	      if( heurdata->useobjfactor )
655  	      {
656  	         objval = SCIPvarGetObj(vars[i])*factor;
657  	
658  	         if( SCIPisZero(scip, objval) )
659  	         {
660  	            objval = 0.0;
661  	         }
662  	      }
663  	      else
664  	      {
665  	         objval = SCIPvarGetObj(vars[i]);
666  	      }
667  	
668  	      /* if a binary variable is out of bound, generalize it to an integer variable */
669  	      if( !SCIPisFeasZero(scip, varslack) && SCIP_VARTYPE_BINARY == vartype )
670  	      {
671  	         vartype = SCIP_VARTYPE_INTEGER;
672  	      }
673  	
674  	      (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "sub_%s", SCIPvarGetName(vars[i]));
675  	
676  	      /* Adds the sub representing variable to the sub-SCIP. */
677  	      SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[i], varname, lb, ub, objval, vartype) );
678  	      SCIP_CALL( SCIPaddVar(subscip, subvars[i]) );
679  	
680  	      /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
681  	      if( heurdata->useslackvars )
682  	      {
683  	         SCIP_CALL( SCIPsetSolVal(subscip, subsol, subvars[i], value) );
684  	      }
685  	
686  	      /* if necessary adds a constraint to represent the original bounds of x.*/
687  	      if( !SCIPisFeasEQ(scip, varslack, 0.0) )
688  	      {
689  	         SCIP_VAR* newvar;
690  	         (void) SCIPsnprintf(slackvarname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIPvarGetName(vars[i]));
691  	         (void) SCIPsnprintf(consvarname, SCIP_MAXSTRLEN, "boundcons_%s", SCIPvarGetName(vars[i]));
692  	
693  	         /* initialize and add an artificial slack variable */
694  	         if( heurdata->useobjfactor )
695  	         {
696  	            SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS));
697  	         }
698  	         else
699  	         {
700  	            SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY));
701  	         }
702  	         SCIP_CALL( SCIPaddVar(subscip, newvar) );
703  	
704  	         /* set the value of the slack variable to 1 to punish the use of it.
705  	          * note that a trivial feasible solution can be only constructed if violations are modeled with slack variables
706  	          */
707  	         if( heurdata->useslackvars )
708  	         {
709  	            SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) );
710  	         }
711  	
712  	         /* adds a linear constraint to represent the old bounds */
713  	         SCIP_CALL( SCIPcreateConsBasicVarbound(subscip, &cons, consvarname, subvars[i], newvar, varslack, lb, ub) );
714  	         SCIP_CALL( SCIPaddCons(subscip, cons) );
715  	         SCIP_CALL( SCIPreleaseVar(subscip, &newvar) );
716  	         SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
717  	
718  	         /* increases the counter for violated vars */
719  	#ifdef SCIP_STATISTIC
720  	         heurdata->nviolatedvars++;
721  	#endif
722  	      }
723  	
724  	#ifdef SCIP_STATISTIC
725  	      if( SCIPisFeasLT(scip, value, lb) || SCIPisFeasGT(scip, value, ub) )
726  	      {
727  	         heurdata->nviolatedvars++;
728  	      }
729  	#endif
730  	      if( SCIP_VARTYPE_BINARY == vartype || SCIP_VARTYPE_INTEGER == vartype )
731  	      {
732  	         ndiscvars++;
733  	      }
734  	   }
735  	
736  	   /* check solution for feasibility regarding the LP rows (SCIPgetRowSolActivity()) */
737  	   rows = SCIPgetLPRows(scip);
738  	   nrows = SCIPgetNLPRows(scip);
739  	
740  	   SCIP_CALL( SCIPallocBufferArray(scip, &potential, nrows) );
741  	   SCIP_CALL( SCIPallocBufferArray(scip, &slacks, nrows) );
742  	   SCIP_CALL( SCIPallocBufferArray(scip, &subcons, nrows) );
743  	   SCIP_CALL( SCIPallocBufferArray(scip, &inftycounter, nrows) );
744  	
745  	   /* Adds all original constraints and computes potentials and slacks */
746  	   for (i = 0; i < nrows; ++i)
747  	   {
748  	      SCIP_COL** cols;
749  	      SCIP_VAR** consvars;
750  	      SCIP_Real* vals;
751  	      SCIP_Real constant;
752  	      SCIP_Real lhs;
753  	      SCIP_Real rhs;
754  	      SCIP_Real rowsolact;
755  	      int nnonz;
756  	      int j;
757  	
758  	#ifdef SCIP_STATISTIC
759  	      heurdata->norcons++;
760  	#endif
761  	
762  	      /* gets the values to check the constraint */
763  	      constant = SCIProwGetConstant(rows[i]);
764  	      lhs = SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ? SCIProwGetLhs(rows[i]) : SCIProwGetLhs(rows[i]) - constant;
765  	      rhs = SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ? SCIProwGetRhs(rows[i]) : SCIProwGetRhs(rows[i]) - constant;
766  	      rowsolact = SCIPgetRowSolActivity(scip, rows[i], sol) - constant;
767  	      vals = SCIProwGetVals(rows[i]);
768  	      potential[i] = 0.0;
769  	      inftycounter[i] = 0;
770  	
771  	      assert(SCIPisFeasLE(scip, lhs, rhs));
772  	
773  	      nnonz = SCIProwGetNNonz(rows[i]);
774  	      cols = SCIProwGetCols(rows[i]);
775  	      SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
776  	
777  	      /* sets the slack if its necessary */
778  	      if( SCIPisFeasLT(scip, rowsolact, lhs) )
779  	      {
780  	         slacks[i] = lhs - rowsolact;
781  	#ifdef SCIP_STATISTIC
782  	         heurdata->nviolatedcons++;
783  	#endif
784  	      }
785  	      else if( SCIPisFeasGT(scip, rowsolact, rhs) )
786  	      {
787  	         slacks[i] = rhs - rowsolact;
788  	#ifdef SCIP_STATISTIC
789  	         heurdata->nviolatedcons++;
790  	#endif
791  	      }
792  	      else
793  	      {
794  	         slacks[i] = 0.0;
795  	      }
796  	
797  	      /* translate all variables from the original SCIP to the sub-SCIP with sub-SCIP variables. */
798  	      for( j = 0; j < nnonz; ++j )
799  	      {
800  	         SCIP_Real contribution;
801  	         int pos;
802  	         int sgn = 1;
803  	
804  	         /* negative slack represents a right hand side violation */
805  	         if( SCIPisFeasGT(scip, 0.0, slacks[i]) )
806  	         {
807  	            assert(!SCIPisInfinity(scip, rhs));
808  	            sgn = -1;
809  	         }
810  	      #ifndef NDEBUG
811  	         else
812  	            assert(!SCIPisInfinity(scip, lhs));
813  	      #endif
814  	
815  	         pos = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
816  	         consvars[j] = subvars[pos];
817  	         assert(pos >= 0);
818  	
819  	         /* compute potentials */
820  	         contribution = getPotentialContributed(scip, sol, vars[pos], vals[j], sgn);
821  	         if( !SCIPisInfinity(scip, REALABS(contribution)) )
822  	         {
823  	            potential[i] += contribution;
824  	         }
825  	         else
826  	         {
827  	            inftycounter[i]++;
828  	         }
829  	
830  	         if( !SCIPisZero(scip, slacks[i]) )
831  	         {
832  	            nviolatedrows[pos]++;
833  	         }
834  	      }
835  	
836  	      /* create a new linear constraint, representing the old one */
837  	      SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &subcons[i], SCIProwGetName(rows[i]),
838  	               nnonz, consvars, vals, lhs, rhs) );
839  	
840  	      if( heurdata->useslackvars )
841  	      {
842  	         SCIP_VAR* newvar;
843  	         char varname[SCIP_MAXSTRLEN];
844  	
845  	         /*if necessary adds a new artificial slack variable*/
846  	         if( !SCIPisFeasEQ(subscip, slacks[i], 0.0) )
847  	         {
848  	            (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIProwGetName(rows[i]));
849  	            SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, varname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS) );
850  	            SCIP_CALL( SCIPaddVar(subscip, newvar) );
851  	
852  	            /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
853  	            SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) );
854  	            SCIP_CALL( SCIPaddCoefLinear(subscip, subcons[i], newvar, slacks[i]) );
855  	            SCIP_CALL( SCIPreleaseVar(subscip, &newvar) );
856  	         }
857  	      }
858  	
859  	      /*Adds the Constraint and release it.*/
860  	      SCIP_CALL( SCIPaddCons(subscip, subcons[i]) );
861  	      SCIP_CALL( SCIPreleaseCons(subscip, &subcons[i]) );
862  	      SCIPfreeBufferArray(subscip, &consvars);
863  	   }
864  	
865  	   if( heurdata->usevarfix )
866  	   {
867  	      /* get the greedy order */
868  	      for( i = 0; i < nvars; ++i )
869  	      {
870  	         permutation[i] = i;
871  	      }
872  	      SCIPsortIntInt(nviolatedrows, permutation, nvars);
873  	
874  	      /* loops over variables and greedily fix variables, but preserve the cover property that enough slack is given to
875  	       * violated rows
876  	       */
877  	      nfixeddiscvars = 0;
878  	      heurdata->nvarfixed = 0;
879  	      for( i = 0; i < nvars; ++i )
880  	      {
881  	         SCIP_Bool fixed;
882  	
883  	         /* continue if we have a loose variable */
884  	         if( SCIPvarGetStatus(vars[permutation[i]]) != SCIP_VARSTATUS_COLUMN )
885  	            continue;
886  	
887  	         SCIP_CALL( tryFixVar(scip, subscip, sol, potential, slacks, vars[permutation[i]], subvars[permutation[i]], inftycounter, heurdata, &fixed) );
888  	
889  	         if( fixed && (SCIP_VARTYPE_BINARY == SCIPvarGetType(subvars[permutation[i]])
890  	            || SCIP_VARTYPE_INTEGER == SCIPvarGetType(subvars[permutation[i]])) )
891  	         {
892  	            nfixeddiscvars++;
893  	         }
894  	       }
895  	      SCIPdebugMsg(scip,"fixings finished\n\n");
896  	      if( heurdata->minfixingrate > ((SCIP_Real)nfixeddiscvars/MAX((SCIP_Real)ndiscvars,1.0)) )
897  	      {
898  	         goto TERMINATE;
899  	      }
900  	   }
901  	
902  	   /* a trivial feasible solution can be constructed if violations are modeled with slack variables */
903  	   if( heurdata->useslackvars )
904  	   {
905  	      SCIP_CALL( SCIPaddSolFree(subscip, &subsol, &success) );
906  	
907  	      if( !success )
908  	      {
909  	         SCIPdebugMsg(scip, "Initial repair solution was not accepted.\n");
910  	      }
911  	   }
912  	
913  	#ifdef SCIP_STATISTIC
914  	   if( heurdata->useslackvars )
915  	      heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, subsol);
916  	#endif
917  	
918  	   /* check whether there is enough time and memory left */
919  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
920  	   if( !SCIPisInfinity(scip, timelimit) )
921  	      timelimit -= SCIPgetSolvingTime(scip);
922  	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
923  	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
924  	
925  	   /* subtract the memory already used by the main SCIP and the estimated memory usage of external software */
926  	   if( !SCIPisInfinity(scip, memorylimit) )
927  	   {
928  	      memorylimit -= SCIPgetMemUsed(scip) / 1048576.0;
929  	      memorylimit -= SCIPgetMemExternEstim(scip) / 1048576.0;
930  	   }
931  	
932  	   /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE)
933  	    * to create a copy of SCIP, including external memory usage */
934  	   if( timelimit <= 0.0 || (avoidmemout && memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0) )
935  	      goto TERMINATE;
936  	
937  	   /* set limits for the subproblem */
938  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
939  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
940  	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
941  	   SCIP_CALL( SCIPsetObjlimit(subscip,1.0) );
942  	
943  	   /* forbid recursive call of heuristics and separators solving sub-SCIPs */
944  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
945  	
946  	   /* disable output to console */
947  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
948  	
949  	#ifdef SCIP_DEBUG
950  	   /* for debugging Repair, enable MIP output */
951  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_FULL) );
952  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
953  	#endif
954  	
955  	   /* solve the subproblem */
956  	   retcode = SCIPsolve(subscip);
957  	
958  	   /* errors in sub-SCIPs should not kill the overall solving process. Hence, we print a warning message. Only
959  	    * in debug mode, SCIP will stop
960  	    */
961  	   if( retcode != SCIP_OKAY )
962  	   {
963  	      SCIPwarningMessage(scip, "Error while solving subproblem in REPAIR heuristic; sub-SCIP terminated with code <%d>\n", retcode);
964  	      SCIPABORT();  /*lint --e{527}*/
965  	      goto TERMINATE;
966  	   }
967  	
968  	   success = FALSE;
969  	
970  	   /* if a solution is found, save its value and create a new solution instance for the original SCIP */
971  	   if( SCIPgetBestSol(subscip) != NULL )
972  	   {
973  	#ifdef SCIP_STATISTIC
974  	      heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip));
975  	#endif
976  	      /* print solving statistics of subproblem if we are in SCIP's debug mode */
977  	      SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
978  	
979  	      assert(SCIPgetNSols(subscip) > 0);
980  	      SCIP_CALL( createNewSol(scip, subscip, subvars, heur, SCIPgetBestSol(subscip), &success) );
981  	
982  	      if( success )
983  	      {
984  	         *result = SCIP_FOUNDSOL;
985  	      }
986  	   }
987  	   else
988  	   {
989  	      SCIPdebugMsg(scip,"No solution found!\n");
990  	   }
991  	
992  	   if( SCIPgetStage(subscip) >= SCIP_STAGE_SOLVED )
993  	   {
994  	      heurdata->subiters = SCIPgetNLPIterations(subscip);
995  	      heurdata->subnodes = SCIPgetNTotalNodes(subscip);
996  	#ifdef SCIP_STATISTIC
997  	      heurdata->subpresoltime = SCIPgetPresolvingTime(subscip);
998  	#endif
999  	      heurdata->runs = SCIPgetNRuns(subscip);
1000 	   }
1001 	
1002 	   /* terminates the solving process  */
1003 	TERMINATE:
1004 	   if( NULL != sol )
1005 	   {
1006 	      SCIP_CALL( SCIPfreeSol(scip, &sol) );
1007 	   }
1008 	   SCIPfreeBufferArrayNull(scip, &nviolatedrows);
1009 	   for( i = 0; i < nvars; ++i )
1010 	   {
1011 	      SCIP_CALL( SCIPreleaseVar(subscip, &subvars[i]) );
1012 	   }
1013 	   SCIPfreeBufferArrayNull(scip, &inftycounter);
1014 	   SCIPfreeBufferArrayNull(scip, &subcons);
1015 	   SCIPfreeBufferArrayNull(scip, &slacks);
1016 	   SCIPfreeBufferArrayNull(scip, &potential);
1017 	   SCIPfreeBufferArrayNull(scip, &permutation);
1018 	   SCIPfreeBufferArrayNull(scip, &subvars);
1019 	
1020 	   if( NULL != subsol )
1021 	   {
1022 	      SCIP_CALL( SCIPfreeSol(subscip, &subsol) );
1023 	   }
1024 	
1025 	   SCIP_CALL( SCIPfree(&subscip) );
1026 	
1027 	   SCIPdebugMsg(scip, "repair finished\n");
1028 	   return SCIP_OKAY;
1029 	}
1030 	
1031 	
1032 	/*
1033 	 * Callback methods of primal heuristic
1034 	 */
1035 	
1036 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1037 	static
1038 	SCIP_DECL_HEURFREE(heurFreeRepair)
1039 	{  /*lint --e{715}*/
1040 	   SCIP_HEURDATA* heurdata;
1041 	
1042 	   heurdata = SCIPheurGetData(heur);
1043 	
1044 	   assert(heurdata != NULL);
1045 	   SCIPfreeMemory(scip, &heurdata);
1046 	
1047 	   SCIPheurSetData(heur, NULL);
1048 	
1049 	   return SCIP_OKAY;
1050 	}
1051 	
1052 	
1053 	/** initialization method of primal heuristic (called after problem was transformed) */
1054 	static
1055 	SCIP_DECL_HEURINIT(heurInitRepair)
1056 	{  /*lint --e{715}*/
1057 	   SCIP_HEURDATA* heurdata;
1058 	
1059 	   heurdata = SCIPheurGetData(heur);
1060 	
1061 	   heurdata->subiters = -1;
1062 	   heurdata->subnodes = -1;
1063 	   heurdata->runs = 0;
1064 	
1065 	   heurdata->nvarfixed = 0;
1066 	   heurdata->relvarfixed = -1;
1067 	
1068 	#ifdef SCIP_STATISTIC
1069 	   heurdata->subpresoltime = 0;
1070 	
1071 	   heurdata->nviolatedvars = 0;
1072 	   heurdata->norigvars = 0;
1073 	   heurdata->relviolatedvars = 0;
1074 	   heurdata->nviolatedcons = 0;
1075 	   heurdata->norcons = 0;
1076 	   heurdata->relviolatedcons = 0;
1077 	
1078 	   heurdata->originalsolval = SCIP_INVALID;
1079 	
1080 	   heurdata->improvedoldsol = SCIP_UNKNOWN;
1081 	#endif
1082 	
1083 	   heurdata->usednodes = 0;
1084 	
1085 	   return SCIP_OKAY;
1086 	}
1087 	
1088 	
1089 	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
1090 	static
1091 	SCIP_DECL_HEUREXIT(heurExitRepair)
1092 	{  /*lint --e{715}*/
1093 	#ifdef SCIP_STATISTIC
1094 	   SCIP_HEURDATA* heurdata;
1095 	   SCIP_Real time;
1096 	   SCIP_Real relvars;
1097 	   SCIP_Real relcons;
1098 	   SCIP_Real relfixed;
1099 	   char solval[SCIP_MAXSTRLEN];
1100 	   int violateds;
1101 	   int ninvars;
1102 	   int ninvcons;
1103 	   int nvars;
1104 	   int ncons;
1105 	   int iterations;
1106 	   int nodes;
1107 	   int runs;
1108 	
1109 	   heurdata = SCIPheurGetData(heur);
1110 	   violateds = heurdata->nviolatedvars+heurdata->nviolatedcons;
1111 	   ninvars = heurdata->nviolatedvars;
1112 	   ninvcons = heurdata->nviolatedcons;
1113 	   nvars = heurdata->norigvars;
1114 	   ncons = heurdata->norcons;
1115 	   iterations = heurdata->subiters;
1116 	   nodes = heurdata->subnodes;
1117 	   time = heurdata->subpresoltime;
1118 	   runs = heurdata->runs;
1119 	
1120 	   if( SCIP_INVALID == heurdata->originalsolval )
1121 	   {
1122 	      (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN ,"--");
1123 	   }
1124 	   else
1125 	   {
1126 	      (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN, "%15.9g", heurdata->originalsolval);
1127 	   }
1128 	
1129 	   heurdata->relviolatedvars = MAX((SCIP_Real)heurdata->norigvars, 1.0);
1130 	   heurdata->relviolatedvars = heurdata->nviolatedvars/heurdata->relviolatedvars;
1131 	   heurdata->relviolatedcons = MAX((SCIP_Real)heurdata->norcons, 1.0);
1132 	   heurdata->relviolatedcons = heurdata->nviolatedcons/heurdata->relviolatedcons;
1133 	
1134 	   heurdata->relvarfixed = MAX((SCIP_Real)heurdata->norigvars, 1.0);
1135 	   heurdata->relvarfixed = heurdata->nvarfixed/heurdata->relvarfixed;
1136 	   relvars = heurdata->relviolatedvars;
1137 	   relcons = heurdata->relviolatedcons;
1138 	   relfixed = heurdata->relvarfixed;
1139 	
1140 	   /* prints all statistic data for a user*/
1141 	   SCIPstatistic(
1142 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "<repair> \n total violations             : %10d\n", violateds);
1143 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated variables           : %10d\n", ninvars);
1144 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total variables              : %10d\n", nvars);
1145 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated variables  : %10.2f%%\n", 100 * relvars);
1146 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated constraints         : %10d\n", ninvcons);
1147 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total constraints            : %10d\n", ncons);
1148 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated constraints: %10.2f%%\n", 100* relcons);
1149 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " fixed variables              : %10d\n", heurdata->nvarfixed);
1150 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative fixed variables     : %10.2f%%\n\n", 100* relfixed);
1151 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " iterations                   : %10d\n", iterations);
1152 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " nodes                        : %10d\n", nodes);
1153 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " number of runs               : %10d\n", runs);
1154 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " presolve time                : %10.2f\n", time);
1155 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "</repair>\n\n");
1156 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " value of best solution       : %10g\n", solval);
1157 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " improved orig. solval        : %10g\n", heurdata->improvedoldsol);
1158 	   )
1159 	
1160 	#endif
1161 	   return SCIP_OKAY;
1162 	}
1163 	
1164 	/** execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound. */
1165 	static
1166 	SCIP_DECL_HEUREXEC(heurExecRepair)
1167 	{ /*lint --e{715}*/
1168 	   SCIP_HEURDATA* heurdata;
1169 	   SCIP_RETCODE retcode;
1170 	   SCIP_Bool success;
1171 	   SCIP_Bool error;
1172 	   SCIP_Longint nnodes;
1173 	
1174 	   heurdata = SCIPheurGetData(heur);
1175 	   SCIPdebugMsg(scip, "%s\n", heurdata->filename);
1176 	
1177 	   /* checks the result pointer */
1178 	   assert(result != NULL);
1179 	   *result = SCIP_DIDNOTRUN;
1180 	
1181 	   /* if repair already ran or neither variable fixing nor slack variables are enabled, stop */
1182 	   if( 0 < SCIPheurGetNCalls(heur) || !(heurdata->usevarfix || heurdata->useslackvars) )
1183 	      return SCIP_OKAY;
1184 	
1185 	   /* do not run if the neither the LP is constructed nor a user given solution exists */
1186 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 )
1187 	      return SCIP_OKAY;
1188 	
1189 	   /* calculate the maximal number of branching nodes until heuristic is aborted */
1190 	   nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1191 	
1192 	   /* reward REPAIR if it succeeded often */
1193 	   nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
1194 	   nnodes -= (SCIP_Longint)(100.0 * SCIPheurGetNCalls(heur));  /* count the setup costs for the sub-MIP as 100 nodes */
1195 	   nnodes += heurdata->nodesofs;
1196 	
1197 	   /* determine the node limit for the current process */
1198 	   nnodes -= heurdata->usednodes;
1199 	   nnodes = MIN(nnodes, heurdata->maxnodes);
1200 	
1201 	   /* check whether we have enough nodes left to call subproblem solving */
1202 	   if( nnodes < heurdata->minnodes )
1203 	      return SCIP_OKAY;
1204 	
1205 	   if( !SCIPhasCurrentNodeLP(scip) )
1206 	      return SCIP_OKAY;
1207 	
1208 	   if( !SCIPisLPConstructed(scip) )
1209 	   {
1210 	      SCIP_Bool cutoff;
1211 	
1212 	      SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
1213 	
1214 	      /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
1215 	      if( cutoff )
1216 	      {
1217 	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
1218 	         return SCIP_OKAY;
1219 	      }
1220 	   }
1221 	
1222 	   /* create original solution */
1223 	   SCIP_CALL( SCIPcreateOrigSol(scip, &(heurdata->infsol), heur) );
1224 	
1225 	   /* use read method to enter solution from a file */
1226 	   if( strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 )
1227 	   {
1228 	      retcode = SCIPlinkLPSol(scip, heurdata->infsol);
1229 	   }
1230 	   else
1231 	   {
1232 	      error = FALSE;
1233 	      retcode = SCIPreadSolFile(scip, heurdata->filename, heurdata->infsol, FALSE, NULL, &error);
1234 	   }
1235 	
1236 	   if( SCIP_NOFILE == retcode )
1237 	   {
1238 	      assert(strcmp(heurdata->filename, DEFAULT_FILENAME) != 0);
1239 	      SCIPwarningMessage(scip, "cannot open file <%s> for reading\n", heurdata->filename);
1240 	
1241 	      SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1242 	      return SCIP_OKAY;
1243 	   }
1244 	   else if( retcode != SCIP_OKAY )
1245 	   {
1246 	      SCIPwarningMessage(scip, "cannot run repair, unknown return status <%d>\n", retcode);
1247 	      SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1248 	      return SCIP_OKAY;
1249 	   }
1250 	   SCIPdebugMsg(scip, "Repair: Solution file read.\n");
1251 	
1252 	   /* checks the integrality of all discrete variable */
1253 	   SCIP_CALL( checkCands(scip, heurdata->infsol, heurdata->roundit, &success) );
1254 	   if( !success )
1255 	   {
1256 	      SCIPdebugMsg(scip,"Given solution is not integral, repair terminates.\n");
1257 	      SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1258 	      return SCIP_OKAY;
1259 	   }
1260 	
1261 	   *result = SCIP_DIDNOTFIND;
1262 	
1263 	   SCIP_CALL( SCIPtrySol(scip, heurdata->infsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1264 	
1265 	   /* the solution is not feasible for the original problem; we will try to repair it */
1266 	   if( !success )
1267 	   {
1268 	      assert(NULL != heurdata->infsol);
1269 	      assert(heurdata->usevarfix || heurdata->useslackvars);
1270 	      SCIP_CALL( applyRepair(scip, heur, result, nnodes) );
1271 	   }
1272 	   else
1273 	   {
1274 	      SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) );
1275 	   }
1276 	
1277 	   return SCIP_OKAY;
1278 	}
1279 	
1280 	/* primal heuristic specific interface methods */
1281 	
1282 	/** creates the repair primal heuristic and includes it in SCIP */
1283 	SCIP_RETCODE SCIPincludeHeurRepair(
1284 	   SCIP*                 scip                /**< SCIP data structure */
1285 	   )
1286 	{
1287 	   SCIP_HEURDATA* heurdata;
1288 	   SCIP_HEUR* heur;
1289 	
1290 	   /* create repair primal heuristic data */
1291 	   heurdata = NULL;
1292 	
1293 	   SCIP_CALL( SCIPallocMemory(scip ,&heurdata) );
1294 	
1295 	   heur = NULL;
1296 	
1297 	   /* include primal heuristic */
1298 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1299 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1300 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRepair, heurdata) );
1301 	
1302 	   assert(heur != NULL);
1303 	   assert(heurdata != NULL);
1304 	
1305 	   /* set non fundamental callbacks via setter functions */
1306 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRepair) );
1307 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRepair) );
1308 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRepair) );
1309 	
1310 	   /* add repair primal heuristic parameters */
1311 	
1312 	   heurdata->filename = NULL;
1313 	   /* add string parameter for filename containing a solution */
1314 	   SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/filename",
1315 	         "file name of a solution to be used as infeasible starting point, [-] if not available",
1316 	         &heurdata->filename, FALSE, DEFAULT_FILENAME, NULL, NULL) );
1317 	
1318 	   /* add bool parameter for decision how to deal with unfractional cands */
1319 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/roundit",
1320 	         "True : fractional variables which are not fractional in the given solution are rounded, "
1321 	         "FALSE : solving process of this heuristic is stopped. ",
1322 	         &heurdata->roundit, FALSE, DEFAULT_ROUNDIT, NULL, NULL));
1323 	
1324 	   /* add bool parameter for decision how the objective function should be */
1325 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useobjfactor",
1326 	         "should a scaled objective function for original variables be used in repair subproblem?",
1327 	         &heurdata->useobjfactor, FALSE, DEFAULT_USEOBJFACTOR, NULL, NULL));
1328 	
1329 	   /* add bool parameter for decision if variable fixings should be used */
1330 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarfix",
1331 	         "should variable fixings be used in repair subproblem?",
1332 	         &heurdata->usevarfix, FALSE, DEFAULT_USEVARFIX, NULL, NULL));
1333 	
1334 	   /* add bool parameter for decision how the objective function should be */
1335 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useslackvars",
1336 	         "should slack variables be used in repair subproblem?",
1337 	         &heurdata->useslackvars, FALSE, DEFAULT_USESLACKVARS, NULL, NULL));
1338 	
1339 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha", "factor for the potential of var fixings",
1340 	         &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.00, NULL, NULL) );
1341 	
1342 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1343 	         "number of nodes added to the contingent of the total nodes",
1344 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
1345 	
1346 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1347 	         "maximum number of nodes to regard in the subproblem",
1348 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
1349 	
1350 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1351 	         "minimum number of nodes required to start the subproblem",
1352 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
1353 	
1354 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1355 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1356 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1357 	
1358 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
1359 	         "minimum percentage of integer variables that have to be fixed",
1360 	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1361 	
1362 	   return SCIP_OKAY;
1363 	}
1364