35 #define PRESOL_NAME "implfree" 36 #define PRESOL_DESC "exploit implied free variables for multi-aggregation" 37 #define PRESOL_PRIORITY -1000 38 #define PRESOL_MAXROUNDS 0 39 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE 41 #define MAXABSRATIO ((SCIP_Real)1000.0) 42 #define SIDECHANGERATIO ((SCIP_Real)10.0) 68 assert(matrix != NULL);
76 for(; (rowpnt < rowend); rowpnt++, valpnt++)
88 maxactivity += val * ub;
94 maxactivity += val * lb;
119 assert(scip != NULL);
120 assert(matrix != NULL);
128 for(; (rowpnt < rowend); rowpnt++, valpnt++)
140 minactivity += val * lb;
146 minactivity += val * ub;
176 assert(scip != NULL);
177 assert(matrix != NULL);
178 assert(minresactivity != NULL);
179 assert(maxresactivity != NULL);
180 assert(isminsettoinfinity != NULL);
181 assert(ismaxsettoinfinity != NULL);
189 *isminsettoinfinity =
FALSE;
190 *ismaxsettoinfinity =
FALSE;
204 assert(nmaxactposinf >= 1);
205 if( nmaxactposinf == 1 && nmaxactneginf == 0 )
210 *ismaxsettoinfinity =
TRUE;
215 if( (nmaxactneginf + nmaxactposinf) > 0 )
218 *ismaxsettoinfinity =
TRUE;
221 *maxresactivity = maxactivity - val * ub;
226 assert(nminactneginf >= 1);
227 if( nminactneginf == 1 && nminactposinf == 0 )
232 *isminsettoinfinity =
TRUE;
237 if( (nminactneginf + nminactposinf) > 0 )
240 *isminsettoinfinity =
TRUE;
243 *minresactivity = minactivity - val * lb;
250 assert(nmaxactneginf >= 1);
251 if( nmaxactneginf == 1 && nmaxactposinf == 0 )
256 *ismaxsettoinfinity =
TRUE;
261 if( (nmaxactneginf + nmaxactposinf) > 0 )
264 *ismaxsettoinfinity =
TRUE;
267 *maxresactivity = maxactivity - val * lb;
272 assert(nminactposinf >= 1);
273 if( nminactposinf == 1 && nminactneginf == 0 )
278 *isminsettoinfinity =
TRUE;
283 if( (nminactneginf + nminactposinf) > 0 )
286 *isminsettoinfinity =
TRUE;
289 *minresactivity = minactivity - val * ub;
315 assert(rowlb != NULL);
316 assert(lbfound != NULL);
317 assert(rowub != NULL);
318 assert(ubfound != NULL);
326 &isminsettoinfinity, &ismaxsettoinfinity);
335 *rowub = (rhs - minresactivity)/val;
341 *rowlb = (lhs - maxresactivity)/val;
349 *rowlb = (rhs - minresactivity)/val;
355 *rowub = (lhs - maxresactivity)/val;
382 assert(scip != NULL);
383 assert(matrix != NULL);
384 assert(lockedcons != NULL);
385 assert(impllbrowidx != NULL);
386 assert(implubrowidx != NULL);
403 for( ; (colpnt < colend); colpnt++, valpnt++ )
410 if( lockedcons[*colpnt] )
420 &rowlb, &lbfound, &rowub, &ubfound);
422 if( lbfound && rowlb > impliedlb )
425 *impllbrowidx = *colpnt;
428 if( ubfound && rowub < impliedub )
431 *implubrowidx = *colpnt;
458 assert(matrix != NULL);
462 assert(rowcnt > 0 && colcnt > 0);
464 nonzerosold = rowcnt + colcnt - 1;
465 nonzerosnew = (colcnt - 1) * (rowcnt - 1);
484 enumerator =
REALABS( -(val * aggrconst) - oldside );
511 assert(scip != NULL);
512 assert(matrix != NULL);
516 for( row = 0; row < nrows; row++ )
518 maxactposhuge[row] = 0;
519 maxactneghuge[row] = 0;
520 minactposhuge[row] = 0;
521 minactneghuge[row] = 0;
527 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
540 maxactposhuge[row]++;
542 maxactneghuge[row]++;
548 minactposhuge[row]++;
550 minactneghuge[row]++;
558 maxactposhuge[row]++;
560 maxactneghuge[row]++;
566 minactposhuge[row]++;
568 minactneghuge[row]++;
608 assert(nmaxactposinf >= 0);
609 assert(nmaxactneginf >= 0);
610 assert(nminactposinf >= 0);
611 assert(nminactneginf >= 0);
612 assert(maxactposhuge[row] >= 0);
613 assert(maxactneghuge[row] >= 0);
614 assert(minactposhuge[row] >= 0);
615 assert(minactneghuge[row] >= 0);
617 numinf = nmaxactposinf + nmaxactneginf + nminactposinf + nminactneginf;
618 numhuge = maxactposhuge[row] + maxactneghuge[row] + minactposhuge[row] + minactneghuge[row];
627 assert(nmaxactposinf >= 1);
628 if( numinf + numhuge - 1 >= 1 )
633 assert(maxactposhuge[row] >= 1);
634 if( numinf + numhuge - 1 >= 1 )
639 assert(maxactneghuge[row] >= 1);
640 if( numinf + numhuge - 1 >= 1 )
645 if( numinf + numhuge >= 1 )
651 assert(nminactneginf >= 1);
652 if( numinf + numhuge - 1 >= 1 )
657 assert(minactposhuge[row] >= 1);
658 if( numinf + numhuge - 1 >= 1 )
663 assert(minactneghuge[row] >= 1);
664 if( numinf + numhuge - 1 >= 1 )
669 if( numinf + numhuge >= 1 )
677 assert(nmaxactneginf >= 1);
678 if( numinf + numhuge - 1 >= 1 )
683 assert(maxactposhuge[row] >= 1);
684 if( numinf + numhuge - 1 >= 1 )
689 assert(maxactneghuge[row] >= 1);
690 if( numinf + numhuge - 1 >= 1 )
695 if( numinf + numhuge >= 1 )
701 assert(nminactposinf >= 1);
702 if( numinf + numhuge - 1 >= 1 )
707 assert(minactposhuge[row] >= 1);
708 if( numinf + numhuge - 1 >= 1 )
713 assert(minactneghuge[row] >= 1);
714 if( numinf + numhuge - 1 >= 1 )
719 if( numinf + numhuge >= 1 )
753 numericalstable =
TRUE;
762 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
767 if( absval < minabsval )
769 if( absval > maxabsval )
778 numericalstable =
FALSE;
779 return numericalstable;
786 for( ; colpnt < colend; colpnt++, valpnt++ )
798 maxactposhuge, maxactneghuge, minactposhuge, minactneghuge,
799 &minisrelax, &maxisrelax);
801 if( minisrelax || maxisrelax )
803 numericalstable =
FALSE;
818 numericalstable =
FALSE;
827 numericalstable =
FALSE;
833 return numericalstable;
853 assert(scip != NULL);
854 assert(matrix != NULL);
855 assert(newlhs != NULL);
856 assert(newrhs != NULL);
869 *newrhs = rhs - coef * lb;
874 *newlhs = lhs - coef * ub;
881 *newlhs = rhs - coef * lb;
886 *newrhs = lhs - coef * ub;
889 assert(
SCIPisLE(scip, *newlhs, *newrhs));
910 consredundant =
FALSE;
913 getActivityResiduals(scip, matrix, col, row, coef, &minresactivity, &maxresactivity, &isminsettoinfinity, &ismaxsettoinfinity);
915 if( !isminsettoinfinity && !ismaxsettoinfinity )
918 return consredundant;
927 int* nummultiaggvars,
928 int* multiaggequalities,
944 int bestimpllbrowidx;
945 int bestimplubrowidx;
948 assert(scip != NULL);
949 assert(matrix != NULL);
950 assert(multiaggvars != NULL);
951 assert(nummultiaggvars != NULL);
952 assert(multiaggequalities != NULL);
953 assert(consredundant != NULL);
954 assert(lockedcons != NULL);
955 assert(skipvars != NULL);
959 for( r = 0; r < nrows; r++ )
975 bestimpllbrowidx = -1;
976 bestimplubrowidx = -1;
977 bestconsredundant =
FALSE;
979 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
992 if( !skipvars[*rowpnt] &&
isVarImpliedFree(scip, matrix, *rowpnt, r, lockedcons, &tmpimpllbrowidx, &tmpimplubrowidx) )
994 assert(tmpimpllbrowidx >= 0 && tmpimplubrowidx >= 0);
998 maxactposhuge, maxactneghuge, minactposhuge, minactneghuge) )
1003 if( (fillin < bestfillin) || (!bestconsredundant && fillin <= 1.0) )
1005 bestfillin = fillin;
1006 bestvaridx = *rowpnt;
1007 bestimpllbrowidx = tmpimpllbrowidx;
1008 bestimplubrowidx = tmpimplubrowidx;
1009 bestconsredundant =
TRUE;
1015 if( bestconsredundant )
1018 if( fillin < bestfillin )
1020 bestfillin = fillin;
1021 bestvaridx = *rowpnt;
1022 bestimpllbrowidx = tmpimpllbrowidx;
1023 bestimplubrowidx = tmpimplubrowidx;
1030 skipvars[*rowpnt] =
TRUE;
1034 if( bestvaridx > -1 && multiaggvars[bestvaridx] !=
TRUE )
1037 multiaggvars[bestvaridx] =
TRUE;
1038 multiaggequalities[bestvaridx] = r;
1039 lockedcons[bestimpllbrowidx] =
TRUE;
1040 lockedcons[bestimplubrowidx] =
TRUE;
1041 (*nummultiaggvars)++;
1043 if( bestconsredundant )
1045 consredundant[r] =
TRUE;
1046 lockedcons[r] =
TRUE;
1061 assert(
scip != NULL);
1062 assert(presol != NULL);
1080 assert(result != NULL);
1097 if( initialized && complete )
1100 int* multiaggequalities;
1101 int nummultiaggvars;
1138 nummultiaggvars = 0;
1140 consredundant, lockedcons, skipvars, maxactposhuge, maxactneghuge, minactposhuge, minactneghuge);
1142 if( nummultiaggvars > 0 )
1145 for( v = 0; v < ncols; v++ )
1147 if( isvartomultiagg[v] )
1168 row = multiaggequalities[v];
1169 assert(row < nrows);
1186 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1190 multiaggcoef = *valpnt;
1204 assert(multiaggcoef != 0.0);
1208 aggrconst = rhs / multiaggcoef;
1218 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1223 scalars[cnt] = -(*valpnt) / multiaggcoef;
1249 if( consredundant[row] )
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
static SCIP_DECL_PRESOLEXEC(presolExecImplfree)
static void getNumHugeActivities(SCIP *scip, SCIP_MATRIX *matrix, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
static void getActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
SCIP_STAGE SCIPgetStage(SCIP *scip)
static SCIP_Real sideChangeNumericalStable(SCIP *scip, SCIP_Real oldside, SCIP_Real aggrconst, SCIP_Real val)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
static SCIP_Bool isConsRedundant(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
int SCIPgetNActivePricers(SCIP *scip)
static void calcNewSidesAfterAggregation(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef, SCIP_Real *newlhs, SCIP_Real *newrhs)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
static void getMultiaggVars(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool *multiaggvars, int *nummultiaggvars, int *multiaggequalities, SCIP_Bool *consredundant, SCIP_Bool *lockedcons, SCIP_Bool *skipvars, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
static SCIP_DECL_PRESOLCOPY(presolCopyImplfree)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
#define SCIPdebugMsgPrint
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
int SCIPgetNContVars(SCIP *scip)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
const char * SCIPconsGetName(SCIP_CONS *cons)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_Real getMaxActSingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
exploit implied free variables for multi-aggregation
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
SCIP_RETCODE SCIPincludePresolImplfree(SCIP *scip)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
static SCIP_Bool isVarImpliedFree(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Bool *lockedcons, int *impllbrowidx, int *implubrowidx)
#define SCIPallocBufferArray(scip, ptr, num)
static SCIP_Bool numericalStable(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real aggrconst, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
static void getActivityRelax(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real val, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge, SCIP_Bool *minisrelax, SCIP_Bool *maxisrelax)
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
static const SCIP_Real scalars[]
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
static SCIP_Real getFillIn(SCIP_MATRIX *matrix, int col, int row)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Real getMinActSingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
#define BMSclearMemoryArray(ptr, num)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowlb, SCIP_Bool *lbfound, SCIP_Real *rowub, SCIP_Bool *ubfound)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)