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,
248 if( maxconsiderednonzeros >= 0 )
598 cancellhs,
cancelrhs,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE,
FALSE) );
602#ifdef SCIP_MORE_DEBUG
623 *nuseless =
MAX(*nuseless, 0);
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) );
780 for(
i = 0;
i < nrows;
i++ )
799 for(
r = 0;
r < nrows;
r++ )
819 for(
i = 0;
i < nnonz; ++
i )
827 if( presoldata->maxconsiderednonzeros >= 0 )
828 nnonz =
MIN(nnonz, presoldata->maxconsiderednonzeros);
830 npairs = (nnonz * (nnonz - 1)) / 2;
843 failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
845 for(
i = 0;
i < nnonz; ++
i )
847 for(
j =
i + 1;
j < nnonz; ++
j )
859 if( rowinds[
i1] < rowinds[
i2])
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);
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) );
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