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

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

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

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

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
rowlb	lower bound of row
lbfound	flag indicating that a lower bound was calculated
rowub	upper bound of row
ubfound	flag 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

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index for implied free test
row	constraint planned for multi-aggregation
lockedcons	constraint not suitable for bound implication
impllbrowidx	row which implies the lower bound
implubrowidx	row 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

matrix	constraint matrix object
col	column index
row	row 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

scip	current scip instance
oldside	old rhs or lhs of constraint
aggrconst	multiaggrconstant
val	coefficient 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

scip	current scip instance
matrix	constraint matrix
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min 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

scip	SCIP data structure
matrix	constraint matrix object
row	row index
col	column index
val	coefficient value of variable in linear constraint
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min activity negative contribution counter
minisrelax	flag indicating min activity could be inexact
maxisrelax	flag 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

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
aggrconst	aggregation constant
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min 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

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
coef	coefficient of aggregated variable
newlhs	new calculated left hand side
newrhs	new 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

scip	SCIP data structure
matrix	constraint matrix object
col	column index
row	row index
coef	coefficient 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

scip	SCIP data structure
matrix	constraint matrix object
multiaggvars	array indicating multi-aggregatable variables
nummultiaggvars	number of multi-aggregatable variables
multiaggequalities	array holding aggregation equality row indices
consredundant	array indicating which constraint became redundant
lockedcons	constraints which could not be used for bound implication
skipvars	array holding which variables should be investigated
maxactposhuge	max activity positive contribution counter
maxactneghuge	max activity negative contribution counter
minactposhuge	min activity positive contribution counter
minactneghuge	min 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().

static SCIP_DECL_PRESOLEXEC ( presolExecImplfree  )

static

execution method of presolver

Definition at line 1074 of file presol_implfree.c.

References BMSclearMemoryArray, getMultiaggVars(), getNumHugeActivities(), NULL, scalars, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPconsGetName(), SCIPdebugMessage, SCIPdebugPrintf, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNActivePricers(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetStage(), SCIPinProbing(), SCIPisEQ(), SCIPisInfinity(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmultiaggregateVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

SCIP_RETCODE SCIPincludePresolImplfree

(

SCIP *

scip

)

creates the implied free presolver and includes it in SCIP

Parameters

scip	SCIP 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().