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