Scippy

SCIP

Solving Constraint Integer Programs

matrix.c File Reference

Detailed Description

methods for MIP matrix data structure

Author
Dieter Weninger
Gerald Gamrath

The MIP matrix is organized as sparse data structure in row and and column major format.

Definition in file matrix.c.

#include <assert.h>
#include <string.h>
#include "scip/def.h"
#include "scip/struct_matrix.h"
#include "scip/pub_matrix.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/cons_varbound.h"

Go to the source code of this file.

Functions

static SCIP_RETCODE getActiveVariables (SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant)
 
static SCIP_RETCODE addRow (SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, int maxnnonzsmem, SCIP_Bool *rowadded)
 
static SCIP_RETCODE addConstraint (SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real lhs, SCIP_Real rhs, int maxnnonzsmem, SCIP_Bool *rowadded)
 
static SCIP_RETCODE setColumnMajorFormat (SCIP *scip, SCIP_MATRIX *matrix)
 
static SCIP_RETCODE calcActivityBounds (SCIP *scip, SCIP_MATRIX *matrix)
 
SCIP_RETCODE SCIPmatrixCreate (SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
 
void SCIPmatrixFree (SCIP *scip, SCIP_MATRIX **matrix)
 
void SCIPmatrixPrintRow (SCIP *scip, SCIP_MATRIX *matrix, int row)
 
SCIP_RETCODE SCIPmatrixGetParallelRows (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass)
 
SCIP_RETCODE SCIPmatrixGetParallelCols (SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *scale, int *pclass, SCIP_Bool *varineq)
 
SCIP_RealSCIPmatrixGetColValPtr (SCIP_MATRIX *matrix, int col)
 
int * SCIPmatrixGetColIdxPtr (SCIP_MATRIX *matrix, int col)
 
int SCIPmatrixGetColNNonzs (SCIP_MATRIX *matrix, int col)
 
int SCIPmatrixGetNColumns (SCIP_MATRIX *matrix)
 
SCIP_Real SCIPmatrixGetColUb (SCIP_MATRIX *matrix, int col)
 
SCIP_Real SCIPmatrixGetColLb (SCIP_MATRIX *matrix, int col)
 
int SCIPmatrixGetColNUplocks (SCIP_MATRIX *matrix, int col)
 
int SCIPmatrixGetColNDownlocks (SCIP_MATRIX *matrix, int col)
 
SCIP_VARSCIPmatrixGetVar (SCIP_MATRIX *matrix, int col)
 
const char * SCIPmatrixGetColName (SCIP_MATRIX *matrix, int col)
 
SCIP_RealSCIPmatrixGetRowValPtr (SCIP_MATRIX *matrix, int row)
 
int * SCIPmatrixGetRowIdxPtr (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetRowNNonzs (SCIP_MATRIX *matrix, int row)
 
const char * SCIPmatrixGetRowName (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetNRows (SCIP_MATRIX *matrix)
 
SCIP_Real SCIPmatrixGetRowLhs (SCIP_MATRIX *matrix, int row)
 
SCIP_Real SCIPmatrixGetRowRhs (SCIP_MATRIX *matrix, int row)
 
SCIP_Bool SCIPmatrixIsRowRhsInfinity (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetNNonzs (SCIP_MATRIX *matrix)
 
SCIP_Real SCIPmatrixGetRowMinActivity (SCIP_MATRIX *matrix, int row)
 
SCIP_Real SCIPmatrixGetRowMaxActivity (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetRowNMinActNegInf (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetRowNMinActPosInf (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetRowNMaxActNegInf (SCIP_MATRIX *matrix, int row)
 
int SCIPmatrixGetRowNMaxActPosInf (SCIP_MATRIX *matrix, int row)
 
SCIP_CONSSCIPmatrixGetCons (SCIP_MATRIX *matrix, int row)
 
SCIP_Bool SCIPmatrixUplockConflict (SCIP_MATRIX *matrix, int col)
 
SCIP_Bool SCIPmatrixDownlockConflict (SCIP_MATRIX *matrix, int col)
 

Function Documentation

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
scipSCIP instance
varsvars array to get active variables for
scalarsscalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c
nvarspointer to number of variables and values in vars and vals array
constantpointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c

Definition at line 46 of file matrix.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, and TRUE.

Referenced by addConstraint().

static SCIP_RETCODE addRow ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_VAR **  vars,
SCIP_Real vals,
int  nvars,
SCIP_Real  lhs,
SCIP_Real  rhs,
int  maxnnonzsmem,
SCIP_Bool rowadded 
)
static

add one row to the constraint matrix

Parameters
scipSCIP data structure
matrixconstraint matrix
varsvariables of this row
valscoefficients of this row
nvarsnumber of variables of this row
lhsleft hand side
rhsright hand side
maxnnonzsmemmaximal number of fillable elements
rowaddedflag indicating if constraint was added to matrix

Definition at line 81 of file matrix.c.

References FALSE, SCIP_Matrix::isrhsinfinite, SCIP_Matrix::lhs, SCIP_Matrix::ndownlocks, SCIP_Matrix::nnonzs, SCIP_Matrix::nrows, NULL, SCIP_Matrix::nuplocks, SCIP_Matrix::rhs, SCIP_Matrix::rowmatbeg, SCIP_Matrix::rowmatcnt, SCIP_Matrix::rowmatind, SCIP_Matrix::rowmatval, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetProbindex(), TRUE, and SCIP_Matrix::vars.

Referenced by addConstraint().

static SCIP_RETCODE addConstraint ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_VAR **  vars,
SCIP_Real vals,
int  nvars,
SCIP_Real  lhs,
SCIP_Real  rhs,
int  maxnnonzsmem,
SCIP_Bool rowadded 
)
static

add one constraint to matrix

Parameters
scipcurrent scip instance
matrixconstraint matrix
varsvariables of this constraint
valsvariable coefficients of this constraint
nvarsnumber of variables
lhsleft hand side
rhsright hand side
maxnnonzsmemmaximal number of fillable elements
rowaddedflag indicating of row was added to matrix

Definition at line 199 of file matrix.c.

References addRow(), FALSE, getActiveVariables(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and SCIPisLE().

Referenced by SCIPmatrixCreate().

static SCIP_RETCODE setColumnMajorFormat ( SCIP scip,
SCIP_MATRIX matrix 
)
static
SCIP_RETCODE SCIPmatrixCreate ( SCIP scip,
SCIP_MATRIX **  matrixptr,
SCIP_Bool initialized,
SCIP_Bool complete 
)

initialize matrix

Parameters
scipcurrent scip instance
matrixptrpointer to constraint matrix object to be initialized
initializedwas the initialization successful?
completeare all constraint represented within the matrix?

Definition at line 430 of file matrix.c.

References addConstraint(), BMSclearMemoryArray, calcActivityBounds(), SCIP_Matrix::colmatbeg, SCIP_Matrix::colmatcnt, SCIP_Matrix::colmatind, SCIP_Matrix::colmatval, SCIP_Matrix::cons, FALSE, SCIP_Matrix::isrhsinfinite, SCIP_Matrix::lb, SCIP_Matrix::lhs, SCIP_Matrix::maxactivity, SCIP_Matrix::maxactivityneginf, SCIP_Matrix::maxactivityposinf, SCIP_Matrix::minactivity, SCIP_Matrix::minactivityneginf, SCIP_Matrix::minactivityposinf, SCIP_Matrix::ncols, SCIP_Matrix::ndownlocks, SCIP_Matrix::nnonzs, SCIP_Matrix::nrows, NULL, SCIP_Matrix::nuplocks, SCIP_Matrix::rhs, SCIP_Matrix::rowmatbeg, SCIP_Matrix::rowmatcnt, SCIP_Matrix::rowmatind, SCIP_Matrix::rowmatval, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBuffer, SCIPallocBufferArray, SCIPallocClearMemoryArray, SCIPconshdlrGetCheckConss(), SCIPconshdlrGetName(), SCIPconshdlrGetNCheckConss(), SCIPconsIsTransformed(), SCIPdebugMessage, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetConshdlrs(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNConshdlrs(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVars(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsSetppc(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPinfinity(), SCIPisStopped(), SCIPreallocBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), setColumnMajorFormat(), TRUE, SCIP_Matrix::ub, and SCIP_Matrix::vars.

Referenced by SCIP_DECL_PRESOLEXEC().

void SCIPmatrixFree ( SCIP scip,
SCIP_MATRIX **  matrix 
)

frees the constraint matrix

Parameters
scipcurrent SCIP instance
matrixconstraint matrix object

Definition at line 782 of file matrix.c.

References NULL, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, and SCIPfreeMemoryArray.

Referenced by SCIP_DECL_PRESOLEXEC().

void SCIPmatrixPrintRow ( SCIP scip,
SCIP_MATRIX matrix,
int  row 
)

print one row of the matrix

Parameters
scipcurrent SCIP instance
matrixconstraint matrix object
rowrow index

Definition at line 845 of file matrix.c.

References SCIP_Matrix::cons, SCIP_Matrix::lhs, SCIP_Matrix::rhs, SCIP_Matrix::rowmatbeg, SCIP_Matrix::rowmatcnt, SCIP_Matrix::rowmatind, SCIP_Matrix::rowmatval, SCIP_Real, SCIPconsGetName(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIP_Matrix::vars.

Referenced by getActivities().

SCIP_RETCODE SCIPmatrixGetParallelRows ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real scale,
int *  pclass 
)

detect parallel rows of matrix. rhs/lhs are ignored.

Parameters
scipSCIP instance
matrixmatrix containing the constraints
scalescale factors of rows
pclassparallel row classes

Definition at line 877 of file matrix.c.

References BMSclearMemoryArray, SCIP_Matrix::colmatbeg, SCIP_Matrix::colmatcnt, SCIP_Matrix::colmatind, SCIP_Matrix::colmatval, SCIP_Matrix::ncols, SCIP_Matrix::nrows, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.

SCIP_RETCODE SCIPmatrixGetParallelCols ( SCIP scip,
SCIP_MATRIX matrix,
SCIP_Real scale,
int *  pclass,
SCIP_Bool varineq 
)

detect parallel rows of matrix. obj coefficients are ignored.

Parameters
scipSCIP instance
matrixmatrix containing the constraints
scalescale factors of cols
pclassparallel column classes
varineqindicating if variable is within an equation

Definition at line 1033 of file matrix.c.

References BMSclearMemoryArray, SCIP_Matrix::isrhsinfinite, SCIP_Matrix::ncols, SCIP_Matrix::nrows, NULL, SCIP_Matrix::rowmatbeg, SCIP_Matrix::rowmatcnt, SCIP_Matrix::rowmatind, SCIP_Matrix::rowmatval, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPsortIntIntReal(), SCIPsortRealInt(), and TRUE.

SCIP_Real* SCIPmatrixGetColValPtr ( SCIP_MATRIX matrix,
int  col 
)

get column based start pointer of values

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1233 of file matrix.c.

References SCIP_Matrix::colmatbeg, SCIP_Matrix::colmatval, and NULL.

Referenced by calcColActivity(), dualBoundStrengthening(), findDominancePairs(), getDownlockRowIdx(), getMinColActWithoutBound(), getMinColActWithoutRow(), getUplockRowIdx(), isVarImpliedFree(), and numericalStable().

int* SCIPmatrixGetColIdxPtr ( SCIP_MATRIX matrix,
int  col 
)
int SCIPmatrixGetColNNonzs ( SCIP_MATRIX matrix,
int  col 
)
int SCIPmatrixGetColNUplocks ( SCIP_MATRIX matrix,
int  col 
)

get number of uplocks of column

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1301 of file matrix.c.

References NULL, and SCIP_Matrix::nuplocks.

Referenced by detectDominatingVlbs(), findUplockAggregations(), getUplockRowIdx(), SCIP_DECL_PRESOLEXEC(), and singletonColumnStuffing().

int SCIPmatrixGetColNDownlocks ( SCIP_MATRIX matrix,
int  col 
)

get number of downlocks of column

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1313 of file matrix.c.

References SCIP_Matrix::ndownlocks, and NULL.

Referenced by detectDominatingVubs(), findDownlockAggregations(), getDownlockRowIdx(), SCIP_DECL_PRESOLEXEC(), and singletonColumnStuffing().

const char* SCIPmatrixGetColName ( SCIP_MATRIX matrix,
int  col 
)

get name of column/variable

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1337 of file matrix.c.

References NULL, SCIPvarGetName(), and SCIP_Matrix::vars.

const char* SCIPmatrixGetRowName ( SCIP_MATRIX matrix,
int  row 
)

get name of row

Parameters
matrixmatrix instance
rowrow index

Definition at line 1385 of file matrix.c.

References SCIP_Matrix::cons, NULL, and SCIPconsGetName().

SCIP_Real SCIPmatrixGetRowRhs ( SCIP_MATRIX matrix,
int  row 
)
int SCIPmatrixGetNNonzs ( SCIP_MATRIX matrix)

get number of non-zeros of matrix

Parameters
matrixmatrix instance

Definition at line 1443 of file matrix.c.

References SCIP_Matrix::nnonzs, and NULL.

SCIP_Real SCIPmatrixGetRowMinActivity ( SCIP_MATRIX matrix,
int  row 
)

get minimal activity of row

Parameters
matrixmatrix instance
rowrow index

Definition at line 1453 of file matrix.c.

References SCIP_Matrix::minactivity, and NULL.

Referenced by findDominancePairs(), getActivityResiduals(), getActivityResidualsLowerBound(), getActivityResidualsUpperBound(), getBinVarIdxInDownlockRow(), and getBinVarIdxInUplockRow().

SCIP_Real SCIPmatrixGetRowMaxActivity ( SCIP_MATRIX matrix,
int  row 
)

get maximal activity of row

Parameters
matrixmatrix instance
rowrow index

Definition at line 1465 of file matrix.c.

References SCIP_Matrix::maxactivity, and NULL.

Referenced by findDominancePairs(), getActivityResiduals(), getActivityResidualsLowerBound(), getActivityResidualsUpperBound(), getBinVarIdxInDownlockRow(), and getBinVarIdxInUplockRow().

int SCIPmatrixGetRowNMinActNegInf ( SCIP_MATRIX matrix,
int  row 
)

get number of negative infinities present within minimal activity

Parameters
matrixmatrix instance
rowrow index

Definition at line 1477 of file matrix.c.

References SCIP_Matrix::minactivityneginf, and NULL.

Referenced by findDominancePairs(), getActivityRelax(), getActivityResiduals(), getActivityResidualsLowerBound(), and getActivityResidualsUpperBound().

int SCIPmatrixGetRowNMinActPosInf ( SCIP_MATRIX matrix,
int  row 
)

get number of positive infinities present within minimal activity

Parameters
matrixmatrix instance
rowrow index

Definition at line 1489 of file matrix.c.

References SCIP_Matrix::minactivityposinf, and NULL.

Referenced by findDominancePairs(), getActivityRelax(), getActivityResiduals(), getActivityResidualsLowerBound(), and getActivityResidualsUpperBound().

int SCIPmatrixGetRowNMaxActNegInf ( SCIP_MATRIX matrix,
int  row 
)

get number of negative infinities present within maximal activity

Parameters
matrixmatrix instance
rowrow index

Definition at line 1501 of file matrix.c.

References SCIP_Matrix::maxactivityneginf, and NULL.

Referenced by findDominancePairs(), getActivityRelax(), getActivityResiduals(), getActivityResidualsLowerBound(), and getActivityResidualsUpperBound().

int SCIPmatrixGetRowNMaxActPosInf ( SCIP_MATRIX matrix,
int  row 
)

get number of positive infinities present within maximal activity

Parameters
matrixmatrix instance
rowrow index

Definition at line 1513 of file matrix.c.

References SCIP_Matrix::maxactivityposinf, and NULL.

Referenced by findDominancePairs(), getActivityRelax(), getActivityResiduals(), getActivityResidualsLowerBound(), and getActivityResidualsUpperBound().

SCIP_CONS* SCIPmatrixGetCons ( SCIP_MATRIX matrix,
int  row 
)

get constraint pointer for constraint representing row

Parameters
matrixmatrix instance
rowrow index

Definition at line 1525 of file matrix.c.

References SCIP_Matrix::cons, and NULL.

Referenced by detectDominatingVlbs(), detectDominatingVubs(), and SCIP_DECL_PRESOLEXEC().

SCIP_Bool SCIPmatrixUplockConflict ( SCIP_MATRIX matrix,
int  col 
)

get if conflicting uplocks of a specific variable present

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1537 of file matrix.c.

References NULL, SCIP_Matrix::nuplocks, SCIPvarGetNLocksUp(), and SCIP_Matrix::vars.

SCIP_Bool SCIPmatrixDownlockConflict ( SCIP_MATRIX matrix,
int  col 
)

get if conflicting downlocks of a specific variable present

Parameters
matrixmatrix instance
colcolumn index

Definition at line 1549 of file matrix.c.

References SCIP_Matrix::ndownlocks, NULL, SCIPvarGetNLocksDown(), and SCIP_Matrix::vars.