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   misc_rowprep.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  linear inequalities in preparation
28   	 * @author Stefan Vigerske
29   	 * @author Benjamin Mueller
30   	 * @author Felipe Serrano
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#include "scip/pub_misc_rowprep.h"
36   	#include "scip/pub_misc_sort.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_lp.h"
39   	#include "scip/scip_mem.h"
40   	#include "scip/scip_message.h"
41   	#include "scip/scip_numerics.h"
42   	#include "scip/scip_sepa.h"
43   	#include "scip/scip_sol.h"
44   	#include "scip/scip_tree.h"
45   	#include "scip/struct_misc.h"
46   	#include "scip/struct_scip.h"
47   	#include "scip/set.h"
48   	
49   	#define ROWPREP_SCALEUP_VIOLNONZERO    (10.0*SCIPepsilon(scip))    /**< minimal violation for considering up-scaling of rowprep (we want to avoid upscaling very small violations) */
50   	#define ROWPREP_SCALEUP_MINVIOLFACTOR  2.0                         /**< scale up will target a violation of ~MINVIOLFACTOR*minviol, where minviol is given by caller */
51   	#define ROWPREP_SCALEUP_MAXMINCOEF     (1.0 / SCIPfeastol(scip))   /**< scale up only if min. coef is below this number (before scaling) */
52   	#define ROWPREP_SCALEUP_MAXMAXCOEF     SCIPgetHugeValue(scip)      /**< scale up only if max. coef will not exceed this number by scaling */
53   	#define ROWPREP_SCALEUP_MAXSIDE        SCIPgetHugeValue(scip)      /**< scale up only if side will not exceed this number by scaling */
54   	#define ROWPREP_SCALEDOWN_MINMAXCOEF   (1.0 / SCIPfeastol(scip))   /**< scale down if max. coef is at least this number (before scaling) */
55   	#define ROWPREP_SCALEDOWN_MINCOEF      SCIPfeastol(scip)           /**< scale down only if min. coef does not drop below this number by scaling */
56   	
57   	#ifndef M_SQRT2
58   	#define M_SQRT2 sqrt(2.0)
59   	#endif
60   	
61   	/** adds a variable to the `rowprep->modifiedvars` array, if recording of modification has been enabled and the variable is not fixed */
62   	static
63   	SCIP_RETCODE rowprepRecordModifiedVar(
64   	   SCIP*                 scip,               /**< SCIP data structure */
65   	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
66   	   SCIP_VAR*             var                 /**< variable to add */
67   	   )
68   	{
69   	   int oldsize;
70   	
71   	   if( !rowprep->recordmodifications )
72   	      return SCIP_OKAY;
73   	
74   	   /* do not record for fixed variables, as they are not suitable for branching */
75   	   if( SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
76   	   {
77   	      SCIPdebugMsg(scip, "skip recording modification for fixed variable <%s>[%g,%g]\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
78   	      return SCIP_OKAY;
79   	   }
80   	
81   	   /* increase modifiedvars array size */
82   	   if( rowprep->nmodifiedvars >= rowprep->modifiedvarssize )
83   	   {
84   	      oldsize = rowprep->modifiedvarssize;
85   	      rowprep->modifiedvarssize = SCIPcalcMemGrowSize(scip, rowprep->nmodifiedvars + 1);
86   	
87   	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &rowprep->modifiedvars, oldsize, rowprep->modifiedvarssize) );
88   	   }
89   	
90   	   rowprep->modifiedvars[rowprep->nmodifiedvars] = var;
91   	   ++rowprep->nmodifiedvars;
92   	
93   	   return SCIP_OKAY;
94   	}
95   	
96   	/** sort terms by absolute value of coefficients, from largest to smallest */
97   	static
98   	SCIP_RETCODE rowprepCleanupSortTerms(
99   	   SCIP*                 scip,               /**< SCIP data structure */
100  	   SCIP_ROWPREP*         rowprep             /**< rowprep to be sorted */
101  	   )
102  	{
103  	   int i;
104  	
105  	   assert(scip != NULL);
106  	   assert(rowprep != NULL);
107  	
108  	   /* special treatment for cuts with few variables */
109  	   switch( rowprep->nvars )
110  	   {
111  	      case 0:
112  	      case 1:
113  	         break;
114  	
115  	      case 2:
116  	      {
117  	         if( REALABS(rowprep->coefs[0]) < REALABS(rowprep->coefs[1]) )
118  	         {
119  	            SCIP_Real tmp1;
120  	            SCIP_VAR* tmp2;
121  	
122  	            tmp1 = rowprep->coefs[0];
123  	            rowprep->coefs[0] = rowprep->coefs[1];
124  	            rowprep->coefs[1] = tmp1;
125  	
126  	            tmp2 = rowprep->vars[0];
127  	            rowprep->vars[0] = rowprep->vars[1];
128  	            rowprep->vars[1] = tmp2;
129  	         }
130  	         break;
131  	      }
132  	
133  	      default :
134  	      {
135  	         SCIP_Real* abscoefs;
136  	
137  	         SCIP_CALL( SCIPallocBufferArray(scip, &abscoefs, rowprep->nvars) );
138  	         for( i = 0; i < rowprep->nvars; ++i )
139  	            abscoefs[i] = REALABS(rowprep->coefs[i]);
140  	         SCIPsortDownRealRealPtr(abscoefs, rowprep->coefs, (void**)rowprep->vars, rowprep->nvars);
141  	         SCIPfreeBufferArray(scip, &abscoefs);
142  	      }
143  	   }
144  	
145  	   /* forget about coefs that are exactly zero (unlikely to have some) */
146  	   while( rowprep->nvars > 0 && rowprep->coefs[rowprep->nvars-1] == 0.0 )
147  	      --rowprep->nvars;
148  	
149  	   return SCIP_OKAY;
150  	}
151  	
152  	/** try to improve coef range by aggregating row with variable bounds
153  	 *
154  	 * Assumes terms have been sorted by rowprepCleanupSortTerms().
155  	 */
156  	static
157  	SCIP_RETCODE rowprepCleanupImproveCoefrange(
158  	   SCIP*                 scip,               /**< SCIP data structure */
159  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be improve */
160  	   SCIP_SOL*             sol,                /**< solution that we try to cut off, or NULL for LP solution */
161  	   SCIP_Real             maxcoefrange        /**< maximal allowed coefficients range */
162  	   )
163  	{
164  	   SCIP_VAR* var;
165  	   SCIP_Real lb;
166  	   SCIP_Real ub;
167  	   SCIP_Real ref;
168  	   SCIP_Real coef;
169  	   SCIP_Real mincoef;
170  	   SCIP_Real maxcoef;
171  	   SCIP_Real loss[2];
172  	   int maxcoefidx;
173  	   int pos;
174  	
175  	   maxcoefidx = 0;
176  	   if( rowprep->nvars > 0 )
177  	   {
178  	      maxcoef = REALABS(rowprep->coefs[0]);
179  	      mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
180  	   }
181  	   else
182  	      mincoef = maxcoef = 1.0;
183  	
184  	   /* eliminate minimal or maximal coefs as long as coef range is too large
185  	    * this is likely going to eliminate coefs that are within eps of 0.0
186  	    * if not, then we do so after scaling (or should we enforce this here?)
187  	    */
188  	   while( maxcoef / mincoef > maxcoefrange  )
189  	   {
190  	      SCIPdebugMsg(scip, "cut coefficients have very large range: mincoef = %g maxcoef = %g\n", mincoef, maxcoef);
191  	
192  	      /* max/min can only be > 1 if there is more than one var
193  	       * we need this below for updating the max/min coef after eliminating a term
194  	       */
195  	      assert(rowprep->nvars > 1);
196  	
197  	      /* try to reduce coef range by aggregating with variable bounds
198  	       * that is, eliminate a term like a*x from a*x + ... <= side by adding -a*x <= -a*lb(x)
199  	       * with ref(x) the reference point we try to eliminate, this would weaken the cut by a*(lb(x)-ref(x))
200  	       *
201  	       * we consider eliminating either the term with maximal or the one with minimal coefficient,
202  	       * taking the one that leads to the least weakening of the cut
203  	       *
204  	       * TODO (suggested by @bzfserra, see !496):
205  	       * - Also one could think of not completely removing the coefficient but do an aggregation that makes the coefficient look better. For instance:
206  	       *   say you have $`a x + 0.1 y \leq r`$ and $`y`$ has only an upper bound, $`y \leq b`$,
207  	       *   then you can't really remove $`y`$. However, you could aggregate it with $`0.9 \cdot (y \leq b)`$ to get
208  	       *   $`a x + y \leq r + 0.9 b`$, which has better numerics (and hopefully still cuts the point... actually, if for the point you want to separate, $`y^* = b`$, then the violation is the same)
209  	       */
210  	
211  	      for( pos = 0; pos < 2; ++pos )
212  	      {
213  	         var = rowprep->vars[pos ? rowprep->nvars-1 : maxcoefidx];
214  	         coef = rowprep->coefs[pos ? rowprep->nvars-1 : maxcoefidx];
215  	         lb = SCIPvarGetLbLocal(var);
216  	         ub = SCIPvarGetUbLocal(var);
217  	         ref = SCIPgetSolVal(scip, sol, var);
218  	         assert(coef != 0.0);
219  	
220  	         /* make sure reference point is something reasonable within the bounds, preferable the value from the solution */
221  	         if( SCIPisInfinity(scip, REALABS(ref)) )
222  	            ref = 0.0;
223  	         ref = MAX(lb, MIN(ub, ref));
224  	
225  	         /* check whether we can eliminate coef*var from rowprep and how much we would loose w.r.t. ref(x) */
226  	         if( ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) )
227  	         {
228  	            /* we would need to aggregate with -coef*var <= -coef*lb(x) */
229  	            if( SCIPisInfinity(scip, -lb) )
230  	               loss[pos] = SCIP_INVALID;
231  	            else
232  	               loss[pos] = REALABS(coef) * (ref - lb);
233  	         }
234  	         else
235  	         {
236  	            assert((coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT));
237  	            /* we would need to aggregate with -coef*var >= -coef*ub(x) */
238  	            if( SCIPisInfinity(scip, ub) )
239  	               loss[pos] = SCIP_INVALID;
240  	            else
241  	               loss[pos] = REALABS(coef) * (ub - ref);
242  	         }
243  	         assert(loss[pos] >= 0.0);  /* assuming SCIP_INVALID >= 0 */
244  	
245  	         SCIPdebugMsg(scip, "aggregating %g*<%s> %c= ... with <%s>[%g] %c= %g looses %g\n",
246  	            coef, SCIPvarGetName(var), rowprep->sidetype == SCIP_SIDETYPE_RIGHT ? '<' : '>',
247  	            SCIPvarGetName(var), ref,
248  	            ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) ? '>' : '<',
249  	            ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) ? lb : ub, loss[pos]);
250  	      }
251  	
252  	      /*lint --e{777} */
253  	      if( loss[0] == SCIP_INVALID && loss[1] == SCIP_INVALID )
254  	         break;  /* cannot eliminate coefficient */
255  	
256  	      /* select position with smaller loss */
257  	      pos = (loss[1] == SCIP_INVALID || loss[1] > loss[0]) ? 0 : 1;
258  	
259  	      /* now do the actual elimination */
260  	      var = rowprep->vars[pos ? rowprep->nvars-1 : maxcoefidx];
261  	      coef = rowprep->coefs[pos ? rowprep->nvars-1 : maxcoefidx];
262  	
263  	      /* eliminate coef*var from rowprep: increase side */
264  	      if( ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) )
265  	      {
266  	         /* we aggregate with -coef*var <= -coef*lb(x) */
267  	         assert(!SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
268  	         SCIProwprepAddConstant(rowprep, coef * SCIPvarGetLbLocal(var));
269  	         rowprep->local |= SCIPisGT(scip, SCIPvarGetLbLocal(var), SCIPvarGetLbGlobal(var));
270  	      }
271  	      else
272  	      {
273  	         assert((coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT));
274  	         /* we aggregate with -coef*var >= -coef*ub(x) */
275  	         assert(!SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
276  	         SCIProwprepAddConstant(rowprep, coef * SCIPvarGetUbLocal(var));
277  	         rowprep->local |= SCIPisLT(scip, SCIPvarGetUbLocal(var), SCIPvarGetUbGlobal(var));
278  	      }
279  	
280  	      /* eliminate coef*var from rowprep: remove coef */
281  	      if( pos == 0 )
282  	      {
283  	         /* set first term to zero */
284  	         rowprep->coefs[maxcoefidx] = 0.0;
285  	
286  	         /* update index */
287  	         ++maxcoefidx;
288  	
289  	         /* update maxcoef */
290  	         maxcoef = REALABS(rowprep->coefs[maxcoefidx]);
291  	      }
292  	      else
293  	      {
294  	         /* forget last term */
295  	         --rowprep->nvars;
296  	
297  	         /* update mincoef */
298  	         mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
299  	      }
300  	
301  	      /* (potentially) remember the variable that has been removed here */
302  	      SCIP_CALL( rowprepRecordModifiedVar(scip, rowprep, var) );
303  	   }
304  	
305  	   /* if maximal coefs were removed, then there are now 0's in the beginning of the coefs array
306  	    * -> move all remaining coefs and vars up front
307  	    */
308  	   if( maxcoefidx > 0 )
309  	   {
310  	      int i;
311  	      for( i = maxcoefidx; i < rowprep->nvars; ++i )
312  	      {
313  	         rowprep->vars[i-maxcoefidx] = rowprep->vars[i];
314  	         rowprep->coefs[i-maxcoefidx] = rowprep->coefs[i];
315  	      }
316  	      rowprep->nvars -= maxcoefidx;
317  	   }
318  	
319  	   return SCIP_OKAY;
320  	}
321  	
322  	
323  	/** scales up rowprep if it seems useful */
324  	static
325  	void rowprepCleanupScaleup(
326  	   SCIP*                 scip,               /**< SCIP data structure */
327  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be improve */
328  	   SCIP_Real*            viol,               /**< violation of cut in sol (input and output) */
329  	   SCIP_Real             minviol             /**< minimal violation we try to achieve */
330  	   )
331  	{
332  	   SCIP_Real scalefactor;
333  	   SCIP_Real mincoef;
334  	   SCIP_Real maxcoef;
335  	
336  	   assert(scip != NULL);
337  	   assert(rowprep != NULL);
338  	   assert(viol != NULL);
339  	
340  	   /* if violation is very small than better don't scale up */
341  	   if( *viol < ROWPREP_SCALEUP_VIOLNONZERO )
342  	      return;
343  	
344  	   /* if violation is already above minviol, then nothing to do */
345  	   if( *viol >= minviol )
346  	      return;
347  	   assert(!SCIPisInfinity(scip, *viol));
348  	
349  	   /* if violation is sufficiently positive (>10*eps), but has not reached minviol,
350  	    * then consider scaling up to reach approx MINVIOLFACTOR*minviol
351  	    */
352  	   scalefactor = ROWPREP_SCALEUP_MINVIOLFACTOR * minviol / *viol;
353  	
354  	   /* scale by approx. scalefactor, if minimal coef is not so large yet and maximal coef and rhs don't get huge by doing so (or have been so before) */
355  	   mincoef = rowprep->nvars > 0 ? REALABS(rowprep->coefs[rowprep->nvars-1]) : 1.0;
356  	   maxcoef = rowprep->nvars > 0 ? REALABS(rowprep->coefs[0]) : 1.0;
357  	   if( mincoef < ROWPREP_SCALEUP_MAXMINCOEF && scalefactor * maxcoef < ROWPREP_SCALEUP_MAXMAXCOEF && scalefactor * REALABS(rowprep->side) < ROWPREP_SCALEUP_MAXSIDE )
358  	   {
359  	      int scaleexp;
360  	
361  	      /* SCIPinfoMessage(scip, NULL, "scale up by ~%g, viol=%g: ", scalefactor, myviol);
362  	         SCIPprintRowprep(scip, rowprep, NULL); */
363  	
364  	      /* SCIPscaleRowprep returns the actually applied scale factor */
365  	      scaleexp = SCIPscaleRowprep(rowprep, scalefactor);
366  	      *viol = ldexp(*viol, scaleexp);
367  	
368  	      /* SCIPinfoMessage(scip, NULL, "scaled up by %g, viol=%g: ", ldexp(1.0, scaleexp), myviol);
369  	         SCIPprintRowprep(scip, rowprep, NULL); */
370  	   }
371  	}
372  	
373  	/** scales down rowprep if it improves coefs and keeps rowprep violated */
374  	static
375  	void rowprepCleanupScaledown(
376  	   SCIP*                 scip,               /**< SCIP data structure */
377  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be improve */
378  	   SCIP_Real*            viol,               /**< violation of cut in sol (input and output) */
379  	   SCIP_Real             minviol             /**< minimal violation we try to keep */
380  	   )
381  	{
382  	   SCIP_Real scalefactor;
383  	
384  	   /* if maxcoef < ROWPREP_SCALEDOWN_MINMAXCOEF (or no terms), then don't consider scaling down */
385  	   if( rowprep->nvars == 0 || REALABS(rowprep->coefs[0]) < ROWPREP_SCALEDOWN_MINMAXCOEF )
386  	      return;
387  	
388  	   /* consider scaling down so that maxcoef ~ 10 */
389  	   scalefactor = 10.0 / REALABS(rowprep->coefs[0]);
390  	
391  	   /* if minimal violation would be lost by scaling down, then increase scalefactor such that minviol is still reached */
392  	   if( *viol > minviol && !SCIPisInfinity(scip, *viol) && scalefactor * *viol < minviol )
393  	   {
394  	      assert(minviol > 0.0);  /* since viol >= 0, the if-condition should ensure that minviol > 0 */
395  	      assert(*viol > 0.0);    /* since minviol > 0, the if-condition ensures viol > 0 */
396  	      scalefactor = ROWPREP_SCALEUP_MINVIOLFACTOR * minviol / *viol;
397  	   }
398  	
399  	   /* scale by approx. scalefactor if scaling down and minimal coef does not get too small
400  	    * myviol < minviol (-> scalefactor > 1) or mincoef < feastol before scaling is possible, in which case we also don't scale down
401  	    */
402  	   if( scalefactor < 1.0 && scalefactor * REALABS(rowprep->coefs[rowprep->nvars-1]) > ROWPREP_SCALEDOWN_MINCOEF )
403  	   {
404  	      int scaleexp;
405  	
406  	      /* SCIPinfoMessage(scip, NULL, "scale down by ~%g, viol=%g: ", scalefactor, myviol);
407  	         SCIPprintRowprep(scip, rowprep, NULL); */
408  	
409  	      scaleexp = SCIPscaleRowprep(rowprep, scalefactor);
410  	      if( !SCIPisInfinity(scip, *viol) )
411  	         *viol = ldexp(*viol, scaleexp);
412  	
413  	      /* SCIPinfoMessage(scip, NULL, "scaled down by %g, viol=%g: ", ldexp(1.0, scaleexp), myviol);
414  	         SCIPprintRowprep(scip, rowprep, NULL); */
415  	   }
416  	}
417  	
418  	/** rounds almost integral coefs to integrals, thereby trying to relax the cut */
419  	static
420  	SCIP_RETCODE rowprepCleanupIntegralCoefs(
421  	   SCIP*                 scip,               /**< SCIP data structure */
422  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be improve */
423  	   SCIP_Real*            viol                /**< NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed */
424  	   )
425  	{
426  	   SCIP_Real coef;
427  	   SCIP_Real roundcoef;
428  	   int i;
429  	
430  	   assert(scip != NULL);
431  	   assert(rowprep != NULL);
432  	
433  	   /* Coefficients smaller than epsilon are rounded to 0.0 when added to row and
434  	    * coefficients very close to integral values are rounded to integers when added to LP.
435  	    * Both cases can be problematic if variable value is very large (bad numerics).
436  	    * Thus, we anticipate by rounding coef here, but also modify constant so that cut is still valid (if possible),
437  	    * i.e., bound coef[i]*x by round(coef[i])*x + (coef[i]-round(coef[i])) * bound(x).
438  	    * Or in other words, we aggregate with the variable bound.
439  	    *
440  	    * If the required bound of x is not finite, then only round coef (introduces an error).
441  	    * @TODO If only the opposite bound is available, then one could move the coefficient
442  	    *   away from the closest integer so that the SCIP_ROW won't try to round it.
443  	    *
444  	    * Exception: If the coefficient is almost zero and there is only one variable, then
445  	    *   we scale up the row instead (if that doesn't make the side too huge).
446  	    *   Eventually, the row would have been changed to a boundchange anyway and a similar
447  	    *   operation happens, but we need to ensure that coefficient isn't just rounded to 0 first.
448  	    */
449  	
450  	   if( rowprep->nvars == 1 && rowprep->coefs[0] != 0.0 && SCIPisZero(scip, rowprep->coefs[0]) && REALABS(rowprep->side / rowprep->coefs[0]) < ROWPREP_SCALEUP_MAXSIDE )
451  	   {
452  	      SCIPdebugMsg(scip, "var with almost zero coef in boundchange-row %.15g*<%s> <=/>= %.15g; scaling up\n",
453  	         rowprep->coefs[0], SCIPvarGetName(rowprep->vars[0]), rowprep->side);
454  	      (void) SCIPscaleRowprep(rowprep, REALABS(1.0/rowprep->coefs[0]));
455  	      return SCIP_OKAY;
456  	   }
457  	
458  	   for( i = 0; i < rowprep->nvars; ++i )
459  	   {
460  	      coef = rowprep->coefs[i];
461  	      roundcoef = SCIPround(scip, coef);
462  	      if( coef != roundcoef && SCIPisEQ(scip, coef, roundcoef) ) /*lint !e777*/
463  	      {
464  	         SCIP_Real xbnd;
465  	         SCIP_VAR* var;
466  	
467  	         var = rowprep->vars[i];
468  	         if( rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
469  	            if( rowprep->local )
470  	               xbnd = coef > roundcoef ? SCIPvarGetLbLocal(var)  : SCIPvarGetUbLocal(var);
471  	            else
472  	               xbnd = coef > roundcoef ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var);
473  	         else
474  	            if( rowprep->local )
475  	               xbnd = coef > roundcoef ? SCIPvarGetUbLocal(var)  : SCIPvarGetLbLocal(var);
476  	            else
477  	               xbnd = coef > roundcoef ? SCIPvarGetUbGlobal(var) : SCIPvarGetLbGlobal(var);
478  	
479  	         if( !SCIPisInfinity(scip, REALABS(xbnd)) )
480  	         {
481  	            /* if there is a bound, then relax row side so rounding coef will not introduce an error */
482  	            SCIPdebugMsg(scip, "var <%s> [%g,%g] has almost integral coef %.15g, round coefficient to %g and add constant %g\n",
483  	               SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), coef, roundcoef, (coef-roundcoef) * xbnd);
484  	            SCIProwprepAddConstant(rowprep, (coef-roundcoef) * xbnd);
485  	         }
486  	         else
487  	         {
488  	            /* if there is no bound, then we make the coef integral, too, even though this will introduce an error
489  	             * however, SCIP_ROW would do this anyway, but doing this here might eliminate some epsilon coefs (so they don't determine mincoef below)
490  	             * and helps to get a more accurate row violation value
491  	             */
492  	            SCIPdebugMsg(scip, "var <%s> [%g,%g] has almost integral coef %.15g, round coefficient to %g without relaxing side (!)\n",
493  	               SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), coef, roundcoef);
494  	         }
495  	         rowprep->coefs[i] = roundcoef;
496  	         if( viol != NULL )
497  	            *viol = SCIP_INVALID;
498  	
499  	         /* (potentially) remember the variable which coef has been modified here */
500  	         SCIP_CALL( rowprepRecordModifiedVar(scip, rowprep, var) );
501  	      }
502  	   }
503  	
504  	   /* forget about coefs that became exactly zero by the above step */
505  	   while( rowprep->nvars > 0 && rowprep->coefs[rowprep->nvars-1] == 0.0 )
506  	      --rowprep->nvars;
507  	
508  	   return SCIP_OKAY;
509  	}
510  	
511  	/** relaxes almost zero side */
512  	static
513  	void rowprepCleanupSide(
514  	   SCIP*                 scip,               /**< SCIP data structure */
515  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be improve */
516  	   SCIP_Real*            viol                /**< NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed */
517  	   )
518  	{
519  	   /* SCIP_ROW handling will replace a side close to 0 by 0.0, even if that makes the row more restrictive
520  	    * we thus relax the side here so that it will either be 0 now or will not be rounded to 0 later
521  	    */
522  	   if( rowprep->side == 0.0 || !SCIPisZero(scip, rowprep->side) )
523  	      return;
524  	
525  	   if( rowprep->side > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
526  	      rowprep->side =  1.1*SCIPepsilon(scip);
527  	   else if( rowprep->side < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT )
528  	      rowprep->side = -1.1*SCIPepsilon(scip);
529  	   else
530  	      rowprep->side = 0.0;
531  	
532  	   if( rowprep->recordmodifications )
533  	      rowprep->modifiedside = TRUE;
534  	
535  	   if( viol != NULL )
536  	      *viol = SCIP_INVALID;
537  	}
538  	
539  	#ifdef NDEBUG
540  	/* Undo the defines from pub_misc_rowprep.h, which exist if NDEBUG is defined. */
541  	#undef SCIProwprepGetNVars
542  	#undef SCIProwprepGetVars
543  	#undef SCIProwprepGetCoefs
544  	#undef SCIProwprepGetSide
545  	#undef SCIProwprepGetSidetype
546  	#undef SCIProwprepIsLocal
547  	#undef SCIProwprepGetName
548  	#undef SCIProwprepGetNModifiedVars
549  	#undef SCIProwprepGetModifiedVars
550  	#undef SCIProwprepSetCoef
551  	#undef SCIProwprepAddSide
552  	#undef SCIProwprepAddConstant
553  	#undef SCIProwprepSetSidetype
554  	#undef SCIProwprepSetLocal
555  	#undef SCIProwprepRecordModifications
556  	#endif
557  	
558  	/** creates a SCIP_ROWPREP datastructure
559  	 *
560  	 * Initial row represents 0 &le; 0.
561  	 */
562  	SCIP_RETCODE SCIPcreateRowprep(
563  	   SCIP*                 scip,               /**< SCIP data structure */
564  	   SCIP_ROWPREP**        rowprep,            /**< buffer to store pointer to rowprep */
565  	   SCIP_SIDETYPE         sidetype,           /**< whether cut will be or lower-equal or larger-equal type */
566  	   SCIP_Bool             local               /**< whether cut will be valid only locally */
567  	   )
568  	{
569  	   assert(scip != NULL);
570  	   assert(rowprep != NULL);
571  	
572  	   SCIP_CALL( SCIPallocBlockMemory(scip, rowprep) );
573  	   BMSclearMemory(*rowprep);
574  	
575  	   (*rowprep)->sidetype = sidetype;
576  	   (*rowprep)->local = local;
577  	
578  	   return SCIP_OKAY;
579  	}
580  	
581  	/** frees a SCIP_ROWPREP datastructure */
582  	void SCIPfreeRowprep(
583  	   SCIP*                 scip,               /**< SCIP data structure */
584  	   SCIP_ROWPREP**        rowprep             /**< pointer that stores pointer to rowprep */
585  	   )
586  	{
587  	   assert(scip != NULL);
588  	   assert(rowprep != NULL);
589  	   assert(*rowprep != NULL);
590  	
591  	   SCIPfreeBlockMemoryArrayNull(scip, &(*rowprep)->vars, (*rowprep)->varssize);
592  	   SCIPfreeBlockMemoryArrayNull(scip, &(*rowprep)->coefs, (*rowprep)->varssize);
593  	   SCIPfreeBlockMemoryArrayNull(scip, &(*rowprep)->modifiedvars, (*rowprep)->modifiedvarssize);
594  	   SCIPfreeBlockMemory(scip, rowprep);
595  	}
596  	
597  	/** creates a copy of a SCIP_ROWPREP datastructure */
598  	SCIP_RETCODE SCIPcopyRowprep(
599  	   SCIP*                 scip,               /**< SCIP data structure */
600  	   SCIP_ROWPREP**        target,             /**< buffer to store pointer of rowprep copy */
601  	   SCIP_ROWPREP*         source              /**< rowprep to copy */
602  	   )
603  	{
604  	   assert(scip != NULL);
605  	   assert(target != NULL);
606  	   assert(source != NULL);
607  	
608  	   SCIP_CALL( SCIPduplicateBlockMemory(scip, target, source) );
609  	   if( source->coefs != NULL )
610  	   {
611  	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*target)->coefs, source->coefs, source->varssize) );
612  	   }
613  	   if( source->vars != NULL )
614  	   {
615  	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*target)->vars, source->vars, source->varssize) );
616  	   }
617  	
618  	   (*target)->recordmodifications = FALSE;
619  	   (*target)->modifiedvars = NULL;
620  	   (*target)->modifiedvarssize = 0;
621  	   (*target)->nmodifiedvars = 0;
622  	   (*target)->modifiedside = FALSE;
623  	
624  	   return SCIP_OKAY;
625  	}
626  	
627  	/** gives number of terms in rowprep */
628  	int SCIProwprepGetNVars(
629  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
630  	   )
631  	{
632  	   assert(rowprep != NULL);
633  	
634  	   return rowprep->nvars;
635  	}
636  	
637  	/** gives variables of rowprep (feel free to modify) */
638  	SCIP_VAR** SCIProwprepGetVars(
639  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
640  	   )
641  	{
642  	   assert(rowprep != NULL);
643  	
644  	   return rowprep->vars;
645  	}
646  	
647  	/** gives coefficients of rowprep (feel free to modify) */
648  	SCIP_Real* SCIProwprepGetCoefs(
649  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
650  	   )
651  	{
652  	   assert(rowprep != NULL);
653  	
654  	   return rowprep->coefs;
655  	}
656  	
657  	/** gives side of rowprep */
658  	SCIP_Real SCIProwprepGetSide(
659  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
660  	   )
661  	{
662  	   assert(rowprep != NULL);
663  	
664  	   return rowprep->side;
665  	}
666  	
667  	/** gives kind of inequality of rowprep */
668  	SCIP_SIDETYPE SCIProwprepGetSidetype(
669  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
670  	   )
671  	{
672  	   assert(rowprep != NULL);
673  	
674  	   return rowprep->sidetype;
675  	}
676  	
677  	/** returns whether rowprep is locally valid only */
678  	SCIP_Bool SCIProwprepIsLocal(
679  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
680  	   )
681  	{
682  	   assert(rowprep != NULL);
683  	
684  	   return rowprep->local;
685  	}
686  	
687  	/** returns name of rowprep (feel free to modify) */
688  	char* SCIProwprepGetName(
689  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
690  	   )
691  	{
692  	   assert(rowprep != NULL);
693  	
694  	   return rowprep->name;
695  	}
696  	
697  	/** returns number of variables which coefficients were modified in cleanup */
698  	int SCIProwprepGetNModifiedVars(
699  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
700  	   )
701  	{
702  	   assert(rowprep != NULL);
703  	
704  	   return rowprep->nmodifiedvars;
705  	}
706  	
707  	/** returns variables which coefficients were modified in cleanup */
708  	SCIP_VAR** SCIProwprepGetModifiedVars(
709  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
710  	   )
711  	{
712  	   assert(rowprep != NULL);
713  	
714  	   return rowprep->modifiedvars;
715  	}
716  	
717  	/** resets rowprep to have 0 terms and side 0.0 */
718  	void SCIProwprepReset(
719  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
720  	   )
721  	{
722  	   assert(rowprep != NULL);
723  	
724  	   rowprep->nvars = 0;
725  	   rowprep->side = 0.0;
726  	
727  	   rowprep->recordmodifications = FALSE;
728  	   rowprep->nmodifiedvars = 0;
729  	   rowprep->modifiedside = FALSE;
730  	}
731  	
732  	/** sets coefficient idx of rowprep */
733  	void SCIProwprepSetCoef(
734  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
735  	   int                   idx,                /**< index of coef to set */
736  	   SCIP_Real             newcoef             /**< new coefficient */
737  	   )
738  	{
739  	   assert(rowprep != NULL);
740  	
741  	   rowprep->coefs[idx] = newcoef;
742  	}
743  	
744  	/** adds constant value to side of rowprep */
745  	void SCIProwprepAddSide(
746  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
747  	   SCIP_Real             side                /**< constant value to be added to side */
748  	   )
749  	{
750  	   assert(rowprep != NULL);
751  	
752  	   rowprep->side += side;
753  	}
754  	
755  	/** adds constant term to rowprep
756  	 *
757  	 * Substracts constant from side.
758  	 */
759  	void SCIProwprepAddConstant(
760  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
761  	   SCIP_Real             constant            /**< constant value to be added */
762  	   )
763  	{
764  	   SCIProwprepAddSide(rowprep, -constant);
765  	}
766  	
767  	/** sets side type of rowprep */
768  	void SCIProwprepSetSidetype(
769  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
770  	   SCIP_SIDETYPE         sidetype            /**< new side type */
771  	   )
772  	{
773  	   assert(rowprep != NULL);
774  	
775  	   rowprep->sidetype = sidetype;
776  	}
777  	
778  	/** sets whether rowprep is local */
779  	void SCIProwprepSetLocal(
780  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
781  	   SCIP_Bool             islocal             /**< whether rowprep is local */
782  	   )
783  	{
784  	   assert(rowprep != NULL);
785  	
786  	   rowprep->local = islocal;
787  	}
788  	
789  	/** enables recording for where modifications were done in cleanup */
790  	void SCIProwprepRecordModifications(
791  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
792  	   )
793  	{
794  	   assert(rowprep != NULL);
795  	
796  	   rowprep->recordmodifications = TRUE;
797  	}
798  	
799  	/** prints a rowprep */
800  	void SCIPprintRowprep(
801  	   SCIP*                 scip,               /**< SCIP data structure */
802  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be printed */
803  	   FILE*                 file                /**< file to print to, or NULL for stdout */
804  	   )
805  	{
806  	   int i;
807  	
808  	   assert(scip != NULL);
809  	   assert(rowprep != NULL);
810  	
811  	   if( *rowprep->name != '\0' )
812  	   {
813  	      SCIPinfoMessage(scip, file, "[%s](%c) ", rowprep->name, rowprep->local ? 'l' : 'g');
814  	   }
815  	
816  	   for( i = 0; i < rowprep->nvars; ++i )
817  	   {
818  	      SCIPinfoMessage(scip, file, "%+.15g*<%s> ", rowprep->coefs[i], SCIPvarGetName(rowprep->vars[i]));
819  	   }
820  	
821  	   SCIPinfoMessage(scip, file, rowprep->sidetype == SCIP_SIDETYPE_LEFT ? ">= %.15g\n" : "<= %.15g\n", rowprep->side);
822  	}
823  	
824  	/** prints a rowprep and values in solution */
825  	void SCIPprintRowprepSol(
826  	   SCIP*                 scip,               /**< SCIP data structure */
827  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be printed */
828  	   SCIP_SOL*             sol,                /**< solution for activity */
829  	   FILE*                 file                /**< file to print to, or NULL for stdout */
830  	   )
831  	{
832  	   SCIP_VAR* var;
833  	   SCIP_Real coef;
834  	   SCIP_Real term;
835  	   SCIP_Real maxterm;
836  	   SCIP_Real activity;
837  	   SCIP_Real violation;
838  	   int maxtermidx;
839  	   int i;
840  	
841  	   assert(scip != NULL);
842  	   assert(rowprep != NULL);
843  	
844  	   if( *rowprep->name != '\0' )
845  	   {
846  	      SCIPinfoMessage(scip, file, "[%s](%c) ", rowprep->name, rowprep->local ? 'l' : 'g');
847  	   }
848  	
849  	   activity = 0.0;
850  	   maxterm = REALABS(rowprep->side);
851  	   maxtermidx = -1;
852  	   for( i = 0; i < rowprep->nvars; ++i )
853  	   {
854  	      coef = rowprep->coefs[i];
855  	      var = rowprep->vars[i];
856  	      SCIPinfoMessage(scip, file, "%+.15g*<%s>(%.15g) ", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
857  	
858  	      term = coef * SCIPgetSolVal(scip, sol, var);
859  	      if( REALABS(term) > maxterm )
860  	      {
861  	         maxterm = term;
862  	         maxtermidx = i;
863  	      }
864  	
865  	      activity += term;
866  	   }
867  	
868  	   SCIPinfoMessage(scip, file, rowprep->sidetype == SCIP_SIDETYPE_LEFT ? ">= %.15g" : "<= %.15g", rowprep->side);
869  	
870  	   if( rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
871  	      /* cut is activity <= side -> violation is activity - side (if positive) */
872  	      violation = activity - rowprep->side;
873  	   else
874  	      /* cut is activity >= side -> violation is side - activity (if positive) */
875  	      violation = rowprep->side - activity;
876  	
877  	   SCIPinfoMessage(scip, file, "; activity %.15g", activity);
878  	   SCIPinfoMessage(scip, file, "; violation %e", violation);
879  	   SCIPinfoMessage(scip, file, "; maxterm %e at pos %d\n", maxterm, maxtermidx);
880  	}
881  	
882  	/** ensures that rowprep has space for at least given number of additional terms
883  	 *
884  	 * Useful when knowing in advance how many terms will be added.
885  	 */
886  	SCIP_RETCODE SCIPensureRowprepSize(
887  	   SCIP*                 scip,               /**< SCIP data structure */
888  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
889  	   int                   size                /**< number of additional terms for which to alloc space in rowprep */
890  	   )
891  	{
892  	   int oldsize;
893  	
894  	   assert(scip != NULL);
895  	   assert(rowprep != NULL);
896  	   assert(size >= 0);
897  	
898  	   if( rowprep->varssize >= rowprep->nvars + size )
899  	      return SCIP_OKAY;  /* already enough space left */
900  	
901  	   /* realloc vars and coefs array */
902  	   oldsize = rowprep->varssize;
903  	   rowprep->varssize = SCIPcalcMemGrowSize(scip, rowprep->nvars + size);
904  	
905  	   SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &rowprep->vars,  oldsize, rowprep->varssize) );
906  	   SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &rowprep->coefs, oldsize, rowprep->varssize) );
907  	
908  	   return SCIP_OKAY;
909  	}
910  	
911  	/** adds a term coef*var to a rowprep */
912  	SCIP_RETCODE SCIPaddRowprepTerm(
913  	   SCIP*                 scip,               /**< SCIP data structure */
914  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
915  	   SCIP_VAR*             var,                /**< variable to add */
916  	   SCIP_Real             coef                /**< coefficient to add */
917  	   )
918  	{
919  	   assert(scip != NULL);
920  	   assert(rowprep != NULL);
921  	   assert(var != NULL);
922  	
923  	   if( coef == 0.0 )
924  	      return SCIP_OKAY;
925  	
926  	   SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, 1) );
927  	   assert(rowprep->varssize > rowprep->nvars);
928  	
929  	   rowprep->vars[rowprep->nvars] = var;
930  	   rowprep->coefs[rowprep->nvars] = coef;
931  	   ++rowprep->nvars;
932  	
933  	   return SCIP_OKAY;
934  	}
935  	
936  	/** adds several terms coef*var to a rowprep */
937  	SCIP_RETCODE SCIPaddRowprepTerms(
938  	   SCIP*                 scip,               /**< SCIP data structure */
939  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
940  	   int                   nvars,              /**< number of terms to add */
941  	   SCIP_VAR**            vars,               /**< variables to add */
942  	   SCIP_Real*            coefs               /**< coefficients to add */
943  	   )
944  	{
945  	   assert(scip != NULL);
946  	   assert(rowprep != NULL);
947  	   assert(vars != NULL || nvars == 0);
948  	   assert(coefs != NULL || nvars == 0);
949  	
950  	   if( nvars == 0 )
951  	      return SCIP_OKAY;
952  	
953  	   SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nvars) );
954  	   assert(rowprep->varssize >= rowprep->nvars + nvars);
955  	
956  	   /*lint --e{866} */
957  	   BMScopyMemoryArray(rowprep->vars + rowprep->nvars, vars, nvars);
958  	   BMScopyMemoryArray(rowprep->coefs + rowprep->nvars, coefs, nvars);
959  	   rowprep->nvars += nvars;
960  	
961  	   return SCIP_OKAY;
962  	}
963  	
964  	/** computes violation of rowprep in a given solution
965  	 *
966  	 * Can return whether the violation value is reliable from a floating-point accuracy point of view.
967  	 * The value will not be deemed reliable when its calculation involved the subtraction of large numbers.
968  	 * To be precise, the violation of an inequality \f$ \sum_i a_ix_i \leq b \f$ in a solution \f$x^*\f$ is deemed
969  	 * reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$.
970  	 */
971  	SCIP_Real SCIPgetRowprepViolation(
972  	   SCIP*                 scip,               /**< SCIP data structure */
973  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
974  	   SCIP_SOL*             sol,                /**< solution or NULL for LP solution */
975  	   SCIP_Bool*            reliable            /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */
976  	   )
977  	{
978  	   SCIP_Real activity;
979  	   SCIP_Real maxterm;
980  	   SCIP_Real term;
981  	   SCIP_Real violation;
982  	   SCIP_Real val;
983  	   int i;
984  	
985  	   activity = 0.0;
986  	   maxterm = REALABS(rowprep->side);
987  	   for( i = 0; i < rowprep->nvars; ++i )
988  	   {
989  	      /* Loose variable have the best bound as LP solution value.
990  	       * HOWEVER, they become column variables when they are added to a row (via SCIPaddVarsToRow below).
991  	       * When this happens, their LP solution value changes to 0.0!
992  	       * So when calculating the row activity for an LP solution, we treat loose variable as if they were already column variables.
993  	       */
994  	      if( sol != NULL || SCIPvarGetStatus(rowprep->vars[i]) != SCIP_VARSTATUS_LOOSE )
995  	      {
996  	         val = SCIPgetSolVal(scip, sol, rowprep->vars[i]);
997  	
998  	         /* If a variable is at infinity, then this should lead to an immediate decision.
999  	          * Having different contradicting infinities is something I would now know how to handle and am ignoring now.
1000 	          */
1001 	         if( SCIPisInfinity(scip, val * (rowprep->coefs[i] >= 0.0 ? 1.0 : -1.0)) )
1002 	         {
1003 	            /* activity = SCIPinfinity(scip); */
1004 	            if( reliable != NULL )
1005 	               *reliable = TRUE;
1006 	            if( rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
1007 	               return SCIPinfinity(scip);  /* infinity <= side -> always violated */
1008 	            else
1009 	               return 0.0;  /* infinity >= side -> never violated */
1010 	         }
1011 	         if( SCIPisInfinity(scip, val * (rowprep->coefs[i] >= 0.0 ? -1.0 : 1.0)) )
1012 	         {
1013 	            /* activity = -SCIPinfinity(scip); */
1014 	            if( reliable != NULL )
1015 	               *reliable = TRUE;
1016 	            if( rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
1017 	               return 0.0;  /* -infinity <= side -> never violated */
1018 	            else
1019 	               return SCIPinfinity(scip);  /* -infinity >= side -> always violated */
1020 	         }
1021 	
1022 	         term = rowprep->coefs[i] * val;
1023 	         activity += term;
1024 	
1025 	         if( reliable != NULL && REALABS(term) > maxterm )
1026 	            maxterm = REALABS(term);
1027 	      }
1028 	   }
1029 	
1030 	   if( rowprep->sidetype == SCIP_SIDETYPE_RIGHT )
1031 	      /* cut is activity <= side -> violation is activity - side (if positive) */
1032 	      violation = activity - rowprep->side;
1033 	   else
1034 	      /* cut is activity >= side -> violation is side - activity (if positive) */
1035 	      violation = rowprep->side - activity;
1036 	
1037 	   /* In double precision, the mantissa (or significand) of a floating point number has 52 bit.
1038 	    * Therefore, if the exponent in the violation is 52 (or more) less than the one of maxterm,
1039 	    * then it is essentially random.
1040 	    * We require here that the exponents differ by at most 50.
1041 	    * To be more robust w.r.t. scaling of the row, we look at the exponent of the quotient maxterm/violation
1042 	    * instead of the difference of the exponents of maxterm and violation.
1043 	    */
1044 	   if( reliable != NULL )
1045 	   {
1046 	      if( violation != 0.0 )
1047 	      {
1048 	         int exponent;
1049 	         (void) frexp(maxterm / violation, &exponent);  /* difference in exponents for maxterm and violation */
1050 	         *reliable = exponent <= 50;
1051 	      }
1052 	      else
1053 	         *reliable = TRUE;  /* not clear how to evaluate reliability here, so think positive */
1054 	   }
1055 	
1056 	   return MAX(violation, 0.0);
1057 	}
1058 	
1059 	/** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable
1060 	 *
1061 	 * @see SCIPgetRowprepViolation()
1062 	 */
1063 	SCIP_Bool SCIPisRowprepViolationReliable(
1064 	   SCIP*                 scip,               /**< SCIP data structure */
1065 	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
1066 	   SCIP_SOL*             sol                 /**< solution or NULL for LP solution */
1067 	   )
1068 	{
1069 	   SCIP_Bool reliable;
1070 	
1071 	   assert(scip != NULL);
1072 	   assert(rowprep != NULL);
1073 	
1074 	   (void) SCIPgetRowprepViolation(scip, rowprep, sol, &reliable);
1075 	
1076 	   return reliable;
1077 	}
1078 	
1079 	/** Merge terms that use same variable and eliminate zero coefficients.
1080 	 *
1081 	 * Removes a variable if its bounds have a relative difference of below epsilon.
1082 	 * Local bounds are checked for local rows, otherwise global bounds are used.
1083 	 * If the bounds are not absolute equal, the bound that relaxes the row is used.
1084 	 *
1085 	 * Terms are sorted by variable (see SCIPvarComp()) after return.
1086 	 */
1087 	void SCIPmergeRowprepTerms(
1088 	   SCIP*                 scip,               /**< SCIP data structure */
1089 	   SCIP_ROWPREP*         rowprep             /**< rowprep to be cleaned up */
1090 	   )
1091 	{
1092 	   int i;
1093 	   int j;
1094 	
1095 	   assert(scip != NULL);
1096 	   assert(rowprep != NULL);
1097 	
1098 	   if( rowprep->nvars <= 1 )
1099 	      return;
1100 	
1101 	   /* sort terms by variable index */
1102 	   SCIPsortPtrReal((void**)rowprep->vars, rowprep->coefs, SCIPvarComp, rowprep->nvars);
1103 	
1104 	   /* merge terms with same variable, drop 0 coefficients */
1105 	   i = 0;
1106 	   j = 1;
1107 	   while( j < rowprep->nvars )
1108 	   {
1109 	      if( rowprep->vars[i] == rowprep->vars[j] )
1110 	      {
1111 	         /* merge term j into term i */
1112 	         rowprep->coefs[i] += rowprep->coefs[j];
1113 	         ++j;
1114 	         continue;
1115 	      }
1116 	
1117 	      /* move term i into side if fixed */
1118 	      if( rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbLocal(rowprep->vars[i]), SCIPvarGetUbLocal(rowprep->vars[i])) )
1119 	      {
1120 	         if( (rowprep->coefs[i] > 0.0) == (rowprep->sidetype == SCIP_SIDETYPE_RIGHT) )
1121 	            rowprep->side -= rowprep->coefs[i] * SCIPvarGetLbLocal(rowprep->vars[i]);
1122 	         else
1123 	            rowprep->side -= rowprep->coefs[i] * SCIPvarGetUbLocal(rowprep->vars[i]);
1124 	         rowprep->coefs[i] = 0.0;  /* so will be cleaned out below */
1125 	      }
1126 	      else if( !rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbGlobal(rowprep->vars[i]), SCIPvarGetUbGlobal(rowprep->vars[i])) )
1127 	      {
1128 	         if( (rowprep->coefs[i] > 0.0) == (rowprep->sidetype == SCIP_SIDETYPE_RIGHT) )
1129 	            rowprep->side -= rowprep->coefs[i] * SCIPvarGetLbGlobal(rowprep->vars[i]);
1130 	         else
1131 	            rowprep->side -= rowprep->coefs[i] * SCIPvarGetUbGlobal(rowprep->vars[i]);
1132 	         rowprep->coefs[i] = 0.0;  /* so will be cleaned out below */
1133 	      }
1134 	
1135 	      if( rowprep->coefs[i] == 0.0 )
1136 	      {
1137 	         /* move term j to position i */
1138 	         rowprep->coefs[i] = rowprep->coefs[j];
1139 	         rowprep->vars[i] = rowprep->vars[j];
1140 	         ++j;
1141 	         continue;
1142 	      }
1143 	
1144 	      /* move term j to position i+1 and move on */
1145 	      if( j != i+1 )
1146 	      {
1147 	         rowprep->vars[i+1] = rowprep->vars[j];
1148 	         rowprep->coefs[i+1] = rowprep->coefs[j];
1149 	      }
1150 	      ++i;
1151 	      ++j;
1152 	   }
1153 	
1154 	   /* move term i into side if fixed */
1155 	   if( rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbLocal(rowprep->vars[i]), SCIPvarGetUbLocal(rowprep->vars[i])) )
1156 	   {
1157 	      if( (rowprep->coefs[i] > 0.0) == (rowprep->sidetype == SCIP_SIDETYPE_RIGHT) )
1158 	         rowprep->side -= rowprep->coefs[i] * SCIPvarGetLbLocal(rowprep->vars[i]);
1159 	      else
1160 	         rowprep->side -= rowprep->coefs[i] * SCIPvarGetUbLocal(rowprep->vars[i]);
1161 	      rowprep->coefs[i] = 0.0;  /* so will be cleaned out below */
1162 	   }
1163 	   else if( !rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbGlobal(rowprep->vars[i]), SCIPvarGetUbGlobal(rowprep->vars[i])) )
1164 	   {
1165 	      if( (rowprep->coefs[i] > 0.0) == (rowprep->sidetype == SCIP_SIDETYPE_RIGHT) )
1166 	         rowprep->side -= rowprep->coefs[i] * SCIPvarGetLbGlobal(rowprep->vars[i]);
1167 	      else
1168 	         rowprep->side -= rowprep->coefs[i] * SCIPvarGetUbGlobal(rowprep->vars[i]);
1169 	      rowprep->coefs[i] = 0.0;  /* so will be cleaned out below */
1170 	   }
1171 	
1172 	   /* remaining term can have coef zero -> forget about it */
1173 	   if( rowprep->coefs[i] == 0.0 )
1174 	      --i;
1175 	
1176 	   /* i points to last term */
1177 	   rowprep->nvars = i+1;
1178 	}
1179 	
1180 	/** Cleans up and attempts to improve rowprep
1181 	 *
1182 	 * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the row.
1183 	 * Scales coefficients up to reach minimal violation, if possible.
1184 	 * Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or
1185 	 * maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF).
1186 	 * Scales coefficients and side down if they are large and if the minimal violation is still reached.
1187 	 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
1188 	 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
1189 	 *
1190 	 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
1191 	 * Thus, the coefrange can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
1192 	 *
1193 	 * `success` is set to TRUE if and only if the rowprep satisfies the following:
1194 	 * - the coefrange is below `maxcoefrange`
1195 	 * - the violation is at least `minviol`
1196 	 * - the violation is reliable or `minviol` = 0
1197 	 * - the absolute value of coefficients are below SCIPinfinity()
1198 	 * - the absolute value of the side is below SCIPinfinity()
1199 	 */
1200 	SCIP_RETCODE SCIPcleanupRowprep(
1201 	   SCIP*                 scip,               /**< SCIP data structure */
1202 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
1203 	   SCIP_SOL*             sol,                /**< solution that we try to cut off, or NULL for LP solution */
1204 	   SCIP_Real             minviol,            /**< minimal absolute violation the row should achieve (w.r.t. sol) */
1205 	   SCIP_Real*            viol,               /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
1206 	   SCIP_Bool*            success             /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
1207 	   )
1208 	{
1209 	   SCIP_Real myviol;
1210 	   SCIP_Bool violreliable = TRUE;
1211 	   SCIP_Real maxcoefrange;
1212 	#ifdef SCIP_DEBUG
1213 	   SCIP_Real mincoef = 1.0;
1214 	   SCIP_Real maxcoef = 1.0;
1215 	#endif
1216 	
1217 	   maxcoefrange = SCIPsetGetSepaMaxCoefRatioRowprep(scip->set);
1218 	
1219 	   if( rowprep->recordmodifications )
1220 	   {
1221 	      /* forget about possible previous modifications */
1222 	      rowprep->nmodifiedvars = 0;
1223 	      rowprep->modifiedside = FALSE;
1224 	   }
1225 	
1226 	   /* sort term by absolute value of coef. */
1227 	   SCIP_CALL( rowprepCleanupSortTerms(scip, rowprep) );
1228 	
1229 	#ifdef SCIP_DEBUG
1230 	   if( rowprep->nvars > 0 )
1231 	   {
1232 	      maxcoef = REALABS(rowprep->coefs[0]);
1233 	      mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
1234 	   }
1235 	
1236 	   SCIPinfoMessage(scip, NULL, "starting cleanup, coefrange %g: ", maxcoef/mincoef);
1237 	   SCIPprintRowprep(scip, rowprep, NULL);
1238 	#endif
1239 	
1240 	   /* improve coefficient range by aggregating out variables */
1241 	   SCIP_CALL( rowprepCleanupImproveCoefrange(scip, rowprep, sol, maxcoefrange) );
1242 	
1243 	   /* get current violation in sol (reliability info only needed if success is not NULL) */
1244 	   myviol = SCIPgetRowprepViolation(scip, rowprep, sol, success != NULL ? &violreliable : NULL);  /*lint !e826*/
1245 	   assert(myviol >= 0.0);
1246 	
1247 	#ifdef SCIP_DEBUG
1248 	   if( rowprep->nvars > 0 )
1249 	   {
1250 	      maxcoef = REALABS(rowprep->coefs[0]);
1251 	      mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
1252 	   }
1253 	
1254 	   SCIPinfoMessage(scip, NULL, "improved coefrange to %g, viol %g: ", maxcoef / mincoef, myviol);
1255 	   SCIPprintRowprep(scip, rowprep, NULL);
1256 	#endif
1257 	
1258 	   /* if there is interest in achieving some minimal violation, then possibly scale up to increase violation
1259 	    * this updates myviol; since this is only scaling the cut, it doesn't change anything about the reliability of the violation value */
1260 	   if( minviol > 0.0 )
1261 	   {
1262 	      /* first, try to achieve scip's minefficacy (typically 1e-4) */
1263 	      if( SCIPgetSepaMinEfficacy(scip) > minviol )
1264 	         rowprepCleanupScaleup(scip, rowprep, &myviol, SCIPgetSepaMinEfficacy(scip));
1265 	      /* in case scip minefficacy could not be reached or was smaller than minviol, try with the given minviol */
1266 	      rowprepCleanupScaleup(scip, rowprep, &myviol, minviol);
1267 	   }
1268 	
1269 	   /* scale down to improve numerics, updates myviol (reliability doesn't change) */
1270 	   rowprepCleanupScaledown(scip, rowprep, &myviol, MAX(SCIPgetSepaMinEfficacy(scip), minviol)); /*lint !e666*/
1271 	
1272 	#ifdef SCIP_DEBUG
1273 	   SCIPinfoMessage(scip, NULL, "applied scaling, viol %g: ", myviol);
1274 	   SCIPprintRowprep(scip, rowprep, NULL);
1275 	#endif
1276 	
1277 	   /* turn almost-integral coefs to integral values, may set myviol to SCIP_INVALID */
1278 	   SCIP_CALL( rowprepCleanupIntegralCoefs(scip, rowprep, &myviol) );
1279 	
1280 	   /* relax almost-zero side, may set myviol to SCIP_INVALID */
1281 	   rowprepCleanupSide(scip, rowprep, &myviol);
1282 	
1283 	#ifdef SCIP_DEBUG
1284 	   SCIPinfoMessage(scip, NULL, "adjusted almost-integral coefs and sides, viol %g: ", myviol);
1285 	   SCIPprintRowprep(scip, rowprep, NULL);
1286 	#endif
1287 	
1288 	#if !1
1289 	   /* compute final coefrange, if requested by caller */
1290 	   if( coefrange != NULL )
1291 	   {
1292 	      if( rowprep->nvars > 0 )
1293 	         *coefrange = REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]);
1294 	      else
1295 	         *coefrange = 1.0;
1296 	   }
1297 	#endif
1298 	
1299 	   /* check whether rowprep could be turned into a reasonable row */
1300 	   if( success != NULL )
1301 	   {
1302 	      *success = TRUE;
1303 	
1304 	      /* check whether the coef.range is below maxcoefrange */
1305 	      if( rowprep->nvars > 0 && REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]) > maxcoefrange )
1306 	      {
1307 	         SCIPdebugMsg(scip, "rowprep coefrange %g is above the limit %g\n", REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]), maxcoefrange);
1308 	         *success = FALSE;
1309 	      }
1310 	
1311 	      /* check whether coefficients are below SCIPinfinity (terms are order by coef value) */
1312 	      if( *success && rowprep->nvars > 0 && SCIPisInfinity(scip, REALABS(rowprep->coefs[0])) )
1313 	      {
1314 	         SCIPdebugMsg(scip, "rowprep coefficient %g is beyond value for infinity\n", rowprep->coefs[0]);
1315 	         *success = FALSE;
1316 	      }
1317 	
1318 	      /* check whether the absolute value of the side is below SCIPinfinity */
1319 	      if( *success && SCIPisInfinity(scip, REALABS(rowprep->side)) )
1320 	      {
1321 	         SCIPdebugMsg(scip, "rowprep side %g is beyond value for infinity\n", rowprep->side);
1322 	         *success = FALSE;
1323 	      }
1324 	
1325 	      /* check if violation is at least minviol and reliable, if minviol > 0 */
1326 	      if( *success && minviol > 0.0 )
1327 	      {
1328 	         /* may need to recompute violation if coefs or side was modified above */
1329 	         if( myviol == SCIP_INVALID )  /*lint !e777 */
1330 	            myviol = SCIPgetRowprepViolation(scip, rowprep, sol, &violreliable);
1331 	
1332 	         if( !violreliable )
1333 	         {
1334 	            SCIPdebugMsg(scip, "rowprep violation %g is not reliable\n", myviol);
1335 	            *success = FALSE;
1336 	         }
1337 	         else if( myviol < minviol )
1338 	         {
1339 	            SCIPdebugMsg(scip, "rowprep violation %g is below minimal violation %g\n", myviol, minviol);
1340 	            *success = FALSE;
1341 	         }
1342 	      }
1343 	   }
1344 	
1345 	   /* If we updated myviol correctly, then it should coincide with freshly computed violation.
1346 	    * I leave this assert off for now, since getting the tolerance in the EQ correctly is not trivial. We recompute viol below anyway.
1347 	    */
1348 	   /* assert(myviol == SCIP_INVALID || SCIPisEQ(scip, myviol, SCIPgetRowprepViolation(scip, rowprep, sol, NULL))); */
1349 	
1350 	   /* compute final violation, if requested by caller */
1351 	   if( viol != NULL )  /*lint --e{777} */
1352 	      *viol = myviol == SCIP_INVALID ? SCIPgetRowprepViolation(scip, rowprep, sol, NULL) : myviol;
1353 	
1354 	   return SCIP_OKAY;
1355 	}
1356 	
1357 	/** Cleans up and attempts to improve rowprep without regard for violation
1358 	 *
1359 	 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
1360 	 * if this can be done by relaxing the row.
1361 	 * Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`.
1362 	 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
1363 	 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
1364 	 *
1365 	 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
1366 	 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
1367 	 *
1368 	 * `success` is set to TRUE if and only if the rowprep satisfies the following:
1369 	 * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
1370 	 * - the absolute value of coefficients are below SCIPinfinity()
1371 	 * - the absolute value of the side is below SCIPinfinity()
1372 	 *
1373 	 * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation.
1374 	 */
1375 	SCIP_RETCODE SCIPcleanupRowprep2(
1376 	   SCIP*                 scip,               /**< SCIP data structure */
1377 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
1378 	   SCIP_SOL*             sol,                /**< solution that we try to cut off, or NULL for LP solution */
1379 	   SCIP_Real             maxcoefbound,       /**< bound on absolute value of largest coefficient */
1380 	   SCIP_Bool*            success             /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
1381 	   )
1382 	{
1383 	   SCIP_Real maxcoefrange;
1384 	#ifdef SCIP_DEBUG
1385 	   SCIP_Real mincoef = 1.0;
1386 	   SCIP_Real maxcoef = 1.0;
1387 	#endif
1388 	
1389 	   assert(maxcoefbound >= 1.0);
1390 	
1391 	   maxcoefrange = SCIPsetGetSepaMaxCoefRatioRowprep(scip->set);
1392 	
1393 	   if( rowprep->recordmodifications )
1394 	   {
1395 	      /* forget about possible previous modifications */
1396 	      rowprep->nmodifiedvars = 0;
1397 	      rowprep->modifiedside = FALSE;
1398 	   }
1399 	
1400 	   /* sort term by absolute value of coef. */
1401 	   SCIP_CALL( rowprepCleanupSortTerms(scip, rowprep) );
1402 	
1403 	#ifdef SCIP_DEBUG
1404 	   if( rowprep->nvars > 0 )
1405 	   {
1406 	      maxcoef = REALABS(rowprep->coefs[0]);
1407 	      mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
1408 	   }
1409 	
1410 	   SCIPinfoMessage(scip, NULL, "starting cleanup, coefrange %g: ", maxcoef/mincoef);
1411 	   SCIPprintRowprep(scip, rowprep, NULL);
1412 	#endif
1413 	
1414 	   /* improve coefficient range by aggregating out variables */
1415 	   SCIP_CALL( rowprepCleanupImproveCoefrange(scip, rowprep, sol, maxcoefrange) );
1416 	
1417 	#ifdef SCIP_DEBUG
1418 	   if( rowprep->nvars > 0 )
1419 	   {
1420 	      maxcoef = REALABS(rowprep->coefs[0]);
1421 	      mincoef = REALABS(rowprep->coefs[rowprep->nvars-1]);
1422 	   }
1423 	
1424 	   SCIPinfoMessage(scip, NULL, "improved coefrange to %g: ", maxcoef / mincoef);
1425 	   SCIPprintRowprep(scip, rowprep, NULL);
1426 	#endif
1427 	
1428 	   /* scale up or down to improve numerics
1429 	    * if maximal coef is below 1.0/maxcoefbound, scale up to reach ~ 1.0/maxcoefbound
1430 	    * if maximal coef is above maxcoefbound, scale down to ~ maxcoefbound
1431 	    */
1432 	   if( rowprep->nvars > 0 && !SCIPisInfinity(scip, maxcoefbound) )
1433 	   {
1434 	      SCIP_Real expon = 0.0;
1435 	      if( REALABS(rowprep->coefs[0]) < 1.0/maxcoefbound )
1436 	         expon = SCIPscaleRowprep(rowprep, (1.0/maxcoefbound) / REALABS(rowprep->coefs[0]));
1437 	      else if( REALABS(rowprep->coefs[0]) > maxcoefbound )
1438 	         expon = SCIPscaleRowprep(rowprep, maxcoefbound / REALABS(rowprep->coefs[0]));
1439 	
1440 	#ifdef SCIP_DEBUG
1441 	      SCIPinfoMessage(scip, NULL, "applied scaling by %g: ", pow(2.0, expon));
1442 	      SCIPprintRowprep(scip, rowprep, NULL);
1443 	#else
1444 	      (void) expon;
1445 	#endif
1446 	   }
1447 	
1448 	   /* turn almost-integral coefs to integral values */
1449 	   SCIP_CALL( rowprepCleanupIntegralCoefs(scip, rowprep, NULL) );
1450 	
1451 	   /* relax almost-zero side */
1452 	   rowprepCleanupSide(scip, rowprep, NULL);
1453 	
1454 	#ifdef SCIP_DEBUG
1455 	   SCIPinfoMessage(scip, NULL, "adjusted almost-integral coefs and sides: ");
1456 	   SCIPprintRowprep(scip, rowprep, NULL);
1457 	#endif
1458 	
1459 	   /* check whether rowprep could be turned into a reasonable row */
1460 	   if( success != NULL )
1461 	   {
1462 	      *success = TRUE;
1463 	
1464 	      /* check whether the coef.range is below maxcoefrange */
1465 	      if( rowprep->nvars > 0 && REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]) > maxcoefrange )
1466 	      {
1467 	         SCIPdebugMsg(scip, "rowprep coefrange %g is above the limit %g\n", REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]), maxcoefrange);
1468 	         *success = FALSE;
1469 	      }
1470 	
1471 	      /* check whether coefficients are below SCIPinfinity (terms are order by coef value) */
1472 	      if( *success && rowprep->nvars > 0 && SCIPisInfinity(scip, REALABS(rowprep->coefs[0])) )
1473 	      {
1474 	         SCIPdebugMsg(scip, "rowprep coefficient %g is beyond value for infinity\n", rowprep->coefs[0]);
1475 	         *success = FALSE;
1476 	      }
1477 	
1478 	      /* check whether the absolute value of the side is below SCIPinfinity */
1479 	      if( *success && SCIPisInfinity(scip, REALABS(rowprep->side)) )
1480 	      {
1481 	         SCIPdebugMsg(scip, "rowprep side %g is beyond value for infinity\n", rowprep->side);
1482 	         *success = FALSE;
1483 	      }
1484 	   }
1485 	
1486 	   return SCIP_OKAY;
1487 	}
1488 	
1489 	/** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible.
1490 	 *
1491 	 * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep.
1492 	 * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon,
1493 	 * if this will not put any coefficient or side above SCIPhugeValue().
1494 	 *
1495 	 * This function does not relax the rowprep.
1496 	 *
1497 	 * `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is,
1498 	 * all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon.
1499 	 * If `success` is set to FALSE, then the rowprep will not have been modified.
1500 	 *
1501 	 * @return The applied scaling factor, if `success` is set to TRUE.
1502 	 */
1503 	SCIP_Real SCIPscaleupRowprep(
1504 	   SCIP*                 scip,               /**< SCIP data structure */
1505 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
1506 	   SCIP_Real             minscaleup,         /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */
1507 	   SCIP_Bool*            success             /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */
1508 	   )
1509 	{
1510 	   SCIP_Real minfrac = 0.5;
1511 	   SCIP_Real minfrac0 = 0.5;
1512 	   SCIP_Real frac;
1513 	   SCIP_Real maxval;
1514 	   SCIP_Real factor = 1.0;
1515 	   SCIP_Bool makeintegral = TRUE;
1516 	   int i;
1517 	
1518 	   /* find the smallest fractionality in rowprep sides and coefficients and the largest absolute coefficient/side */
1519 	   frac = REALABS(floor(rowprep->side + 0.5) - rowprep->side);
1520 	   if( frac != 0.0 )
1521 	   {
1522 	      if( REALABS(rowprep->side) > 0.5 )
1523 	      {
1524 	         if( frac < minfrac )
1525 	            minfrac = frac;
1526 	      }
1527 	      else if( frac < minfrac0 )
1528 	         minfrac0 = frac;
1529 	   }
1530 	   maxval = REALABS(rowprep->side);
1531 	
1532 	   for( i = 0; i < rowprep->nvars; ++i )
1533 	   {
1534 	      frac = REALABS(floor(rowprep->coefs[i] + 0.5) - rowprep->coefs[i]);
1535 	      if( frac != 0.0 )
1536 	      {
1537 	         if( REALABS(rowprep->coefs[i]) > 0.5 )
1538 	         {
1539 	            if( frac < minfrac )
1540 	               minfrac = frac;
1541 	         }
1542 	         else if( frac < minfrac0 )
1543 	            minfrac0 = frac;
1544 	      }
1545 	      if( REALABS(rowprep->coefs[i]) > maxval )
1546 	         maxval = REALABS(rowprep->coefs[i]);
1547 	   }
1548 	
1549 	   SCIPdebugMsg(scip, "minimal fractional of rowprep coefs and side is %g, max coef/side is %g\n", MIN(minfrac, minfrac0), maxval);
1550 	
1551 	   /* in order for SCIP_ROW to not modify the coefs and side, they need to be more than epsilon way from an integer value
1552 	    *
1553 	    * If the integer value is 0, then scaling up the rowprep by epsilon/minfrac will increase its minimal fractionality
1554 	    * above epsilon.
1555 	    * If the integer value is not zero, then scaling up the rowprep by a well-chosen fractional number alpha will increase
1556 	    * the minimal fractionality by about alpha*integer-value mod 1. To reduce the chance that alpha*integer-value is integral,
1557 	    * we use a "very fractional" value for alpha.
1558 	    *
1559 	    * If the scaling increases the maximal coef/value beyond SCIPinfinity, then the rowprep would be useless.
1560 	    * We even check that we don't increase beyond SCIPhugeValue here
1561 	    */
1562 	   if( minfrac0 <= SCIPepsilon(scip) )
1563 	   {
1564 	      factor = 1.1 * SCIPepsilon(scip) / minfrac0;
1565 	
1566 	      if( factor < minscaleup )
1567 	         factor = minscaleup;
1568 	   }
1569 	   else if( minfrac <= SCIPepsilon(scip) )
1570 	   {
1571 	      factor = MAX(M_SQRT2, minscaleup);
1572 	      makeintegral = FALSE;
1573 	   }
1574 	   else if( minscaleup > 1.0 )
1575 	   {
1576 	      factor = minscaleup;
1577 	   }
1578 	   else
1579 	   {
1580 	      /* do not scale up, only check whether maxval is already below infinity */
1581 	      if( success != NULL )
1582 	         *success = !SCIPisInfinity(scip, maxval);
1583 	
1584 	      return 1.0;
1585 	   }
1586 	
1587 	   if( !SCIPisHugeValue(scip, factor * maxval) )
1588 	   {
1589 	      if( makeintegral)
1590 	      {
1591 	         factor = SCIPscaleRowprep(rowprep, factor);
1592 	
1593 	#ifdef SCIP_DEBUG
1594 	         factor = pow(2.0, factor);  /* SCIPscaleRowprep() actually returned log2 of factor */
1595 	#endif
1596 	      }
1597 	      else
1598 	      {
1599 	         /* multiply each coefficient by factor */
1600 	         for( i = 0; i < rowprep->nvars; ++i )
1601 	            rowprep->coefs[i] *= factor;
1602 	
1603 	         /* multiply side by factor */
1604 	         rowprep->side *= factor;
1605 	      }
1606 	#ifdef SCIP_DEBUG
1607 	      maxval *= factor;
1608 	      SCIPinfoMessage(scip, NULL, "scaled up rowprep by %g (minfrac=%g, minscaleup=%g), maxval is now %g\n", factor, minfrac, minscaleup, maxval);
1609 	      SCIPprintRowprep(scip, rowprep, NULL);
1610 	#endif
1611 	
1612 	      if( success != NULL )
1613 	         *success = TRUE;
1614 	   }
1615 	   else if( success != NULL )
1616 	      *success = FALSE;
1617 	
1618 	   return factor;
1619 	}
1620 	
1621 	/** scales a rowprep by given factor (after some rounding)
1622 	 *
1623 	 * @return Exponent of actually applied scaling factor, if written as \f$2^x\f$.
1624 	 */
1625 	int SCIPscaleRowprep(
1626 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be scaled */
1627 	   SCIP_Real             factor              /**< suggested scale factor */
1628 	   )
1629 	{
1630 	   double v;
1631 	   int expon;
1632 	   int i;
1633 	
1634 	   assert(rowprep != NULL);
1635 	   assert(factor > 0.0);
1636 	
1637 	   /* write factor as v*2^expon with v in [0.5,1) */
1638 	   v = frexp(factor, &expon);
1639 	   /* adjust to v'*2^expon with v' in (0.5,1] by v'=v if v > 0.5, v'=1 if v=0.5 */
1640 	   if( v == 0.5 )
1641 	      --expon;
1642 	
1643 	   /* multiply each coefficient by 2^expon */
1644 	   for( i = 0; i < rowprep->nvars; ++i )
1645 	      rowprep->coefs[i] = ldexp(rowprep->coefs[i], expon);
1646 	
1647 	   /* multiply side by 2^expon */
1648 	   rowprep->side = ldexp(rowprep->side, expon);
1649 	
1650 	   return expon;
1651 	}
1652 	
1653 	/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */
1654 	SCIP_RETCODE SCIPgetRowprepRowConshdlr(
1655 	   SCIP*                 scip,               /**< SCIP data structure */
1656 	   SCIP_ROW**            row,                /**< buffer to store pointer to new row */
1657 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be turned into a row */
1658 	   SCIP_CONSHDLR*        conshdlr            /**< constraint handler */
1659 	   )
1660 	{
1661 	   assert(scip != NULL);
1662 	   assert(row != NULL);
1663 	   assert(rowprep != NULL);
1664 	   assert(conshdlr != NULL);
1665 	
1666 	   SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, row, conshdlr, rowprep->name,
1667 	      rowprep->sidetype == SCIP_SIDETYPE_LEFT  ? rowprep->side : -SCIPinfinity(scip),
1668 	      rowprep->sidetype == SCIP_SIDETYPE_RIGHT ? rowprep->side :  SCIPinfinity(scip),
1669 	      rowprep->local && (SCIPgetDepth(scip) > 0), FALSE, TRUE) );
1670 	
1671 	   SCIP_CALL( SCIPaddVarsToRow(scip, *row, rowprep->nvars, rowprep->vars, rowprep->coefs) );
1672 	
1673 	   return SCIP_OKAY;
1674 	}
1675 	
1676 	/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */
1677 	SCIP_RETCODE SCIPgetRowprepRowCons(
1678 	   SCIP*                 scip,               /**< SCIP data structure */
1679 	   SCIP_ROW**            row,                /**< buffer to store pointer to new row */
1680 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be turned into a row */
1681 	   SCIP_CONS*            cons                /**< constraint */
1682 	   )
1683 	{
1684 	   assert(scip != NULL);
1685 	   assert(row != NULL);
1686 	   assert(rowprep != NULL);
1687 	   assert(cons != NULL);
1688 	
1689 	   SCIP_CALL( SCIPcreateEmptyRowCons(scip, row, cons, rowprep->name,
1690 	      rowprep->sidetype == SCIP_SIDETYPE_LEFT  ? rowprep->side : -SCIPinfinity(scip),
1691 	      rowprep->sidetype == SCIP_SIDETYPE_RIGHT ? rowprep->side :  SCIPinfinity(scip),
1692 	      rowprep->local && (SCIPgetDepth(scip) > 0), FALSE, TRUE) );
1693 	
1694 	   SCIP_CALL( SCIPaddVarsToRow(scip, *row, rowprep->nvars, rowprep->vars, rowprep->coefs) );
1695 	
1696 	   return SCIP_OKAY;
1697 	}
1698 	
1699 	/** generates a SCIP_ROW from a rowprep, setting its origin to given separator */
1700 	SCIP_RETCODE SCIPgetRowprepRowSepa(
1701 	   SCIP*                 scip,               /**< SCIP data structure */
1702 	   SCIP_ROW**            row,                /**< buffer to store pointer to new row */
1703 	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be turned into a row */
1704 	   SCIP_SEPA*            sepa                /**< separator */
1705 	   )
1706 	{
1707 	   assert(scip != NULL);
1708 	   assert(row != NULL);
1709 	   assert(rowprep != NULL);
1710 	
1711 	   SCIP_CALL( SCIPcreateEmptyRowSepa(scip, row, sepa, rowprep->name,
1712 	      rowprep->sidetype == SCIP_SIDETYPE_LEFT  ? rowprep->side : -SCIPinfinity(scip),
1713 	      rowprep->sidetype == SCIP_SIDETYPE_RIGHT ? rowprep->side :  SCIPinfinity(scip),
1714 	      rowprep->local && (SCIPgetDepth(scip) > 0), FALSE, TRUE) );
1715 	
1716 	   SCIP_CALL( SCIPaddVarsToRow(scip, *row, rowprep->nvars, rowprep->vars, rowprep->coefs) );
1717 	
1718 	   return SCIP_OKAY;
1719 	}
1720