Scippy

SCIP

Solving Constraint Integer Programs

presol_implfree.c File Reference

Detailed Description

perform multi-aggregation on implied free variables

Author
Dieter Weninger

This presolver tries to find implied free variables within equalities which are convenient for multi-aggregation.

Definition in file presol_implfree.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "presol_implfree.h"

Go to the source code of this file.

Macros

#define PRESOL_NAME   "implfree"
 
#define PRESOL_DESC   "exploit implied free variables for multi-aggregation"
 
#define PRESOL_PRIORITY   -1000
 
#define PRESOL_MAXROUNDS   0
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define MAXABSRATIO   ((SCIP_Real)1000.0)
 
#define SIDECHANGERATIO   ((SCIP_Real)10.0)
 

Functions

static SCIP_Real getMaxActSingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
 
static SCIP_Real getMinActSingleRowWithoutCol (SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
 
static void getActivityResiduals (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 *rowlb, SCIP_Bool *lbfound, SCIP_Real *rowub, SCIP_Bool *ubfound)
 
static SCIP_Bool isVarImpliedFree (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Bool *lockedcons, int *impllbrowidx, int *implubrowidx)
 
static SCIP_Real getFillIn (SCIP_MATRIX *matrix, int col, int row)
 
static SCIP_Real sideChangeNumericalStable (SCIP *scip, SCIP_Real oldside, SCIP_Real aggrconst, SCIP_Real val)
 
static void getNumHugeActivities (SCIP *scip, SCIP_MATRIX *matrix, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
 
static void getActivityRelax (SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real val, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge, SCIP_Bool *minisrelax, SCIP_Bool *maxisrelax)
 
static SCIP_Bool numericalStable (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real aggrconst, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
 
static void calcNewSidesAfterAggregation (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef, SCIP_Real *newlhs, SCIP_Real *newrhs)
 
static SCIP_Bool isConsRedundant (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef)
 
static void getMultiaggVars (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool *multiaggvars, int *nummultiaggvars, int *multiaggequalities, SCIP_Bool *consredundant, SCIP_Bool *lockedcons, SCIP_Bool *skipvars, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
 
static SCIP_DECL_PRESOLCOPY (presolCopyImplfree)
 
static SCIP_DECL_PRESOLEXEC (presolExecImplfree)
 
SCIP_RETCODE SCIPincludePresolImplfree (SCIP *scip)
 

Macro Definition Documentation

#define PRESOL_NAME   "implfree"

Definition at line 35 of file presol_implfree.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolImplfree().

#define PRESOL_DESC   "exploit implied free variables for multi-aggregation"

Definition at line 36 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

#define PRESOL_PRIORITY   -1000

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

Definition at line 37 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

#define PRESOL_MAXROUNDS   0

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

Definition at line 38 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

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

Definition at line 39 of file presol_implfree.c.

Referenced by SCIPincludePresolImplfree().

#define MAXABSRATIO   ((SCIP_Real)1000.0)

max abs coefficients ratio

Definition at line 41 of file presol_implfree.c.

Referenced by numericalStable().

#define SIDECHANGERATIO   ((SCIP_Real)10.0)

max side change ratio

Definition at line 42 of file presol_implfree.c.

Referenced by sideChangeNumericalStable().

Function Documentation

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

calculate max activity of one row without one column

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

Definition at line 51 of file presol_implfree.c.

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

Referenced by getActivityResiduals().

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

calculate min activity of one row without one column

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

Definition at line 103 of file presol_implfree.c.

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

Referenced by getActivityResiduals().

static void getActivityResiduals ( 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 min/max residual activity without the 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 155 of file presol_implfree.c.

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

Referenced by getVarBoundsOfRow(), and isConsRedundant().

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

calculate the bounds 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
rowlblower bound of row
lbfoundflag indicating that a lower bound was calculated
rowubupper bound of row
ubfoundflag indicating that an upper bound was calculated

Definition at line 296 of file presol_implfree.c.

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

Referenced by isVarImpliedFree().

static SCIP_Bool isVarImpliedFree ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Bool lockedcons,
int *  impllbrowidx,
int *  implubrowidx 
)
static

verify if the variable is implied free

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index for implied free test
rowconstraint planned for multi-aggregation
lockedconsconstraint not suitable for bound implication
impllbrowidxrow which implies the lower bound
implubrowidxrow which implied the upper bound

Definition at line 363 of file presol_implfree.c.

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

Referenced by getMultiaggVars().

static SCIP_Real getFillIn ( SCIP_MATRIX matrix,
int  col,
int  row 
)
static

calculate the amount of fill-in getting from multi-aggregation

Parameters
matrixconstraint matrix object
colcolumn index
rowrow index

Definition at line 446 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPmatrixGetColNNonzs(), and SCIPmatrixGetRowNNonzs().

Referenced by getMultiaggVars().

static SCIP_Real sideChangeNumericalStable ( SCIP scip,
SCIP_Real  oldside,
SCIP_Real  aggrconst,
SCIP_Real  val 
)
static

verify if the multi-aggregation is numerical stable concerning the side change

Parameters
scipcurrent scip instance
oldsideold rhs or lhs of constraint
aggrconstmultiaggrconstant
valcoefficient of multiaggvariable not within the aggregated constraint

Definition at line 474 of file presol_implfree.c.

References MAX, REALABS, SCIP_Real, and SIDECHANGERATIO.

Referenced by numericalStable().

static void getNumHugeActivities ( SCIP scip,
SCIP_MATRIX matrix,
int *  maxactposhuge,
int *  maxactneghuge,
int *  minactposhuge,
int *  minactneghuge 
)
static

calculate the huge contribution counters

Parameters
scipcurrent scip instance
matrixconstraint matrix
maxactposhugemax activity positive contribution counter
maxactneghugemax activity negative contribution counter
minactposhugemin activity positive contribution counter
minactneghugemin activity negative contribution counter

Definition at line 492 of file presol_implfree.c.

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

Referenced by SCIP_DECL_PRESOLEXEC().

static void getActivityRelax ( SCIP scip,
SCIP_MATRIX matrix,
int  row,
int  col,
SCIP_Real  val,
int *  maxactposhuge,
int *  maxactneghuge,
int *  minactposhuge,
int *  minactneghuge,
SCIP_Bool minisrelax,
SCIP_Bool maxisrelax 
)
static

verify if activities could be inexact

Parameters
scipSCIP data structure
matrixconstraint matrix object
rowrow index
colcolumn index
valcoefficient value of variable in linear constraint
maxactposhugemax activity positive contribution counter
maxactneghugemax activity negative contribution counter
minactposhugemin activity positive contribution counter
minactneghugemin activity negative contribution counter
minisrelaxflag indicating min activity could be inexact
maxisrelaxflag indicating max activity could be inexact

Definition at line 577 of file presol_implfree.c.

References FALSE, SCIP_Real, SCIPisHugeValue(), SCIPisInfinity(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), and TRUE.

Referenced by numericalStable().

static SCIP_Bool numericalStable ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  aggrconst,
int *  maxactposhuge,
int *  maxactneghuge,
int *  minactposhuge,
int *  minactneghuge 
)
static

verify if the multi-aggregation is numerical stable

Parameters
scipSCIP data structure
matrixconstraint matrix object
colcolumn index
rowrow index
aggrconstaggregation constant
maxactposhugemax activity positive contribution counter
maxactneghugemax activity negative contribution counter
minactposhugemin activity positive contribution counter
minactneghugemin activity negative contribution counter

Definition at line 728 of file presol_implfree.c.

References FALSE, getActivityRelax(), MAXABSRATIO, REALABS, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), sideChangeNumericalStable(), and TRUE.

Referenced by getMultiaggVars().

static void calcNewSidesAfterAggregation ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  coef,
SCIP_Real newlhs,
SCIP_Real newrhs 
)
static

calculate sides after aggregation

Parameters
scipSCIP data structure
matrixconstraint matrix object
colcolumn index
rowrow index
coefcoefficient of aggregated variable
newlhsnew calculated left hand side
newrhsnew calculated right hand side

Definition at line 838 of file presol_implfree.c.

References NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPisLE(), SCIPmatrixGetColLb(), SCIPmatrixGetColUb(), SCIPmatrixGetRowLhs(), and SCIPmatrixGetRowRhs().

Referenced by isConsRedundant().

static SCIP_Bool isConsRedundant ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  coef 
)
static

verify if the constraint becomes redundant after aggregation

Parameters
scipSCIP data structure
matrixconstraint matrix object
colcolumn index
rowrow index
coefcoefficient of aggregated variable

Definition at line 894 of file presol_implfree.c.

References calcNewSidesAfterAggregation(), FALSE, getActivityResiduals(), SCIP_Bool, SCIP_Real, and SCIPisFeasLE().

Referenced by getMultiaggVars().

static void getMultiaggVars ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Bool multiaggvars,
int *  nummultiaggvars,
int *  multiaggequalities,
SCIP_Bool consredundant,
SCIP_Bool lockedcons,
SCIP_Bool skipvars,
int *  maxactposhuge,
int *  maxactneghuge,
int *  minactposhuge,
int *  minactneghuge 
)
static

identify candidates for multi-aggregation

Parameters
scipSCIP data structure
matrixconstraint matrix object
multiaggvarsarray indicating multi-aggregatable variables
nummultiaggvarsnumber of multi-aggregatable variables
multiaggequalitiesarray holding aggregation equality row indices
consredundantarray indicating which constraint became redundant
lockedconsconstraints which could not be used for bound implication
skipvarsarray holding which variables should be investigated
maxactposhugemax activity positive contribution counter
maxactneghugemax activity negative contribution counter
minactposhugemin activity positive contribution counter
minactneghugemin activity negative contribution counter

Definition at line 923 of file presol_implfree.c.

References FALSE, getFillIn(), isConsRedundant(), isVarImpliedFree(), NULL, numericalStable(), SCIP_Bool, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPisEQ(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPvarGetType(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_DECL_PRESOLCOPY ( presolCopyImplfree  )
static

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

Definition at line 1059 of file presol_implfree.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolImplfree(), and SCIPpresolGetName().

SCIP_RETCODE SCIPincludePresolImplfree ( SCIP scip)

creates the implied free presolver and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 1278 of file presol_implfree.c.

References NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIPincludePresolBasic(), and SCIPsetPresolCopy().

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().