presol_sparsify.c
Go to the documentation of this file.
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
65 #define PRESOL_PRIORITY -24000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
66 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
67 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
70 #define DEFAULT_CANCELLINEAR TRUE /**< should we cancel nonzeros in constraints of the linear constraint handler? */
71 #define DEFAULT_PRESERVEINTCOEFS TRUE /**< should we forbid cancellations that destroy integer coefficients? */
72 #define DEFAULT_MAX_CONT_FILLIN 0 /**< default value for the maximal fillin for continuous variables */
73 #define DEFAULT_MAX_BIN_FILLIN 0 /**< default value for the maximal fillin for binary variables */
74 #define DEFAULT_MAX_INT_FILLIN 0 /**< default value for the maximal fillin for integer variables (including binary) */
75 #define DEFAULT_MAXNONZEROS -1 /**< maximal support of one equality to be used for cancelling (-1: no limit) */
76 #define DEFAULT_MAXCONSIDEREDNONZEROS 70 /**< maximal number of considered non-zeros within one row (-1: no limit) */
77 #define DEFAULT_ROWSORT 'd' /**< order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros) */
78 #define DEFAULT_MAXRETRIEVEFAC 100.0 /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
79 #define DEFAULT_WAITINGFAC 2.0 /**< number of calls to wait until next execution as a multiple of the number of useless calls */
91 int ncancels; /**< total number of canceled nonzeros (net value, i.e., removed minus added nonzeros) */
98 int maxnonzeros; /**< maximal support of one equality to be used for cancelling (-1: no limit) */
99 int maxconsiderednonzeros;/**< maximal number of considered non-zeros within one row (-1: no limit) */
100 SCIP_Real maxretrievefac; /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
101 SCIP_Real waitingfac; /**< number of calls to wait until next execution as a multiple of the number of useless calls */
102 char rowsort; /**< order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros) */
104 SCIP_Bool cancellinear; /**< should we cancel nonzeros in constraints of the linear constraint handler? */
105 SCIP_Bool preserveintcoefs; /**< should we forbid cancellations that destroy integer coefficients? */
173 SCIP_Bool preserveintcoefs, /**< only perform non-zero cancellation if integrality of coefficients is preserved? */
199 rowiseq = SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, rowidx), SCIPmatrixGetRowRhs(matrix, rowidx));
209 /* for set packing and logicor constraints, only accept equalities where all modified coefficients are cancelled */
242 locks[i] = SCIPmatrixGetColNDownlocks(matrix, cancelrowinds[i]) + SCIPmatrixGetColNUplocks(matrix, cancelrowinds[i]);
301 if( rowiseq && (cancelrowlen < eqrowlen || (cancelrowlen == eqrowlen && rowidx < eqrowvarpair->rowindex)) )
344 /* do not flip signs for non-canceled coefficients if this adds a lock to a variable that had at most one lock
350 /* if we get into this case the variable had a positive coefficient in a <= constraint or a negative
351 * coefficient in a >= constraint, e.g. an uplock. If this was the only uplock we do not abort their
485 /* we accept the best candidate immediately if it does not create any fill-in or alter coefficients */
572 /* swap the temporary arrays so that the cancelrowinds and cancelrowvals arrays, contain the new
597 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, SCIPmatrixGetRowName(matrix, rowidx), cancelrowlen, consvars, cancelrowvals,
617 /* if successful, decrease the useless hashtable retrieves counter; the rationale here is that we want to keep
618 * going if, after many useless calls that almost exceeded the budget, we finally reach a useful section; but we
619 * don't allow a negative build-up for the case that the useful section is all at the beginning and we just want
731 if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
742 SCIPdebugMsg(scip, "skipping sparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
747 /* if we want to cancel only from specialized constraints according to the parameter, then we can skip execution if
751 if( !presoldata->cancellinear && linearhdlr != NULL && SCIPconshdlrGetNConss(linearhdlr) >= SCIPgetNConss(scip) )
796 SCIP_CALL( SCIPhashtableCreate(&pairtable, SCIPblkmem(scip), 1, SCIPhashGetKeyStandard, varPairsEqual, varPairHashval, (void*) scip) );
805 /* consider equalities with support at most maxnonzeros; skip singleton equalities, because these are faster
822 locks[i] = SCIPmatrixGetColNDownlocks(matrix, rowinds[i]) + SCIPmatrixGetColNUplocks(matrix, rowinds[i]);
838 /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
839 * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit, this
840 * results in different variable pairs being tried and avoids trying the same useless cancellations
892 while( (othervarpair = (ROWVARPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &varpairs[r])) != NULL )
897 if( SCIPmatrixGetRowNNonzs(matrix, othervarpair->rowindex) <= SCIPmatrixGetRowNNonzs(matrix, varpairs[r].rowindex) )
912 if( ((SCIP_Longint)SCIPhashtableGetNEntries(pairtable) * (SCIP_Longint)(8 * sizeof(void*))) > (SCIP_Longint)INT_MAX )
957 /* check whether we want to cancel only from specialized constraints; one reasoning behind this may be that
958 * cancelling fractional coefficients requires more numerical care than is currently implemented in method
962 if( !presoldata->cancellinear && SCIPconsGetHdlr(SCIPmatrixGetCons(matrix, rowidx)) == linearhdlr )
995 presoldata->ncancels, SCIPpresolGetNChgCoefs(presol) + *nchgcoefs - oldnchgcoefs, presoldata->nfillin);
1001 SCIPdebugMsg(scip, "sparsify failure statistic: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
1042 /* set the counters in the init (and not in the initpre) callback such that they persist across restarts */
1064 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
1109 &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1113 "order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)",
1118 "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
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)
Definition: scip_presol.c:105
Definition: struct_presol.h:46
Definition: type_result.h:42
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1104
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
public methods for SCIP parameter handling
Definition: struct_scip.h:68
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2496
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1829
Definition: type_result.h:58
public methods for timing
Definition: struct_var.h:207
Definition: type_message.h:54
public methods for presolving plugins
public methods for problem variables
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:447
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)
Definition: scip_param.c:83
public methods for numerical tolerances
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)
Definition: misc.c:2245
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1677
cancel non-zeros of the constraint matrix
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1711
public methods for managing constraints
Definition: type_result.h:44
Definition: struct_cons.h:46
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
Definition: struct_cons.h:126
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:172
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1665
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)
Definition: presol_sparsify.c:164
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1689
static SCIP_DECL_PRESOLCOPY(presolCopySparsify)
Definition: presol_sparsify.c:680
Definition: type_retcode.h:42
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)
Definition: matrix.c:454
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2626
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1653
Definition: presol_sparsify.c:109
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
public methods for constraint handler plugins and constraints
public data structures and miscellaneous methods
Definition: type_set.h:49
static SCIP_DECL_PRESOLINIT(presolInitSparsify)
Definition: presol_sparsify.c:1038
Definition: struct_matrix.h:47
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2557
public methods for matrix
public methods for variable pricer plugins
public methods for nonlinear relaxation
methods for sorting joint arrays of various types
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)
Definition: cons_linear.c:17851
public methods for presolvers
Definition: struct_misc.h:89
general public methods
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)
Definition: scip_param.c:167
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1723
public methods for the probing mode
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
Definition: presol_sparsify.c:654
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
public methods for message output
public methods for message handling
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1617
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2726
static SCIP_DECL_PRESOLFREE(presolFreeSparsify)
Definition: presol_sparsify.c:1022
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1605
Definition: objbenders.h:43
SCIP_RETCODE SCIPincludePresolSparsify(SCIP *scip)
Definition: presol_sparsify.c:1053
public methods for global and local (sub)problems
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)
Definition: scip_param.c:139
Definition: type_result.h:48
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)
Definition: scip_param.c:57
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
static SCIP_DECL_PRESOLEXEC(presolExecSparsify)
Definition: presol_sparsify.c:701
memory allocation routines