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 "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/presol_sparsify.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_timing.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | RowVarPair |
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 |
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 62 of file presol_sparsify.c.
#define PRESOL_DESC "eliminate non-zero coefficients" |
Definition at line 63 of file presol_sparsify.c.
#define PRESOL_PRIORITY -24000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 65 of file presol_sparsify.c.
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 66 of file presol_sparsify.c.
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 67 of file presol_sparsify.c.
#define DEFAULT_ENABLECOPY TRUE |
should sparsify presolver be copied to sub-SCIPs?
Definition at line 69 of file presol_sparsify.c.
#define DEFAULT_CANCELLINEAR TRUE |
should we cancel nonzeros in constraints of the linear constraint handler?
Definition at line 70 of file presol_sparsify.c.
Referenced by SCIPincludePresolSparsify().
#define DEFAULT_PRESERVEINTCOEFS TRUE |
should we forbid cancellations that destroy integer coefficients?
Definition at line 71 of file presol_sparsify.c.
#define DEFAULT_MAX_CONT_FILLIN 0 |
default value for the maximal fillin for continuous variables
Definition at line 72 of file presol_sparsify.c.
#define DEFAULT_MAX_BIN_FILLIN 0 |
default value for the maximal fillin for binary variables
Definition at line 73 of file presol_sparsify.c.
#define DEFAULT_MAX_INT_FILLIN 0 |
default value for the maximal fillin for integer variables (including binary)
Definition at line 74 of file presol_sparsify.c.
#define DEFAULT_MAXNONZEROS -1 |
maximal support of one equality to be used for cancelling (-1: no limit)
Definition at line 75 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 76 of file presol_sparsify.c.
#define DEFAULT_ROWSORT 'd' |
order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)
Definition at line 77 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 78 of file presol_sparsify.c.
#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 79 of file presol_sparsify.c.
#define MAXSCALE 1000.0 |
maximal allowed scale for cancelling non-zeros
Definition at line 81 of file presol_sparsify.c.
typedef struct RowVarPair ROWVARPAIR |
Definition at line 118 of file presol_sparsify.c.
|
static |
returns TRUE iff both keys are equal
Definition at line 126 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 152 of file presol_sparsify.c.
References SCIPhashThree, 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 164 of file presol_sparsify.c.
References a, assert(), b, bestcand, COPYSIGN, FALSE, i, MAX, MAXSCALE, MIN, NULL, REALABS, RowVarPair::rowindex, SCIP_Bool, SCIP_CALL, SCIP_Longint, 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, var, 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 654 of file presol_sparsify.c.
References assert(), NULL, SCIP_Bool, and SCIP_Real.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 680 of file presol_sparsify.c.
References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolSparsify(), SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
execution method of presolver
Definition at line 701 of file presol_sparsify.c.
References assert(), cancelRow(), FALSE, i, MIN, NULL, r, result, RowVarPair::rowindex, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, 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(), SCIPhashtableGetNEntries(), 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 1022 of file presol_sparsify.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 1038 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 1053 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, NULL, 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().