Detailed Description

cancel non-zeros of the constraint matrix

Author: Dieter Weninger; Robert Lion Gottwald; Ambros Gleixner

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)

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME "sparsify"

Definition at line 37 of file presol_sparsify.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolSparsify().

◆ PRESOL_DESC

#define PRESOL_DESC "eliminate non-zero coefficients"

Definition at line 38 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ PRESOL_PRIORITY

#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().

◆ PRESOL_MAXROUNDS

#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().

◆ PRESOL_TIMING

#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().

◆ DEFAULT_ENABLECOPY

#define DEFAULT_ENABLECOPY TRUE

should sparsify presolver be copied to sub-SCIPs?

Definition at line 44 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ DEFAULT_CANCELLINEAR

#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().

◆ DEFAULT_PRESERVEINTCOEFS

#define DEFAULT_PRESERVEINTCOEFS TRUE

should we forbid cancellations that destroy integer coefficients?

Definition at line 46 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ DEFAULT_MAX_CONT_FILLIN

#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().

◆ DEFAULT_MAX_BIN_FILLIN

#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().

◆ DEFAULT_MAX_INT_FILLIN

#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().

◆ DEFAULT_MAXNONZEROS

#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().

◆ DEFAULT_MAXCONSIDEREDNONZEROS

#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().

◆ DEFAULT_ROWSORT

#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().

◆ 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 53 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ 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 54 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ MAXSCALE

#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 Documentation

◆ ROWVARPAIR

typedef struct RowVarPair ROWVARPAIR

Definition at line 93 of file presol_sparsify.c.

Function Documentation

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( varPairsEqual )

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.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( varPairHashval )

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.

◆ cancelRow()

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

try non-zero cancellation for given row

Parameters

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, REALABS, 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().

◆ updateFailureStatistic()

static void updateFailureStatistic	(	SCIP_PRESOLDATA *	presoldata,
		SCIP_Bool	success
	)

static

updates failure counter after one execution

Parameters

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().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopySparsify )

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().

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecSparsify )

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.

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeSparsify )

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().

◆ SCIP_DECL_PRESOLINIT()

static SCIP_DECL_PRESOLINIT ( presolInitSparsify )

static

initialization method of presolver (called after problem was transformed)

Definition at line 947 of file presol_sparsify.c.

References SCIP_OKAY, and SCIPpresolGetData().

◆ SCIPincludePresolSparsify()

SCIP_RETCODE SCIPincludePresolSparsify ( SCIP * scip )

creates the sparsify presolver and includes it in SCIP

Parameters

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().

SCIP

Detailed Description

Macros

Typedefs

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ DEFAULT_ENABLECOPY

◆ DEFAULT_CANCELLINEAR

◆ DEFAULT_PRESERVEINTCOEFS

◆ DEFAULT_MAX_CONT_FILLIN

◆ DEFAULT_MAX_BIN_FILLIN

◆ DEFAULT_MAX_INT_FILLIN

◆ DEFAULT_MAXNONZEROS

◆ DEFAULT_MAXCONSIDEREDNONZEROS

◆ DEFAULT_ROWSORT

◆ DEFAULT_MAXRETRIEVEFAC

◆ DEFAULT_WAITINGFAC

◆ MAXSCALE

Typedef Documentation

◆ ROWVARPAIR

Function Documentation

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ cancelRow()

◆ updateFailureStatistic()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLEXEC()

◆ SCIP_DECL_PRESOLFREE()

◆ SCIP_DECL_PRESOLINIT()

◆ SCIPincludePresolSparsify()