presol_implint.c File Reference

Detailed Description

Presolver that detects implicit integer variables.

Author

Rolf van der Hulst

Definition in file presol_implint.c.

#include <assert.h>
#include "scip/presol_implint.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_network.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.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_timing.h"
#include "scip/scip_var.h"
#include "scip/cons_and.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_or.h"
#include "scip/cons_setppc.h"
#include "scip/cons_varbound.h"
#include "scip/cons_xor.h"

Go to the source code of this file.

Data Structures
struct	ImplintMatrix
struct	MatrixComponents
struct	MatrixStatistics
struct	IntegerCandidateData

Macros
#define	PRESOL_NAME   "implint"
#define	PRESOL_DESC   "detects implicit integer variables"
#define	PRESOL_PRIORITY   -900000
#define	PRESOL_MAXROUNDS   0
#define	PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
#define	DEFAULT_CONVERTINTEGERS   FALSE
#define	DEFAULT_COLUMNROWRATIO   50.0
#define	DEFAULT_NUMERICSLIMIT   1e8

Functions
static SCIP_Real *	matrixGetColumnVals (IMPLINT_MATRIX *matrix, int column)
static int *	matrixGetColumnInds (IMPLINT_MATRIX *matrix, int column)
static int	matrixGetColumnNNonzs (IMPLINT_MATRIX *matrix, int column)
static SCIP_Real *	matrixGetRowVals (IMPLINT_MATRIX *matrix, int row)
static int *	matrixGetRowInds (IMPLINT_MATRIX *matrix, int row)
static int	matrixGetRowNNonzs (IMPLINT_MATRIX *matrix, int row)
static int	matrixGetNRows (IMPLINT_MATRIX *matrix)
static int	matrixGetNCols (IMPLINT_MATRIX *matrix)
static SCIP_VAR *	matrixGetVar (IMPLINT_MATRIX *matrix, int column)
static SCIP_Bool	matrixColIsIntegral (IMPLINT_MATRIX *matrix, int column)
static SCIP_Bool	matrixColIsImpliedIntegral (IMPLINT_MATRIX *matrix, int column)
static SCIP_Bool	matrixColInNonlinearTerm (IMPLINT_MATRIX *matrix, int column)
static SCIP_Real	matrixGetColLb (IMPLINT_MATRIX *matrix, int column)
static SCIP_Real	matrixGetColUb (IMPLINT_MATRIX *matrix, int column)
static SCIP_Real	matrixGetRowLhs (IMPLINT_MATRIX *matrix, int row)
static SCIP_Real	matrixGetRowRhs (IMPLINT_MATRIX *matrix, int row)
static SCIP_RETCODE	getActiveVariables (SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant)
static SCIP_RETCODE	matrixAddRow (SCIP *scip, IMPLINT_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_CONS *cons)
static SCIP_RETCODE	addLinearConstraint (SCIP *scip, IMPLINT_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_CONS *cons)
static SCIP_RETCODE	addAndOrLinearization (SCIP *scip, IMPLINT_MATRIX *matrix, SCIP_CONS *cons, SCIP_VAR **operands, int noperands, SCIP_VAR *resultant, SCIP_Bool isAndCons)
static SCIP_RETCODE	addXorLinearization (SCIP *scip, IMPLINT_MATRIX *matrix, SCIP_CONS *cons, SCIP_VAR **operands, int noperands, SCIP_VAR *intvar, SCIP_Real rhs)
static SCIP_RETCODE	matrixSetColumnMajor (SCIP *scip, IMPLINT_MATRIX *matrix)
static SCIP_RETCODE	matrixCreate (SCIP *scip, IMPLINT_MATRIX **pmatrix)
static void	matrixFree (SCIP *scip, IMPLINT_MATRIX **pmatrix)
static SCIP_RETCODE	createMatrixComponents (SCIP *scip, IMPLINT_MATRIX *matrix, MATRIX_COMPONENTS **pmatrixcomponents)
static void	freeMatrixComponents (SCIP *scip, MATRIX_COMPONENTS **pmatrixcomponents)
static int	disjointSetFind (int *disjointset, int ind)
static int	disjointSetMerge (int *disjointset, int first, int second)
static SCIP_RETCODE	computeContinuousComponents (SCIP *scip, IMPLINT_MATRIX *matrix, MATRIX_COMPONENTS *comp, SCIP_Bool includeimplints)
static SCIP_RETCODE	computeMatrixStatistics (SCIP *scip, IMPLINT_MATRIX *matrix, MATRIX_STATISTICS **pstats, SCIP_Real numericslimit)
static void	freeMatrixStatistics (SCIP *scip, MATRIX_STATISTICS **pstats)
static SCIP_RETCODE	findImpliedIntegers (SCIP *scip, SCIP_PRESOLDATA *presoldata, IMPLINT_MATRIX *matrix, MATRIX_COMPONENTS *comp, MATRIX_STATISTICS *stats, int *nchgvartypes)
static	SCIP_DECL_PRESOLCOPY (presolCopyImplint)
static	SCIP_DECL_PRESOLFREE (presolFreeImplint)
static	SCIP_DECL_PRESOLEXEC (presolExecImplint)
SCIP_RETCODE	SCIPincludePresolImplint (SCIP *scip)

Macro Definition Documentation

PRESOL_NAME

#define PRESOL_NAME   "implint"

Definition at line 67 of file presol_implint.c.

PRESOL_DESC

#define PRESOL_DESC   "detects implicit integer variables"

Definition at line 68 of file presol_implint.c.

PRESOL_PRIORITY

#define PRESOL_PRIORITY   -900000

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

Definition at line 76 of file presol_implint.c.

PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   0

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

Definition at line 77 of file presol_implint.c.

PRESOL_TIMING

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

Definition at line 78 of file presol_implint.c.

DEFAULT_CONVERTINTEGERS

#define DEFAULT_CONVERTINTEGERS   FALSE

should implied integrality also be detected for enforced integral variables?

Definition at line 80 of file presol_implint.c.

Referenced by SCIPincludePresolImplint().

DEFAULT_COLUMNROWRATIO

#define DEFAULT_COLUMNROWRATIO   50.0

use the network row addition algorithm when the column to row ratio becomes larger than this threshold

Definition at line 81 of file presol_implint.c.

Referenced by SCIPincludePresolImplint().

DEFAULT_NUMERICSLIMIT

#define DEFAULT_NUMERICSLIMIT   1e8

a row that contains variables with coefficients that are greater in absolute value than this limit is not considered for implied integrality detection

Definition at line 82 of file presol_implint.c.

Referenced by SCIPincludePresolImplint().

Typedef Documentation

IMPLINT_MATRIX

typedef struct ImplintMatrix IMPLINT_MATRIX

Definition at line 133 of file presol_implint.c.

MATRIX_COMPONENTS

typedef struct MatrixComponents MATRIX_COMPONENTS

Definition at line 150 of file presol_implint.c.

MATRIX_STATISTICS

typedef struct MatrixStatistics MATRIX_STATISTICS

Definition at line 163 of file presol_implint.c.

INTEGER_CANDIDATE_DATA

typedef struct IntegerCandidateData INTEGER_CANDIDATE_DATA

Definition at line 173 of file presol_implint.c.

Function Documentation

matrixGetColumnVals()

SCIP_Real * matrixGetColumnVals ( IMPLINT_MATRIX * matrix, int column )

static

gets a pointer to the array of nonzero values for the nonzeros in the given column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 177 of file presol_implint.c.

References assert(), ImplintMatrix::colmatbeg, ImplintMatrix::colmatval, IntegerCandidateData::column, NULL, and SCIP_Real.

Referenced by findImpliedIntegers().

matrixGetColumnInds()

int * matrixGetColumnInds ( IMPLINT_MATRIX * matrix, int column )

static

gets a pointer to the array of row indices for the nonzeros in the given column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 191 of file presol_implint.c.

References assert(), ImplintMatrix::colmatbeg, ImplintMatrix::colmatind, IntegerCandidateData::column, and NULL.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixGetColumnNNonzs()

int matrixGetColumnNNonzs ( IMPLINT_MATRIX * matrix, int column )

static

gets the number of nonzeros in the given column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 205 of file presol_implint.c.

References assert(), ImplintMatrix::colmatcnt, IntegerCandidateData::column, and NULL.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixGetRowVals()

SCIP_Real * matrixGetRowVals ( IMPLINT_MATRIX * matrix, int row )

static

gets a pointer to the array of nonzero values for the nonzeros in the given row

Parameters

matrix	the matrix data structure
row	the row

Definition at line 219 of file presol_implint.c.

References assert(), NULL, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatval, and SCIP_Real.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetRowInds()

int * matrixGetRowInds ( IMPLINT_MATRIX * matrix, int row )

static

gets a pointer to the array of column indices for the nonzeros in the given row

Parameters

matrix	the matrix data structure
row	the row

Definition at line 233 of file presol_implint.c.

References assert(), NULL, ImplintMatrix::rowmatbeg, and ImplintMatrix::rowmatind.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetRowNNonzs()

int matrixGetRowNNonzs ( IMPLINT_MATRIX * matrix, int row )

static

gets the number of nonzeros in the given row

Parameters

matrix	the matrix data structure
row	the row

Definition at line 247 of file presol_implint.c.

References assert(), NULL, and ImplintMatrix::rowmatcnt.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetNRows()

int matrixGetNRows ( IMPLINT_MATRIX * matrix )

static

returns the number of rows in the matrix

Parameters

matrix

the matrix data structure

Definition at line 261 of file presol_implint.c.

References assert(), ImplintMatrix::nrows, and NULL.

Referenced by computeMatrixStatistics(), and createMatrixComponents().

matrixGetNCols()

int matrixGetNCols ( IMPLINT_MATRIX * matrix )

static

returns the number of columns in the matrix

Parameters

matrix

the matrix data structure

Definition at line 272 of file presol_implint.c.

References assert(), ImplintMatrix::ncols, and NULL.

Referenced by computeMatrixStatistics(), and createMatrixComponents().

matrixGetVar()

SCIP_VAR * matrixGetVar ( IMPLINT_MATRIX * matrix, int column )

static

returns the variable associated with the column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 283 of file presol_implint.c.

References assert(), IntegerCandidateData::column, ImplintMatrix::colvar, and NULL.

Referenced by findImpliedIntegers().

matrixColIsIntegral()

SCIP_Bool matrixColIsIntegral ( IMPLINT_MATRIX * matrix, int column )

static

returns TRUE if the given column originates from an integral variable

Parameters

matrix	the matrix data structure
column	the column

Definition at line 297 of file presol_implint.c.

References assert(), ImplintMatrix::colintegral, IntegerCandidateData::column, NULL, and SCIP_Bool.

Referenced by computeContinuousComponents(), computeMatrixStatistics(), and findImpliedIntegers().

matrixColIsImpliedIntegral()

SCIP_Bool matrixColIsImpliedIntegral ( IMPLINT_MATRIX * matrix, int column )

static

returns TRUE if the given column originates from an implied integral variable

Parameters

matrix	the matrix data structure
column	the column

Definition at line 311 of file presol_implint.c.

References assert(), ImplintMatrix::colimplintegral, IntegerCandidateData::column, NULL, and SCIP_Bool.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixColInNonlinearTerm()

SCIP_Bool matrixColInNonlinearTerm ( IMPLINT_MATRIX * matrix, int column )

static

returns TRUE if the given column occurs in a nonlinear expression in some constraint

Parameters

matrix	the matrix data structure
column	the column

Definition at line 325 of file presol_implint.c.

References assert(), ImplintMatrix::colinnonlinterm, IntegerCandidateData::column, NULL, and SCIP_Bool.

Referenced by findImpliedIntegers().

matrixGetColLb()

SCIP_Real matrixGetColLb ( IMPLINT_MATRIX * matrix, int column )

static

returns the lower bound of the given column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 339 of file presol_implint.c.

References assert(), IntegerCandidateData::column, ImplintMatrix::lb, NULL, and SCIP_Real.

Referenced by computeMatrixStatistics().

matrixGetColUb()

SCIP_Real matrixGetColUb ( IMPLINT_MATRIX * matrix, int column )

static

returns the upper bound of the given column

Parameters

matrix	the matrix data structure
column	the column

Definition at line 353 of file presol_implint.c.

References assert(), IntegerCandidateData::column, NULL, SCIP_Real, and ImplintMatrix::ub.

Referenced by computeMatrixStatistics().

matrixGetRowLhs()

SCIP_Real matrixGetRowLhs ( IMPLINT_MATRIX * matrix, int row )

static

returns the left hand side of the given row

Parameters

matrix	the matrix data structure
row	the row

Definition at line 367 of file presol_implint.c.

References assert(), ImplintMatrix::lhs, NULL, and SCIP_Real.

Referenced by computeMatrixStatistics().

matrixGetRowRhs()

SCIP_Real matrixGetRowRhs ( IMPLINT_MATRIX * matrix, int row )

static

returns the right hand side of the given row

Parameters

matrix	the matrix data structure
row	the row

Definition at line 381 of file presol_implint.c.

References assert(), NULL, ImplintMatrix::rhs, and SCIP_Real.

Referenced by computeMatrixStatistics().

getActiveVariables()

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 instance
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 395 of file presol_implint.c.

References assert(), NULL, nvars, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, and vars.

Referenced by addLinearConstraint(), and addXorLinearization().

matrixAddRow()

SCIP_RETCODE matrixAddRow ( SCIP * scip, IMPLINT_MATRIX * matrix, SCIP_VAR ** vars, SCIP_Real * vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_CONS * cons )

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
cons	constraint where the row originated from

Definition at line 430 of file presol_implint.c.

References assert(), ImplintMatrix::lhs, ImplintMatrix::nnonzs, ImplintMatrix::nnonzssize, ImplintMatrix::nrows, NULL, nvars, ImplintMatrix::rhs, ImplintMatrix::rowcons, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatcnt, ImplintMatrix::rowmatind, ImplintMatrix::rowmatval, SCIP_OKAY, SCIP_Real, SCIPisZero(), SCIPvarGetProbindex(), and vars.

Referenced by addLinearConstraint().

addLinearConstraint()

SCIP_RETCODE addLinearConstraint ( SCIP * scip, IMPLINT_MATRIX * matrix, SCIP_VAR ** vars, SCIP_Real * vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_CONS * cons )

static

transforms the weighted sum to active variables and then adds the given linear constraint to the matrix

Parameters

scip	current scip instance
matrix	constraint matrix
vars	variables of this constraint
vals	variable coefficients of this constraint. **< If set to NULL, all values are assumed to be equal to 1.0.
nvars	number of variables
lhs	left hand side
rhs	right hand side
cons	constraint belonging to the row

Definition at line 478 of file presol_implint.c.

References assert(), getActiveVariables(), matrixAddRow(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), and vars.

Referenced by addAndOrLinearization(), addXorLinearization(), and matrixCreate().

addAndOrLinearization()

SCIP_RETCODE addAndOrLinearization ( SCIP * scip, IMPLINT_MATRIX * matrix, SCIP_CONS * cons, SCIP_VAR ** operands, int noperands, SCIP_VAR * resultant, SCIP_Bool isAndCons )

static

adds the linearization of a given AND constraint or OR constraint to the constraint matrix

Parameters

scip	current scip instance
matrix	constraint matrix
cons	The constraint that is linearized
operands	variables of this constraint
noperands	number of operands
resultant	Resultant variable
isAndCons	Indicates if the constraint is an AND or OR linearization

Definition at line 552 of file presol_implint.c.

References addLinearConstraint(), i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfinity(), and vars.

Referenced by matrixCreate().

addXorLinearization()

SCIP_RETCODE addXorLinearization ( SCIP * scip, IMPLINT_MATRIX * matrix, SCIP_CONS * cons, SCIP_VAR ** operands, int noperands, SCIP_VAR * intvar, SCIP_Real rhs )

static

adds the linearization of a given XOR constraint to the constraint matrix

Parameters

scip	current scip instance
matrix	constraint matrix
cons	The constraint that is linearized
operands	variables of this constraint
noperands	number of operands
intvar	the intvar of the xor constraint
rhs	the right hand side of the xor constraint

Definition at line 622 of file presol_implint.c.

References addLinearConstraint(), assert(), ImplintMatrix::colinnonlinterm, getActiveVariables(), i, ImplintMatrix::ncols, NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfinity(), SCIPisIntegral(), SCIPvarGetProbindex(), TRUE, and vars.

Referenced by matrixCreate().

matrixSetColumnMajor()

SCIP_RETCODE matrixSetColumnMajor ( SCIP * scip, IMPLINT_MATRIX * matrix )

static

transform row major format into column major format

Parameters

scip	current scip instance
matrix	constraint matrix

Definition at line 739 of file presol_implint.c.

References assert(), BMSclearMemoryArray, ImplintMatrix::colmatbeg, ImplintMatrix::colmatcnt, ImplintMatrix::colmatind, ImplintMatrix::colmatval, i, ImplintMatrix::ncols, ImplintMatrix::nrows, NULL, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatcnt, ImplintMatrix::rowmatind, ImplintMatrix::rowmatval, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by matrixCreate().

matrixCreate()

SCIP_RETCODE matrixCreate ( SCIP * scip, IMPLINT_MATRIX ** pmatrix )

static

create the matrix from the current transformed problem

Parameters

scip	the scip data structure
pmatrix	pointer to create the matrix at

Definition at line 808 of file presol_implint.c.

References addAndOrLinearization(), addLinearConstraint(), addXorLinearization(), assert(), c, ImplintMatrix::colimplintegral, ImplintMatrix::colinnonlinterm, ImplintMatrix::colintegral, ImplintMatrix::colmatbeg, ImplintMatrix::colmatcnt, ImplintMatrix::colmatind, ImplintMatrix::colmatval, ImplintMatrix::colvar, FALSE, i, ImplintMatrix::lb, ImplintMatrix::lhs, matrixSetColumnMajor(), ImplintMatrix::ncols, ImplintMatrix::nnonzs, ImplintMatrix::nnonzssize, ImplintMatrix::nrows, NULL, nvars, ImplintMatrix::rhs, ImplintMatrix::rowcons, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatcnt, ImplintMatrix::rowmatind, ImplintMatrix::rowmatval, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_LOCKTYPE_MODEL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPABORT, SCIPallocBuffer, SCIPallocBufferArray, SCIPconshdlrGetCheckConss(), SCIPconshdlrGetName(), SCIPconshdlrGetNCheckConss(), SCIPconsIsModifiable(), SCIPconsIsTransformed(), SCIPduplicateBufferArray, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetCapacityKnapsack(), SCIPgetConshdlrs(), SCIPgetIntVarXor(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNActivePricers(), SCIPgetNConshdlrs(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetNVarsAnd(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsOr(), SCIPgetNVarsSetppc(), SCIPgetNVarsXor(), SCIPgetResultantAnd(), SCIPgetResultantOr(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetRhsXor(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVars(), SCIPgetVarsAnd(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsOr(), SCIPgetVarsSetppc(), SCIPgetVarsXor(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPinfinity(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarIsImpliedIntegral(), SCIPvarIsIntegral(), TRUE, ImplintMatrix::ub, and vars.

Referenced by SCIP_DECL_PRESOLEXEC().

matrixFree()

void matrixFree ( SCIP * scip, IMPLINT_MATRIX ** pmatrix )

static

frees the matrix from memory

Parameters

scip	the scip data structure
pmatrix	pointer to the allocated matrix

Definition at line 1199 of file presol_implint.c.

References assert(), ImplintMatrix::colimplintegral, ImplintMatrix::colinnonlinterm, ImplintMatrix::colintegral, ImplintMatrix::colmatbeg, ImplintMatrix::colmatcnt, ImplintMatrix::colmatind, ImplintMatrix::colmatval, ImplintMatrix::colvar, ImplintMatrix::lb, ImplintMatrix::lhs, ImplintMatrix::ncols, ImplintMatrix::nnonzs, ImplintMatrix::nrows, NULL, ImplintMatrix::rhs, ImplintMatrix::rowcons, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatcnt, ImplintMatrix::rowmatind, ImplintMatrix::rowmatval, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, and ImplintMatrix::ub.

Referenced by SCIP_DECL_PRESOLEXEC().

createMatrixComponents()

SCIP_RETCODE createMatrixComponents ( SCIP * scip, IMPLINT_MATRIX * matrix, MATRIX_COMPONENTS ** pmatrixcomponents )

static

creates the matrix components data structure

Parameters

scip	SCIP data structure
matrix	The constraint matrix
pmatrixcomponents	Pointer to create the matrix components data structure

Definition at line 1254 of file presol_implint.c.

References MatrixComponents::colcomponent, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, i, matrixGetNCols(), matrixGetNRows(), MatrixComponents::ncomponents, MatrixComponents::nmatrixcols, MatrixComponents::nmatrixrows, MatrixComponents::rowcomponent, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.

Referenced by findImpliedIntegers(), and SCIP_DECL_PRESOLEXEC().

freeMatrixComponents()

void freeMatrixComponents ( SCIP * scip, MATRIX_COMPONENTS ** pmatrixcomponents )

static

frees the matrix components data structure

Parameters

scip	SCIP data structure
pmatrixcomponents	Pointer to the allocated matrix components data structure

Definition at line 1295 of file presol_implint.c.

References MatrixComponents::colcomponent, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, MatrixComponents::rowcomponent, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by findImpliedIntegers(), and SCIP_DECL_PRESOLEXEC().

disjointSetFind()

int disjointSetFind ( int * disjointset, int ind )

static

finds the representative of an element in the disjoint set datastructure Afterwards compresses the path to speed up subsequent queries.

Parameters

disjointset	The array storing the disjoint set representatives
ind	The index to find

Definition at line 1317 of file presol_implint.c.

References assert(), and NULL.

Referenced by computeContinuousComponents().

disjointSetMerge()

int disjointSetMerge ( int * disjointset, int first, int second )

static

merges two sets/elements into one set. Returns the index of the merged element The provided elements to be merged must be representative (i.e. returned by disjointSetFind()).

Parameters

disjointset	The array storing the disjoint set representatives
first	The first index to merge
second	The second index to merge

Definition at line 1348 of file presol_implint.c.

References assert(), and SCIPswapInts().

Referenced by computeContinuousComponents().

computeContinuousComponents()

SCIP_RETCODE computeContinuousComponents ( SCIP * scip, IMPLINT_MATRIX * matrix, MATRIX_COMPONENTS * comp, SCIP_Bool includeimplints )

static

computes the connected components of the submatrix given by all continuous columns

Parameters

scip	SCIP data structure
matrix	the constraint matrix to compute the components for
comp	the connected components data structure to store the components in
includeimplints	should implied integral variables be treated continuous?

Definition at line 1381 of file presol_implint.c.

References assert(), MatrixComponents::colcomponent, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, disjointSetFind(), disjointSetMerge(), i, matrixColIsImpliedIntegral(), matrixColIsIntegral(), matrixGetColumnInds(), matrixGetColumnNNonzs(), MatrixComponents::ncomponents, MatrixComponents::nmatrixcols, MatrixComponents::nmatrixrows, MatrixComponents::rowcomponent, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by findImpliedIntegers(), and SCIP_DECL_PRESOLEXEC().

computeMatrixStatistics()

SCIP_RETCODE computeMatrixStatistics ( SCIP * scip, IMPLINT_MATRIX * matrix, MATRIX_STATISTICS ** pstats, SCIP_Real numericslimit )

static

creates the matrix statistics data structure

Parameters

scip	SCIP data structure
matrix	The constraint matrix to compute the statistics for
pstats	Pointer to allocate the statistics data structure at
numericslimit	The limit beyond which we consider integrality of coefficients to be unreliable

Definition at line 1535 of file presol_implint.c.

References ABS, assert(), MatrixStatistics::colintegralbounds, FALSE, i, matrixColIsIntegral(), matrixGetColLb(), matrixGetColUb(), matrixGetNCols(), matrixGetNRows(), matrixGetRowInds(), matrixGetRowLhs(), matrixGetRowNNonzs(), matrixGetRowRhs(), matrixGetRowVals(), MatrixStatistics::rowbadnumerics, MatrixStatistics::rowequality, MatrixStatistics::rowintegral, MatrixStatistics::rowncontinuous, MatrixStatistics::rowncontinuouspmone, MatrixStatistics::rownnonz, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIPisIntegral(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

freeMatrixStatistics()

void freeMatrixStatistics ( SCIP * scip, MATRIX_STATISTICS ** pstats )

static

frees the matrix statistics data structure

Parameters

scip	SCIP data structure
pstats	Pointer to the statistics data structure to be freed

Definition at line 1624 of file presol_implint.c.

References MatrixStatistics::colintegralbounds, MatrixStatistics::rowbadnumerics, MatrixStatistics::rowequality, MatrixStatistics::rowintegral, MatrixStatistics::rowncontinuous, MatrixStatistics::rowncontinuouspmone, MatrixStatistics::rownnonz, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_PRESOLEXEC().

findImpliedIntegers()

SCIP_RETCODE findImpliedIntegers ( SCIP * scip, SCIP_PRESOLDATA * presoldata, IMPLINT_MATRIX * matrix, MATRIX_COMPONENTS * comp, MATRIX_STATISTICS * stats, int * nchgvartypes )

static

detects components of implied integral variables Given the continuous components and statistics on the matrix, each component is checked if the associated matrix describes either a network or a transposed network (or both, in which case it is represented by a planar graph) and whether bounds/sides/coefficients are integral. We choose to check if it is a (transposed) network matrix either in a row-wise or in a column-wise fashion, depending on the size of the component. Finally, every variable that is in a network matrix or transposed network matrix is derived to be weakly implied integral.

Parameters

scip	SCIP data structure
presoldata	data belonging to the presolver
matrix	constraint matrix to compute implied integral variables for
comp	continuous connected components of the matrix
stats	statistics of the matrix
nchgvartypes	pointer to count the number of changed variable types

Definition at line 1652 of file presol_implint.c.

References ABS, assert(), MatrixComponents::colcomponent, MatrixStatistics::colintegralbounds, IntegerCandidateData::column, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, computeContinuousComponents(), createMatrixComponents(), FALSE, freeMatrixComponents(), i, matrixColInNonlinearTerm(), matrixColIsImpliedIntegral(), matrixColIsIntegral(), matrixGetColumnInds(), matrixGetColumnNNonzs(), matrixGetColumnVals(), matrixGetRowInds(), matrixGetRowNNonzs(), matrixGetRowVals(), matrixGetVar(), MatrixComponents::ncomponents, MatrixComponents::nmatrixcols, MatrixComponents::nmatrixrows, NULL, IntegerCandidateData::numContNetworkEntries, IntegerCandidateData::numContPlanarEntries, IntegerCandidateData::numContTransNetworkEntries, MatrixStatistics::rowbadnumerics, MatrixComponents::rowcomponent, MatrixStatistics::rowintegral, MatrixStatistics::rowncontinuous, MatrixStatistics::rowncontinuouspmone, SCIP_Bool, SCIP_CALL, SCIP_IMPLINTTYPE_WEAK, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPblkmem(), SCIPchgVarImplType(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPisEQ(), SCIPnetmatdecContainsColumn(), SCIPnetmatdecContainsRow(), SCIPnetmatdecCreate(), SCIPnetmatdecFree(), SCIPnetmatdecRemoveComponent(), SCIPnetmatdecTryAddCol(), SCIPnetmatdecTryAddRow(), SCIPsortDownRealInt(), SCIPvarGetType(), SCIPvarIsIntegral(), SCIPvarIsNonimpliedIntegral(), TRUE, and var.

Referenced by SCIP_DECL_PRESOLEXEC().

SCIP_DECL_PRESOLCOPY()

SCIP_DECL_PRESOLCOPY ( presolCopyImplint )

static

copy method for presolver plugins (called when SCIP copies plugins)

Definition at line 2197 of file presol_implint.c.

References assert(), NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPfindPresol(), SCIPincludePresolImplint(), SCIPpresolGetData(), and SCIPpresolGetName().

SCIP_DECL_PRESOLFREE()

SCIP_DECL_PRESOLFREE ( presolFreeImplint )

static

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

Definition at line 2221 of file presol_implint.c.

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

SCIP_DECL_PRESOLEXEC()

SCIP_DECL_PRESOLEXEC ( presolExecImplint )

static

execution method of presolver

Definition at line 2237 of file presol_implint.c.

References assert(), computeContinuousComponents(), computeMatrixStatistics(), createMatrixComponents(), FALSE, findImpliedIntegers(), freeMatrixComponents(), freeMatrixStatistics(), matrixCreate(), matrixFree(), NULL, result, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallowStrongDualReds(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPinProbing(), SCIPisNLPEnabled(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolGetData(), SCIPverbMessage(), and TRUE.