62#define PRESOL_NAME "sparsify"
63#define PRESOL_DESC "eliminate non-zero coefficients"
65#define PRESOL_PRIORITY -24000
66#define PRESOL_MAXROUNDS -1
67#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE
69#define DEFAULT_ENABLECOPY TRUE
70#define DEFAULT_CANCELLINEAR TRUE
71#define DEFAULT_PRESERVEINTCOEFS TRUE
72#define DEFAULT_MAX_CONT_FILLIN 0
73#define DEFAULT_MAX_BIN_FILLIN 0
74#define DEFAULT_MAX_INT_FILLIN 0
75#define DEFAULT_MAXNONZEROS -1
76#define DEFAULT_MAXCONSIDEREDNONZEROS 70
77#define DEFAULT_ROWSORT 'd'
78#define DEFAULT_MAXRETRIEVEFAC 100.0
79#define DEFAULT_WAITINGFAC 2.0
81#define MAXSCALE 1000.0
99 int maxconsiderednonzeros;
100 SCIP_Real maxretrievefac;
101 SCIP_Real waitingfac;
103 SCIP_Bool enablecopy;
104 SCIP_Bool cancellinear;
105 SCIP_Bool preserveintcoefs;
172 int maxconsiderednonzeros,
173 SCIP_Bool preserveintcoefs,
174 SCIP_Longint* nuseless,
181 SCIP_Real* cancelrowvals;
184 SCIP_Real bestcancelrate;
190 SCIP_Real* rowvalptr;
194 SCIP_Real mincancelrate;
196 SCIP_Bool swapped =
FALSE;
237 bestcancelrate = 0.0;
239 for(
i = 0;
i < cancelrowlen; ++
i )
247 maxlen = cancelrowlen;
248 if( maxconsiderednonzeros >= 0 )
249 maxlen =
MIN(cancelrowlen, maxconsiderednonzeros);
251 for(
i = 0;
i < maxlen; ++
i )
253 for( j =
i + 1; j < maxlen; ++j )
263 SCIP_Real* eqrowvals;
266 SCIP_Real cancelrate;
273 assert(cancelrowinds[
i] < cancelrowinds[j]);
275 if( cancelrowinds[i1] < cancelrowinds[i2] )
277 rowvarpair.
varindex1 = cancelrowinds[i1];
278 rowvarpair.
varindex2 = cancelrowinds[i2];
279 rowvarpair.
varcoef1 = cancelrowvals[i1];
280 rowvarpair.
varcoef2 = cancelrowvals[i2];
284 rowvarpair.
varindex1 = cancelrowinds[i2];
285 rowvarpair.
varindex2 = cancelrowinds[i1];
286 rowvarpair.
varcoef1 = cancelrowvals[i2];
287 rowvarpair.
varcoef2 = cancelrowvals[i1];
293 if( eqrowvarpair ==
NULL || eqrowvarpair->
rowindex == rowidx )
301 if( rowiseq && (cancelrowlen < eqrowlen || (cancelrowlen == eqrowlen && rowidx < eqrowvarpair->
rowindex)) )
307 scale = -rowvarpair.varcoef1 / eqrowvarpair->
varcoef1;
320 while(
a < cancelrowlen &&
b < eqrowlen )
322 if( cancelrowinds[
a] == eqrowinds[
b] )
326 newcoef = cancelrowvals[
a] + scale * eqrowvals[
b];
378 else if( cancelrowinds[
a] < eqrowinds[
b] )
388 newcoef = scale * eqrowvals[
b];
422 if( ++nintfillin > maxintfillin )
430 if( ++ncontfillin > maxcontfillin )
442 while(
b < eqrowlen )
450 if( ++nintfillin > maxintfillin )
455 if( ++ncontfillin > maxcontfillin )
460 if( ncontfillin > maxcontfillin || nbinfillin > maxbinfillin || nintfillin > maxintfillin )
463 ntotfillin = nintfillin + ncontfillin;
465 if( ntotfillin >= ncancel )
468 cancelrate = (ncancel - ntotfillin) / (SCIP_Real) eqrowlen;
470 if( cancelrate < mincancelrate )
473 if( cancelrate > bestcancelrate )
475 bestnfillin = ntotfillin;
478 bestcancelrate = cancelrate;
481 if( cancelrate == 1.0 )
486 if(
bestcand != -1 && bestcancelrate == 1.0 )
495 SCIP_Real* eqrowvals;
513 cancellhs += bestscale * eqrhs;
515 cancelrhs += bestscale * eqrhs;
518 while(
a < cancelrowlen &&
b < eqrowlen )
520 if( cancelrowinds[
a] == eqrowinds[
b] )
522 SCIP_Real val = cancelrowvals[
a] + bestscale * eqrowvals[
b];
526 tmpinds[tmprowlen] = cancelrowinds[
a];
527 tmpvals[tmprowlen] = val;
535 else if( cancelrowinds[
a] < eqrowinds[
b] )
537 tmpinds[tmprowlen] = cancelrowinds[
a];
538 tmpvals[tmprowlen] = cancelrowvals[
a];
544 tmpinds[tmprowlen] = eqrowinds[
b];
545 tmpvals[tmprowlen] = eqrowvals[
b] * bestscale;
552 while(
a < cancelrowlen )
554 tmpinds[tmprowlen] = cancelrowinds[
a];
555 tmpvals[tmprowlen] = cancelrowvals[
a];
560 while(
b < eqrowlen )
562 tmpinds[tmprowlen] = eqrowinds[
b];
563 tmpvals[tmprowlen] = eqrowvals[
b] * bestscale;
570 *nfillin += bestnfillin;
577 cancelrowlen = tmprowlen;
593 for(
i = 0;
i < cancelrowlen; ++
i )
598 cancellhs, cancelrhs,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE,
FALSE) );
602#ifdef SCIP_MORE_DEBUG
614 *nchgcoefs += nchgcoef;
622 *nuseless -= nretrieves;
623 *nuseless =
MAX(*nuseless, 0);
630 *nuseless += nretrieves;
663 presoldata->nfailures = 0;
664 presoldata->nwaitingcalls = 0;
668 presoldata->nfailures++;
669 presoldata->nwaitingcalls = (int)(presoldata->waitingfac*(SCIP_Real)presoldata->nfailures);
691 if( presoldata->enablecopy )
704 SCIP_Bool initialized;
706 SCIP_Bool infeasible;
723 SCIP_Longint maxuseless;
724 SCIP_Longint nuseless;
739 if( presoldata->nwaitingcalls > 0 )
741 presoldata->nwaitingcalls--;
742 SCIPdebugMsg(
scip,
"skipping sparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
743 presoldata->nwaitingcalls);
762 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
775 if( initialized && complete )
780 for(
i = 0;
i < nrows;
i++ )
799 for(
r = 0;
r < nrows;
r++ )
808 if( nnonz >= 2 && (presoldata->maxnonzeros < 0 || nnonz <= presoldata->maxnonzeros)
819 for(
i = 0;
i < nnonz; ++
i )
827 if( presoldata->maxconsiderednonzeros >= 0 )
828 nnonz =
MIN(nnonz, presoldata->maxconsiderednonzeros);
830 npairs = (nnonz * (nnonz - 1)) / 2;
831 if( nvarpairs + npairs > varpairssize )
835 varpairssize = newsize;
843 failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
845 for(
i = 0;
i < nnonz; ++
i )
847 for( j =
i + 1; j < nnonz; ++j )
852 assert(nvarpairs < varpairssize);
855 i1 = perm[(
i + failshift) % nnonz];
856 i2 = perm[(j + failshift) % nnonz];
859 if( rowinds[i1] < rowinds[i2])
861 varpairs[nvarpairs].
varindex1 = rowinds[i1];
862 varpairs[nvarpairs].
varindex2 = rowinds[i2];
863 varpairs[nvarpairs].
varcoef1 = rowvals[i1];
864 varpairs[nvarpairs].
varcoef2 = rowvals[i2];
868 varpairs[nvarpairs].
varindex1 = rowinds[i2];
869 varpairs[nvarpairs].
varindex2 = rowinds[i1];
870 varpairs[nvarpairs].
varcoef1 = rowvals[i2];
871 varpairs[nvarpairs].
varcoef2 = rowvals[i1];
880 for(
r = 0;
r < nvarpairs; ++
r )
912 if( ((SCIP_Longint)
SCIPhashtableGetNEntries(pairtable) * (SCIP_Longint)(8 *
sizeof(
void*))) > (SCIP_Longint)INT_MAX )
922 if( presoldata->rowsort ==
'i' || presoldata->rowsort ==
'd' )
926 for(
r = 0;
r < nrows; ++
r )
928 if( presoldata->rowsort ==
'i' )
930 for(
r = 0;
r < nrows; ++
r )
933 else if( presoldata->rowsort ==
'd' )
935 for(
r = 0;
r < nrows; ++
r )
942 assert(presoldata->rowsort ==
'n');
948 maxuseless = (
SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)nrows);
950 oldnchgcoefs = *nchgcoefs;
955 rowidx = rowidxsorted !=
NULL ? rowidxsorted[
r] :
r;
968 presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
969 presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
970 presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
971 presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
972 &nuseless, nchgcoefs, &numcancel, &nfillin) );
985 presoldata->ncancels += numcancel;
986 presoldata->nfillin += nfillin;
991 " (%.1fs) sparsify %s: %d/%d (%.1f%%) nonzeros canceled"
992 " - in total %d canceled nonzeros, %d changed coefficients, %d added nonzeros\n",
1001 SCIPdebugMsg(
scip,
"sparsify failure statistic: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
1002 presoldata->nwaitingcalls);
1008 presoldata->nwaitingcalls = INT_MAX;
1044 presoldata->ncancels = 0;
1045 presoldata->nfillin = 0;
1046 presoldata->nfailures = 0;
1047 presoldata->nwaitingcalls = 0;
1072 "presolving/sparsify/enablecopy",
1073 "should sparsify presolver be copied to sub-SCIPs?",
1077 "presolving/sparsify/cancellinear",
1078 "should we cancel nonzeros in constraints of the linear constraint handler?",
1082 "presolving/sparsify/preserveintcoefs",
1083 "should we forbid cancellations that destroy integer coefficients?",
1087 "presolving/sparsify/maxcontfillin",
1088 "maximal fillin for continuous variables (-1: unlimited)",
1092 "presolving/sparsify/maxbinfillin",
1093 "maximal fillin for binary variables (-1: unlimited)",
1097 "presolving/sparsify/maxintfillin",
1098 "maximal fillin for integer variables including binaries (-1: unlimited)",
1102 "presolving/sparsify/maxnonzeros",
1103 "maximal support of one equality to be used for cancelling (-1: no limit)",
1107 "presolving/sparsify/maxconsiderednonzeros",
1108 "maximal number of considered non-zeros within one row (-1: no limit)",
1112 "presolving/sparsify/rowsort",
1113 "order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)",
1117 "presolving/sparsify/maxretrievefac",
1118 "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
1122 "presolving/sparsify/waitingfac",
1123 "number of calls to wait until next execution as a multiple of the number of useless calls",
Constraint handler for linear constraints in their most general form, .
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 SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
#define SCIPhashThree(a, b, c)
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)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
static INLINE uint32_t SCIPrealHashCode(double x)
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
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_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)
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)
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 SCIPswapPointers(void **pointer1, void **pointer2)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
int SCIPpresolGetNChgCoefs(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
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)
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol,)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
assert(minobj< SCIPgetCutoffbound(scip))
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define DEFAULT_MAXCONSIDEREDNONZEROS
#define DEFAULT_MAXNONZEROS
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)
#define DEFAULT_MAX_INT_FILLIN
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
SCIP_RETCODE SCIPincludePresolSparsify(SCIP *scip)
#define DEFAULT_CANCELLINEAR
#define DEFAULT_ENABLECOPY
#define DEFAULT_MAX_CONT_FILLIN
#define DEFAULT_WAITINGFAC
#define DEFAULT_MAXRETRIEVEFAC
#define DEFAULT_MAX_BIN_FILLIN
#define DEFAULT_PRESERVEINTCOEFS
cancel non-zeros of the constraint matrix
public methods for managing constraints
public methods for matrix
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for timing
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHKEYVAL(x)
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
#define SCIP_DECL_PRESOLINIT(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE