Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

dual inference presolver

Author
Dieter Weninger

This presolver does bound strengthening on continuous variables for getting better bounds on dual variables y. The bounds on the dual variables are then used to derive variable fixings or side changes. We distinguish two cases: i) positive reduced costs: c_j - sup{A_{.j}^T y} > 0 => x_j = l_j ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i

Definition in file presol_dualinfer.c.

#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/presol_dualinfer.h"
#include "scip/pub_cons.h"
#include "scip/pub_matrix.h"
#include "scip/pub_message.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_numerics.h"
#include "scip/scip_presol.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   "dualinfer"
 
#define PRESOL_DESC   "exploit dual informations for fixings and side changes"
 
#define PRESOL_PRIORITY   -2000
 
#define PRESOL_MAXROUNDS   0
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define MAX_LOOPS   3
 

Typedefs

typedef enum Fixingdirection FIXINGDIRECTION
 
typedef enum SideChange SIDECHANGE
 

Enumerations

enum  Fixingdirection {
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATLB = -1,
  NOFIX = 0,
  FIXATUB = 1
}
 
enum  SideChange {
  RHSTOLHS = -1,
  NOCHANGE = 0,
  LHSTORHS = 1
}
 

Functions

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 getVarUpperBoundOfRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound)
 
static SCIP_Bool isUpperBoundImplied (SCIP *scip, SCIP_MATRIX *matrix, int col)
 
static SCIP_Real getMinColActWithoutRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part)
 
static void calcColActResidual (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, int *mincolactinf, SCIP_Real *mincolresact)
 
static void calcColActivity (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool onlyconvars, int startcol, int stopcol, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
 
static void updateDualBounds (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, int *boundchanges, SCIP_Bool *updateinfcnt)
 
static void infCntUpdate (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real val, int row, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
 
static SCIP_RETCODE dualBoundStrengthening (SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
 
static SCIP_DECL_PRESOLCOPY (presolCopyDualinfer)
 
static SCIP_DECL_PRESOLEXEC (presolExecDualinfer)
 
SCIP_RETCODE SCIPincludePresolDualinfer (SCIP *scip)
 

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME   "dualinfer"

Definition at line 49 of file presol_dualinfer.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDualinfer().

◆ PRESOL_DESC

#define PRESOL_DESC   "exploit dual informations for fixings and side changes"

Definition at line 50 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   -2000

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

Definition at line 51 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   0

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

Definition at line 52 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ PRESOL_TIMING

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

Definition at line 53 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

◆ MAX_LOOPS

#define MAX_LOOPS   3

maximal number of dual bound strengthening loops

Definition at line 54 of file presol_dualinfer.c.

Referenced by dualBoundStrengthening().

Typedef Documentation

◆ FIXINGDIRECTION

Definition at line 68 of file presol_dualinfer.c.

◆ SIDECHANGE

typedef enum SideChange SIDECHANGE

Definition at line 77 of file presol_dualinfer.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 
FIXATLB 

fix variable at lower bound

NOFIX 

do not fix variable

FIXATUB 

fix variable at upper bound

Definition at line 63 of file presol_dualinfer.c.

◆ SideChange

enum SideChange

type of side change

Enumerator
RHSTOLHS 
NOCHANGE 
LHSTORHS 

Definition at line 71 of file presol_dualinfer.c.

Function Documentation

◆ getMaxActivitySingleRowWithoutCol()

static SCIP_Real getMaxActivitySingleRowWithoutCol ( 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 86 of file presol_dualinfer.c.

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

Referenced by getMinMaxActivityResiduals().

◆ getMinActivitySingleRowWithoutCol()

static SCIP_Real getMinActivitySingleRowWithoutCol ( 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 138 of file presol_dualinfer.c.

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

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 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 190 of file presol_dualinfer.c.

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

Referenced by getVarUpperBoundOfRow().

◆ getVarUpperBoundOfRow()

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

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

Definition at line 328 of file presol_dualinfer.c.

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

Referenced by isUpperBoundImplied().

◆ isUpperBoundImplied()

static SCIP_Bool isUpperBoundImplied ( SCIP scip,
SCIP_MATRIX matrix,
int  col 
)
static

verify which variable upper bounds are implied

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index for implied free test

Definition at line 378 of file presol_dualinfer.c.

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

Referenced by dualBoundStrengthening().

◆ getMinColActWithoutRow()

static SCIP_Real getMinColActWithoutRow ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  withoutrow,
SCIP_Real lbdual[2],
SCIP_Real ubdual[2],
int  part 
)
static

calculate minimal column activity from one continuous variable without one row

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index
withoutrowexclude row index
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
partwhich of part of the dual variables is active

Definition at line 423 of file presol_dualinfer.c.

References NULL, SCIP_Real, SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), and SCIPmatrixIsRowRhsInfinity().

Referenced by calcColActResidual().

◆ calcColActResidual()

static void calcColActResidual ( SCIP scip,
SCIP_MATRIX matrix,
int  col,
int  row,
SCIP_Real  val,
SCIP_Real lbdual[2],
SCIP_Real ubdual[2],
int  part,
SCIP_Real mincolact,
int *  mincolactinf,
SCIP_Real mincolresact 
)
static

calculate minimal/maximal column residual activities

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
colcolumn index
rowrow index
valmatrix coefficient
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
partwhich of part of the dual variables is active
mincolactminimal column activities
mincolactinfnumber of (negative) infinite contributions to minimal column activity
mincolresactminimal column residual activity

Definition at line 517 of file presol_dualinfer.c.

References getMinColActWithoutRow(), NULL, SCIPinfinity(), SCIPisInfinity(), and SCIPmatrixIsRowRhsInfinity().

Referenced by dualBoundStrengthening().

◆ calcColActivity()

static void calcColActivity ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Bool  onlyconvars,
int  startcol,
int  stopcol,
SCIP_Real lbdual[2],
SCIP_Real ubdual[2],
SCIP_Real mincolact,
SCIP_Real maxcolact,
int *  maxcolactinf,
int *  mincolactinf,
SCIP_Bool isimplfree 
)
static

calculate minimal/maximal column activities

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
onlyconvarsconsider only continuous variables for activity calculation
startcolstart column for activity calculations
stopcolstop column for activity calculations
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
mincolactminimal column activities
maxcolactmaximal column activities
maxcolactinfnumber of (positive) infinite contributions to maximal column activity
mincolactinfnumber of (negative) infinite contributions to minimal column activity
isimplfreeis upper bound of variable implied

Definition at line 585 of file presol_dualinfer.c.

References NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by dualBoundStrengthening(), and infCntUpdate().

◆ updateDualBounds()

static void updateDualBounds ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real  objval,
SCIP_Real  val,
int  row,
SCIP_Real  mincolresact,
SCIP_Real lbdual[2],
SCIP_Real ubdual[2],
int  part,
int *  boundchanges,
SCIP_Bool updateinfcnt 
)
static

update bounds on dual variables

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
objvalobjective function value
valmatrix coefficient
rowrow index
mincolresactminimal column residual activity
lbdualdual lower bounds (ranged, equality)
ubdualdual upper bounds (ranged, equatity)
partwhich of part of the dual variables is active
boundchangesnumber of bound changes
updateinfcntflag indicating to update infinity counters

Definition at line 731 of file presol_dualinfer.c.

References FALSE, NULL, SCIP_Real, SCIPisGE(), SCIPisInfinity(), SCIPmatrixIsRowRhsInfinity(), and TRUE.

Referenced by dualBoundStrengthening().

◆ infCntUpdate()

static void infCntUpdate ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real  val,
int  row,
SCIP_Real lbdual[2],
SCIP_Real ubdual[2],
int  part,
SCIP_Real mincolact,
SCIP_Real maxcolact,
int *  maxcolactinf,
int *  mincolactinf,
SCIP_Bool isimplfree 
)
static

update minimal/maximal column activity infinity counters

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
valmatrix coefficient
rowrow index
lbduallower bounds of dual variables
ubdualupper bounds of dual variables
partwhich part of the dual variables is active
mincolactminimal column activities
maxcolactmaximal column activities
maxcolactinfnumber of (positive) infinity contributions to maximal column activity
mincolactinfnumber of (negative) infinity contributions to minimal column activity
isimplfreeis upper bound of variable implied

Definition at line 799 of file presol_dualinfer.c.

References calcColActivity(), NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPisInfinity(), SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetType(), and TRUE.

Referenced by dualBoundStrengthening().

◆ dualBoundStrengthening()

static SCIP_RETCODE dualBoundStrengthening ( SCIP scip,
SCIP_MATRIX matrix,
FIXINGDIRECTION varstofix,
int *  npossiblefixings,
SIDECHANGE sidestochange,
int *  npossiblesidechanges 
)
static

dual bound strengthening

Parameters
scipSCIP main data structure
matrixmatrix containing the constraints
varstofixarray holding information for later upper/lower bound fixing
npossiblefixingsnumber of possible fixings
sidestochangearray holding if this is an implied equality
npossiblesidechangesnumber of possible equality changes

Definition at line 900 of file presol_dualinfer.c.

References calcColActivity(), calcColActResidual(), FALSE, FIXATLB, infCntUpdate(), isUpperBoundImplied(), LHSTORHS, MAX_LOOPS, NOCHANGE, NOFIX, NULL, r, RHSTOLHS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPmatrixGetColIdxPtr(), SCIPmatrixGetColNNonzs(), SCIPmatrixGetColValPtr(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), TRUE, and updateDualBounds().

Referenced by SCIP_DECL_PRESOLEXEC().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyDualinfer  )
static

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

Definition at line 1104 of file presol_dualinfer.c.

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

◆ SCIP_DECL_PRESOLEXEC()