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

Typedefs
typedef struct ImplintMatrix	IMPLINT_MATRIX
typedef struct MatrixComponents	MATRIX_COMPONENTS
typedef struct MatrixStatistics	MATRIX_STATISTICS
typedef struct IntegerCandidateData	INTEGER_CANDIDATE_DATA

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.

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.

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.

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

static 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 ImplintMatrix::colmatbeg, ImplintMatrix::colmatval, IntegerCandidateData::column, and NULL.

Referenced by findImpliedIntegers().

matrixGetColumnInds()

static 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 ImplintMatrix::colmatbeg, ImplintMatrix::colmatind, IntegerCandidateData::column, and NULL.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixGetColumnNNonzs()

static 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 ImplintMatrix::colmatcnt, IntegerCandidateData::column, and NULL.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixGetRowVals()

static 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 NULL, ImplintMatrix::rowmatbeg, and ImplintMatrix::rowmatval.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetRowInds()

static 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 NULL, ImplintMatrix::rowmatbeg, and ImplintMatrix::rowmatind.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetRowNNonzs()

static 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 NULL, and ImplintMatrix::rowmatcnt.

Referenced by computeMatrixStatistics(), and findImpliedIntegers().

matrixGetNRows()

static 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 ImplintMatrix::nrows, and NULL.

Referenced by computeMatrixStatistics(), and createMatrixComponents().

matrixGetNCols()

static 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 ImplintMatrix::ncols, and NULL.

Referenced by computeMatrixStatistics(), and createMatrixComponents().

matrixGetVar()

static 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 IntegerCandidateData::column, ImplintMatrix::colvar, and NULL.

Referenced by findImpliedIntegers().

matrixColIsIntegral()

static 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 ImplintMatrix::colintegral, IntegerCandidateData::column, and NULL.

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

matrixColIsImpliedIntegral()

static 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 ImplintMatrix::colimplintegral, IntegerCandidateData::column, and NULL.

Referenced by computeContinuousComponents(), and findImpliedIntegers().

matrixColInNonlinearTerm()

static 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 ImplintMatrix::colinnonlinterm, IntegerCandidateData::column, and NULL.

Referenced by findImpliedIntegers().

matrixGetColLb()

static 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 IntegerCandidateData::column, ImplintMatrix::lb, and NULL.

Referenced by computeMatrixStatistics().

matrixGetColUb()

static 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 IntegerCandidateData::column, NULL, and ImplintMatrix::ub.

Referenced by computeMatrixStatistics().

matrixGetRowLhs()

static 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 ImplintMatrix::lhs, and NULL.

Referenced by computeMatrixStatistics().

matrixGetRowRhs()

static 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 NULL, and ImplintMatrix::rhs.

Referenced by computeMatrixStatistics().

getActiveVariables()

static 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 NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), and SCIPreallocBufferArray.

Referenced by addLinearConstraint(), and addXorLinearization().

matrixAddRow()

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

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 ImplintMatrix::lhs, ImplintMatrix::nnonzs, ImplintMatrix::nnonzssize, ImplintMatrix::nrows, NULL, ImplintMatrix::rhs, ImplintMatrix::rowcons, ImplintMatrix::rowmatbeg, ImplintMatrix::rowmatcnt, ImplintMatrix::rowmatind, ImplintMatrix::rowmatval, SCIP_OKAY, SCIPisZero(), and SCIPvarGetProbindex().

Referenced by addLinearConstraint().

addLinearConstraint()

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

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 getActiveVariables(), matrixAddRow(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), and SCIPisPositive().

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

addAndOrLinearization()

static 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(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPinfinity().

Referenced by matrixCreate().

addXorLinearization()

static 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(), ImplintMatrix::colinnonlinterm, getActiveVariables(), ImplintMatrix::ncols, NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfinity(), SCIPisIntegral(), SCIPvarGetProbindex(), and TRUE.

Referenced by matrixCreate().

matrixSetColumnMajor()

static 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 BMSclearMemoryArray, ImplintMatrix::colmatbeg, ImplintMatrix::colmatcnt, ImplintMatrix::colmatind, ImplintMatrix::colmatval, 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()

static 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(), ImplintMatrix::colimplintegral, ImplintMatrix::colinnonlinterm, ImplintMatrix::colintegral, ImplintMatrix::colmatbeg, ImplintMatrix::colmatcnt, ImplintMatrix::colmatind, ImplintMatrix::colmatval, ImplintMatrix::colvar, FALSE, ImplintMatrix::lb, ImplintMatrix::lhs, matrixSetColumnMajor(), ImplintMatrix::ncols, ImplintMatrix::nnonzs, ImplintMatrix::nnonzssize, ImplintMatrix::nrows, NULL, 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, and ImplintMatrix::ub.

Referenced by SCIP_DECL_PRESOLEXEC().

matrixFree()

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

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

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

static 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 NULL.

Referenced by computeContinuousComponents().

disjointSetMerge()

static 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 SCIPswapInts().

Referenced by computeContinuousComponents().

computeContinuousComponents()

static 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 MatrixComponents::colcomponent, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, disjointSetFind(), disjointSetMerge(), matrixColIsImpliedIntegral(), matrixColIsIntegral(), matrixGetColumnInds(), matrixGetColumnNNonzs(), MatrixComponents::ncomponents, MatrixComponents::nmatrixcols, MatrixComponents::nmatrixrows, MatrixComponents::rowcomponent, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by findImpliedIntegers(), and SCIP_DECL_PRESOLEXEC().

computeMatrixStatistics()

static 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, MatrixStatistics::colintegralbounds, FALSE, 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()

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

static 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, MatrixComponents::colcomponent, MatrixStatistics::colintegralbounds, IntegerCandidateData::column, MatrixComponents::componentcolend, MatrixComponents::componentcols, MatrixComponents::componentrowend, MatrixComponents::componentrows, computeContinuousComponents(), createMatrixComponents(), FALSE, freeMatrixComponents(), 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(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

SCIP_DECL_PRESOLCOPY()

static 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 NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPfindPresol(), SCIPincludePresolImplint(), SCIPpresolGetData(), and SCIPpresolGetName().

SCIP_DECL_PRESOLFREE()

static 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 NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolSetData().

SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecImplint  )

static

execution method of presolver

Definition at line 2237 of file presol_implint.c.

References computeContinuousComponents(), computeMatrixStatistics(), createMatrixComponents(), FALSE, findImpliedIntegers(), freeMatrixComponents(), freeMatrixStatistics(), matrixCreate(), matrixFree(), NULL, 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.