presol_domcol.c File Reference

Detailed Description

dominated column presolver

Author

Dieter Weninger

Gerald Gamrath

This presolver looks for dominance relations between variable pairs. From a dominance relation and certain bound/clique-constellations variable fixings mostly at the lower bound of the dominated variable can be derived. Additionally it is possible to improve bounds by predictive bound strengthening.

Definition in file presol_domcol.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_varbound.h"
#include "presol_domcol.h"

Go to the source code of this file.

Macros
#define	PRESOL_NAME   "domcol"
#define	PRESOL_DESC   "dominated column presolver"
#define	PRESOL_PRIORITY   20000000
#define	PRESOL_MAXROUNDS   -1
#define	PRESOL_DELAY   TRUE
#define	DEFAULT_NUMMINPAIRS   1024
#define	DEFAULT_NUMMAXPAIRS   1048576
#define	DEFAULT_PREDBNDSTR   FALSE
#define	DEFAULT_SINGCOLSTUFF   TRUE

Typedefs
typedef enum Fixingdirection	FIXINGDIRECTION
typedef struct ConstraintMatrix	CONSTRAINTMATRIX

Enumerations
enum	Fixingdirection {   FIXATLB = -1,   NOFIX = 0,   FIXATUB = 1,   FIXATLB = -1,   NOFIX = 0,   FIXATUB = 1 }

Functions
static SCIP_RETCODE	getActiveVariables (SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant)
static SCIP_RETCODE	addRow (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs)
static SCIP_RETCODE	addConstraint (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs)
static SCIP_RETCODE	setColumnMajorFormat (SCIP *scip, CONSTRAINTMATRIX *matrix)
static SCIP_RETCODE	calcActivityBounds (SCIP *scip, CONSTRAINTMATRIX *matrix)
static SCIP_RETCODE	initMatrix (SCIP *scip, CONSTRAINTMATRIX **matrixptr, SCIP_Bool *initialized)
static void	freeMatrix (SCIP *scip, CONSTRAINTMATRIX **matrix)
static void	getActivityResidualsUpperBound (SCIP *scip, CONSTRAINTMATRIX *matrix, int row, int col, SCIP_Real coef, int upperboundcol, SCIP_Real upperboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
static void	getActivityResidualsLowerBound (SCIP *scip, CONSTRAINTMATRIX *matrix, int row, int col, SCIP_Real coef, int lowerboundcol, SCIP_Real lowerboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
static SCIP_RETCODE	calcVarBoundsDominated (SCIP *scip, CONSTRAINTMATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
static SCIP_RETCODE	calcVarBoundsDominating (SCIP *scip, CONSTRAINTMATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
static SCIP_RETCODE	updateBounds (SCIP *scip, CONSTRAINTMATRIX *matrix, int row, int col1, SCIP_Real val1, int col2, SCIP_Real val2, SCIP_Bool predictdominating, SCIP_Real *upperbound, SCIP_Real *wclowerbound, SCIP_Real *lowerbound, SCIP_Real *wcupperbound)
static SCIP_RETCODE	detectParallelCols (SCIP *scip, CONSTRAINTMATRIX *matrix, int *pclass, SCIP_Bool *varineq)
static SCIP_RETCODE	predBndStr (SCIP *scip, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, SCIP_Real dominatedub, SCIP_Real dominatedwclb, SCIP_Real dominatedlb, FIXINGDIRECTION *varstofix, int *nchgbds)
static SCIP_RETCODE	findFixings (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatingwclb, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, FIXINGDIRECTION *varstofix, SCIP_Bool onlybinvars, SCIP_Bool onlyoneone, int *nfixings)
static SCIP_RETCODE	findDominancePairs (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_PRESOLDATA *presoldata, int *searchcols, int searchsize, SCIP_Bool onlybinvars, FIXINGDIRECTION *varstofix, int *nfixings, SCIP_Longint *ndomrelations, int *nchgbds)
static SCIP_RETCODE	singletonColumnStuffing (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_Bool *varsprocessed, FIXINGDIRECTION *varstofix, int *nfixings)
static	SCIP_DECL_PRESOLCOPY (presolCopyDomcol)
static	SCIP_DECL_PRESOLFREE (presolFreeDomcol)
static	SCIP_DECL_PRESOLEXEC (presolExecDomcol)
SCIP_RETCODE	SCIPincludePresolDomcol (SCIP *scip)

Macro Definition Documentation

#define PRESOL_NAME   "domcol"

Definition at line 52 of file presol_domcol.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDomcol().

#define PRESOL_DESC   "dominated column presolver"

Definition at line 53 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define PRESOL_PRIORITY   20000000

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

Definition at line 54 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define PRESOL_MAXROUNDS   -1

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

Definition at line 55 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define PRESOL_DELAY   TRUE

should presolver be delayed, if other presolvers found reductions?

Definition at line 56 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define DEFAULT_NUMMINPAIRS   1024

minimal number of pair comparisons

Definition at line 58 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define DEFAULT_NUMMAXPAIRS   1048576

maximal number of pair comparisons

Definition at line 59 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define DEFAULT_PREDBNDSTR   FALSE

should predictive bound strengthening be applied?

Definition at line 61 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

#define DEFAULT_SINGCOLSTUFF   TRUE

should singleton columns stuffing be applied?

Definition at line 62 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

Typedef Documentation

typedef enum Fixingdirection FIXINGDIRECTION

Definition at line 90 of file presol_domcol.c.

typedef struct ConstraintMatrix CONSTRAINTMATRIX

Definition at line 130 of file presol_domcol.c.

Enumeration Type Documentation

enum Fixingdirection

type of fixing direction

Enumerator:

FIXATLB	fix variable at lower bound
NOFIX	do not fix variable
FIXATUB	fix variable at upper bound
FIXATLB
NOFIX
FIXATUB

Definition at line 84 of file presol_domcol.c.

Function Documentation

static SCIP_RETCODE getActiveVariables ( SCIP *  scip, SCIP_VAR ***  vars, SCIP_Real **  scalars, int *  nvars, SCIP_Real *  constant  )

static

transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant

Parameters

scip	SCIP data structure
vars	vars array to get active variables for
scalars	scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c
nvars	pointer to number of variables and values in vars and vals array
constant	pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c

Definition at line 134 of file presol_domcol.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, and TRUE.

Referenced by addConstraint().

static SCIP_RETCODE addRow ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_VAR **  vars, SCIP_Real *  vals, int  nvars, SCIP_Real  lhs, SCIP_Real  rhs  )

static

add one row to the constraint matrix

Parameters

scip	SCIP data structure
matrix	constraint matrix
vars	variables of this row
vals	coefficients of this row
nvars	number of variables of this row
lhs	left hand side
rhs	right hand side

Definition at line 169 of file presol_domcol.c.

References FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPvarGetProbindex(), and TRUE.

Referenced by addConstraint().

static SCIP_RETCODE addConstraint ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_VAR **  vars, SCIP_Real *  vals, int  nvars, SCIP_Real  lhs, SCIP_Real  rhs  )

static

add one constraint to matrix

Parameters

scip	current scip instance
matrix	constraint matrix
vars	variables of this constraint
vals	variable coefficients of this constraint
nvars	number of variables
lhs	left hand side
rhs	right hand side

Definition at line 272 of file presol_domcol.c.

References addRow(), getActiveVariables(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and SCIPisLE().

Referenced by initMatrix().

static SCIP_RETCODE setColumnMajorFormat ( SCIP *  scip, CONSTRAINTMATRIX *  matrix  )

static

transform row major format into column major format

Parameters

scip	current scip instance
matrix	constraint matrix

Definition at line 351 of file presol_domcol.c.

References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by initMatrix().

static SCIP_RETCODE calcActivityBounds ( SCIP *  scip, CONSTRAINTMATRIX *  matrix  )

static

calculate min/max activity per row

Parameters

scip	current scip instance
matrix	constraint matrix

Definition at line 418 of file presol_domcol.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), and SCIPisZero().

Referenced by initMatrix().

static SCIP_RETCODE initMatrix ( SCIP *  scip, CONSTRAINTMATRIX **  matrixptr, SCIP_Bool *  initialized  )

static

initialize matrix

Parameters

scip	current scip instance
matrixptr	pointer to constraint matrix object to be initialized
initialized	was the initialization successful?

Definition at line 494 of file presol_domcol.c.

References addConstraint(), BMSclearMemoryArray, calcActivityBounds(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBuffer, SCIPallocBufferArray, SCIPallocClearMemoryArray, SCIPconsGetName(), SCIPconshdlrGetCheckConss(), SCIPconshdlrGetName(), SCIPconshdlrGetNCheckConss(), SCIPconsIsTransformed(), SCIPdebugMessage, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetConshdlrs(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNConshdlrs(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVars(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsSetppc(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPinfinity(), SCIPisStopped(), SCIPreallocBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), setColumnMajorFormat(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static void freeMatrix ( SCIP *  scip, CONSTRAINTMATRIX **  matrix  )

static

frees the constraint matrix

Parameters

scip	current SCIP instance
matrix	constraint matrix object

Definition at line 822 of file presol_domcol.c.

References NULL, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, and SCIPfreeMemoryArray.

Referenced by SCIP_DECL_PRESOLEXEC().

static void getActivityResidualsUpperBound ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  row, int  col, SCIP_Real  coef, int  upperboundcol, SCIP_Real  upperboundcoef, SCIP_Real *  minresactivity, SCIP_Real *  maxresactivity, SCIP_Bool *  success  )

static

get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound

Definition at line 1033 of file presol_domcol.c.

References FALSE, NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by calcVarBoundsDominated().

static void getActivityResidualsLowerBound ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  row, int  col, SCIP_Real  coef, int  lowerboundcol, SCIP_Real  lowerboundcoef, SCIP_Real *  minresactivity, SCIP_Real *  maxresactivity, SCIP_Bool *  success  )

static

get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	row index
col	column index
coef	coefficient of the column in this row
lowerboundcol	column index of variable to set to its lower bound
lowerboundcoef	coefficient in this row of the column to be set to its lower bound
minresactivity	minimum residual activity of this row
maxresactivity	maximum residual activity of this row
success	pointer to store whether the computation was successful

Definition at line 1210 of file presol_domcol.c.

References FALSE, NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by calcVarBoundsDominating().

static SCIP_RETCODE calcVarBoundsDominated ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  row, int  coldominating, SCIP_Real  valdominating, int  coldominated, SCIP_Real  valdominated, SCIP_Bool *  ubcalculated, SCIP_Real *  calculatedub, SCIP_Bool *  wclbcalculated, SCIP_Real *  calculatedwclb, SCIP_Bool *  lbcalculated, SCIP_Real *  calculatedlb, SCIP_Bool *  wcubcalculated, SCIP_Real *  calculatedwcub  )

static

Calculate bounds of the dominated variable by rowbound analysis. We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound.

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	current row index
coldominating	column index of dominating variable
valdominating	row coefficient of dominating variable
coldominated	column index of dominated variable
valdominated	row coefficient of dominated variable
ubcalculated	was a upper bound calculated?
calculatedub	predicted upper bound
wclbcalculated	was a lower worst case bound calculated?
calculatedwclb	predicted worst case lower bound
lbcalculated	was a lower bound calculated?
calculatedlb	predicted lower bound
wcubcalculated	was a worst case upper bound calculated?
calculatedwcub	calculated worst case upper bound

Definition at line 1389 of file presol_domcol.c.

References FALSE, getActivityResidualsUpperBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetStatus(), and TRUE.

Referenced by updateBounds().

static SCIP_RETCODE calcVarBoundsDominating ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  row, int  coldominating, SCIP_Real  valdominating, int  coldominated, SCIP_Real  valdominated, SCIP_Bool *  ubcalculated, SCIP_Real *  calculatedub, SCIP_Bool *  wclbcalculated, SCIP_Real *  calculatedwclb, SCIP_Bool *  lbcalculated, SCIP_Real *  calculatedlb, SCIP_Bool *  wcubcalculated, SCIP_Real *  calculatedwcub  )

static

Calculate bounds of the dominating variable by rowbound analysis. We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound.

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	current row index
coldominating	column index of dominating variable
valdominating	row coefficient of dominating variable
coldominated	column index of dominated variable
valdominated	row coefficient of dominated variable
ubcalculated	was a upper bound calculated?
calculatedub	predicted upper bound
wclbcalculated	was a lower worst case bound calculated?
calculatedwclb	predicted worst case lower bound
lbcalculated	was a lower bound calculated?
calculatedlb	predicted lower bound
wcubcalculated	was a worst case upper bound calculated?
calculatedwcub	calculated worst case upper bound

Definition at line 1564 of file presol_domcol.c.

References FALSE, getActivityResidualsLowerBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetStatus(), and TRUE.

Referenced by updateBounds().

static SCIP_RETCODE updateBounds ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  row, int  col1, SCIP_Real  val1, int  col2, SCIP_Real  val2, SCIP_Bool  predictdominating, SCIP_Real *  upperbound, SCIP_Real *  wclowerbound, SCIP_Real *  lowerbound, SCIP_Real *  wcupperbound  )

static

try to find new variable bounds and update them when they are better then the old bounds

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
row	row index
col1	dominating variable index
val1	dominating variable coefficient
col2	dominated variable index
val2	dominated variable coefficient
predictdominating	flag indicating if bounds of dominating or dominated variable are predicted
upperbound	predicted upper bound
wclowerbound	predicted worst case lower bound
lowerbound	predicted lower bound
wcupperbound	predicted worst case upper bound

Definition at line 1737 of file presol_domcol.c.

References calcVarBoundsDominated(), calcVarBoundsDominating(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPinfinity().

Referenced by findDominancePairs().

static SCIP_RETCODE detectParallelCols ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int *  pclass, SCIP_Bool *  varineq  )

static

detect parallel columns by using the algorithm of Bixby and Wagner see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
pclass	parallel column classes
varineq	indicating if variable is within an equation

Definition at line 1820 of file presol_domcol.c.

References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisZero(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE predBndStr ( SCIP *  scip, SCIP_VAR *  dominatingvar, int  dominatingidx, SCIP_Real  dominatingub, SCIP_Real  dominatinglb, SCIP_Real  dominatingwcub, SCIP_VAR *  dominatedvar, int  dominatedidx, SCIP_Real  dominatedub, SCIP_Real  dominatedwclb, SCIP_Real  dominatedlb, FIXINGDIRECTION *  varstofix, int *  nchgbds  )

static

try to improve variable bounds by predictive bound strengthening

Parameters

scip	SCIP main data structure
dominatingvar	dominating variable
dominatingidx	column index of the dominating variable
dominatingub	predicted upper bound of the dominating variable
dominatinglb	predicted lower bound of the dominating variable
dominatingwcub	predicted worst case upper bound of the dominating variable
dominatedvar	dominated variable
dominatedidx	column index of the dominated variable
dominatedub	predicted upper bound of the dominated variable
dominatedwclb	predicted worst case lower bound of the dominated variable
dominatedlb	predicted lower bound of the dominated variable
varstofix	array holding fixing information
nchgbds	count number of bound changes

Definition at line 1990 of file presol_domcol.c.

References NOFIX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPceil(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebugMessage, SCIPfloor(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().

Referenced by findDominancePairs().

static SCIP_RETCODE findFixings ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_VAR *  dominatingvar, int  dominatingidx, SCIP_Real  dominatingub, SCIP_Real  dominatingwclb, SCIP_Real  dominatinglb, SCIP_Real  dominatingwcub, SCIP_VAR *  dominatedvar, int  dominatedidx, FIXINGDIRECTION *  varstofix, SCIP_Bool  onlybinvars, SCIP_Bool  onlyoneone, int *  nfixings  )

static

try to find variable fixings

Parameters

scip	SCIP main data structure
matrix	constraint matrix structure
dominatingvar	dominating variable
dominatingidx	column index of the dominating variable
dominatingub	predicted upper bound of the dominating variable
dominatingwclb	predicted worst case lower bound of the dominating variable
dominatinglb	predicted lower bound of the dominating variable
dominatingwcub	predicted worst case upper bound of the dominating variable
dominatedvar	dominated variable
dominatedidx	column index of the dominated variable
varstofix	array holding fixing information
onlybinvars	flag indicating only binary variables are present
onlyoneone	when onlybinvars is TRUE, flag indicates if both binary variables are in clique
nfixings	counter for possible fixings

Definition at line 2188 of file presol_domcol.c.

References FALSE, FIXATLB, FIXATUB, NOFIX, SCIP_OKAY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarsHaveCommonClique(), and TRUE.

Referenced by findDominancePairs().

static SCIP_RETCODE findDominancePairs ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_PRESOLDATA *  presoldata, int *  searchcols, int  searchsize, SCIP_Bool  onlybinvars, FIXINGDIRECTION *  varstofix, int *  nfixings, SCIP_Longint *  ndomrelations, int *  nchgbds  )

static

find dominance relation between variable pairs

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
presoldata	presolver data
searchcols	indexes of variables for pair comparisons
searchsize	number of variables for pair comparisons
onlybinvars	flag indicating searchcols has only binary variable indexes
varstofix	array holding information for later upper/lower bound fixing
nfixings	found number of possible fixings
ndomrelations	found number of dominance relations
nchgbds	number of changed bounds

Definition at line 2327 of file presol_domcol.c.

References FALSE, findFixings(), FIXATLB, MIN, NOFIX, NULL, predBndStr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisFeasGE(), SCIPisGE(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and updateBounds().

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE singletonColumnStuffing ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_Bool *  varsprocessed, FIXINGDIRECTION *  varstofix, int *  nfixings  )

static

try to fix singleton column continuous variables

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
varsprocessed	array indicating that this variable has been processed
varstofix	array holding fixing information
nfixings	number of possible fixings

Definition at line 2711 of file presol_domcol.c.

References BMSclearMemoryArray, FALSE, FIXATLB, FIXATUB, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPsortRealRealIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_DECL_PRESOLCOPY ( presolCopyDomcol  )

static

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

Definition at line 3032 of file presol_domcol.c.

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

static SCIP_DECL_PRESOLFREE ( presolFreeDomcol  )

static

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

Definition at line 3046 of file presol_domcol.c.

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

static SCIP_DECL_PRESOLEXEC ( presolExecDomcol  )

static

execution method of presolver

Definition at line 3062 of file presol_domcol.c.

References BMSclearMemoryArray, detectParallelCols(), FALSE, findDominancePairs(), FIXATLB, FIXATUB, freeMatrix(), initMatrix(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPdebugMessage, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetStage(), SCIPinProbing(), SCIPisFeasIntegral(), SCIPisNLPEnabled(), SCIPisStopped(), SCIPpresolGetData(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), singletonColumnStuffing(), and TRUE.

SCIP_RETCODE SCIPincludePresolDomcol

(

SCIP *

scip

)

creates the domcol presolver and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 3501 of file presol_domcol.c.

References DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, DEFAULT_PREDBNDSTR, DEFAULT_SINGCOLSTUFF, FALSE, NULL, PRESOL_DELAY, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludePresolBasic(), SCIPsetPresolCopy(), SCIPsetPresolExitpre(), and SCIPsetPresolFree().

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().