Detailed Description
cancel nonzeros of the constraint matrix based on the columns
This presolver attempts to cancel non-zero entries of the constraint matrix by adding scaled columns to other columns.
In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have
| A_{j.} | - | A_{j.} - s*A_{k.} | > eta,
where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is nonimplied free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem to keep the bounds constraints of variable x_k.
Further information can be found in Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
Definition in file presol_dualsparsify.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/presol_dualsparsify.h"
#include "scip/pub_cons.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | ColConsPair |
Macros | |
#define | PRESOL_NAME "dualsparsify" |
#define | PRESOL_DESC "eliminate non-zero coefficients" |
#define | PRESOL_PRIORITY -240000 |
#define | PRESOL_MAXROUNDS -1 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_ENABLECOPY TRUE |
#define | DEFAULT_PRESERVEINTCOEFS FALSE |
#define | DEFAULT_PRESERVEGOODLOCKS FALSE |
#define | DEFAULT_MAX_CONT_FILLIN 1 |
#define | DEFAULT_MAX_BIN_FILLIN 1 |
#define | DEFAULT_MAX_INT_FILLIN 1 |
#define | DEFAULT_MAXCONSIDEREDNONZEROS 70 |
#define | DEFAULT_MINELIMINATEDNONZEROS 100 |
#define | DEFAULT_MAXRETRIEVEFAC 100.0 |
#define | DEFAULT_WAITINGFAC 2.0 |
#define | MAXSCALE 1000.0 |
Typedefs | |
typedef struct ColConsPair | COLCONSPAIR |
Functions | |
static | SCIP_DECL_HASHKEYEQ (consPairsEqual) |
static | SCIP_DECL_HASHKEYVAL (consPairHashval) |
static SCIP_Real | getMaxActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col) |
static SCIP_Real | getMinActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col) |
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) |
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) |
static void | getImpliedBounds (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied) |
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) |
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) |
static void | updateFailureStatistic (SCIP_PRESOLDATA *presoldata, SCIP_Bool success) |
static | SCIP_DECL_PRESOLCOPY (presolCopyDualsparsify) |
static | SCIP_DECL_PRESOLEXEC (presolExecDualsparsify) |
static | SCIP_DECL_PRESOLFREE (presolFreeDualsparsify) |
static | SCIP_DECL_PRESOLINIT (presolInitDualsparsify) |
SCIP_RETCODE | SCIPincludePresolDualsparsify (SCIP *scip) |
Macro Definition Documentation
◆ PRESOL_NAME
#define PRESOL_NAME "dualsparsify" |
Definition at line 71 of file presol_dualsparsify.c.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDualsparsify().
◆ PRESOL_DESC
#define PRESOL_DESC "eliminate non-zero coefficients" |
Definition at line 72 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ PRESOL_PRIORITY
#define PRESOL_PRIORITY -240000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 74 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 75 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ PRESOL_TIMING
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 76 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_ENABLECOPY
#define DEFAULT_ENABLECOPY TRUE |
should dualsparsify presolver be copied to sub-SCIPs?
Definition at line 78 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_PRESERVEINTCOEFS
#define DEFAULT_PRESERVEINTCOEFS FALSE |
should we forbid cancellations that destroy integer coefficients?
Definition at line 79 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_PRESERVEGOODLOCKS
#define DEFAULT_PRESERVEGOODLOCKS FALSE |
should we preserve good locked properties of variables (at most one lock in one direction)?
Definition at line 80 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MAX_CONT_FILLIN
#define DEFAULT_MAX_CONT_FILLIN 1 |
default value for the maximal fillin for continuous variables
Definition at line 81 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MAX_BIN_FILLIN
#define DEFAULT_MAX_BIN_FILLIN 1 |
default value for the maximal fillin for binary variables
Definition at line 82 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MAX_INT_FILLIN
#define DEFAULT_MAX_INT_FILLIN 1 |
default value for the maximal fillin for integer variables (including binary)
Definition at line 83 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MAXCONSIDEREDNONZEROS
#define DEFAULT_MAXCONSIDEREDNONZEROS 70 |
maximal number of considered nonzeros within one column (-1: no limit)
Definition at line 84 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MINELIMINATEDNONZEROS
#define DEFAULT_MINELIMINATEDNONZEROS 100 |
minimal eleminated nonzeros within one column if we need to add a constraint to the problem
Definition at line 85 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_MAXRETRIEVEFAC
#define DEFAULT_MAXRETRIEVEFAC 100.0 |
limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints
Definition at line 86 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ DEFAULT_WAITINGFAC
#define DEFAULT_WAITINGFAC 2.0 |
number of calls to wait until next execution as a multiple of the number of useless calls
Definition at line 87 of file presol_dualsparsify.c.
Referenced by SCIPincludePresolDualsparsify().
◆ MAXSCALE
#define MAXSCALE 1000.0 |
maximal allowed scale for cancelling nonzeros
Definition at line 89 of file presol_dualsparsify.c.
Referenced by buildFlowCover(), and cancelCol().
Typedef Documentation
◆ COLCONSPAIR
typedef struct ColConsPair COLCONSPAIR |
Definition at line 126 of file presol_dualsparsify.c.
Function Documentation
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both keys are equal
Definition at line 134 of file presol_dualsparsify.c.
References ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, SCIP_Real, and SCIPisEQ().
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 160 of file presol_dualsparsify.c.
References ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, SCIPhashThree, and SCIPrealHashCode().
◆ getMaxActivitySingleRowWithoutCol()
|
static |
calculate maximal activity of one row without one specific column
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints row row index col column index
Definition at line 171 of file presol_dualsparsify.c.
References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by getMinMaxActivityResiduals().
◆ getMinActivitySingleRowWithoutCol()
|
static |
calculate minimal activity of one row without one specific column
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints row row index col column index
Definition at line 225 of file presol_dualsparsify.c.
References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().
Referenced by getMinMaxActivityResiduals().
◆ getMinMaxActivityResiduals()
|
static |
get minimal and maximal residual activity without one specified column
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints col column index row row index val coefficient of this variable in this row minresactivity minimum residual activity of this row maxresactivity maximum residual activity of this row isminsettoinfinity flag indicating if minresactiviy is set to infinity ismaxsettoinfinity flag indicating if maxresactiviy is set to infinity
Definition at line 279 of file presol_dualsparsify.c.
References FALSE, getMaxActivitySingleRowWithoutCol(), getMinActivitySingleRowWithoutCol(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), and TRUE.
Referenced by getVarBoundsOfRow().
◆ getVarBoundsOfRow()
|
static |
calculate the upper and lower bound of one variable from one row
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints col column index of variable row row index val coefficient of this column in this row rowub upper bound of row ubfound flag indicating that an upper bound was calculated rowlb lower bound of row lbfound flag indicating that a lower bound was caluclated
Definition at line 417 of file presol_dualsparsify.c.
References FALSE, getMinMaxActivityResiduals(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.
Referenced by getImpliedBounds().
◆ getImpliedBounds()
|
static |
detect implied variable bounds
- Parameters
-
scip SCIP main data structure matrix matrix containing the constraints col column index for implied free test ubimplied flag indicating an implied upper bound lbimplied flag indicating an implied lower bound
Definition at line 485 of file presol_dualsparsify.c.
References FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColLb(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColUb(), SCIPmatrixGetColValPtr(), and TRUE.
Referenced by aggregation(), cancelCol(), and SCIP_DECL_PRESOLEXEC().
◆ aggregation()
|
static |
y = weight1 * var[colidx1] + var[colidx2]
- Parameters
-
scip SCIP datastructure matrix matrix datastructure presoldata presolver data vars the current variables colidx1 one of the indexes of column to try nonzero cancellation for colidx2 one of the indexes of column to try nonzero cancellation for isimpliedfree is the aggregated variable implied free? weight1 weight variable one in the aggregated expression
Definition at line 546 of file presol_dualsparsify.c.
References FALSE, getImpliedBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdoNotMultaggrVar(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixRemoveColumnBounds(), SCIPmultiaggregateVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsInitial(), SCIPvarIsIntegral(), SCIPvarIsRemovable(), and TRUE.
Referenced by cancelCol().
◆ cancelCol()
|
static |
try nonzero cancellation for given column
- Parameters
-
scip SCIP datastructure matrix the constraint matrix presoldata presolver data pairtable the hashtable containing COLCONSPAIR's of equations ishashingcols array to indicates whether it is impliedfree or not vars array to store the current variables isblockedvar array to indicates whether it is blocked or not colidx index of column to try nonzero cancellation for maxcontfillin maximal fill-in allowed for continuous variables maxintfillin maximal fill-in allowed for integral variables maxbinfillin maximal fill-in allowed for binary variables maxconsiderednonzeros maximal number of nonzeros to consider for cancellation preserveintcoefs only perform nonzero cancellation if integrality of coefficients is preserved? nuseless pointer to update number of useless hashtable retrieves nchgcoefs pointer to update number of changed coefficients ncanceled pointer to update number of canceled nonzeros nfillin pointer to update the produced fill-in isaddedcons whether a linear constraint required to added to keep the validity
Definition at line 699 of file presol_dualsparsify.c.
References a, aggregation(), b, ColConsPair::colindex, ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, getImpliedBounds(), MAX, MAXSCALE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), SCIPisZero(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPsortRealInt(), SCIPswapPointers(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
◆ updateFailureStatistic()
|
static |
updates failure counter after one execution
- Parameters
-
presoldata presolver data success was this execution successful?
Definition at line 1184 of file presol_dualsparsify.c.
References NULL, and SCIP_Real.
Referenced by SCIP_DECL_PRESOLEXEC().
◆ SCIP_DECL_PRESOLCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1209 of file presol_dualsparsify.c.
References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolDualsparsify(), SCIPpresolGetData(), and SCIPpresolGetName().
◆ SCIP_DECL_PRESOLEXEC()
|
static |
execution method of presolver
Definition at line 1231 of file presol_dualsparsify.c.
References cancelCol(), ColConsPair::colindex, ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, getImpliedBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPdoNotAggr(), SCIPdoNotMultaggrVar(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNRuns(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRemoveAll(), SCIPhashtableRetrieve(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixDownlockConflict(), SCIPmatrixFree(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetVar(), SCIPmatrixUplockConflict(), SCIPpresolGetData(), SCIPreallocBufferArray, SCIPsortIntInt(), SCIPsortIntReal(), SCIPsortRealInt(), TRUE, and updateFailureStatistic().
◆ SCIP_DECL_PRESOLFREE()
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1713 of file presol_dualsparsify.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
◆ SCIP_DECL_PRESOLINIT()
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 1729 of file presol_dualsparsify.c.
References SCIP_OKAY, and SCIPpresolGetData().
◆ SCIPincludePresolDualsparsify()
SCIP_RETCODE SCIPincludePresolDualsparsify | ( | SCIP * | scip | ) |
creates the dualsparsify presolver and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1745 of file presol_dualsparsify.c.
References DEFAULT_ENABLECOPY, DEFAULT_MAX_BIN_FILLIN, DEFAULT_MAX_CONT_FILLIN, DEFAULT_MAX_INT_FILLIN, DEFAULT_MAXCONSIDEREDNONZEROS, DEFAULT_MAXRETRIEVEFAC, DEFAULT_MINELIMINATEDNONZEROS, DEFAULT_PRESERVEGOODLOCKS, DEFAULT_PRESERVEINTCOEFS, DEFAULT_WAITINGFAC, FALSE, NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludePresolBasic(), SCIPsetPresolCopy(), SCIPsetPresolFree(), SCIPsetPresolInit(), and TRUE.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().