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