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_intshifting.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variables, and
28   	 *         solves a final LP to calculate feasible values for continuous variables
29   	 * @author Tobias Achterberg
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/heur_intshifting.h"
36   	#include "scip/pub_heur.h"
37   	#include "scip/pub_lp.h"
38   	#include "scip/pub_message.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/pub_var.h"
41   	#include "scip/scip_branch.h"
42   	#include "scip/scip_general.h"
43   	#include "scip/scip_heur.h"
44   	#include "scip/scip_lp.h"
45   	#include "scip/scip_mem.h"
46   	#include "scip/scip_message.h"
47   	#include "scip/scip_numerics.h"
48   	#include "scip/scip_prob.h"
49   	#include "scip/scip_randnumgen.h"
50   	#include "scip/scip_sol.h"
51   	#include "scip/scip_solvingstats.h"
52   	#include <string.h>
53   	
54   	#define HEUR_NAME             "intshifting"
55   	#define HEUR_DESC             "LP rounding heuristic with infeasibility recovering and final LP solving"
56   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_ROUNDING
57   	#define HEUR_PRIORITY         -10000
58   	#define HEUR_FREQ             10
59   	#define HEUR_FREQOFS          0
60   	#define HEUR_MAXDEPTH         -1
61   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
62   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
63   	
64   	#define MAXSHIFTINGS          50        /**< maximal number of non improving shiftings */
65   	#define WEIGHTFACTOR          1.1
66   	#define DEFAULT_RANDSEED      17
67   	
68   	/* locally defined heuristic data */
69   	struct SCIP_HeurData
70   	{
71   	   SCIP_SOL*             sol;                /**< working solution */
72   	   SCIP_Longint          lastlp;             /**< last LP number where the heuristic was applied */
73   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
74   	};
75   	
76   	
77   	/*
78   	 * local methods
79   	 */
80   	
81   	/** update row violation arrays after a row's activity value changed */
82   	static
83   	void updateViolations(
84   	   SCIP*                 scip,               /**< SCIP data structure */
85   	   SCIP_ROW*             row,                /**< LP row */
86   	   SCIP_ROW**            violrows,           /**< array with currently violated rows */
87   	   int*                  violrowpos,         /**< position of LP rows in violrows array */
88   	   int*                  nviolrows,          /**< pointer to the number of currently violated rows */
89   	   int*                  nviolfracrows,      /**< pointer to the number of violated rows with fractional candidates */
90   	   int*                  nfracsinrow,        /**< array with number of fractional variables for every row */
91   	   SCIP_Real             oldminactivity,     /**< old minimal activity value of LP row */
92   	   SCIP_Real             oldmaxactivity,     /**< old maximal activity value of LP row */
93   	   SCIP_Real             newminactivity,     /**< new minimal activity value of LP row */
94   	   SCIP_Real             newmaxactivity      /**< new maximal activity value of LP row */
95   	   )
96   	{
97   	   SCIP_Real lhs;
98   	   SCIP_Real rhs;
99   	   SCIP_Bool oldviol;
100  	   SCIP_Bool newviol;
101  	
102  	   assert(violrows != NULL);
103  	   assert(violrowpos != NULL);
104  	   assert(nviolrows != NULL);
105  	
106  	   lhs = SCIProwGetLhs(row);
107  	   rhs = SCIProwGetRhs(row);
108  	
109  	   /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */
110  	   if( ! (SCIPisInfinity(scip, oldmaxactivity) || SCIPisInfinity(scip, -oldmaxactivity)
111  	       || SCIPisInfinity(scip, oldminactivity) || SCIPisInfinity(scip, -oldminactivity)) )
112  	   {
113  	      oldviol = (SCIPisFeasLT(scip, oldmaxactivity, lhs) || SCIPisFeasGT(scip, oldminactivity, rhs));
114  	   }
115  	   else
116  	   {
117  	      oldviol = (SCIPisInfinity(scip, -oldmaxactivity) && !SCIPisInfinity(scip, -lhs)) ||
118  	         (SCIPisInfinity(scip, oldminactivity) && !SCIPisInfinity(scip, rhs));
119  	   }
120  	
121  	   /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */
122  	   if( ! (SCIPisInfinity(scip, newmaxactivity) || SCIPisInfinity(scip, -newmaxactivity)
123  	       || SCIPisInfinity(scip, newminactivity) || SCIPisInfinity(scip, -newminactivity)) )
124  	   {
125  	      newviol = (SCIPisFeasLT(scip, newmaxactivity, lhs) || SCIPisFeasGT(scip, newminactivity, rhs));
126  	   }
127  	   else
128  	   {
129  	      newviol = (SCIPisInfinity(scip, -newmaxactivity) && !SCIPisInfinity(scip, -lhs)) ||
130  	         (SCIPisInfinity(scip, newminactivity) && !SCIPisInfinity(scip, rhs));
131  	   }
132  	
133  	   if( oldviol != newviol )
134  	   {
135  	      int rowpos;
136  	      int violpos;
137  	
138  	      rowpos = SCIProwGetLPPos(row);
139  	      assert(rowpos >= 0);
140  	
141  	      if( oldviol )
142  	      {
143  	         /* the row violation was repaired: remove row from violrows array, decrease violation count */
144  	         violpos = violrowpos[rowpos];
145  	         assert(0 <= violpos && violpos < *nviolrows);
146  	         assert(violrows[violpos] == row);
147  	         violrowpos[rowpos] = -1;
148  	         /* first, move the row to the end of the subset of violated rows with fractional variables */
149  	         if( nfracsinrow[rowpos] > 0 )
150  	         {
151  	            violrows[violpos] = violrows[*nviolrows-1];
152  	            assert(violpos < *nviolfracrows);
153  	
154  	            /* replace with last violated row containing fractional variables */
155  	            if( violpos != *nviolfracrows - 1 )
156  	            {
157  	               violrows[violpos] = violrows[*nviolfracrows - 1];
158  	               violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
159  	               violpos = *nviolfracrows - 1;
160  	            }
161  	            (*nviolfracrows)--;
162  	         }
163  	
164  	         assert(violpos >= *nviolfracrows);
165  	
166  	         /* swap row at the end of the violated array to the position of this row and decrease the counter */
167  	         if( violpos != *nviolrows - 1 )
168  	         {
169  	            violrows[violpos] = violrows[*nviolrows - 1];
170  	            violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
171  	         }
172  	         (*nviolrows)--;
173  	      }
174  	      else
175  	      {
176  	         /* the row is now violated: add row to violrows array, increase violation count */
177  	         assert(violrowpos[rowpos] == -1);
178  	         violrows[*nviolrows] = row;
179  	         violrowpos[rowpos] = *nviolrows;
180  	         (*nviolrows)++;
181  	
182  	         /* if the row contains fractional variables, swap with the last violated row that has no fractional variables
183  	          * at position *nviolfracrows
184  	          */
185  	         if( nfracsinrow[rowpos] > 0 )
186  	         {
187  	            if( *nviolfracrows < *nviolrows - 1 )
188  	            {
189  	               assert(nfracsinrow[SCIProwGetLPPos(violrows[*nviolfracrows])] == 0);
190  	
191  	               violrows[*nviolrows - 1] = violrows[*nviolfracrows];
192  	               violrowpos[SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1;
193  	
194  	               violrows[*nviolfracrows] = row;
195  	               violrowpos[rowpos] = *nviolfracrows;
196  	            }
197  	            (*nviolfracrows)++;
198  	         }
199  	      }
200  	   }
201  	}
202  	
203  	/** update row activities after a variable's solution value changed */
204  	static
205  	SCIP_RETCODE updateActivities(
206  	   SCIP*                 scip,               /**< SCIP data structure */
207  	   SCIP_Real*            minactivities,      /**< LP row minimal activities */
208  	   SCIP_Real*            maxactivities,      /**< LP row maximal activities */
209  	   SCIP_ROW**            violrows,           /**< array with currently violated rows */
210  	   int*                  violrowpos,         /**< position of LP rows in violrows array */
211  	   int*                  nviolrows,          /**< pointer to the number of currently violated rows */
212  	   int*                  nviolfracrows,      /**< pointer to the number of violated rows with fractional candidates */
213  	   int*                  nfracsinrow,        /**< array with number of fractional variables for every row */
214  	   int                   nlprows,            /**< number of rows in current LP */
215  	   SCIP_VAR*             var,                /**< variable that has been changed */
216  	   SCIP_Real             oldsolval,          /**< old solution value of variable */
217  	   SCIP_Real             newsolval           /**< new solution value of variable */
218  	   )
219  	{
220  	   SCIP_COL* col;
221  	   SCIP_ROW** colrows;
222  	   SCIP_Real* colvals;
223  	   SCIP_Real delta;
224  	   int ncolrows;
225  	   int r;
226  	
227  	   assert(minactivities != NULL);
228  	   assert(maxactivities != NULL);
229  	   assert(nviolrows != NULL);
230  	   assert(0 <= *nviolrows && *nviolrows <= nlprows);
231  	   assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
232  	
233  	   delta = newsolval - oldsolval;
234  	   col = SCIPvarGetCol(var);
235  	   colrows = SCIPcolGetRows(col);
236  	   colvals = SCIPcolGetVals(col);
237  	   ncolrows = SCIPcolGetNLPNonz(col);
238  	   assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
239  	
240  	   for( r = 0; r < ncolrows; ++r )
241  	   {
242  	      SCIP_ROW* row;
243  	      int rowpos;
244  	
245  	      row = colrows[r];
246  	      rowpos = SCIProwGetLPPos(row);
247  	      assert(-1 <= rowpos && rowpos < nlprows);
248  	
249  	      if( rowpos >= 0 && !SCIProwIsLocal(row) )
250  	      {
251  	         SCIP_Real oldminactivity;
252  	         SCIP_Real oldmaxactivity;
253  	         SCIP_Real newminactivity;
254  	         SCIP_Real newmaxactivity;
255  	
256  	         assert(SCIProwIsInLP(row));
257  	
258  	         /* update row activities */
259  	         oldminactivity = minactivities[rowpos];
260  	         oldmaxactivity = maxactivities[rowpos];
261  	
262  	         if( !SCIPisInfinity(scip, -oldminactivity) )
263  	         {
264  	            newminactivity = oldminactivity + delta * colvals[r];
265  	            minactivities[rowpos] = newminactivity;
266  	         }
267  	         else
268  	            newminactivity = -SCIPinfinity(scip);
269  	         if( !SCIPisInfinity(scip, oldmaxactivity) )
270  	         {
271  	            newmaxactivity = oldmaxactivity + delta * colvals[r];
272  	            maxactivities[rowpos] = newmaxactivity;
273  	         }
274  	         else
275  	            newmaxactivity = SCIPinfinity(scip);
276  	
277  	         /* update row violation arrays */
278  	         updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldminactivity, oldmaxactivity,
279  	            newminactivity, newmaxactivity);
280  	      }
281  	   }
282  	
283  	   return SCIP_OKAY;
284  	}
285  	
286  	/** returns an integer variable, that pushes activity of the row in the given direction with minimal negative impact on
287  	 *  other rows;
288  	 *  if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
289  	 *  prefer fractional integers over other variables in order to become integral during the process;
290  	 *  shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable
291  	 *  was already shifted in the opposite direction
292  	 */
293  	static
294  	SCIP_RETCODE selectShifting(
295  	   SCIP*                 scip,               /**< SCIP data structure */
296  	   SCIP_SOL*             sol,                /**< primal solution */
297  	   SCIP_ROW*             row,                /**< LP row */
298  	   SCIP_Real             rowactivity,        /**< activity of LP row */
299  	   int                   direction,          /**< should the activity be increased (+1) or decreased (-1)? */
300  	   SCIP_Real*            nincreases,         /**< array with weighted number of increasings per variables */
301  	   SCIP_Real*            ndecreases,         /**< array with weighted number of decreasings per variables */
302  	   SCIP_Real             increaseweight,     /**< current weight of increase/decrease updates */
303  	   SCIP_VAR**            shiftvar,           /**< pointer to store the shifting variable, returns NULL if impossible */
304  	   SCIP_Real*            oldsolval,          /**< pointer to store old solution value of shifting variable */
305  	   SCIP_Real*            newsolval           /**< pointer to store new (shifted) solution value of shifting variable */
306  	   )
307  	{
308  	   SCIP_COL** rowcols;
309  	   SCIP_Real* rowvals;
310  	   int nrowcols;
311  	   SCIP_Real activitydelta;
312  	   SCIP_Real bestshiftscore;
313  	   SCIP_Real bestdeltaobj;
314  	   int c;
315  	
316  	   assert(direction == +1 || direction == -1);
317  	   assert(nincreases != NULL);
318  	   assert(ndecreases != NULL);
319  	   assert(shiftvar != NULL);
320  	   assert(oldsolval != NULL);
321  	   assert(newsolval != NULL);
322  	
323  	   /* get row entries */
324  	   rowcols = SCIProwGetCols(row);
325  	   rowvals = SCIProwGetVals(row);
326  	   nrowcols = SCIProwGetNLPNonz(row);
327  	
328  	   /* calculate how much the activity must be shifted in order to become feasible */
329  	   activitydelta = (direction == +1 ? SCIProwGetLhs(row) - rowactivity : SCIProwGetRhs(row) - rowactivity);
330  	   assert((direction == +1 && SCIPisPositive(scip, activitydelta))
331  	      || (direction == -1 && SCIPisNegative(scip, activitydelta)));
332  	
333  	   /* select shifting variable */
334  	   bestshiftscore = SCIP_REAL_MAX;
335  	   bestdeltaobj = SCIPinfinity(scip);
336  	   *shiftvar = NULL;
337  	   *newsolval = 0.0;
338  	   *oldsolval = 0.0;
339  	   for( c = 0; c < nrowcols; ++c )
340  	   {
341  	      SCIP_COL* col;
342  	      SCIP_VAR* var;
343  	      SCIP_Real val;
344  	      SCIP_Real solval;
345  	      SCIP_Real shiftval;
346  	      SCIP_Real shiftscore;
347  	      SCIP_Bool isfrac;
348  	      SCIP_Bool increase;
349  	      int probindex;
350  	
351  	      col = rowcols[c];
352  	      var = SCIPcolGetVar(col);
353  	      val = rowvals[c];
354  	      assert(!SCIPisZero(scip, val));
355  	      solval = SCIPgetSolVal(scip, sol, var);
356  	
357  	      /* only accept integer variables */
358  	      if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && SCIPvarGetType(var) != SCIP_VARTYPE_INTEGER )
359  	         continue;
360  	
361  	      isfrac = !SCIPisFeasIntegral(scip, solval);
362  	      increase = (direction * val > 0.0);
363  	      probindex = SCIPvarGetProbindex(var);
364  	
365  	      /* calculate the score of the shifting (prefer smaller values) */
366  	      if( isfrac )
367  	         shiftscore = increase ? -1.0 / (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) + 1.0) :
368  	            -1.0 / (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + 1.0);
369  	      else
370  	      {
371  	         if( increase )
372  	            shiftscore = ndecreases[probindex]/increaseweight;
373  	         else
374  	            shiftscore = nincreases[probindex]/increaseweight;
375  	         shiftscore += 1.0;
376  	      }
377  	
378  	      if( shiftscore <= bestshiftscore )
379  	      {
380  	         SCIP_Real deltaobj;
381  	
382  	         if( !increase )
383  	         {
384  	            /* shifting down */
385  	            assert(direction * val < 0.0);
386  	            if( isfrac )
387  	               shiftval = SCIPfeasFloor(scip, solval);
388  	            else
389  	            {
390  	               SCIP_Real lb;
391  	
392  	               assert(activitydelta/val < 0.0);
393  	               shiftval = solval + activitydelta/val;
394  	               assert(shiftval <= solval); /* may be equal due to numerical digit erasement in the subtraction */
395  	               shiftval = SCIPfeasFloor(scip, shiftval);
396  	               lb = SCIPvarGetLbGlobal(var);
397  	               shiftval = MAX(shiftval, lb);
398  	            }
399  	         }
400  	         else
401  	         {
402  	            /* shifting up */
403  	            assert(direction * val > 0.0);
404  	            if( isfrac )
405  	               shiftval = SCIPfeasCeil(scip, solval);
406  	            else
407  	            {
408  	               SCIP_Real ub;
409  	
410  	               assert(activitydelta/val > 0.0);
411  	               shiftval = solval + activitydelta/val;
412  	               assert(shiftval >= solval); /* may be equal due to numerical digit erasement in the subtraction */
413  	               shiftval = SCIPfeasCeil(scip, shiftval);
414  	               ub = SCIPvarGetUbGlobal(var);
415  	               shiftval = MIN(shiftval, ub);
416  	            }
417  	         }
418  	
419  	         if( SCIPisEQ(scip, shiftval, solval) )
420  	            continue;
421  	
422  	         deltaobj = SCIPvarGetObj(var) * (shiftval - solval);
423  	         if( (shiftscore < bestshiftscore || deltaobj < bestdeltaobj)
424  	            && !SCIPisHugeValue(scip, REALABS(shiftval)) ) /* ignore candidates for which shiftval is too large */
425  	         {
426  	            bestshiftscore = shiftscore;
427  	            bestdeltaobj = deltaobj;
428  	            *shiftvar = var;
429  	            *oldsolval = solval;
430  	            *newsolval = shiftval;
431  	         }
432  	      }
433  	   }
434  	
435  	   return SCIP_OKAY;
436  	}
437  	
438  	/** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to
439  	 *  fix in the other direction;
440  	 *  if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
441  	 *  shifting in a direction is forbidden, if this forces the objective value over the upper bound
442  	 */
443  	static
444  	SCIP_RETCODE selectEssentialRounding(
445  	   SCIP*                 scip,               /**< SCIP data structure */
446  	   SCIP_SOL*             sol,                /**< primal solution */
447  	   SCIP_Real             minobj,             /**< minimal objective value possible after shifting remaining fractional vars */
448  	   SCIP_VAR**            lpcands,            /**< fractional variables in LP */
449  	   int                   nlpcands,           /**< number of fractional variables in LP */
450  	   SCIP_VAR**            shiftvar,           /**< pointer to store the shifting variable, returns NULL if impossible */
451  	   SCIP_Real*            oldsolval,          /**< old (fractional) solution value of shifting variable */
452  	   SCIP_Real*            newsolval           /**< new (shifted) solution value of shifting variable */
453  	   )
454  	{
455  	   SCIP_VAR* var;
456  	   SCIP_Real solval;
457  	   SCIP_Real shiftval;
458  	   SCIP_Real obj;
459  	   SCIP_Real deltaobj;
460  	   SCIP_Real bestdeltaobj;
461  	   int maxnlocks;
462  	   int nlocks;
463  	   int v;
464  	
465  	   assert(shiftvar != NULL);
466  	   assert(oldsolval != NULL);
467  	   assert(newsolval != NULL);
468  	
469  	   /* select shifting variable */
470  	   maxnlocks = -1;
471  	   bestdeltaobj = SCIPinfinity(scip);
472  	   *shiftvar = NULL;
473  	   for( v = 0; v < nlpcands; ++v )
474  	   {
475  	      var = lpcands[v];
476  	      assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
477  	
478  	      solval = SCIPgetSolVal(scip, sol, var);
479  	      if( !SCIPisFeasIntegral(scip, solval) )
480  	      {
481  	         obj = SCIPvarGetObj(var);
482  	
483  	         /* shifting down */
484  	         nlocks = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
485  	         if( nlocks >= maxnlocks )
486  	         {
487  	            shiftval = SCIPfeasFloor(scip, solval);
488  	            deltaobj = obj * (shiftval - solval);
489  	            if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
490  	            {
491  	               maxnlocks = nlocks;
492  	               bestdeltaobj = deltaobj;
493  	               *shiftvar = var;
494  	               *oldsolval = solval;
495  	               *newsolval = shiftval;
496  	            }
497  	         }
498  	
499  	         /* shifting up */
500  	         nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
501  	         if( nlocks >= maxnlocks )
502  	         {
503  	            shiftval = SCIPfeasCeil(scip, solval);
504  	            deltaobj = obj * (shiftval - solval);
505  	            if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
506  	            {
507  	               maxnlocks = nlocks;
508  	               bestdeltaobj = deltaobj;
509  	               *shiftvar = var;
510  	               *oldsolval = solval;
511  	               *newsolval = shiftval;
512  	            }
513  	         }
514  	      }
515  	   }
516  	
517  	   return SCIP_OKAY;
518  	}
519  	
520  	/** adds a given value to the fractionality counters of the rows in which the given variable appears */
521  	static
522  	void addFracCounter(
523  	   int*                  nfracsinrow,        /**< array to store number of fractional variables per row */
524  	   SCIP_ROW**            violrows,           /**< array with currently violated rows */
525  	   int*                  violrowpos,         /**< position of LP rows in violrows array */
526  	   int*                  nviolfracrows,      /**< pointer to store the number of violated rows with fractional variables */
527  	   int                   nviolrows,          /**< the number of currently violated rows (stays unchanged in this method) */
528  	   int                   nlprows,            /**< number of rows in LP */
529  	   SCIP_VAR*             var,                /**< variable for which the counting should be updated */
530  	   int                   incval              /**< value that should be added to the corresponding array entries */
531  	   )
532  	{
533  	   SCIP_COL* col;
534  	   SCIP_ROW** rows;
535  	   int nrows;
536  	   int r;
537  	
538  	   assert(incval != 0);
539  	   assert(nviolrows >= *nviolfracrows);
540  	
541  	   col = SCIPvarGetCol(var);
542  	   rows = SCIPcolGetRows(col);
543  	   nrows = SCIPcolGetNLPNonz(col);
544  	   for( r = 0; r < nrows; ++r )
545  	   {
546  	      int rowlppos;
547  	      int theviolrowpos;
548  	      SCIP_ROW* row;
549  	
550  	      row = rows[r];
551  	      assert(NULL != row);
552  	      rowlppos = SCIProwGetLPPos(row);
553  	      assert(0 <= rowlppos && rowlppos < nlprows);
554  	      assert(!SCIProwIsLocal(row) || violrowpos[rowlppos] == -1);
555  	
556  	      if( SCIProwIsLocal(row) )
557  	         continue;
558  	
559  	      nfracsinrow[rowlppos] += incval;
560  	      assert(nfracsinrow[rowlppos] >= 0);
561  	
562  	      theviolrowpos = violrowpos[rowlppos];
563  	
564  	      /* swap positions in violrows array if fractionality has changed to 0 */
565  	      if( theviolrowpos >= 0 )
566  	      {
567  	         /* first case: the number of fractional variables has become zero: swap row in violrows array to the
568  	          * second part, containing only violated rows without fractional variables
569  	          */
570  	         if( nfracsinrow[rowlppos] == 0 )
571  	         {
572  	            assert(theviolrowpos <= *nviolfracrows - 1);
573  	
574  	            /* nothing to do if row is already at the end of the first part, otherwise, swap it to the last position
575  	             * and decrease the counter */
576  	            if( theviolrowpos < *nviolfracrows - 1 )
577  	            {
578  	               violrows[theviolrowpos] = violrows[*nviolfracrows - 1];
579  	               violrows[*nviolfracrows - 1] = row;
580  	
581  	               violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
582  	               violrowpos[rowlppos] = *nviolfracrows - 1;
583  	            }
584  	            (*nviolfracrows)--;
585  	         }
586  	         /* second interesting case: the number of fractional variables was zero before, swap it with the first
587  	          * violated row without fractional variables
588  	          */
589  	         else if( nfracsinrow[rowlppos] == incval )
590  	         {
591  	            assert(theviolrowpos >= *nviolfracrows);
592  	
593  	            /* nothing to do if the row is exactly located at index *nviolfracrows */
594  	            if( theviolrowpos > *nviolfracrows )
595  	            {
596  	               violrows[theviolrowpos] = violrows[*nviolfracrows];
597  	               violrows[*nviolfracrows] = row;
598  	
599  	               violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
600  	               violrowpos[rowlppos] = *nviolfracrows;
601  	            }
602  	            (*nviolfracrows)++;
603  	         }
604  	      }
605  	   }
606  	}
607  	
608  	
609  	/*
610  	 * Callback methods
611  	 */
612  	
613  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
614  	static
615  	SCIP_DECL_HEURCOPY(heurCopyIntshifting)
616  	{  /*lint --e{715}*/
617  	   assert(scip != NULL);
618  	   assert(heur != NULL);
619  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
620  	
621  	   /* call inclusion method of primal heuristic */
622  	   SCIP_CALL( SCIPincludeHeurIntshifting(scip) );
623  	
624  	   return SCIP_OKAY;
625  	}
626  	
627  	
628  	/** initialization method of primal heuristic (called after problem was transformed) */
629  	static
630  	SCIP_DECL_HEURINIT(heurInitIntshifting) /*lint --e{715}*/
631  	{  /*lint --e{715}*/
632  	   SCIP_HEURDATA* heurdata;
633  	
634  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
635  	   assert(SCIPheurGetData(heur) == NULL);
636  	
637  	   /* create heuristic data */
638  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
639  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
640  	   heurdata->lastlp = -1;
641  	   SCIPheurSetData(heur, heurdata);
642  	
643  	   /* create random number generator */
644  	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
645  	         DEFAULT_RANDSEED, TRUE) );
646  	
647  	   return SCIP_OKAY;
648  	}
649  	
650  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
651  	static
652  	SCIP_DECL_HEUREXIT(heurExitIntshifting) /*lint --e{715}*/
653  	{  /*lint --e{715}*/
654  	   SCIP_HEURDATA* heurdata;
655  	
656  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
657  	
658  	   /* free heuristic data */
659  	   heurdata = SCIPheurGetData(heur);
660  	   assert(heurdata != NULL);
661  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
662  	
663  	   /* free random number generator */
664  	   SCIPfreeRandom(scip, &heurdata->randnumgen);
665  	
666  	   SCIPfreeBlockMemory(scip, &heurdata);
667  	   SCIPheurSetData(heur, NULL);
668  	
669  	   return SCIP_OKAY;
670  	}
671  	
672  	/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
673  	static
674  	SCIP_DECL_HEURINITSOL(heurInitsolIntshifting)
675  	{
676  	   SCIP_HEURDATA* heurdata;
677  	
678  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
679  	
680  	   heurdata = SCIPheurGetData(heur);
681  	   assert(heurdata != NULL);
682  	   heurdata->lastlp = -1;
683  	
684  	   return SCIP_OKAY;
685  	}
686  	
687  	
688  	/** execution method of primal heuristic */
689  	static
690  	SCIP_DECL_HEUREXEC(heurExecIntshifting) /*lint --e{715}*/
691  	{  /*lint --e{715}*/
692  	   SCIP_HEURDATA* heurdata;
693  	   SCIP_SOL* sol;
694  	   SCIP_VAR** lpcands;
695  	   SCIP_Real* lpcandssol;
696  	   SCIP_ROW** lprows;
697  	   SCIP_Real* minactivities;
698  	   SCIP_Real* maxactivities;
699  	   SCIP_ROW** violrows;
700  	   SCIP_Real* nincreases;
701  	   SCIP_Real* ndecreases;
702  	   int* violrowpos;
703  	   int* nfracsinrow;
704  	   SCIP_Real increaseweight;
705  	   SCIP_Real obj;
706  	   SCIP_Real bestshiftval;
707  	   SCIP_Real minobj;
708  	   int nlpcands;
709  	   int nlprows;
710  	   int nvars;
711  	   int nfrac;
712  	   int nviolrows;
713  	   int nviolfracrows;
714  	   int nprevviolrows;
715  	   int minnviolrows;
716  	   int nnonimprovingshifts;
717  	   int c;
718  	   int r;
719  	   SCIP_Longint nlps;
720  	   SCIP_Longint ncalls;
721  	   SCIP_Longint nsolsfound;
722  	   SCIP_Longint nnodes;
723  	
724  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
725  	   assert(scip != NULL);
726  	   assert(result != NULL);
727  	   assert(SCIPhasCurrentNodeLP(scip));
728  	
729  	   *result = SCIP_DIDNOTRUN;
730  	
731  	   /* do not call heuristic of node was already detected to be infeasible */
732  	   if( nodeinfeasible )
733  	      return SCIP_OKAY;
734  	
735  	   /* don't call heuristic, if no continuous variables are present
736  	    *  -> in this case, it is equivalent to shifting heuristic
737  	    */
738  	   if( SCIPgetNContVars(scip) == 0 )
739  	      return SCIP_OKAY;
740  	
741  	   /* only call heuristic, if an optimal LP solution is at hand */
742  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
743  	      return SCIP_OKAY;
744  	
745  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
746  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
747  	      return SCIP_OKAY;
748  	
749  	   /* get heuristic data */
750  	   heurdata = SCIPheurGetData(heur);
751  	   assert(heurdata != NULL);
752  	
753  	   /* don't call heuristic, if we have already processed the current LP solution */
754  	   nlps = SCIPgetNLPs(scip);
755  	   if( nlps == heurdata->lastlp )
756  	      return SCIP_OKAY;
757  	   heurdata->lastlp = nlps;
758  	
759  	   /* don't call heuristic, if it was not successful enough in the past */
760  	   ncalls = SCIPheurGetNCalls(heur);
761  	   nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + SCIPheurGetNSolsFound(heur);
762  	   nnodes = SCIPgetNNodes(scip);
763  	   if( nnodes % (ncalls/(nsolsfound+1)+1) != 0 )  /*?????????? ncalls/100 */
764  	      return SCIP_OKAY;
765  	
766  	   /* get fractional variables, that should be integral */
767  	   /* todo check if heuristic should include implicit integer variables for its calculations */
768  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
769  	   nfrac = nlpcands;
770  	
771  	   /* only call heuristic, if LP solution is fractional */
772  	   if( nfrac == 0 )
773  	      return SCIP_OKAY;
774  	
775  	   *result = SCIP_DIDNOTFIND;
776  	
777  	   /* get LP rows */
778  	   SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
779  	
780  	   SCIPdebugMsg(scip, "executing intshifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
781  	
782  	   /* get memory for activities, violated rows, and row violation positions */
783  	   nvars = SCIPgetNVars(scip);
784  	   SCIP_CALL( SCIPallocBufferArray(scip, &minactivities, nlprows) );
785  	   SCIP_CALL( SCIPallocBufferArray(scip, &maxactivities, nlprows) );
786  	   SCIP_CALL( SCIPallocBufferArray(scip, &violrows, nlprows) );
787  	   SCIP_CALL( SCIPallocBufferArray(scip, &violrowpos, nlprows) );
788  	   SCIP_CALL( SCIPallocBufferArray(scip, &nfracsinrow, nlprows) );
789  	   SCIP_CALL( SCIPallocBufferArray(scip, &nincreases, nvars) );
790  	   SCIP_CALL( SCIPallocBufferArray(scip, &ndecreases, nvars) );
791  	   BMSclearMemoryArray(nfracsinrow, nlprows);
792  	   BMSclearMemoryArray(nincreases, nvars);
793  	   BMSclearMemoryArray(ndecreases, nvars);
794  	
795  	   /* get the minimal and maximal activity for all globally valid rows for continuous variables in their full range;
796  	    * these are the values of a*x' with x' being the LP solution for integer variables and the lower or upper bound
797  	    * for the continuous variables
798  	    */
799  	   nviolrows = 0;
800  	   for( r = 0; r < nlprows; ++r )
801  	   {
802  	      SCIP_ROW* row;
803  	
804  	      row = lprows[r];
805  	      assert(SCIProwGetLPPos(row) == r);
806  	
807  	      if( !SCIProwIsLocal(row) )
808  	      {
809  	         SCIP_COL** cols;
810  	         SCIP_Real* vals;
811  	         int nnonz;
812  	         SCIP_Bool mininf;
813  	         SCIP_Bool maxinf;
814  	
815  	         mininf = FALSE;
816  	         maxinf = FALSE;
817  	         minactivities[r] = 0.0;
818  	         maxactivities[r] = 0.0;
819  	         cols = SCIProwGetCols(row);
820  	         vals = SCIProwGetVals(row);
821  	         nnonz = SCIProwGetNNonz(row);
822  	         for( c = 0; c < nnonz && !(mininf && maxinf); ++c )
823  	         {
824  	            SCIP_VAR* var;
825  	
826  	            var = SCIPcolGetVar(cols[c]);
827  	            if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER )
828  	            {
829  	               SCIP_Real act;
830  	
831  	               act = vals[c] * SCIPcolGetPrimsol(cols[c]);
832  	               minactivities[r] += act;
833  	               maxactivities[r] += act;
834  	            }
835  	            else if( vals[c] > 0.0 )
836  	            {
837  	               SCIP_Real lb;
838  	               SCIP_Real ub;
839  	
840  	               lb = SCIPvarGetLbGlobal(var);
841  	               ub = SCIPvarGetUbGlobal(var);
842  	               if( SCIPisInfinity(scip, -lb) )
843  	                  mininf = TRUE;
844  	               else
845  	                  minactivities[r] += vals[c] * lb;
846  	               if( SCIPisInfinity(scip, ub) )
847  	                  maxinf = TRUE;
848  	               else
849  	                  maxactivities[r] += vals[c] * ub;
850  	            }
851  	            else if( vals[c] < 0.0 )
852  	            {
853  	               SCIP_Real lb;
854  	               SCIP_Real ub;
855  	
856  	               lb = SCIPvarGetLbGlobal(var);
857  	               ub = SCIPvarGetUbGlobal(var);
858  	               if( SCIPisInfinity(scip, ub) )
859  	                  mininf = TRUE;
860  	               else
861  	                  minactivities[r] += vals[c] * ub;
862  	               if( SCIPisInfinity(scip, -lb) )
863  	                  maxinf = TRUE;
864  	               else
865  	                  maxactivities[r] += vals[c] * lb;
866  	            }
867  	
868  	            if( mininf )
869  	               minactivities[r] = -SCIPinfinity(scip);
870  	            if( maxinf )
871  	               maxactivities[r] = SCIPinfinity(scip);
872  	         }
873  	
874  	         if( SCIPisFeasLT(scip, maxactivities[r], SCIProwGetLhs(row))
875  	            || SCIPisFeasGT(scip, minactivities[r], SCIProwGetRhs(row)) )
876  	         {
877  	            violrows[nviolrows] = row;
878  	            violrowpos[r] = nviolrows;
879  	            nviolrows++;
880  	         }
881  	         else
882  	            violrowpos[r] = -1;
883  	      }
884  	      else
885  	         /* if row is a local row */
886  	         violrowpos[r] = -1;
887  	   }
888  	
889  	   nviolfracrows = 0;
890  	   /* calc the current number of fractional variables in rows */
891  	   for( c = 0; c < nlpcands; ++c )
892  	      addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);
893  	
894  	   /* get the working solution from heuristic's local data */
895  	   sol = heurdata->sol;
896  	   assert(sol != NULL);
897  	
898  	   /* copy the current LP solution to the working solution */
899  	   SCIP_CALL( SCIPlinkLPSol(scip, sol) );
900  	
901  	   /* calculate the minimal objective value possible after rounding fractional variables */
902  	   minobj = SCIPgetSolTransObj(scip, sol);
903  	   assert(minobj < SCIPgetCutoffbound(scip));
904  	   for( c = 0; c < nlpcands; ++c )
905  	   {
906  	      obj = SCIPvarGetObj(lpcands[c]);
907  	      bestshiftval = obj > 0.0 ? SCIPfeasFloor(scip, lpcandssol[c]) : SCIPfeasCeil(scip, lpcandssol[c]);
908  	      minobj += obj * (bestshiftval - lpcandssol[c]);
909  	   }
910  	
911  	   /* try to shift remaining variables in order to become/stay feasible */
912  	   nnonimprovingshifts = 0;
913  	   minnviolrows = INT_MAX;
914  	   increaseweight = 1.0;
915  	   while( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts < MAXSHIFTINGS && !SCIPisStopped(scip) )
916  	   {
917  	      SCIP_VAR* shiftvar;
918  	      SCIP_Real oldsolval;
919  	      SCIP_Real newsolval;
920  	      SCIP_Bool oldsolvalisfrac;
921  	      int probindex;
922  	
923  	      SCIPdebugMsg(scip, "intshifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
924  	         nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj),
925  	         SCIPretransformObj(scip, SCIPgetCutoffbound(scip)));
926  	
927  	      nprevviolrows = nviolrows;
928  	
929  	      /* choose next variable to process:
930  	       *  - if a violated row exists, shift a variable decreasing the violation, that has least impact on other rows
931  	       *  - otherwise, shift a variable, that has strongest devastating impact on rows in opposite direction
932  	       */
933  	      shiftvar = NULL;
934  	      oldsolval = 0.0;
935  	      newsolval = 0.0;
936  	      if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts < MAXSHIFTINGS-1) )
937  	      {
938  	         SCIP_ROW* row;
939  	         int rowidx;
940  	         int rowpos;
941  	         int direction;
942  	
943  	         assert(nviolfracrows == 0 || nfrac > 0);
944  	         /* violated rows containing fractional variables are preferred; if such a row exists, choose the last one from the list
945  	          * (at position nviolfracrows - 1) because removing this row will cause one swapping operation less than other rows
946  	          */
947  	         if( nviolfracrows > 0 )
948  	            rowidx = nviolfracrows - 1;
949  	         else
950  	            rowidx = SCIPrandomGetInt(heurdata->randnumgen, 0, nviolrows-1);
951  	
952  	         assert(0 <= rowidx && rowidx < nviolrows);
953  	         row = violrows[rowidx];
954  	         rowpos = SCIProwGetLPPos(row);
955  	         assert(0 <= rowpos && rowpos < nlprows);
956  	         assert(violrowpos[rowpos] == rowidx);
957  	         assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);
958  	
959  	         SCIPdebugMsg(scip, "intshifting heuristic: try to fix violated row <%s>: %g <= [%g,%g] <= %g\n",
960  	            SCIProwGetName(row), SCIProwGetLhs(row), minactivities[rowpos], maxactivities[rowpos], SCIProwGetRhs(row));
961  	         SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
962  	
963  	         /* get direction in which activity must be shifted */
964  	         assert(SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row))
965  	            || SCIPisFeasGT(scip, minactivities[rowpos], SCIProwGetRhs(row)));
966  	         direction = SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row)) ? +1 : -1;
967  	
968  	         /* search an integer variable that can shift the activity in the necessary direction */
969  	         SCIP_CALL( selectShifting(scip, sol, row, direction == +1 ? maxactivities[rowpos] : minactivities[rowpos],
970  	               direction, nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );
971  	      }
972  	
973  	      if( shiftvar == NULL && nfrac > 0 )
974  	      {
975  	         SCIPdebugMsg(scip, "intshifting heuristic: search rounding variable and try to stay feasible\n");
976  	         SCIP_CALL( selectEssentialRounding(scip, sol, minobj, lpcands, nlpcands, &shiftvar, &oldsolval, &newsolval) );
977  	      }
978  	
979  	      /* check, whether shifting was possible */
980  	      if( shiftvar == NULL || SCIPisEQ(scip, oldsolval, newsolval) )
981  	      {
982  	         SCIPdebugMsg(scip, "intshifting heuristic:  -> didn't find a shifting variable\n");
983  	         break;
984  	      }
985  	
986  	      assert(SCIPvarGetType(shiftvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(shiftvar) == SCIP_VARTYPE_INTEGER);
987  	
988  	      SCIPdebugMsg(scip, "intshifting heuristic:  -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
989  	         SCIPvarGetName(shiftvar), SCIPvarGetLbGlobal(shiftvar), SCIPvarGetUbGlobal(shiftvar), SCIPvarGetType(shiftvar),
990  	         oldsolval, newsolval, SCIPvarGetObj(shiftvar));
991  	
992  	      /* update row activities of globally valid rows */
993  	      SCIP_CALL( updateActivities(scip, minactivities, maxactivities, violrows, violrowpos, &nviolrows, &nviolfracrows,
994  	            nfracsinrow, nlprows, shiftvar, oldsolval, newsolval) );
995  	
996  	      if( nviolrows >= nprevviolrows )
997  	         nnonimprovingshifts++;
998  	      else if( nviolrows < minnviolrows )
999  	      {
1000 	         minnviolrows = nviolrows;
1001 	         nnonimprovingshifts = 0;
1002 	      }
1003 	
1004 	      /* store new solution value and decrease fractionality counter */
1005 	      SCIP_CALL( SCIPsetSolVal(scip, sol, shiftvar, newsolval) );
1006 	
1007 	      /* update fractionality counter and minimal objective value possible after shifting remaining variables */
1008 	      oldsolvalisfrac = !SCIPisFeasIntegral(scip, oldsolval);
1009 	      obj = SCIPvarGetObj(shiftvar);
1010 	      if( oldsolvalisfrac )
1011 	      {
1012 	         assert(SCIPisFeasIntegral(scip, newsolval));
1013 	         nfrac--;
1014 	         nnonimprovingshifts = 0;
1015 	         minnviolrows = INT_MAX;
1016 	         addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);
1017 	
1018 	         /* the rounding was already calculated into the minobj -> update only if rounding in "wrong" direction */
1019 	         if( obj > 0.0 && newsolval > oldsolval )
1020 	            minobj += obj;
1021 	         else if( obj < 0.0 && newsolval < oldsolval )
1022 	            minobj -= obj;
1023 	      }
1024 	      else
1025 	      {
1026 	         /* update minimal possible objective value */
1027 	         minobj += obj * (newsolval - oldsolval);
1028 	      }
1029 	
1030 	      /* update increase/decrease arrays */
1031 	      if( !oldsolvalisfrac )
1032 	      {
1033 	         probindex = SCIPvarGetProbindex(shiftvar);
1034 	         assert(0 <= probindex && probindex < nvars);
1035 	         increaseweight *= WEIGHTFACTOR;
1036 	         if( newsolval < oldsolval )
1037 	            ndecreases[probindex] += increaseweight;
1038 	         else
1039 	            nincreases[probindex] += increaseweight;
1040 	         if( increaseweight >= 1e+09 )
1041 	         {
1042 	            int i;
1043 	
1044 	            for( i = 0; i < nvars; ++i )
1045 	            {
1046 	               nincreases[i] /= increaseweight;
1047 	               ndecreases[i] /= increaseweight;
1048 	            }
1049 	            increaseweight = 1.0;
1050 	         }
1051 	      }
1052 	
1053 	      SCIPdebugMsg(scip, "intshifting heuristic:  -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
1054 	         nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj));
1055 	   }
1056 	
1057 	   /* check, if the new solution is potentially feasible and solve the LP to calculate values for the continuous
1058 	    * variables
1059 	    */
1060 	   if( nfrac == 0 && nviolrows == 0 )
1061 	   {
1062 	      SCIP_VAR** vars;
1063 	      SCIP_Bool lperror;
1064 	      int nintvars;
1065 	      int v;
1066 	#ifdef NDEBUG
1067 	      SCIP_RETCODE retstat;
1068 	#endif
1069 	
1070 	      SCIPdebugMsg(scip, "shifted solution is potentially feasible -> solve LP to fix continuous variables\n");
1071 	
1072 	      /* start diving to calculate the LP relaxation */
1073 	      SCIP_CALL( SCIPstartDive(scip) );
1074 	
1075 	      /* set the bounds of the variables: fixed for integers, global bounds for continuous */
1076 	      vars = SCIPgetVars(scip);
1077 	      nintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1078 	      for( v = 0; v < nvars; ++v )
1079 	      {
1080 	         if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
1081 	         {
1082 	            SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) );
1083 	            SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) );
1084 	         }
1085 	      }
1086 	      for( v = 0; v < nintvars; ++v ) /* apply this after global bounds to not cause an error with intermediate empty domains */
1087 	      {
1088 	         if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
1089 	         {
1090 	            SCIP_Real solval;
1091 	            solval = SCIPgetSolVal(scip, sol, vars[v]);
1092 	            SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) );
1093 	            SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) );
1094 	         }
1095 	      }
1096 	
1097 	      /* solve LP */
1098 	      SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1099 	
1100 	      /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1101 	       * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1102 	       */
1103 	#ifdef NDEBUG
1104 	      retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
1105 	      if( retstat != SCIP_OKAY )
1106 	      {
1107 	         SCIPwarningMessage(scip, "Error while solving LP in Intshifting heuristic; LP solve terminated with code <%d>\n",retstat);
1108 	      }
1109 	#else
1110 	      SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) );
1111 	#endif
1112 	
1113 	      SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1114 	      SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
1115 	
1116 	      /* check if this is a feasible solution */
1117 	      if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
1118 	      {
1119 	         SCIP_Bool stored;
1120 	
1121 	         /* copy the current LP solution to the working solution */
1122 	         SCIP_CALL( SCIPlinkLPSol(scip, sol) );
1123 	
1124 	         /* check solution for feasibility, and add it to solution store if possible
1125 	          * neither integrality nor feasibility of LP rows has to be checked, because this is already
1126 	          * done in the intshifting heuristic itself and due to the LP resolve
1127 	          */
1128 	         SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
1129 	
1130 	         if( stored )
1131 	         {
1132 	            SCIPdebugMsg(scip, "found feasible shifted solution:\n");
1133 	            SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) );
1134 	            *result = SCIP_FOUNDSOL;
1135 	         }
1136 	      }
1137 	
1138 	      /* terminate the diving */
1139 	      SCIP_CALL( SCIPendDive(scip) );
1140 	   }
1141 	
1142 	   /* free memory buffers */
1143 	   SCIPfreeBufferArray(scip, &ndecreases);
1144 	   SCIPfreeBufferArray(scip, &nincreases);
1145 	   SCIPfreeBufferArray(scip, &nfracsinrow);
1146 	   SCIPfreeBufferArray(scip, &violrowpos);
1147 	   SCIPfreeBufferArray(scip, &violrows);
1148 	   SCIPfreeBufferArray(scip, &maxactivities);
1149 	   SCIPfreeBufferArray(scip, &minactivities);
1150 	
1151 	   return SCIP_OKAY;
1152 	}
1153 	
1154 	
1155 	/*
1156 	 * heuristic specific interface methods
1157 	 */
1158 	
1159 	/** creates the intshifting heuristic with infeasibility recovering and includes it in SCIP */
1160 	SCIP_RETCODE SCIPincludeHeurIntshifting(
1161 	   SCIP*                 scip                /**< SCIP data structure */
1162 	   )
1163 	{
1164 	   SCIP_HEUR* heur;
1165 	
1166 	   /* include primal heuristic */
1167 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1168 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1169 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntshifting, NULL) );
1170 	
1171 	   assert(heur != NULL);
1172 	
1173 	   /* set non-NULL pointers to callback methods */
1174 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntshifting) );
1175 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntshifting) );
1176 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntshifting) );
1177 	   SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolIntshifting) );
1178 	
1179 	   return SCIP_OKAY;
1180 	}
1181