Scippy

SCIP

Solving Constraint Integer Programs

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 "blockmemshell/memory.h"
#include "scip/presol_domcol.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.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_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define PRESOL_NAME   "domcol"
 
#define PRESOL_DESC   "dominated column presolver"
 
#define PRESOL_PRIORITY   -1000
 
#define PRESOL_MAXROUNDS   -1
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define DEFAULT_NUMMINPAIRS   1024
 
#define DEFAULT_NUMMAXPAIRS   1048576
 
#define DEFAULT_PREDBNDSTR   FALSE
 
#define DEFAULT_CONTINUOUS_RED   TRUE
 

Typedefs

typedef enum Fixingdirection FIXINGDIRECTION
 

Enumerations

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

Functions

static void getActivityResidualsUpperBound (SCIP *scip, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *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, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, int *searchcols, int searchsize, SCIP_Bool onlybinvars, FIXINGDIRECTION *varstofix, int *nfixings, SCIP_Longint *ndomrelations, int *nchgbds)
 
static SCIP_DECL_PRESOLCOPY (presolCopyDomcol)
 
static SCIP_DECL_PRESOLFREE (presolFreeDomcol)
 
static SCIP_DECL_PRESOLEXEC (presolExecDomcol)
 
SCIP_RETCODE SCIPincludePresolDomcol (SCIP *scip)
 

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME   "domcol"

Definition at line 61 of file presol_domcol.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDomcol().

◆ PRESOL_DESC

#define PRESOL_DESC   "dominated column presolver"

Definition at line 62 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   -1000

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

Definition at line 63 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   -1

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

Definition at line 64 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ PRESOL_TIMING

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

Definition at line 65 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ DEFAULT_NUMMINPAIRS

#define DEFAULT_NUMMINPAIRS   1024

minimal number of pair comparisons

Definition at line 67 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ DEFAULT_NUMMAXPAIRS

#define DEFAULT_NUMMAXPAIRS   1048576

maximal number of pair comparisons

Definition at line 68 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ DEFAULT_PREDBNDSTR

#define DEFAULT_PREDBNDSTR   FALSE

should predictive bound strengthening be applied?

Definition at line 70 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

◆ DEFAULT_CONTINUOUS_RED

#define DEFAULT_CONTINUOUS_RED   TRUE

should reductions for continuous variables be carried out?

Definition at line 71 of file presol_domcol.c.

Referenced by SCIPincludePresolDomcol().

Typedef Documentation

◆ FIXINGDIRECTION

Definition at line 96 of file presol_domcol.c.

Enumeration Type Documentation

◆ Fixingdirection

type of fixing direction

Enumerator
FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

FIXATLB 
NOFIX 

fix variable at its lower bound

FIXATUB 

no fixing

FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

Definition at line 90 of file presol_domcol.c.

Function Documentation

◆ getActivityResidualsUpperBound()

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

◆ getActivityResidualsLowerBound()

static void getActivityResidualsLowerBound ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
rowrow index
colcolumn index
coefcoefficient of the column in this row
lowerboundcolcolumn index of variable to set to its lower bound
lowerboundcoefcoefficient in this row of the column to be set to its lower bound
minresactivityminimum residual activity of this row
maxresactivitymaximum residual activity of this row
successpointer to store whether the computation was successful

Definition at line 421 of file presol_domcol.c.

References FALSE, NULL, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetNRows(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by calcVarBoundsDominating().

◆ calcVarBoundsDominated()

static SCIP_RETCODE calcVarBoundsDominated ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
rowcurrent row index
coldominatingcolumn index of dominating variable
valdominatingrow coefficient of dominating variable
coldominatedcolumn index of dominated variable
valdominatedrow coefficient of dominated variable
ubcalculatedwas a upper bound calculated?
calculatedubpredicted upper bound
wclbcalculatedwas a lower worst case bound calculated?
calculatedwclbpredicted worst case lower bound
lbcalculatedwas a lower bound calculated?
calculatedlbpredicted lower bound
wcubcalculatedwas a worst case upper bound calculated?
calculatedwcubcalculated worst case upper bound

Definition at line 600 of file presol_domcol.c.

References FALSE, getActivityResidualsUpperBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.

Referenced by updateBounds().

◆ calcVarBoundsDominating()

static SCIP_RETCODE calcVarBoundsDominating ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
rowcurrent row index
coldominatingcolumn index of dominating variable
valdominatingrow coefficient of dominating variable
coldominatedcolumn index of dominated variable
valdominatedrow coefficient of dominated variable
ubcalculatedwas a upper bound calculated?
calculatedubpredicted upper bound
wclbcalculatedwas a lower worst case bound calculated?
calculatedwclbpredicted worst case lower bound
lbcalculatedwas a lower bound calculated?
calculatedlbpredicted lower bound
wcubcalculatedwas a worst case upper bound calculated?
calculatedwcubcalculated worst case upper bound

Definition at line 775 of file presol_domcol.c.

References FALSE, getActivityResidualsLowerBound(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetStatus(), and TRUE.

Referenced by updateBounds().

◆ updateBounds()

static SCIP_RETCODE updateBounds ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
rowrow index
col1dominating variable index
val1dominating variable coefficient
col2dominated variable index
val2dominated variable coefficient
predictdominatingflag indicating if bounds of dominating or dominated variable are predicted
upperboundpredicted upper bound
wclowerboundpredicted worst case lower bound
lowerboundpredicted lower bound
wcupperboundpredicted worst case upper bound

Definition at line 948 of file presol_domcol.c.

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

Referenced by findDominancePairs().

◆ detectParallelCols()

static SCIP_RETCODE detectParallelCols ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
pclassparallel column classes
varineqindicating if variable is within an equation

Definition at line 1028 of file presol_domcol.c.

References BMSclearMemoryArray, NULL, r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixIsRowRhsInfinity(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

◆ predBndStr()

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
scipSCIP main data structure
dominatingvardominating variable
dominatingidxcolumn index of the dominating variable
dominatingubpredicted upper bound of the dominating variable
dominatinglbpredicted lower bound of the dominating variable
dominatingwcubpredicted worst case upper bound of the dominating variable
dominatedvardominated variable
dominatedidxcolumn index of the dominated variable
dominatedubpredicted upper bound of the dominated variable
dominatedwclbpredicted worst case lower bound of the dominated variable
dominatedlbpredicted lower bound of the dominated variable
varstofixarray holding fixing information
nchgbdscount number of bound changes

Definition at line 1199 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(), SCIPdebugMsg, SCIPfloor(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and SCIPvarIsBinary().

Referenced by findDominancePairs().

◆ findFixings()

static SCIP_RETCODE findFixings ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixconstraint matrix structure
dominatingvardominating variable
dominatingidxcolumn index of the dominating variable
dominatingubpredicted upper bound of the dominating variable
dominatingwclbpredicted worst case lower bound of the dominating variable
dominatinglbpredicted lower bound of the dominating variable
dominatingwcubpredicted worst case upper bound of the dominating variable
dominatedvardominated variable
dominatedidxcolumn index of the dominated variable
varstofixarray holding fixing information
onlybinvarsflag indicating only binary variables are present
onlyoneonewhen onlybinvars is TRUE, flag indicates if both binary variables are in clique
nfixingscounter for possible fixings

Definition at line 1397 of file presol_domcol.c.

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

Referenced by findDominancePairs().

◆ findDominancePairs()

static SCIP_RETCODE findDominancePairs ( SCIP scip,
SCIP_MATRIX 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
scipSCIP main data structure
matrixmatrix containing the constraints
presoldatapresolver data
searchcolsindexes of variables for pair comparisons
searchsizenumber of variables for pair comparisons
onlybinvarsflag indicating searchcols contains only binary variable indexes
varstofixarray holding information for later upper/lower bound fixing
nfixingsfound number of possible fixings
ndomrelationsfound number of dominance relations
nchgbdsnumber of changed bounds

Definition at line 1535 of file presol_domcol.c.

References FALSE, findFixings(), FIXATLB, MAX, NOFIX, NULL, predBndStr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGE(), SCIPisLT(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowMaxActivity(), SCIPmatrixGetRowMinActivity(), SCIPmatrixGetRowNMaxActNegInf(), SCIPmatrixGetRowNMaxActPosInf(), SCIPmatrixGetRowNMinActNegInf(), SCIPmatrixGetRowNMinActPosInf(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), TRUE, and updateBounds().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyDomcol  )
static

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

Definition at line 1969 of file presol_domcol.c.

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

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeDomcol  )
static

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

Definition at line 1983 of file presol_domcol.c.

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

◆ SCIP_DECL_PRESOLEXEC()