misc_rowprep.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 #define ROWPREP_SCALEUP_VIOLNONZERO (10.0*SCIPepsilon(scip)) /**< minimal violation for considering up-scaling of rowprep (we want to avoid upscaling very small violations) */
41 #define ROWPREP_SCALEUP_MINVIOLFACTOR 2.0 /**< scale up will target a violation of ~MINVIOLFACTOR*minviol, where minviol is given by caller */
42 #define ROWPREP_SCALEUP_MAXMINCOEF (1.0 / SCIPfeastol(scip)) /**< scale up only if min. coef is below this number (before scaling) */
43 #define ROWPREP_SCALEUP_MAXMAXCOEF SCIPgetHugeValue(scip) /**< scale up only if max. coef will not exceed this number by scaling */
44 #define ROWPREP_SCALEUP_MAXSIDE SCIPgetHugeValue(scip) /**< scale up only if side will not exceed this number by scaling */
45 #define ROWPREP_SCALEDOWN_MINMAXCOEF (1.0 / SCIPfeastol(scip)) /**< scale down if max. coef is at least this number (before scaling) */
46 #define ROWPREP_SCALEDOWN_MINCOEF SCIPfeastol(scip) /**< scale down only if min. coef does not drop below this number by scaling */
52 /** adds a variable to the `rowprep->modifiedvars` array, if recording of modification has been enabled and the variable is not fixed */
68 SCIPdebugMsg(scip, "skip recording modification for fixed variable <%s>[%g,%g]\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
78 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &rowprep->modifiedvars, oldsize, rowprep->modifiedvarssize) );
181 SCIPdebugMsg(scip, "cut coefficients have very large range: mincoef = %g maxcoef = %g\n", mincoef, maxcoef);
190 * with ref(x) the reference point we try to eliminate, this would weaken the cut by a*(lb(x)-ref(x))
196 * - Also one could think of not completely removing the coefficient but do an aggregation that makes the coefficient look better. For instance:
198 * then you can't really remove $`y`$. However, you could aggregate it with $`0.9 \cdot (y \leq b)`$ to get
199 * $`a x + y \leq r + 0.9 b`$, which has better numerics (and hopefully still cuts the point... actually, if for the point you want to separate, $`y^* = b`$, then the violation is the same)
211 /* make sure reference point is something reasonable within the bounds, preferable the value from the solution */
216 /* check whether we can eliminate coef*var from rowprep and how much we would loose w.r.t. ref(x) */
217 if( ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) )
227 assert((coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT));
239 ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) ? '>' : '<',
240 ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) ? lb : ub, loss[pos]);
255 if( ((coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT)) )
264 assert((coef < 0.0 && rowprep->sidetype == SCIP_SIDETYPE_RIGHT) || (coef > 0.0 && rowprep->sidetype == SCIP_SIDETYPE_LEFT));
345 /* scale by approx. scalefactor, if minimal coef is not so large yet and maximal coef and rhs don't get huge by doing so (or have been so before) */
348 if( mincoef < ROWPREP_SCALEUP_MAXMINCOEF && scalefactor * maxcoef < ROWPREP_SCALEUP_MAXMAXCOEF && scalefactor * REALABS(rowprep->side) < ROWPREP_SCALEUP_MAXSIDE )
382 /* if minimal violation would be lost by scaling down, then increase scalefactor such that minviol is still reached */
391 * myviol < minviol (-> scalefactor > 1) or mincoef < feastol before scaling is possible, in which case we also don't scale down
393 if( scalefactor < 1.0 && scalefactor * REALABS(rowprep->coefs[rowprep->nvars-1]) > ROWPREP_SCALEDOWN_MINCOEF )
414 SCIP_Real* viol /**< NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed */
427 * Thus, we anticipate by rounding coef here, but also modify constant so that cut is still valid (if possible),
459 SCIPdebugMsg(scip, "var <%s> [%g,%g] has almost integral coef %.15g, round coefficient to %g and add constant %g\n",
460 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), coef, roundcoef, (coef-roundcoef) * xbnd);
465 /* if there is no bound, then we make the coef integral, too, even though this will introduce an error
466 * however, SCIP_ROW would do this anyway, but doing this here might eliminate some epsilon coefs (so they don't determine mincoef below)
469 SCIPdebugMsg(scip, "var <%s> [%g,%g] has almost integral coef %.15g, round coefficient to %g without relaxing side (!)\n",
493 SCIP_Real* viol /**< NULL or violation of cut in sol (input), set to SCIP_INVALID if some coef changed */
496 /* SCIP_ROW handling will replace a side close to 0 by 0.0, even if that makes the row more restrictive
587 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*target)->coefs, source->coefs, source->varssize) );
591 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*target)->vars, source->vars, source->varssize) );
787 SCIPinfoMessage(scip, file, "%+.15g*<%s> ", rowprep->coefs[i], SCIPvarGetName(rowprep->vars[i]));
790 SCIPinfoMessage(scip, file, rowprep->sidetype == SCIP_SIDETYPE_LEFT ? ">= %.15g\n" : "<= %.15g\n", rowprep->side);
825 SCIPinfoMessage(scip, file, "%+.15g*<%s>(%.15g) ", coef, SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
837 SCIPinfoMessage(scip, file, rowprep->sidetype == SCIP_SIDETYPE_LEFT ? ">= %.15g" : "<= %.15g", rowprep->side);
935 * Can return whether the violation value is reliable from a floating-point accuracy point of view.
936 * The value will not be deemed reliable when its calculation involved the subtraction of large numbers.
937 * To be precise, the violation of an inequality \f$ \sum_i a_ix_i \leq b \f$ in a solution \f$x^*\f$ is deemed
944 SCIP_Bool* reliable /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */
959 * HOWEVER, they become column variables when they are added to a row (via SCIPaddVarsToRow below).
961 * So when calculating the row activity for an LP solution, we treat loose variable as if they were already column variables.
968 * Having different contradicting infinities is something I would now know how to handle and am ignoring now.
1010 * To be more robust w.r.t. scaling of the row, we look at the exponent of the quotient maxterm/violation
1018 (void) frexp(maxterm / violation, &exponent); /* difference in exponents for maxterm and violation */
1028 /** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable
1087 if( rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbLocal(rowprep->vars[i]), SCIPvarGetUbLocal(rowprep->vars[i])) )
1095 else if( !rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbGlobal(rowprep->vars[i]), SCIPvarGetUbGlobal(rowprep->vars[i])) )
1124 if( rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbLocal(rowprep->vars[i]), SCIPvarGetUbLocal(rowprep->vars[i])) )
1132 else if( !rowprep->local && SCIPisRelEQ(scip, SCIPvarGetLbGlobal(rowprep->vars[i]), SCIPvarGetUbGlobal(rowprep->vars[i])) )
1151 * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the row.
1155 * Scales coefficients and side down if they are large and if the minimal violation is still reached.
1156 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
1159 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
1160 * Thus, the coefrange can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
1174 SCIP_Real* viol, /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
1175 SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
1213 myviol = SCIPgetRowprepViolation(scip, rowprep, sol, success != NULL ? &violreliable : NULL); /*lint !e826*/
1227 /* if there is interest in achieving some minimal violation, then possibly scale up to increase violation
1228 * this updates myviol; since this is only scaling the cut, it doesn't change anything about the reliability of the violation value */
1234 /* in case scip minefficacy could not be reached or was smaller than minviol, try with the given minviol */
1239 rowprepCleanupScaledown(scip, rowprep, &myviol, MAX(SCIPgetSepaMinEfficacy(scip), minviol)); /*lint !e666*/
1274 if( rowprep->nvars > 0 && REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]) > maxcoefrange )
1276 SCIPdebugMsg(scip, "rowprep coefrange %g is above the limit %g\n", REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]), maxcoefrange);
1283 SCIPdebugMsg(scip, "rowprep coefficient %g is beyond value for infinity\n", rowprep->coefs[0]);
1315 * I leave this assert off for now, since getting the tolerance in the EQ correctly is not trivial. We recompute viol below anyway.
1317 /* assert(myviol == SCIP_INVALID || SCIPisEQ(scip, myviol, SCIPgetRowprepViolation(scip, rowprep, sol, NULL))); */
1328 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
1331 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
1334 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
1335 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
1342 * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation.
1349 SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
1434 if( rowprep->nvars > 0 && REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]) > maxcoefrange )
1436 SCIPdebugMsg(scip, "rowprep coefrange %g is above the limit %g\n", REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1]), maxcoefrange);
1443 SCIPdebugMsg(scip, "rowprep coefficient %g is beyond value for infinity\n", rowprep->coefs[0]);
1458 /** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible.
1460 * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep.
1461 * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon,
1475 SCIP_Real minscaleup, /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */
1476 SCIP_Bool* success /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */
1487 /* find the smallest fractionality in rowprep sides and coefficients and the largest absolute coefficient/side */
1518 SCIPdebugMsg(scip, "minimal fractional of rowprep coefs and side is %g, max coef/side is %g\n", MIN(minfrac, minfrac0), maxval);
1520 /* in order for SCIP_ROW to not modify the coefs and side, they need to be more than epsilon way from an integer value
1522 * If the integer value is 0, then scaling up the rowprep by epsilon/minfrac will increase its minimal fractionality
1524 * If the integer value is not zero, then scaling up the rowprep by a well-chosen fractional number alpha will increase
1525 * the minimal fractionality by about alpha*integer-value mod 1. To reduce the chance that alpha*integer-value is integral,
1528 * If the scaling increases the maximal coef/value beyond SCIPinfinity, then the rowprep would be useless.
1577 SCIPinfoMessage(scip, NULL, "scaled up rowprep by %g (minfrac=%g, minscaleup=%g), maxval is now %g\n", factor, minfrac, minscaleup, maxval);
void SCIProwprepRecordModifications(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:759
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1413
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
static SCIP_RETCODE rowprepCleanupSortTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:89
Definition: struct_scip.h:59
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1149
public methods for memory management
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
Definition: misc_rowprep.c:1344
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:769
Definition: struct_var.h:198
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
Definition: misc_rowprep.c:574
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
Definition: misc_rowprep.c:1669
miscellaneous datastructures
public methods for problem variables
SCIP_SIDETYPE SCIProwprepGetSidetype(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:644
Definition: type_lp.h:55
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: struct_sepa.h:37
static SCIP_RETCODE rowprepCleanupIntegralCoefs(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol)
Definition: misc_rowprep.c:411
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:855
public methods for separator plugins
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
Definition: misc_rowprep.c:1646
public methods for numerical tolerances
Definition: struct_sol.h:64
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:624
public methods for the branch-and-bound tree
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
Definition: struct_cons.h:37
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
Definition: struct_cons.h:117
SCIP_Real SCIPscaleupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
Definition: misc_rowprep.c:1472
static void rowprepCleanupScaledown(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol, SCIP_Real minviol)
Definition: misc_rowprep.c:366
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
Definition: misc_rowprep.c:737
SCIP_Bool SCIPisRowprepViolationReliable(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
Definition: misc_rowprep.c:1032
Definition: type_retcode.h:33
SCIP_RETCODE SCIPgetRowprepRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
Definition: misc_rowprep.c:1623
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:558
internal methods for global SCIP settings
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: misc_rowprep.c:714
SCIP main data structure.
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
Definition: misc_rowprep.c:940
SCIP_VAR ** SCIProwprepGetModifiedVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:684
static SCIP_RETCODE rowprepCleanupImproveCoefrange(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefrange)
Definition: misc_rowprep.c:148
int SCIProwprepGetNModifiedVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:674
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:728
static void rowprepCleanupScaleup(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol, SCIP_Real minviol)
Definition: misc_rowprep.c:316
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:1056
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
Definition: misc_rowprep.c:1594
Definition: struct_lp.h:192
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1444
Definition: type_var.h:41
public methods for the LP relaxation, rows and columns
methods for sorting joint arrays of various types
void SCIPprintRowprepSol(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
Definition: misc_rowprep.c:794
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
public methods for solutions
SCIP_Real SCIPsetGetSepaMaxCoefRatioRowprep(SCIP_SET *set)
Definition: set.c:5932
static SCIP_RETCODE rowprepRecordModifiedVar(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var)
Definition: misc_rowprep.c:54
void SCIPsortDownRealRealPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, void **ptrarray, int len)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1712
Definition: type_lp.h:56
public methods for message handling
void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:538
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:881
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real minviol, SCIP_Real *viol, SCIP_Bool *success)
Definition: misc_rowprep.c:1169
SCIPallocBlockMemory(scip, subsol))
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:748
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
Definition: misc_rowprep.c:906
Definition: objbenders.h:33
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
#define SCIPduplicateBlockMemory(scip, ptr, source)
Definition: scip_mem.h:94
preparation of a linear inequality to become a SCIP_ROW
static void rowprepCleanupSide(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real *viol)
Definition: misc_rowprep.c:490
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:614
Definition: struct_misc.h:277