presol_dualsparsify.c
Go to the documentation of this file.
46 * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
83#define PRESOL_PRIORITY -240000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
84#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
85#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
88#define DEFAULT_PRESERVEINTCOEFS FALSE /**< should we forbid cancellations that destroy integer coefficients? */
89#define DEFAULT_PRESERVEGOODLOCKS FALSE /**< should we preserve good locked properties of variables (at most one lock in one direction)? */
90#define DEFAULT_MAX_CONT_FILLIN 1 /**< default value for the maximal fillin for continuous variables */
91#define DEFAULT_MAX_BIN_FILLIN 1 /**< default value for the maximal fillin for binary variables */
92#define DEFAULT_MAX_INT_FILLIN 1 /**< default value for the maximal fillin for integer variables (including binary) */
93#define DEFAULT_MAXCONSIDEREDNONZEROS 70 /**< maximal number of considered nonzeros within one column (-1: no limit) */
94#define DEFAULT_MINELIMINATEDNONZEROS 100 /**< minimal eleminated nonzeros within one column if we need to add a constraint to the problem */
95#define DEFAULT_MAXRETRIEVEFAC 100.0 /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
96#define DEFAULT_WAITINGFAC 2.0 /**< number of calls to wait until next execution as a multiple of the number of useless calls */
114 int maxconsiderednonzeros;/**< maximal number of considered nonzeros within one column (-1: no limit) */
115 int mineliminatednonzeros;/**< minimal eliminated nonzeros within one column if we need to add a constraint to the problem */
116 SCIP_Real maxretrievefac; /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
117 SCIP_Real waitingfac; /**< number of calls to wait until next execution as a multiple of the number of useless calls */
119 SCIP_Bool preserveintcoefs; /**< should we forbid cancellations that destroy integer coefficients? */
120 SCIP_Bool preservegoodlocks; /**< should we preserve good locked properties of variables (at most one lock in one direction)? */
173 return SCIPhashThree(conspair->consindex1, conspair->consindex2, SCIPrealHashCode(conspair->conscoef2 / conspair->conscoef1));
650 SCIPvarIsInitial(aggregatedvar), SCIPvarIsRemovable(aggregatedvar), NULL, NULL, NULL, NULL, NULL) );
664 SCIPdebugMsg(scip, "set debug solution value of %s to %g\n", SCIPvarGetName(newvar), weight1 * val1 + val2);
673 SCIP_CALL( SCIPmultiaggregateVar(scip, aggregatedvar, 2, tmpvars, coefs, constant, &infeasible, &aggregated) );
680 /* create a linear constraint that ensures that var[colidx2].lb <= y - weight1 * var[colidx1] <= var[colidx2].ub;
681 * note that it might happen that vars[colidx2] is not implied free even though it has infinite bounds because
686 SCIPdebugMsg(scip, "create a linear constraint to ensure %g <= %g %s + %g %s <= %g\n", lhs, coefs[0], SCIPvarGetName(tmpvars[0]),
688 (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "dualsparsifycons_%d", presoldata->naggregated);
719 SCIP_Bool preserveintcoefs, /**< only perform nonzero cancellation if integrality of coefficients is preserved? */
724 SCIP_Bool isaddedcons /**< whether a linear constraint required to added to keep the validity */
790 scores[i] = -SCIPmatrixGetRowNNonzs(matrix, cancelcolinds[i]) - 1.0 * cancelcolinds[i] / (ncols);
847 /* if the column we want to cancel is a hashing column (which we stored for canceling other columns),
848 * we will only use the hashing columns for canceling with less nonzeros and if the number of nonzeros
1026 /* if a linear constraint is needed to keep the validity, we require a large nonzero cancellation */
1037 /* recompute whether a variable is still implied free; after some previous multi-aggregations of
1038 * some variables, it might be that other variables that are contained in the same linear rows of the
1061 /* we accept the best candidate immediately if it does not create any fill-in or alter coefficients */
1076 SCIPdebugMsg(scip, "cancelcol %d (%s) candidate column %d (%s) (bestcancelrate = %g, bestscale = %g)\n",
1077 colidx, SCIPvarGetName(cancelvar), bestcand, SCIPvarGetName(vars[bestcand]), bestcancelrate, bestscale);
1141 /* swap the temporary arrays so that the cancelcolinds and cancelcolvals arrays, contain the new
1148 SCIP_CALL( aggregation(scip, matrix, presoldata, vars, colidx, bestcand, ishashingcols[bestcand], -bestscale) );
1150 /* the newly created variable is now at the position bestcand and is assumed to have the same coefficients.
1151 * this is not the case if the variable is not implied free since then a new constraint was added and the
1169 /* if successful, decrease the useless hashtable retrieves counter; the rationale here is that we want to keep
1170 * going if, after many useless calls that almost exceeded the budget, we finally reach a useful section; but we
1171 * don't allow a negative build-up for the case that the useful section is all at the beginning and we just want
1286 * However, SCIPmatrixCreate() only collects the original constraints (not the constraints transformed from cuts)
1297 SCIPdebugMsg(scip, "skipping dualsparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
1420 /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1421 * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit, this
1422 * results in different constraint pairs being tried and avoids trying the same useless cancellations
1475 while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1477 /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1487 /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1523 SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1553 if( SCIPmatrixDownlockConflict(matrix, c) || SCIPmatrixUplockConflict(matrix, c) || SCIPdoNotMultaggrVar(scip, vars[c]) )
1599 /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1600 * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit,
1657 while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1659 /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1669 /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1705 SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1766 /* set the counters in the init (and not in the initpre) callback such that they persist across restarts */
1787 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
1827 &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1832 &presoldata->mineliminatednonzeros, FALSE, DEFAULT_MINELIMINATEDNONZEROS, 0, INT_MAX, NULL, NULL) );
1836 "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
Constraint handler for linear constraints in their most general form, .
methods for debugging
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:17855
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:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
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
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
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
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
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
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPdoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8598
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)
Definition: scip_var.c:8535
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1872
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1812
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1580
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1648
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1592
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1636
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1800
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1625
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1884
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1754
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1568
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1824
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_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1788
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1848
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1836
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
void SCIPmatrixRemoveColumnBounds(SCIP *scip, SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1169
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1614
memory allocation routines
Definition: objbenders.h:44
static SCIP_RETCODE cancelCol(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_HASHTABLE *pairtable, SCIP_Bool *ishashingcols, SCIP_VAR **vars, SCIP_Bool *isblockedvar, int colidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin, SCIP_Bool isaddedcons)
Definition: presol_dualsparsify.c:706
#define DEFAULT_MAXCONSIDEREDNONZEROS
Definition: presol_dualsparsify.c:93
SCIP_RETCODE SCIPincludePresolDualsparsify(SCIP *scip)
Definition: presol_dualsparsify.c:1776
static SCIP_DECL_PRESOLINIT(presolInitDualsparsify)
Definition: presol_dualsparsify.c:1762
static SCIP_DECL_PRESOLFREE(presolFreeDualsparsify)
Definition: presol_dualsparsify.c:1746
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
Definition: presol_dualsparsify.c:424
static SCIP_RETCODE aggregation(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_VAR **vars, int colidx1, int colidx2, SCIP_Bool isimpliedfree, SCIP_Real weight1)
Definition: presol_dualsparsify.c:553
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
Definition: presol_dualsparsify.c:1204
#define DEFAULT_MINELIMINATEDNONZEROS
Definition: presol_dualsparsify.c:94
static SCIP_Real getMinActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
Definition: presol_dualsparsify.c:232
static SCIP_DECL_PRESOLEXEC(presolExecDualsparsify)
Definition: presol_dualsparsify.c:1251
static SCIP_DECL_PRESOLCOPY(presolCopyDualsparsify)
Definition: presol_dualsparsify.c:1229
static void getImpliedBounds(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
Definition: presol_dualsparsify.c:492
static SCIP_DECL_HASHKEYVAL(consPairHashval)
Definition: presol_dualsparsify.c:167
static SCIP_Real getMaxActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
Definition: presol_dualsparsify.c:178
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
Definition: presol_dualsparsify.c:286
cancel nonzeros of the constraint matrix based on the columns
public methods for managing constraints
public methods for matrix
public methods for message output
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
general public methods
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 querying solving statistics
public methods for timing
public methods for SCIP variables
Definition: presol_dualsparsify.c:125
Definition: struct_cons.h:47
Definition: struct_misc.h:90
Definition: struct_matrix.h:48
Definition: struct_presol.h:47
Definition: struct_var.h:208
Definition: struct_scip.h:70