37 #define PRESOL_NAME "sparsify" 38 #define PRESOL_DESC "eliminate non-zero coefficients" 40 #define PRESOL_PRIORITY -24000 41 #define PRESOL_MAXROUNDS -1 42 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE 44 #define DEFAULT_ENABLECOPY TRUE 45 #define DEFAULT_CANCELLINEAR TRUE 46 #define DEFAULT_PRESERVEINTCOEFS TRUE 47 #define DEFAULT_MAX_CONT_FILLIN 0 48 #define DEFAULT_MAX_BIN_FILLIN 0 49 #define DEFAULT_MAX_INT_FILLIN 0 50 #define DEFAULT_MAXNONZEROS -1 51 #define DEFAULT_MAXCONSIDEREDNONZEROS 70 52 #define DEFAULT_ROWSORT 'd' 53 #define DEFAULT_MAXRETRIEVEFAC 100.0 54 #define DEFAULT_WAITINGFAC 2.0 56 #define MAXSCALE 1000.0 64 struct SCIP_PresolData
74 int maxconsiderednonzeros;
109 scip = (
SCIP*) userptr;
122 return SCIPisEQ(scip, ratio1, ratio2);
147 int maxconsiderednonzeros,
211 bestcancelrate = 0.0;
213 for( i = 0; i < cancelrowlen; ++i )
221 maxlen = cancelrowlen;
222 if( maxconsiderednonzeros >= 0 )
223 maxlen = MIN(cancelrowlen, maxconsiderednonzeros);
225 for( i = 0; i < maxlen; ++i )
227 for( j = i + 1; j < maxlen; ++j )
247 assert(cancelrowinds[i] < cancelrowinds[j]);
249 if( cancelrowinds[i1] < cancelrowinds[i2] )
251 rowvarpair.
varindex1 = cancelrowinds[i1];
252 rowvarpair.
varindex2 = cancelrowinds[i2];
253 rowvarpair.
varcoef1 = cancelrowvals[i1];
254 rowvarpair.
varcoef2 = cancelrowvals[i2];
258 rowvarpair.
varindex1 = cancelrowinds[i2];
259 rowvarpair.
varindex2 = cancelrowinds[i1];
260 rowvarpair.
varcoef1 = cancelrowvals[i2];
261 rowvarpair.
varcoef2 = cancelrowvals[i1];
267 if( eqrowvarpair == NULL || eqrowvarpair->
rowindex == rowidx )
275 if( rowiseq && (cancelrowlen < eqrowlen || (cancelrowlen == eqrowlen && rowidx < eqrowvarpair->
rowindex)) )
294 while( a < cancelrowlen && b < eqrowlen )
296 if( cancelrowinds[a] == eqrowinds[b] )
300 newcoef = cancelrowvals[a] + scale * eqrowvals[b];
316 COPYSIGN(1.0, newcoef) != COPYSIGN(1.0, cancelrowvals[a]) )
321 if( (cancelrowvals[a] > 0.0 && !
SCIPisInfinity(scip, cancelrhs)) ||
350 else if( cancelrowinds[a] < eqrowinds[b] )
360 if( ++nintfillin > maxintfillin )
373 if( ++ncontfillin > maxcontfillin )
385 cancelrate = ncancel / (
SCIP_Real) eqrowlen;
387 if( cancelrate < mincancelrate )
390 while( b < eqrowlen )
396 if( ++nbinfillin > maxbinfillin )
401 if( ++nintfillin > maxintfillin )
406 if( ++ncontfillin > maxcontfillin )
411 if( ncontfillin > maxcontfillin || nbinfillin > maxbinfillin || nintfillin > maxintfillin )
414 ntotfillin = nbinfillin + nintfillin + ncontfillin;
416 if( cancelrate > bestcancelrate )
418 bestnfillin = ntotfillin;
421 bestcancelrate = cancelrate;
424 if( cancelrate == 1.0 )
429 if( bestcand != -1 && bestcancelrate == 1.0 )
456 cancellhs += bestscale * eqrhs;
458 cancelrhs += bestscale * eqrhs;
461 while( a < cancelrowlen && b < eqrowlen )
463 if( cancelrowinds[a] == eqrowinds[b] )
465 SCIP_Real val = cancelrowvals[a] + bestscale * eqrowvals[b];
469 tmpinds[tmprowlen] = cancelrowinds[a];
470 tmpvals[tmprowlen] = val;
478 else if( cancelrowinds[a] < eqrowinds[b] )
480 tmpinds[tmprowlen] = cancelrowinds[a];
481 tmpvals[tmprowlen] = cancelrowvals[a];
487 tmpinds[tmprowlen] = eqrowinds[b];
488 tmpvals[tmprowlen] = eqrowvals[b] * bestscale;
495 while( a < cancelrowlen )
497 tmpinds[tmprowlen] = cancelrowinds[a];
498 tmpvals[tmprowlen] = cancelrowvals[a];
503 while( b < eqrowlen )
505 tmpinds[tmprowlen] = eqrowinds[b];
506 tmpvals[tmprowlen] = eqrowvals[b] * bestscale;
517 cancelrowlen = tmprowlen;
532 for( i = 0; i < cancelrowlen; ++i )
537 cancellhs, cancelrhs,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE,
FALSE) );
541 #ifdef SCIP_MORE_DEBUG 553 *nchgcoefs += nchgcoef;
555 *nfillin += bestnfillin;
562 *nuseless -= nretrieves;
563 *nuseless =
MAX(*nuseless, 0);
570 *nuseless += nretrieves;
589 assert(presoldata != NULL);
593 presoldata->nfailures = 0;
594 presoldata->nwaitingcalls = 0;
598 presoldata->nfailures++;
599 presoldata->nwaitingcalls = (int)(presoldata->waitingfac*(
SCIP_Real)presoldata->nfailures);
614 assert(
scip != NULL);
615 assert(presol != NULL);
620 assert(presoldata != NULL);
621 if( presoldata->enablecopy )
656 assert(result != NULL);
668 if( presoldata->nwaitingcalls > 0 )
670 presoldata->nwaitingcalls--;
671 SCIPdebugMsg(
scip,
"skipping sparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
672 presoldata->nwaitingcalls);
693 if( initialized && complete )
698 for( i = 0; i < nrows; i++ )
717 for( r = 0; r < nrows; r++ )
726 if( nnonz >= 2 && (presoldata->maxnonzeros < 0 || nnonz <= presoldata->maxnonzeros)
737 for( i = 0; i < nnonz; ++i )
745 if( presoldata->maxconsiderednonzeros >= 0 )
746 nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
748 npairs = (nnonz * (nnonz - 1)) / 2;
749 if( nvarpairs + npairs > varpairssize )
753 varpairssize = newsize;
761 failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
763 for( i = 0; i < nnonz; ++i )
765 for( j = i + 1; j < nnonz; ++j )
770 assert(nvarpairs < varpairssize);
771 assert(varpairs != NULL);
773 i1 = perm[(i + failshift) % nnonz];
774 i2 = perm[(j + failshift) % nnonz];
777 if( rowinds[i1] < rowinds[i2])
779 varpairs[nvarpairs].
varindex1 = rowinds[i1];
780 varpairs[nvarpairs].
varindex2 = rowinds[i2];
781 varpairs[nvarpairs].
varcoef1 = rowvals[i1];
782 varpairs[nvarpairs].
varcoef2 = rowvals[i2];
786 varpairs[nvarpairs].
varindex1 = rowinds[i2];
787 varpairs[nvarpairs].
varindex2 = rowinds[i1];
788 varpairs[nvarpairs].
varcoef1 = rowvals[i2];
789 varpairs[nvarpairs].
varcoef2 = rowvals[i1];
798 for( r = 0; r < nvarpairs; ++r )
803 assert(varpairs != NULL);
833 if( presoldata->rowsort ==
'i' || presoldata->rowsort ==
'd' )
837 for( r = 0; r < nrows; ++r )
839 if( presoldata->rowsort ==
'i' )
841 for( r = 0; r < nrows; ++r )
844 else if( presoldata->rowsort ==
'd' )
846 for( r = 0; r < nrows; ++r )
853 assert(presoldata->rowsort ==
'n');
861 oldnchgcoefs = *nchgcoefs;
862 for( r = 0; r < nrows && nuseless <= maxuseless; r++ )
866 rowidx = rowidxsorted != NULL ? rowidxsorted[r] : r;
879 presoldata->maxcontfillin, presoldata->maxintfillin, presoldata->maxbinfillin, \
880 presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
881 &nuseless, nchgcoefs, &numcancel, &nfillin) );
894 presoldata->ncancels += numcancel;
895 presoldata->nfillin += nfillin;
900 " (%.1fs) sparsify %s: %d/%d (%.1f%%) nonzeros canceled" 901 " - in total %d canceled nonzeros, %d changed coefficients, %d added nonzeros\n",
902 SCIPgetSolvingTime(scip), (nuseless > maxuseless ?
"aborted" :
"finished"), numcancel,
910 SCIPdebugMsg(scip,
"sparsify failure statistic: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
911 presoldata->nwaitingcalls);
917 presoldata->nwaitingcalls = INT_MAX;
937 assert(presoldata != NULL);
953 presoldata->ncancels = 0;
954 presoldata->nfillin = 0;
955 presoldata->nfailures = 0;
956 presoldata->nwaitingcalls = 0;
981 "presolving/sparsify/enablecopy",
982 "should sparsify presolver be copied to sub-SCIPs?",
986 "presolving/sparsify/cancellinear",
987 "should we cancel nonzeros in constraints of the linear constraint handler?",
991 "presolving/sparsify/preserveintcoefs",
992 "should we forbid cancellations that destroy integer coefficients?",
996 "presolving/sparsify/maxcontfillin",
997 "maximal fillin for continuous variables (-1: unlimited)",
1001 "presolving/sparsify/maxbinfillin",
1002 "maximal fillin for binary variables (-1: unlimited)",
1006 "presolving/sparsify/maxintfillin",
1007 "maximal fillin for integer variables including binaries (-1: unlimited)",
1011 "presolving/sparsify/maxnonzeros",
1012 "maximal support of one equality to be used for cancelling (-1: no limit)",
1016 "presolving/sparsify/maxconsiderednonzeros",
1017 "maximal number of considered non-zeros within one row (-1: no limit)",
1021 "presolving/sparsify/rowsort",
1022 "order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)",
1026 "presolving/sparsify/maxretrievefac",
1027 "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
1031 "presolving/sparsify/waitingfac",
1032 "number of calls to wait until next execution as a multiple of the number of useless calls",
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)
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
struct SCIP_PresolData SCIP_PRESOLDATA
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
#define DEFAULT_MAXRETRIEVEFAC
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
void SCIPswapPointers(void **pointer1, void **pointer2)
int SCIPpresolGetNChgCoefs(SCIP_PRESOL *presol)
int SCIPgetNActivePricers(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
static SCIP_DECL_HASHKEYEQ(varPairsEqual)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
#define DEFAULT_ENABLECOPY
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPdebugPrintCons(x, y, z)
#define DEFAULT_WAITINGFAC
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
#define DEFAULT_PRESERVEINTCOEFS
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
cancel non-zeros of the constraint matrix
#define DEFAULT_MAXCONSIDEREDNONZEROS
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
#define DEFAULT_CANCELLINEAR
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
static INLINE uint32_t SCIPrealHashCode(double x)
#define SCIPfreeBufferArrayNull(scip, ptr)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
static SCIP_RETCODE cancelRow(SCIP *scip, SCIP_MATRIX *matrix, SCIP_HASHTABLE *pairtable, int rowidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin)
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
#define DEFAULT_MAX_BIN_FILLIN
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
static SCIP_DECL_PRESOLCOPY(presolCopySparsify)
#define SCIPhashTwo(a, b)
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
#define SCIPallocBufferArray(scip, ptr, num)
#define DEFAULT_MAX_CONT_FILLIN
static SCIP_DECL_HASHKEYVAL(varPairHashval)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
static SCIP_DECL_PRESOLINIT(presolInitSparsify)
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
int SCIPgetNConss(SCIP *scip)
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
SCIP_Bool SCIPisStopped(SCIP *scip)
#define DEFAULT_MAX_INT_FILLIN
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
#define DEFAULT_MAXNONZEROS
static SCIP_DECL_PRESOLFREE(presolFreeSparsify)
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
SCIP_RETCODE SCIPincludePresolSparsify(SCIP *scip)
#define SCIPcombineTwoInt(a, b)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
#define SCIPreallocBufferArray(scip, ptr, num)
static SCIP_DECL_PRESOLEXEC(presolExecSparsify)