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