Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

cancel non-zeros of the constraint matrix

Author
Dieter Weninger
Leona 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 62 of file presol_sparsify.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolSparsify().

◆ PRESOL_DESC

#define PRESOL_DESC   "eliminate non-zero coefficients"

Definition at line 63 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 65 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 66 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 67 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 69 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 70 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 71 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 72 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 73 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 74 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 75 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 76 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 77 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 78 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 79 of file presol_sparsify.c.

Referenced by SCIPincludePresolSparsify().

◆ MAXSCALE

#define MAXSCALE   1000.0

maximal allowed scale for cancelling non-zeros

Definition at line 81 of file presol_sparsify.c.

Referenced by cancelRow().

Typedef Documentation

◆ ROWVARPAIR

typedef struct RowVarPair ROWVARPAIR

Definition at line 118 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 126 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 152 of file presol_sparsify.c.

References SCIPhashThree, 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
scipSCIP datastructure
matrixthe constraint matrix
pairtablethe hashtable containing ROWVARPAIR's of equations
rowidxindex of row to try non-zero cancellation for
maxcontfillinmaximal fill-in allowed for continuous variables
maxintfillinmaximal fill-in allowed for integral variables
maxbinfillinmaximal fill-in allowed for binary variables
maxconsiderednonzerosmaximal number of non-zeros to consider for cancellation
preserveintcoefsonly perform non-zero cancellation if integrality of coefficients is preserved?
nuselesspointer to update number of useless hashtable retrieves
nchgcoefspointer to update number of changed coefficients
ncanceledpointer to update number of canceled nonzeros
nfillinpointer to update the produced fill-in

Definition at line 164 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
presoldatapresolver data
successwas this execution successful?

Definition at line 654 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 680 of file presol_sparsify.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolSparsify(), SCIPpresolGetData(), and SCIPpresolGetName().

◆ SCIP_DECL_PRESOLEXEC()

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeSparsify  )
static

destructor of presolver to free user data (called when SCIP is exiting)

Definition at line 1022 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 1038 of file presol_sparsify.c.

References SCIP_OKAY, and SCIPpresolGetData().

◆ SCIPincludePresolSparsify()