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

typedef enum Fixingdirection 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

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

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

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

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

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
rowub	upper bound of row
ubfound	flag 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

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

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

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

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
mincolact	minimal column activities
mincolactinf	number of (negative) infinite contributions to minimal column activity
mincolresact	minimal 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

scip	SCIP main data structure
matrix	matrix containing the constraints
onlyconvars	consider only continuous variables for activity calculation
startcol	start column for activity calculations
stopcol	stop column for activity calculations
lbdual	lower bounds of dual variables
ubdual	upper bounds of dual variables
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
isimplfree	is 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

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

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

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

static SCIP_DECL_PRESOLEXEC ( presolExecDualinfer )

static

execution method of presolver

Definition at line 1118 of file presol_dualinfer.c.

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

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ MAX_LOOPS

Typedef Documentation

◆ FIXINGDIRECTION

◆ SIDECHANGE

Enumeration Type Documentation

◆ Fixingdirection

◆ SideChange

Function Documentation

◆ getMaxActivitySingleRowWithoutCol()

◆ getMinActivitySingleRowWithoutCol()

◆ getMinMaxActivityResiduals()

◆ getVarUpperBoundOfRow()

◆ isUpperBoundImplied()

◆ getMinColActWithoutRow()

◆ calcColActResidual()

◆ calcColActivity()

◆ updateDualBounds()

◆ infCntUpdate()

◆ dualBoundStrengthening()

◆ SCIP_DECL_PRESOLCOPY()

◆ SCIP_DECL_PRESOLEXEC()