cancel non-zeros of the constraint matrix
This presolver attempts to cancel non-zero entries of the constraint matrix by adding scaled equalities to other constraints.
Definition in file presol_sparsify.c.
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "scip/cons_linear.h"
#include "scip/presol_sparsify.h"
Go to the source code of this file.
Macros | |
#define | PRESOL_NAME "sparsify" |
#define | PRESOL_DESC "eliminate non-zero coefficients" |
#define | PRESOL_PRIORITY -24000 |
#define | PRESOL_MAXROUNDS -1 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_ENABLECOPY TRUE |
#define | DEFAULT_CANCELLINEAR TRUE |
#define | DEFAULT_PRESERVEINTCOEFS TRUE |
#define | DEFAULT_MAX_CONT_FILLIN 0 |
#define | DEFAULT_MAX_BIN_FILLIN 0 |
#define | DEFAULT_MAX_INT_FILLIN 0 |
#define | DEFAULT_MAXNONZEROS -1 |
#define | DEFAULT_MAXCONSIDEREDNONZEROS 70 |
#define | DEFAULT_ROWSORT 'd' |
#define | DEFAULT_MAXRETRIEVEFAC 100.0 |
#define | DEFAULT_WAITINGFAC 2.0 |
#define | MAXSCALE 1000.0 |
Typedefs | |
typedef struct RowVarPair | ROWVARPAIR |
Functions | |
static | SCIP_DECL_HASHKEYEQ (varPairsEqual) |
static | SCIP_DECL_HASHKEYVAL (varPairHashval) |
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) |
static void | updateFailureStatistic (SCIP_PRESOLDATA *presoldata, SCIP_Bool success) |
static | SCIP_DECL_PRESOLCOPY (presolCopySparsify) |
static | SCIP_DECL_PRESOLEXEC (presolExecSparsify) |
static | SCIP_DECL_PRESOLFREE (presolFreeSparsify) |
static | SCIP_DECL_PRESOLINIT (presolInitSparsify) |
SCIP_RETCODE | SCIPincludePresolSparsify (SCIP *scip) |
#define PRESOL_NAME "sparsify" |
Definition at line 37 of file presol_sparsify.c.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolSparsify().
#define PRESOL_DESC "eliminate non-zero coefficients" |
Definition at line 38 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define PRESOL_PRIORITY -24000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 40 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 41 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 42 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_ENABLECOPY TRUE |
should sparsify presolver be copied to sub-SCIPs?
Definition at line 44 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_CANCELLINEAR TRUE |
should we cancel nonzeros in constraints of the linear constraint handler?
Definition at line 45 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_PRESERVEINTCOEFS TRUE |
should we forbid cancellations that destroy integer coefficients?
Definition at line 46 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_MAX_CONT_FILLIN 0 |
default value for the maximal fillin for continuous variables
Definition at line 47 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_MAX_BIN_FILLIN 0 |
default value for the maximal fillin for binary variables
Definition at line 48 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_MAX_INT_FILLIN 0 |
default value for the maximal fillin for integer variables (including binary)
Definition at line 49 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_MAXNONZEROS -1 |
maximal support of one equality to be used for cancelling (-1: no limit)
Definition at line 50 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_MAXCONSIDEREDNONZEROS 70 |
maximal number of considered non-zeros within one row (-1: no limit)
Definition at line 51 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_ROWSORT 'd' |
order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)
Definition at line 52 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#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 53 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#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 54 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define MAXSCALE 1000.0 |
maximal allowed scale for cancelling non-zeros
Definition at line 56 of file presol_sparsify.c.
Referenced by buildFlowCover(), and cancelRow().
typedef struct RowVarPair ROWVARPAIR |
Definition at line 93 of file presol_sparsify.c.
|
static |
returns TRUE iff both keys are equal
Definition at line 101 of file presol_sparsify.c.
References FALSE, SCIP_Real, SCIPisEQ(), RowVarPair::varcoef1, RowVarPair::varcoef2, RowVarPair::varindex1, and RowVarPair::varindex2.
|
static |
returns the hash value of the key
Definition at line 127 of file presol_sparsify.c.
References SCIPcombineTwoInt, SCIPhashTwo, SCIPrealHashCode(), RowVarPair::varcoef1, RowVarPair::varcoef2, RowVarPair::varindex1, and RowVarPair::varindex2.
|
static |
try non-zero cancellation for given row
scip | SCIP datastructure |
matrix | the constraint matrix |
pairtable | the hashtable containing ROWVARPAIR's of equations |
rowidx | index of row to try non-zero 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 non-zeros to consider for cancellation |
preserveintcoefs | only perform non-zero 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 |
Definition at line 139 of file presol_sparsify.c.
References FALSE, MAX, MAXSCALE, RowVarPair::rowindex, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), SCIPisZero(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowName(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixPrintRow(), SCIPreleaseCons(), SCIPsortIntInt(), SCIPswapPointers(), SCIPvarIsBinary(), SCIPvarIsIntegral(), TRUE, RowVarPair::varcoef1, RowVarPair::varcoef2, RowVarPair::varindex1, and RowVarPair::varindex2.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
updates failure counter after one execution
presoldata | presolver data |
success | was this execution successful? |
Definition at line 584 of file presol_sparsify.c.
References SCIP_Real.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 610 of file presol_sparsify.c.
References PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolSparsify(), SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
execution method of presolver
Definition at line 631 of file presol_sparsify.c.
References cancelRow(), FALSE, RowVarPair::rowindex, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPconsGetHdlr(), SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNActivePricers(), SCIPgetNConss(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPinProbing(), SCIPisEQ(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNNonzs(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPpresolGetData(), SCIPpresolGetNChgCoefs(), SCIPreallocBufferArray, SCIPsortIntInt(), SCIPsortIntReal(), SCIPverbMessage(), TRUE, updateFailureStatistic(), RowVarPair::varcoef1, RowVarPair::varcoef2, RowVarPair::varindex1, and RowVarPair::varindex2.
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 931 of file presol_sparsify.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 947 of file presol_sparsify.c.
References SCIP_OKAY, and SCIPpresolGetData().
SCIP_RETCODE SCIPincludePresolSparsify | ( | SCIP * | scip | ) |
creates the sparsify presolver and includes it in SCIP
scip | SCIP data structure |
Definition at line 962 of file presol_sparsify.c.
References DEFAULT_CANCELLINEAR, DEFAULT_ENABLECOPY, DEFAULT_MAX_BIN_FILLIN, DEFAULT_MAX_CONT_FILLIN, DEFAULT_MAX_INT_FILLIN, DEFAULT_MAXCONSIDEREDNONZEROS, DEFAULT_MAXNONZEROS, DEFAULT_MAXRETRIEVEFAC, DEFAULT_PRESERVEINTCOEFS, DEFAULT_ROWSORT, DEFAULT_WAITINGFAC, FALSE, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludePresolBasic(), SCIPsetPresolCopy(), SCIPsetPresolFree(), SCIPsetPresolInit(), and TRUE.
Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().