Scippy

SCIP

Solving Constraint Integer Programs

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