Scippy

SCIP

Solving Constraint Integer Programs

presol_dualsparsify.c File Reference

Detailed Description

cancel nonzeros of the constraint matrix based on the columns

Author
Dieter Weninger
Leona Gottwald
Ambros Gleixner
Weikun Chen

This presolver attempts to cancel non-zero entries of the constraint matrix by adding scaled columns to other columns.

In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have

             | A_{j.} | - | A_{j.} - s*A_{k.} | > eta,

where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is nonimplied free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem to keep the bounds constraints of variable x_k.

Further information can be found in Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".

Definition in file presol_dualsparsify.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/debug.h"
#include "scip/presol_dualsparsify.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_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  ColConsPair
 

Macros

#define PRESOL_NAME   "dualsparsify"
 
#define PRESOL_DESC   "eliminate non-zero coefficients"
 
#define PRESOL_PRIORITY   -240000
 
#define PRESOL_MAXROUNDS   -1
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define DEFAULT_ENABLECOPY   TRUE
 
#define DEFAULT_PRESERVEINTCOEFS   FALSE
 
#define DEFAULT_PRESERVEGOODLOCKS   FALSE
 
#define DEFAULT_MAX_CONT_FILLIN   1
 
#define DEFAULT_MAX_BIN_FILLIN   1
 
#define DEFAULT_MAX_INT_FILLIN   1
 
#define DEFAULT_MAXCONSIDEREDNONZEROS   70
 
#define DEFAULT_MINELIMINATEDNONZEROS   100
 
#define DEFAULT_MAXRETRIEVEFAC   100.0
 
#define DEFAULT_WAITINGFAC   2.0
 
#define MAXSCALE   1000.0
 

Typedefs

typedef struct ColConsPair COLCONSPAIR
 

Functions

static SCIP_DECL_HASHKEYEQ (consPairsEqual)
 
static SCIP_DECL_HASHKEYVAL (consPairHashval)
 
static SCIP_Real getMaxActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
 
static SCIP_Real getMinActivitySingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
 
static void getMinMaxActivityResiduals (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
 
static void getVarBoundsOfRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
 
static void getImpliedBounds (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
 
static SCIP_RETCODE aggregation (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_VAR **vars, int colidx1, int colidx2, SCIP_Bool isimpliedfree, SCIP_Real weight1)
 
static SCIP_RETCODE cancelCol (SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_HASHTABLE *pairtable, SCIP_Bool *ishashingcols, SCIP_VAR **vars, SCIP_Bool *isblockedvar, int colidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin, SCIP_Bool isaddedcons)
 
static void updateFailureStatistic (SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
 
static SCIP_DECL_PRESOLCOPY (presolCopyDualsparsify)
 
static SCIP_DECL_PRESOLEXEC (presolExecDualsparsify)
 
static SCIP_DECL_PRESOLFREE (presolFreeDualsparsify)
 
static SCIP_DECL_PRESOLINIT (presolInitDualsparsify)
 
SCIP_RETCODE SCIPincludePresolDualsparsify (SCIP *scip)
 

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME   "dualsparsify"

Definition at line 80 of file presol_dualsparsify.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDualsparsify().

◆ PRESOL_DESC

#define PRESOL_DESC   "eliminate non-zero coefficients"

Definition at line 81 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   -240000

priority of the presolver (>= 0: before, < 0: after constraint handlers)

Definition at line 83 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 84 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ PRESOL_TIMING

#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 85 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_ENABLECOPY

#define DEFAULT_ENABLECOPY   TRUE

should dualsparsify presolver be copied to sub-SCIPs?

Definition at line 87 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_PRESERVEINTCOEFS

#define DEFAULT_PRESERVEINTCOEFS   FALSE

should we forbid cancellations that destroy integer coefficients?

Definition at line 88 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_PRESERVEGOODLOCKS

#define DEFAULT_PRESERVEGOODLOCKS   FALSE

should we preserve good locked properties of variables (at most one lock in one direction)?

Definition at line 89 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_MAX_CONT_FILLIN

#define DEFAULT_MAX_CONT_FILLIN   1

default value for the maximal fillin for continuous variables

Definition at line 90 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_MAX_BIN_FILLIN

#define DEFAULT_MAX_BIN_FILLIN   1

default value for the maximal fillin for binary variables

Definition at line 91 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_MAX_INT_FILLIN

#define DEFAULT_MAX_INT_FILLIN   1

default value for the maximal fillin for integer variables (including binary)

Definition at line 92 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_MAXCONSIDEREDNONZEROS

#define DEFAULT_MAXCONSIDEREDNONZEROS   70

maximal number of considered nonzeros within one column (-1: no limit)

Definition at line 93 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ DEFAULT_MINELIMINATEDNONZEROS

#define DEFAULT_MINELIMINATEDNONZEROS   100

minimal eleminated nonzeros within one column if we need to add a constraint to the problem

Definition at line 94 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ 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 95 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ 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 96 of file presol_dualsparsify.c.

Referenced by SCIPincludePresolDualsparsify().

◆ MAXSCALE

#define MAXSCALE   1000.0

maximal allowed scale for cancelling nonzeros

Definition at line 98 of file presol_dualsparsify.c.

Referenced by buildFlowCover(), and cancelCol().

Typedef Documentation

◆ COLCONSPAIR

typedef struct ColConsPair COLCONSPAIR

Definition at line 135 of file presol_dualsparsify.c.

Function Documentation

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( consPairsEqual  )
static

returns TRUE iff both keys are equal

Definition at line 143 of file presol_dualsparsify.c.

References ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, SCIP_Real, and SCIPisEQ().

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( consPairHashval  )
static

◆ getMaxActivitySingleRowWithoutCol()

static SCIP_Real getMaxActivitySingleRowWithoutCol ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
int  col 
)
static

calculate maximal activity of one row without one specific column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
rowrow index
colcolumn index

Definition at line 180 of file presol_dualsparsify.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by getMinMaxActivityResiduals().

◆ getMinActivitySingleRowWithoutCol()

static SCIP_Real getMinActivitySingleRowWithoutCol ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
int  col 
)
static

calculate minimal activity of one row without one specific column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
rowrow index
colcolumn index

Definition at line 234 of file presol_dualsparsify.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), and SCIPmatrixGetRowValPtr().

Referenced by getMinMaxActivityResiduals().

◆ getMinMaxActivityResiduals()

static void getMinMaxActivityResiduals ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  val,
SCIP_Real minresactivity,
SCIP_Real maxresactivity,
SCIP_Bool isminsettoinfinity,
SCIP_Bool ismaxsettoinfinity 
)
static

get minimal and maximal residual activity without one specified column

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index
rowrow index
valcoefficient of this variable in this row
minresactivityminimum residual activity of this row
maxresactivitymaximum residual activity of this row
isminsettoinfinityflag indicating if minresactiviy is set to infinity
ismaxsettoinfinityflag indicating if maxresactiviy is set to infinity

Definition at line 288 of file presol_dualsparsify.c.

References FALSE, getMaxActivitySingleRowWithoutCol(), getMinActivitySingleRowWithoutCol(), NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), and TRUE.

Referenced by getVarBoundsOfRow().

◆ getVarBoundsOfRow()

static void getVarBoundsOfRow ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  val,
SCIP_Real rowub,
SCIP_Bool ubfound,
SCIP_Real rowlb,
SCIP_Bool lbfound 
)
static

calculate the upper and lower bound of one variable from one row

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index of variable
rowrow index
valcoefficient of this column in this row
rowubupper bound of row
ubfoundflag indicating that an upper bound was calculated
rowlblower bound of row
lbfoundflag indicating that a lower bound was caluclated

Definition at line 426 of file presol_dualsparsify.c.

References FALSE, getMinMaxActivityResiduals(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), and TRUE.

Referenced by getImpliedBounds().

◆ getImpliedBounds()

static void getImpliedBounds ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
SCIP_Bool ubimplied,
SCIP_Bool lbimplied 
)
static

detect implied variable bounds

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index for implied free test
ubimpliedflag indicating an implied upper bound
lbimpliedflag indicating an implied lower bound

Definition at line 494 of file presol_dualsparsify.c.

References FALSE, getVarBoundsOfRow(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColLb(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColUb(), SCIPmatrixGetColValPtr(), and TRUE.

Referenced by aggregation(), cancelCol(), and SCIP_DECL_PRESOLEXEC().

◆ aggregation()

static SCIP_RETCODE aggregation ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_PRESOLDATA presoldata,
SCIP_VAR **  vars,
int  colidx1,
int  colidx2,
SCIP_Bool  isimpliedfree,
SCIP_Real  weight1 
)
static

y = weight1 * var[colidx1] + var[colidx2]

Parameters
scipSCIP datastructure
matrixmatrix datastructure
presoldatapresolver data
varsthe current variables
colidx1one of the indexes of column to try nonzero cancellation for
colidx2one of the indexes of column to try nonzero cancellation for
isimpliedfreeis the aggregated variable implied free?
weight1weight variable one in the aggregated expression

Definition at line 555 of file presol_dualsparsify.c.

References FALSE, getImpliedBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdoNotMultaggrVar(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixRemoveColumnBounds(), SCIPmultiaggregateVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsInitial(), SCIPvarIsIntegral(), SCIPvarIsRemovable(), and TRUE.

Referenced by cancelCol().

◆ cancelCol()

static SCIP_RETCODE cancelCol ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_PRESOLDATA presoldata,
SCIP_HASHTABLE pairtable,
SCIP_Bool ishashingcols,
SCIP_VAR **  vars,
SCIP_Bool isblockedvar,
int  colidx,
int  maxcontfillin,
int  maxintfillin,
int  maxbinfillin,
int  maxconsiderednonzeros,
SCIP_Bool  preserveintcoefs,
SCIP_Longint nuseless,
int *  nchgcoefs,
int *  ncanceled,
int *  nfillin,
SCIP_Bool  isaddedcons 
)
static

try nonzero cancellation for given column

Parameters
scipSCIP datastructure
matrixthe constraint matrix
presoldatapresolver data
pairtablethe hashtable containing COLCONSPAIR's of equations
ishashingcolsarray to indicates whether it is impliedfree or not
varsarray to store the current variables
isblockedvararray to indicates whether it is blocked or not
colidxindex of column to try nonzero 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 nonzeros to consider for cancellation
preserveintcoefsonly perform nonzero 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
isaddedconswhether a linear constraint required to added to keep the validity

Definition at line 708 of file presol_dualsparsify.c.

References a, aggregation(), b, ColConsPair::colindex, ColConsPair::conscoef1, ColConsPair::conscoef2, ColConsPair::consindex1, ColConsPair::consindex2, FALSE, getImpliedBounds(), MAX, MAXSCALE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), SCIPisZero(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNDownlocks(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColNUplocks(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPsortRealInt(), SCIPswapPointers(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), and TRUE.

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 1206 of file presol_dualsparsify.c.

References NULL, and SCIP_Real.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyDualsparsify  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1231 of file presol_dualsparsify.c.

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

◆ SCIP_DECL_PRESOLEXEC()

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeDualsparsify  )
static

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

Definition at line 1735 of file presol_dualsparsify.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().

◆ SCIP_DECL_PRESOLINIT()

static SCIP_DECL_PRESOLINIT ( presolInitDualsparsify  )
static

initialization method of presolver (called after problem was transformed)

Definition at line 1751 of file presol_dualsparsify.c.

References SCIP_OKAY, and SCIPpresolGetData().

◆ SCIPincludePresolDualsparsify()