presol_dualinfer.c File Reference

Detailed Description

dual inference presolver

Author

Dieter Weninger

This presolver exploits dual informations on continuous variables for fixings of integer/continuous variables and side changes.

Definition in file presol_dualinfer.c.

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "scip/pub_matrix.h"
#include "scip/cons_linear.h"
#include "presol_dualinfer.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   -200
#define	PRESOL_MAXROUNDS   0
#define	PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
#define	MAX_LOOPS   7

Typedefs
typedef enum Fixingdirection	FIXINGDIRECTION
typedef enum SideChange	SIDECHANGE

Enumerations
enum	Fixingdirection {   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	getMinColActWithoutRow (SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2])
static SCIP_Real	getMinColActWithoutBound (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Bool explicitub, SCIP_Bool explicitlb)
static void	calcColActResidualCommon (SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Real *mincolresact)
static void	calcColActResidualExplicitBound (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Bool explicitub, SCIP_Bool explicitlb, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Real *mincolresact)
static void	calcColActivity (SCIP *scip, SCIP_MATRIX *matrix, int startcol, int stopcol, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf)
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	updateDualBoundsExplicit (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, int col, SCIP_Real mincolresact, SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Bool explicitub, SCIP_Bool explicitlb, 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], SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], int part, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf)
static void	infCntUpdateExplicit (SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *lbdualbounds[2], SCIP_Real *ubdualbounds[2], SCIP_Bool explicitub, SCIP_Bool explicitlb, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf)
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

#define PRESOL_NAME   "dualinfer"

Definition at line 36 of file presol_dualinfer.c.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludePresolDualinfer().

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

Definition at line 37 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

#define PRESOL_PRIORITY   -200

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

Definition at line 38 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

#define PRESOL_MAXROUNDS   0

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

Definition at line 39 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

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

Definition at line 40 of file presol_dualinfer.c.

Referenced by SCIPincludePresolDualinfer().

#define MAX_LOOPS   7

maximal number of dual bound strengthening loops

Definition at line 41 of file presol_dualinfer.c.

Referenced by dualBoundStrengthening().

Typedef Documentation

typedef enum Fixingdirection FIXINGDIRECTION

Definition at line 55 of file presol_dualinfer.c.

typedef enum SideChange SIDECHANGE

Definition at line 64 of file presol_dualinfer.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
FIXATLB	fix variable at lower bound
NOFIX	do not fix variable
FIXATUB	fix variable at upper bound

Definition at line 50 of file presol_dualinfer.c.

enum SideChange

type of side change

Enumerator
RHSTOLHS
NOCHANGE
LHSTORHS

Definition at line 58 of file presol_dualinfer.c.

Function Documentation

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

static

calculate minimal column activity from one continuous variable without one row

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
withoutrow	exclude row index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
part	which of part of the dual variables is active
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds

Definition at line 73 of file presol_dualinfer.c.

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

Referenced by calcColActResidualCommon().

static SCIP_Real getMinColActWithoutBound ( SCIP *  scip, SCIP_MATRIX *  matrix, int  col, SCIP_Real *  lbdual[2], SCIP_Real *  ubdual[2], SCIP_Real *  lbdualbounds[2], SCIP_Real *  ubdualbounds[2], SCIP_Bool  explicitub, SCIP_Bool  explicitlb  )

static

calculate minimal column activity from one continuous variable without one row for explicit bounds

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds
explicitub	is this the explicit upper bound constraint
explicitlb	is this the explicit lower bound constraint

Definition at line 191 of file presol_dualinfer.c.

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

Referenced by calcColActResidualExplicitBound().

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

static

calculate minimal/maximal column residual activities

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
row	row index
val	matrix coefficient
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
part	which of part of the dual variables is active
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds
mincolact	minimal column activities
maxcolact	maximal column activities
maxcolactinf	number of (positive) infinite contributions to maximal column activity
mincolactinf	number of (negative) infinite contributions to minimal column activity
mincolresact	minimal column residual activity

Definition at line 278 of file presol_dualinfer.c.

References getMinColActWithoutRow(), NULL, SCIP_VARTYPE_CONTINUOUS, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetVar(), SCIPmatrixIsRowRhsInfinity(), and SCIPvarGetType().

Referenced by dualBoundStrengthening().

static void calcColActResidualExplicitBound ( SCIP *  scip, SCIP_MATRIX *  matrix, int  col, SCIP_Real *  lbdual[2], SCIP_Real *  ubdual[2], SCIP_Real *  lbdualbounds[2], SCIP_Real *  ubdualbounds[2], SCIP_Bool  explicitub, SCIP_Bool  explicitlb, SCIP_Real *  mincolact, SCIP_Real *  maxcolact, int *  maxcolactinf, int *  mincolactinf, SCIP_Real *  mincolresact  )

static

calculate minimal/maximal column residual activities of explicit bounds

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds
explicitub	is this the constraint for the explicit upper bound
explicitlb	is this the constraint for the explicit lower bound
mincolact	minimal column activities
maxcolact	maximal column activities
maxcolactinf	number of (positive) infinite contributions to maximal column activity
mincolactinf	number of (negative) infinite contributions to minimal column activity
mincolresact	minimal column residual activity

Definition at line 357 of file presol_dualinfer.c.

References getMinColActWithoutBound(), NULL, SCIP_VARTYPE_CONTINUOUS, SCIPinfinity(), SCIPisInfinity(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by dualBoundStrengthening().

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

static

calculate minimal/maximal column activity on continuous variables

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
startcol	start column index
stopcol	stop column index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds
mincolact	minimal column activities
maxcolact	maximal column activities
maxcolactinf	number of (positive) infinite contributions to maximal column activity
mincolactinf	number of (negative) infinite contributions to minimal column activity

Definition at line 443 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(), infCntUpdate(), and infCntUpdateExplicit().

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

scip	SCIP main data structure
matrix	matrix containing the constraints
objval	objective function value
val	matrix coefficient
row	row index
mincolresact	minimal column residual activity
lbdual	dual lower bounds (ranged, equality)
ubdual	dual upper bounds (ranged, equatity)
part	which of part of the dual variables is active
boundchanges	number of bound changes
updateinfcnt	flag indicating to update infinity counters

Definition at line 579 of file presol_dualinfer.c.

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

Referenced by dualBoundStrengthening().

static void updateDualBoundsExplicit ( SCIP *  scip, SCIP_MATRIX *  matrix, SCIP_Real  objval, int  col, SCIP_Real  mincolresact, SCIP_Real *  lbdualbounds[2], SCIP_Real *  ubdualbounds[2], SCIP_Bool  explicitub, SCIP_Bool  explicitlb, int *  boundchanges, SCIP_Bool *  updateinfcnt  )

static

update bounds on dual variables of explicit bounds

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
objval	objective function value
col	column index
mincolresact	minimal column residual activity
lbdualbounds	lower bounds of dual variables corresponding to variable bounds
ubdualbounds	upper bounds of dual variables corresponding to variable bounds
explicitub	flag indicating if explicit upper bound is active
explicitlb	flag indicating if explicit lower bound is active
boundchanges	number of bound changes
updateinfcnt	flag indicating to update infinity counters

Definition at line 644 of file presol_dualinfer.c.

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

Referenced by dualBoundStrengthening().

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

static

update minimal/maximal column activity infinity counters

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
val	matrix coefficient
row	row index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
lbdualbounds	lower bounds of dual variables corresponding to primal variable bounds
ubdualbounds	upper bounds of dual variables corresponding to primal variable bounds
part	which part of the dual variables is active
mincolact	minimal column activities
maxcolact	maximal column activities
maxcolactinf	number of (positive) infinity contributions to maximal column activity
mincolactinf	number of (negative) infinity contributions to minimal column activity

Definition at line 716 of file presol_dualinfer.c.

References calcColActivity(), NULL, SCIP_Real, SCIPmatrixGetRowIdxPtr(), SCIPmatrixGetRowNNonzs(), SCIPmatrixGetRowValPtr(), and SCIPmatrixIsRowRhsInfinity().

Referenced by dualBoundStrengthening().

static void infCntUpdateExplicit ( SCIP *  scip, SCIP_MATRIX *  matrix, int  col, SCIP_Real *  lbdual[2], SCIP_Real *  ubdual[2], SCIP_Real *  lbdualbounds[2], SCIP_Real *  ubdualbounds[2], SCIP_Bool  explicitub, SCIP_Bool  explicitlb, SCIP_Real *  mincolact, SCIP_Real *  maxcolact, int *  maxcolactinf, int *  mincolactinf  )

static

update minimal/maximal column activity infinity counters for explicit bounds

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
col	column index
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
lbdualbounds	lower bounds of dual variables corresponding to variable bounds
ubdualbounds	upper bounds of dual variables corresponding to variable bounds
explicitub	flag indicating if explicit upper bound is active
explicitlb	flag indicating if explicit lower bound is active
mincolact	minimal column activities
maxcolact	maximal column activities
maxcolactinf	number of (positive) infinity contributions to maximal column activity
mincolactinf	number of (negative) infinity contributions to minimal column activity

Definition at line 818 of file presol_dualinfer.c.

References calcColActivity(), NULL, SCIPisInfinity(), SCIPmatrixGetVar(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by dualBoundStrengthening().

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

static

dual bound strengthening

Parameters

scip	SCIP main data structure
matrix	matrix containing the constraints
varstofix	array holding information for later upper/lower bound fixing
npossiblefixings	number of possible fixings
sidestochange	array holding if this is an implied equality
npossiblesidechanges	number of possible equality changes

Definition at line 884 of file presol_dualinfer.c.

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

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_DECL_PRESOLCOPY ( presolCopyDualinfer  )

static

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

Definition at line 1107 of file presol_dualinfer.c.

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

static SCIP_DECL_PRESOLEXEC ( presolExecDualinfer  )

static

execution method of presolver

Definition at line 1121 of file presol_dualinfer.c.

References BMSclearMemoryArray, dualBoundStrengthening(), FIXATLB, NOCHANGE, NULL, RHSTOLHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallowDualReds(), SCIPchgLhsLinear(), SCIPchgRhsLinear(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPfixVar(), SCIPfreeBufferArray, SCIPgetLhsLinear(), SCIPgetNContVars(), SCIPgetRhsLinear(), SCIPgetStage(), SCIPinProbing(), SCIPisEQ(), SCIPmatrixCreate(), SCIPmatrixFree(), SCIPmatrixGetCons(), SCIPmatrixGetNColumns(), SCIPmatrixGetNRows(), SCIPmatrixGetRowLhs(), SCIPmatrixGetRowRhs(), SCIPmatrixGetVar(), SCIPvarGetLbLocal(), and SCIPvarGetType().

SCIP_RETCODE SCIPincludePresolDualinfer

(

SCIP *

scip

)

creates the dual inference presolver and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1293 of file presol_dualinfer.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().