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 "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

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

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolSparsify().

◆ PRESOL_DESC

#define PRESOL_DESC "eliminate non-zero coefficients"

Definition at line 53 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 55 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 56 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 57 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 59 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 60 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 61 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 62 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 63 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 64 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 65 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 66 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 67 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 68 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 69 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ MAXSCALE

#define MAXSCALE 1000.0

maximal allowed scale for cancelling non-zeros

Definition at line 71 of file presol_sparsify.c.

Referenced by buildFlowCover(), and cancelRow().

Typedef Documentation

◆ ROWVARPAIR

typedef struct RowVarPair ROWVARPAIR

Definition at line 108 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 116 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 142 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 154 of file presol_sparsify.c.

References a, b, COPYSIGN, FALSE, MAX, MAXSCALE, MIN, NULL, 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 632 of file presol_sparsify.c.

References NULL, and 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 658 of file presol_sparsify.c.

References NULL, 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 679 of file presol_sparsify.c.

References cancelRow(), FALSE, MIN, NULL, r, 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 980 of file presol_sparsify.c.

References NULL, 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 996 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 1011 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().

SCIP

Detailed Description

Data Structures

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