# SCIP

Solving Constraint Integer Programs

presol_dualsparsify.c File Reference

## Detailed Description

cancel nonzeros of the constraint matrix based on the columns

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)

## ◆ PRESOL_NAME

 #define PRESOL_NAME   "dualsparsify"

Definition at line 80 of file presol_dualsparsify.c.

## ◆ PRESOL_DESC

 #define PRESOL_DESC   "eliminate non-zero coefficients"

Definition at line 81 of file presol_dualsparsify.c.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ DEFAULT_ENABLECOPY

 #define DEFAULT_ENABLECOPY   TRUE

should dualsparsify presolver be copied to sub-SCIPs?

Definition at line 87 of file presol_dualsparsify.c.

## ◆ DEFAULT_PRESERVEINTCOEFS

 #define DEFAULT_PRESERVEINTCOEFS   FALSE

should we forbid cancellations that destroy integer coefficients?

Definition at line 88 of file presol_dualsparsify.c.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ 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.

## ◆ MAXSCALE

 #define MAXSCALE   1000.0

maximal allowed scale for cancelling nonzeros

Definition at line 98 of file presol_dualsparsify.c.

## ◆ COLCONSPAIR

 typedef struct ColConsPair COLCONSPAIR

Definition at line 133 of file presol_dualsparsify.c.

## ◆ SCIP_DECL_HASHKEYEQ()

 static SCIP_DECL_HASHKEYEQ ( consPairsEqual )
static

returns TRUE iff both keys are equal

Definition at line 141 of file presol_dualsparsify.c.

## ◆ SCIP_DECL_HASHKEYVAL()

 static SCIP_DECL_HASHKEYVAL ( consPairHashval )
static

returns the hash value of the key

Definition at line 167 of file presol_dualsparsify.c.

## ◆ 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
 scip SCIP main data structure matrix matrix containing the constraints row row index col column index

Definition at line 178 of file presol_dualsparsify.c.

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
 scip SCIP main data structure matrix matrix containing the constraints row row index col column index

Definition at line 232 of file presol_dualsparsify.c.

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
 scip SCIP main data structure matrix matrix containing the constraints col column index row row index val coefficient of this variable in this row minresactivity minimum residual activity of this row maxresactivity maximum residual activity of this row isminsettoinfinity flag indicating if minresactiviy is set to infinity ismaxsettoinfinity flag indicating if maxresactiviy is set to infinity

Definition at line 286 of file presol_dualsparsify.c.

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
 scip SCIP main data structure matrix matrix containing the constraints col column index of variable row row index val coefficient of this column in this row rowub upper bound of row ubfound flag indicating that an upper bound was calculated rowlb lower bound of row lbfound flag indicating that a lower bound was caluclated

Definition at line 424 of file presol_dualsparsify.c.

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
 scip SCIP main data structure matrix matrix containing the constraints col column index for implied free test ubimplied flag indicating an implied upper bound lbimplied flag indicating an implied lower bound

Definition at line 492 of file presol_dualsparsify.c.

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
 scip SCIP datastructure matrix matrix datastructure presoldata presolver data vars the current variables colidx1 one of the indexes of column to try nonzero cancellation for colidx2 one of the indexes of column to try nonzero cancellation for isimpliedfree is the aggregated variable implied free? weight1 weight variable one in the aggregated expression

Definition at line 553 of file presol_dualsparsify.c.

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
 scip SCIP datastructure matrix the constraint matrix presoldata presolver data pairtable the hashtable containing COLCONSPAIR's of equations ishashingcols array to indicates whether it is impliedfree or not vars array to store the current variables isblockedvar array to indicates whether it is blocked or not colidx index of column to try nonzero 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 nonzeros to consider for cancellation preserveintcoefs only perform nonzero 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 isaddedcons whether a linear constraint required to added to keep the validity

Definition at line 706 of file presol_dualsparsify.c.

Referenced by SCIP_DECL_PRESOLEXEC().

## ◆ updateFailureStatistic()

 static void updateFailureStatistic ( SCIP_PRESOLDATA * presoldata, SCIP_Bool success )
static

updates failure counter after one execution

Parameters

Definition at line 1204 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 1229 of file presol_dualsparsify.c.

## ◆ SCIP_DECL_PRESOLEXEC()

 static SCIP_DECL_PRESOLEXEC ( presolExecDualsparsify )
static

## ◆ SCIP_DECL_PRESOLFREE()

 static SCIP_DECL_PRESOLFREE ( presolFreeDualsparsify )
static

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

Definition at line 1746 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 1762 of file presol_dualsparsify.c.

References SCIP_OKAY, and SCIPpresolGetData().

## ◆ SCIPincludePresolDualsparsify()

 SCIP_RETCODE SCIPincludePresolDualsparsify ( SCIP * scip )

creates the dualsparsify presolver and includes it in SCIP

Parameters
 scip SCIP data structure

Definition at line 1776 of file presol_dualsparsify.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().