Scippy

SCIP

Solving Constraint Integer Programs

cuts.c File Reference

Detailed Description

Methods used to generate and strengthen cuts.

Author
Jakob Witzig

Definition in file cuts.c.

#include "scip/def.h"
#include "scip/retcode.h"
#include "scip/cuts.h"
#include "scip/debug.h"
#include "scip/pub_lp.h"
#include "scip/lp.h"
#include "scip/prob.h"
#include "scip/set.h"
#include "scip/sol.h"
#include "scip/var.h"
#include "scip/scip.h"
#include "scip/struct_scip.h"

Go to the source code of this file.

Macros

#define MAXCMIRSCALE   1e+6
 
#define debugRowPrint(x)
 

Functions

static SCIP_Real getMaxAbsWeightCalcSparsity (SCIP_SET *set, SCIP_LP *lp, SCIP_Real *weights, int *rowinds, int *nrowinds, int *rowlensum)
 
static SCIP_Real getMaxAbsWeight (SCIP_SET *set, SCIP_LP *lp, SCIP_Real *weights, int *rowinds, int *nrowinds, int *rowlensum)
 
static void findBestLb (SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, int *bestlbtype)
 
static void findBestUb (SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, int *bestubtype)
 
static SCIP_Real getMIRRowActivity (SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_SOL *sol, SCIP_Real *mircoef, int *varinds, int nvarinds)
 
static SCIP_Real getMIRMinActivity (SCIP_PROB *prob, SCIP_Real *mircoef, int *varinds, int nvarinds, SCIP_Bool islocal)
 
static void addRowToAggregation (SCIP_SET *set, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *slacksign, SCIP_Bool *varused, int *varinds, int *nvarinds, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool uselhs)
 
static void cutsSumStrongCGRow (SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, SCIP_Real *weights, SCIP_Real scale, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real *strongcgcoef, SCIP_Real *strongcgrhs, int *slacksign, SCIP_Bool *varused, int *varinds, int *nvarinds, int *rowinds, int *nrowinds, SCIP_Bool *emptyrow, SCIP_Bool *localrowsused, SCIP_Bool *rowtoolong, int *cutrank)
 
static void cutsSumMIRRow (SCIP_SET *set, SCIP_PROB *prob, SCIP_LP *lp, SCIP_Real *weights, SCIP_Real knownmaxweight, int *sidetypes, SCIP_Real scale, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Bool compress, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *slacksign, SCIP_Bool *varused, int *varinds, int *nvarinds, int *rowinds, int *nrowinds, SCIP_Bool *emptyrow, SCIP_Bool *localrowsused, SCIP_Bool *rowtoolong, int *cutrank)
 
static void cutsCleanupMIRRow (SCIP_SET *set, SCIP_PROB *prob, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Bool *varused, int *varinds, int *nvarinds, SCIP_Bool cutislocal)
 
static void cutsTransformStrongCGRow (SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *strongcgcoef, SCIP_Real *strongcgrhs, SCIP_Bool *varused, int *varinds, int *nvarinds, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
 
static SCIP_RETCODE cutsTransformMIRRow (SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Bool *varused, int *varinds, int *nvarinds, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
 
static void cutsRoundStrongCGRow (SCIP_SET *set, SCIP_PROB *prob, SCIP_Real *strongcgcoef, SCIP_Real *strongcgrhs, SCIP_Bool *varused, int *varinds, int *nvarinds, int *varsign, int *boundtype, SCIP_Real f0, SCIP_Real k)
 
static void cutsRoundMIRRow (SCIP_SET *set, SCIP_PROB *prob, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Bool *varused, int *varinds, int *nvarinds, int *varsign, int *boundtype, SCIP_Real f0)
 
static void cutsSubstituteStrongCGRow (SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_Real *weights, SCIP_Real scale, SCIP_Real *strongcgcoef, SCIP_Real *strongcgrhs, int *slacksign, SCIP_Bool *varused, int *varinds, int *nvarinds, int *rowinds, int nrowinds, SCIP_Real f0, SCIP_Real k)
 
static void cutsSubstituteMIRRow (SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_Real *weights, SCIP_Real scale, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *slacksign, SCIP_Bool *varused, int *varinds, int *nvarinds, int *rowinds, int nrowinds, SCIP_Real f0)
 
static SCIP_RETCODE cutsLpCalcStrongCG (SCIP_LP *lp, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *strongcgcoef, SCIP_Real *strongcgrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
 
static SCIP_RETCODE cutsLpCalcMIR (SCIP_LP *lp, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
 
static SCIP_RETCODE cutsApplyMIR (SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *varinds, int *nvarinds, SCIP_Real *minact, SCIP_Bool *varused, SCIP_Bool *success, SCIP_Bool *islocal)
 
SCIP_RETCODE SCIPcutsCalcStrongCG (SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, int *inds, int ninds, SCIP_Real scale, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
 
SCIP_RETCODE SCIPcutsCalcLpMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
 
SCIP_RETCODE SCIPcutsApplyMIR (SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, int *varinds, int *nvarinds, SCIP_Real *minact, SCIP_Bool *varused, SCIP_Bool *success, SCIP_Bool *islocal)
 
void SCIPcutsCleanupRow (SCIP *scip, SCIP_Real *coefs, SCIP_Real *rhs, SCIP_Bool *varused, int *varinds, int *nvarinds, SCIP_Bool islocal)
 

Macro Definition Documentation

◆ MAXCMIRSCALE

#define MAXCMIRSCALE   1e+6

maximal scaling (scale/(1-f0)) allowed in c-MIR calculations

Definition at line 37 of file cuts.c.

Referenced by cutsApplyMIR(), and cutsLpCalcMIR().

◆ debugRowPrint

#define debugRowPrint (   x)

Definition at line 87 of file cuts.c.

Referenced by cutsSumMIRRow(), and cutsSumStrongCGRow().

Function Documentation

◆ getMaxAbsWeightCalcSparsity()

static SCIP_Real getMaxAbsWeightCalcSparsity ( SCIP_SET set,
SCIP_LP lp,
SCIP_Real weights,
int *  rowinds,
int *  nrowinds,
int *  rowlensum 
)
static

returns the maximum absolute row weight in the given weight vector, and calculates the sparsity pattern of the weights

Parameters
setglobal SCIP settings
lpLP data
weightsrow weights in row summation
rowindsarray to store sparsity pattern of used rows; size lp->nrows
nrowindspointer to store number of used rows
rowlensumpointer to store total number of non-zeros in used rows

Definition at line 138 of file cuts.c.

References MAX, SCIP_Lp::nrows, NULL, REALABS, SCIP_Lp::rows, SCIP_Real, SCIProwGetNNonz(), and SCIPsetIsZero().

Referenced by cutsSumMIRRow(), and cutsSumStrongCGRow().

◆ getMaxAbsWeight()

static SCIP_Real getMaxAbsWeight ( SCIP_SET set,
SCIP_LP lp,
SCIP_Real weights,
int *  rowinds,
int *  nrowinds,
int *  rowlensum 
)
static

returns the maximum absolute row weight in the given weight vector using given sparsity pattern

Parameters
setglobal SCIP settings
lpLP data
weightsrow weights in row summation
rowindsarray of sparsity pattern of used rows; size lp->nrows
nrowindspointer to store number of used rows
rowlensumpointer to store total number of non-zeros in used rows

Definition at line 183 of file cuts.c.

References MAX, NULL, REALABS, SCIP_Lp::rows, SCIP_Real, SCIProwGetNNonz(), and SCIPsetIsZero().

Referenced by cutsSumMIRRow(), and cutsSumStrongCGRow().

◆ findBestLb()

static void findBestLb ( SCIP_SET set,
SCIP_STAT stat,
SCIP_VAR var,
SCIP_SOL sol,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Real bestlb,
int *  bestlbtype 
)
static

finds the best lower bound of the variable to use for MIR transformation

Parameters
setglobal SCIP settings
statproblem statistics
varproblem variable
solthe solution that should be separated, or NULL for LP solution
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
bestlbpointer to store best bound value
bestlbtypepointer to store best bound type

Definition at line 229 of file cuts.c.

References NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPsetIsGE(), SCIPsetIsGT(), SCIPvarGetClosestVlb(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetVlbVars().

Referenced by cutsTransformMIRRow().

◆ findBestUb()

static void findBestUb ( SCIP_SET set,
SCIP_STAT stat,
SCIP_VAR var,
SCIP_SOL sol,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Real bestub,
int *  bestubtype 
)
static

finds the best upper bound of the variable to use for MIR transformation

Parameters
setglobal SCIP settings
statproblem statistics
varproblem variable
solthe solution that should be separated, or NULL for LP solution
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
bestubpointer to store best bound value
bestubtypepointer to store best bound type

Definition at line 286 of file cuts.c.

References NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPsetIsLE(), SCIPsetIsLT(), SCIPvarGetClosestVub(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIPvarGetVubVars().

Referenced by cutsTransformMIRRow().

◆ getMIRRowActivity()

static SCIP_Real getMIRRowActivity ( SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_SOL sol,
SCIP_Real mircoef,
int *  varinds,
int  nvarinds 
)
static

calculates the activity of the given MIR cut

Parameters
setglobal SCIP settings
statproblem statistics
probproblem data
solthe solution that should be separated, or NULL for LP solution
mircoefarray to store MIR coefficients: must be of size nvars
varindssparsity pattern of non-zero MIR coefficients
nvarindsnumber of non-zero MIR coefficients

Definition at line 343 of file cuts.c.

References NULL, SCIP_Real, SCIPsolGetVal(), SCIPvarGetLPSol(), and SCIP_Prob::vars.

Referenced by cutsLpCalcMIR(), and cutsLpCalcStrongCG().

◆ getMIRMinActivity()

static SCIP_Real getMIRMinActivity ( SCIP_PROB prob,
SCIP_Real mircoef,
int *  varinds,
int  nvarinds,
SCIP_Bool  islocal 
)
static

calculates the minimal activity of the given MIR

Parameters
probproblem data
mircoefarray to store MIR coefficients: must be of size nvars
varindssparsity pattern of non-zero MIR coefficients
nvarindsnumber of non-zero MIR coefficients
islocalwhether local bounds should be used

Definition at line 373 of file cuts.c.

References SCIP_Real, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIP_Prob::vars.

Referenced by cutsApplyMIR().

◆ addRowToAggregation()

static void addRowToAggregation ( SCIP_SET set,
SCIP_Real mircoef,
SCIP_Real mirrhs,
int *  slacksign,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
SCIP_ROW row,
SCIP_Real  weight,
SCIP_Bool  uselhs 
)
static

adds a single row to an aggregation

Parameters
setglobal SCIP settings
mircoefarray of aggregation coefficients: must be of size prob->nvars
mirrhspointer to store the right hand side of the MIR row
slacksignstores the sign of the row's slack variable in summation
varusedarray to flag variables that appear in the MIR constraint; size prob->nvars
varindsarray to store sparsity pattern of non-zero MIR coefficients; size prob->nvars
nvarindspointer to store number of non-zero MIR coefficients
rowrow to add to the aggregation
weightweight of row in aggregation
uselhsTRUE if lhs should be used, FALSE if rhs should be used

Definition at line 407 of file cuts.c.

References SCIP_Row::cols, SCIP_Row::constant, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, SCIP_Row::lppos, NULL, SCIP_Row::rhs, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPsetFeasCeil(), SCIPsetFeasFloor(), SCIPvarGetCol(), SCIPvarGetProbindex(), SCIPvarGetStatus(), TRUE, SCIP_Row::vals, SCIP_Col::var, and SCIP_Col::var_probindex.

Referenced by cutsSumMIRRow(), and cutsSumStrongCGRow().

◆ cutsSumStrongCGRow()

static void cutsSumStrongCGRow ( SCIP_SET set,
SCIP_PROB prob,
SCIP_LP lp,
SCIP_Real weights,
SCIP_Real  scale,
SCIP_Bool  allowlocal,
int  maxmksetcoefs,
SCIP_Real  maxweightrange,
SCIP_Real strongcgcoef,
SCIP_Real strongcgrhs,
int *  slacksign,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  rowinds,
int *  nrowinds,
SCIP_Bool emptyrow,
SCIP_Bool localrowsused,
SCIP_Bool rowtoolong,
int *  cutrank 
)
static

builds a weighted sum of rows, and decides whether to use the left or right hand side of the rows in summation

Parameters
setglobal SCIP settings
probproblem data
lpLP data
weightsrow weights in row summation
scaleadditional scaling factor multiplied to all rows
allowlocalshould local rows be included, resulting in a locally valid summation?
maxmksetcoefsmaximal number of nonzeros allowed in aggregated base inequality
maxweightrangemaximal valid range max(|weights|)/min(|weights|) of row weights
strongcgcoefarray to store strong CG coefficients: must be of size prob->nvars
strongcgrhspointer to store the right hand side of the strong CG row
slacksignstores the sign of the row's slack variable in summation
varusedarray to flag variables that appear in the MIR constraint; size prob->nvars
varindsarray to store sparsity pattern of non-zero MIR coefficients; size prob->nvars
nvarindspointer to store number of non-zero MIR coefficients
rowindsarray to store sparsity pattern of used rows; size lp->nrows
nrowindspointer to store number of used rows
emptyrowpointer to store whether the returned row is empty
localrowsusedpointer to store whether local rows were used in summation
rowtoolongpointer to store whether the aggregated row is too long and thus invalid
cutrankpointer to store the rank of the returned aggregation; or NULL

Definition at line 478 of file cuts.c.

References addRowToAggregation(), BMSclearMemoryArray, SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, debugRowPrint, FALSE, getMaxAbsWeight(), getMaxAbsWeightCalcSparsity(), SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, SCIP_Row::local, MAX, SCIP_Row::modifiable, NULL, SCIP_Prob::nvars, SCIP_Row::rank, SCIP_Row::rhs, SCIP_Lp::rows, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIProwGetName(), SCIPsetIsInfinity(), SCIPsetIsSumZero(), SCIPsetIsZero(), TRUE, and SCIP_Row::vals.

Referenced by cutsLpCalcStrongCG().

◆ cutsSumMIRRow()

static void cutsSumMIRRow ( SCIP_SET set,
SCIP_PROB prob,
SCIP_LP lp,
SCIP_Real weights,
SCIP_Real  knownmaxweight,
int *  sidetypes,
SCIP_Real  scale,
SCIP_Bool  allowlocal,
int  maxmksetcoefs,
SCIP_Real  maxweightrange,
SCIP_Bool  compress,
SCIP_Real mircoef,
SCIP_Real mirrhs,
int *  slacksign,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  rowinds,
int *  nrowinds,
SCIP_Bool emptyrow,
SCIP_Bool localrowsused,
SCIP_Bool rowtoolong,
int *  cutrank 
)
static

builds a weighted sum of rows, and decides whether to use the left or right hand side of the rows in summation

Parameters
setglobal SCIP settings
probproblem data
lpLP data
weightsrow weights in row summation
knownmaxweightlargest magnitude of weights. Set to 0 if compress == TRUE
sidetypesspecify row side type (-1 = lhs, 0 = unkown, 1 = rhs) or NULL for automatic choices
scaleadditional scaling factor multiplied to all rows
allowlocalshould local rows be included, resulting in a locally valid summation?
maxmksetcoefsmaximal number of nonzeros allowed in aggregated base inequality
maxweightrangemaximal valid range max(|weights|)/min(|weights|) of row weights
compressif rowinds is unknown and weights should be compressed
mircoefarray to store MIR coefficients: must be of size prob->nvars
mirrhspointer to store the right hand side of the MIR row
slacksignstores the sign of the row's slack variable in summation
varusedarray to flag variables that appear in the MIR constraint; size prob->nvars
varindsarray to store sparsity pattern of non-zero MIR coefficients; size prob->nvars
nvarindspointer to store number of non-zero MIR coefficients
rowindsarray to store sparsity pattern of used rows; size lp->nrows
nrowindspointer to store number of used rows
emptyrowpointer to store whether the returned row is empty
localrowsusedpointer to store whether local rows were used in summation
rowtoolongpointer to store whether the aggregated row is too long and thus invalid
cutrankpointer to store the rank of the returned aggregation; or NULL

Definition at line 649 of file cuts.c.

References addRowToAggregation(), BMSclearMemoryArray, SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, debugRowPrint, FALSE, getMaxAbsWeight(), getMaxAbsWeightCalcSparsity(), SCIP_Row::len, SCIP_Row::lhs, SCIP_Row::local, MAX, SCIP_Row::modifiable, NULL, SCIP_Prob::nvars, SCIP_Row::rank, REALABS, SCIP_Row::rhs, SCIP_Lp::rows, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIProwGetName(), SCIPsetIsInfinity(), SCIPsetIsSumZero(), SCIPsetIsZero(), TRUE, and SCIP_Row::vals.

Referenced by cutsLpCalcMIR().

◆ cutsCleanupMIRRow()

static void cutsCleanupMIRRow ( SCIP_SET set,
SCIP_PROB prob,
SCIP_Real mircoef,
SCIP_Real mirrhs,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
SCIP_Bool  cutislocal 
)
static

removes all nearly-zero coefficients from MIR row and relaxes the right hand side correspondingly in order to prevent numerical rounding errors

Parameters
setglobal SCIP settings
probproblem data
mircoefarray to store MIR coefficients: must be of size nvars
mirrhspointer to store the right hand side of the MIR row
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
cutislocalis the cut only valid locally?

Definition at line 840 of file cuts.c.

References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPsetInfinity(), SCIPsetIsInfinity(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetIsSumZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIP_Prob::vars.

Referenced by cutsApplyMIR(), cutsLpCalcMIR(), cutsLpCalcStrongCG(), and SCIPcutsCleanupRow().

◆ cutsTransformStrongCGRow()

static void cutsTransformStrongCGRow ( SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_Real  boundswitch,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Real strongcgcoef,
SCIP_Real strongcgrhs,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  varsign,
int *  boundtype,
SCIP_Bool freevariable,
SCIP_Bool localbdsused 
)
static

Transform equation \( a*x == b \), \( lb <= x <= ub \) into standard form \( a^\prime*x^\prime == b\), \( 0 <= x^\prime <= ub^\prime \).

Transform variables (lb or ub):

\[ \begin{array}{llll} x^\prime_j := x_j - lb_j,& x_j == x^\prime_j + lb_j,& a^\prime_j == a_j,& \mbox{if lb is used in transformation} \\ x^\prime_j := ub_j - x_j,& x_j == ub_j - x^\prime_j,& a^\prime_j == -a_j,& \mbox{if ub is used in transformation} \end{array} \]

and move the constant terms \( a_j * lb_j \) or \( a_j * ub_j \) to the rhs.

Transform variables (vlb or vub):

\[ \begin{array}{llll} x^\prime_j := x_j - (bl_j * zl_j + dl_j),& x_j == x^\prime_j + (bl_j * zl_j + dl_j),& a^\prime_j == a_j,& \mbox{if vlb is used in transf.} \\ x^\prime_j := (bu_j * zu_j + du_j) - x_j,& x_j == (bu_j * zu_j + du_j) - x^\prime_j,& a^\prime_j == -a_j,& \mbox{if vub is used in transf.} \end{array} \]

move the constant terms \( a_j * dl_j \) or \( a_j * du_j \) to the rhs, and update the coefficient of the VLB variable:

\[ \begin{array}{ll} a_{zl_j} := a_{zl_j} + a_j * bl_j,& \mbox{or} \\ a_{zu_j} := a_{zu_j} + a_j * bu_j& \end{array} \]

Parameters
setglobal SCIP settings
statproblem statistics
probproblem data
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
strongcgcoefarray to store strong CG coefficients: must be of size nvars
strongcgrhspointer to store the right hand side of the strong CG row
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
freevariablestores whether a free variable was found in strong CG row -> invalid summation
localbdsusedpointer to store whether local bounds were used in transformation

Definition at line 933 of file cuts.c.

References FALSE, NULL, SCIP_Prob::nvars, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMessage, SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsetIsZero(), SCIPsortDownInt(), SCIPvarGetClosestVlb(), SCIPvarGetClosestVub(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), TRUE, and SCIP_Prob::vars.

Referenced by cutsLpCalcStrongCG().

◆ cutsTransformMIRRow()

static SCIP_RETCODE cutsTransformMIRRow ( SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_SOL sol,
SCIP_Real  boundswitch,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Bool  fixintegralrhs,
SCIP_Bool  ignoresol,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
SCIP_Real  minfrac,
SCIP_Real  maxfrac,
SCIP_Real mircoef,
SCIP_Real mirrhs,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  varsign,
int *  boundtype,
SCIP_Bool freevariable,
SCIP_Bool localbdsused 
)
static

Transform equation \( a \cdot x = b; lb \leq x \leq ub \) into standard form \( a^\prime \cdot x^\prime = b,\; 0 \leq x^\prime \leq ub' \).

Transform variables (lb or ub):

\[ \begin{array}{llll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation}\\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation} \end{array} \]

and move the constant terms \( a_j\, lb_j \) or \( a_j\, ub_j \) to the rhs.

Transform variables (vlb or vub):

\[ \begin{array}{llll} x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.} \end{array} \]

move the constant terms \( a_j\, dl_j \) or \( a_j\, du_j \) to the rhs, and update the coefficient of the VLB variable:

\[ \begin{array}{ll} a_{zl_j} := a_{zl_j} + a_j\, bl_j,& \mbox{or} \\ a_{zu_j} := a_{zu_j} + a_j\, bu_j & \end{array} \]

Parameters
setglobal SCIP settings
statproblem statistics
probproblem data
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
fixintegralrhsshould complementation tried to be adjusted such that rhs gets fractional?
ignoresolshould the LP solution be ignored? (eg, apply MIR to dualray)
boundsfortransbounds that should be used for transformed variables: vlb_idx/vub_idx, -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound; NULL for using closest bound for all variables
boundtypesfortranstype of bounds that should be used for transformed variables; NULL for using closest bound for all variables
minfracminimal fractionality of rhs to produce MIR cut for
maxfracmaximal fractionality of rhs to produce MIR cut for
mircoefarray to store MIR coefficients: must be of size nvars
mirrhspointer to store the right hand side of the MIR row
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
freevariablestores whether a free variable was found in MIR row -> invalid summation
localbdsusedpointer to store whether local bounds were used in transformation

Definition at line 1233 of file cuts.c.

References FALSE, findBestLb(), findBestUb(), NULL, SCIP_Prob::nvars, REALABS, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPcolGetBasisStatus(), SCIPdebugMessage, SCIPerrorMessage, SCIPsetAllocBufferArray, SCIPsetFrac(), SCIPsetFreeBufferArray, SCIPsetIsGE(), SCIPsetIsGT(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsLT(), SCIPsetIsNegative(), SCIPsetIsZero(), SCIPsetSumFrac(), SCIPsolGetVal(), SCIPsortDownInt(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), TRUE, and SCIP_Prob::vars.

Referenced by cutsApplyMIR(), and cutsLpCalcMIR().

◆ cutsRoundStrongCGRow()

static void cutsRoundStrongCGRow ( SCIP_SET set,
SCIP_PROB prob,
SCIP_Real strongcgcoef,
SCIP_Real strongcgrhs,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  varsign,
int *  boundtype,
SCIP_Real  f0,
SCIP_Real  k 
)
static

Calculate fractionalities \( f_0 := b - down(b) \), \( f_j := a^\prime_j - down(a^\prime_j) \) and integer \( k >= 1 \) with \( 1/(k + 1) <= f_0 < 1/k \) and \( (=> k = up(1/f_0) + 1) \) integer \( 1 <= p_j <= k \) with \( f_0 + ((p_j - 1) * (1 - f_0)/k) < f_j <= f_0 + (p_j * (1 - f_0)/k)\) \( (=> p_j = up( k*(f_j - f_0)/(1 - f_0) )) \) and derive strong CG cut \( \tilde{a}*x^\prime <= down(b) \)

\[ \begin{array}{rll} integers : & \tilde{a}_j = down(a^\prime_j) &, if \qquad f_j <= f_0 \\ & \tilde{a}_j = down(a^\prime_j) + p_j/(k + 1) &, if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0 &, if \qquad a^\prime_j >= 0 \\ & \mbox{no strong CG cut found} &, if \qquad a^\prime_j < 0 \end{array} \]

Transform inequality back to \( \hat{a}*x <= rhs \):

(lb or ub):

\[ \begin{array}{lllll} x^\prime_j := x_j - lb_j,& x_j == x^\prime_j + lb_j,& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation} \\ x^\prime_j := ub_j - x_j,& x_j == ub_j - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation} \end{array} \]

\[ and move the constant terms \begin{array}{rl} -\tilde{a}_j * lb_j == -\hat{a}_j * lb_j, & \mbox{or} \\ \tilde{a}_j * ub_j == -\hat{a}_j * ub_j & \end{array} \]

to the rhs.

(vlb or vub):

\[ \begin{array}{lllll} x^\prime_j := x_j - (bl_j * zl_j + dl_j),& x_j == x^\prime_j + (bl_j * zl_j + dl_j),& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\ x^\prime_j := (bu_j * zu_j + du_j) - x_j,& x_j == (bu_j * zu_j + du_j) - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)} \end{array} \]

move the constant terms

\[ \begin{array}{rl} -\tilde{a}_j * dl_j == -\hat{a}_j * dl_j,& \mbox{or} \\ \tilde{a}_j * du_j == -\hat{a}_j * du_j & \end{array} \]

to the rhs, and update the VB variable coefficients:

\[ \begin{array}{ll} \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\ \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j * bu_j == \hat{a}_{zu_j} - \hat{a}_j * bu_j & \end{array} \]

Parameters
setglobal SCIP settings
probproblem data
strongcgcoefarray to store strong CG coefficients: must be of size nvars
strongcgrhspointer to store the right hand side of the strong CG row
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)
f0fractional value of rhs
kfactor to strengthen strongcg cut

Definition at line 1838 of file cuts.c.

References FALSE, SCIP_Prob::ncontvars, NULL, SCIP_Prob::nvars, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPsetCeil(), SCIPsetFloor(), SCIPsetIsInfinity(), SCIPsetIsSumLE(), SCIPsetIsZero(), SCIPsortDownInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and SCIP_Prob::vars.

Referenced by cutsLpCalcStrongCG().

◆ cutsRoundMIRRow()

static void cutsRoundMIRRow ( SCIP_SET set,
SCIP_PROB prob,
SCIP_Real mircoef,
SCIP_Real mirrhs,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  varsign,
int *  boundtype,
SCIP_Real  f0 
)
static

Calculate fractionalities \( f_0 := b - down(b), f_j := a^\prime_j - down(a^\prime_j) \), and derive MIR cut \( \tilde{a} \cdot x' \leq down(b) \)

\[ \begin{array}{rll} integers :& \tilde{a}_j = down(a^\prime_j), & if \qquad f_j \leq f_0 \\ & \tilde{a}_j = down(a^\prime_j) + (f_j - f_0)/(1 - f_0),& if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0, & if \qquad a^\prime_j \geq 0 \\ & \tilde{a}_j = a^\prime_j/(1 - f_0), & if \qquad a^\prime_j < 0 \end{array} \]

Transform inequality back to \( \hat{a} \cdot x \leq rhs \):

(lb or ub):

\[ \begin{array}{lllll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation} \\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation} \end{array} \]

and move the constant terms

\[ \begin{array}{cl} -\tilde{a}_j \cdot lb_j = -\hat{a}_j \cdot lb_j,& \mbox{or} \\ \tilde{a}_j \cdot ub_j = -\hat{a}_j \cdot ub_j & \end{array} \]

to the rhs.

(vlb or vub):

\[ \begin{array}{lllll} x^\prime_j := x_j - (bl_j \cdot zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)} \end{array} \]

move the constant terms

\[ \begin{array}{cl} -\tilde{a}_j\, dl_j = -\hat{a}_j\, dl_j,& \mbox{or} \\ \tilde{a}_j\, du_j = -\hat{a}_j\, du_j & \end{array} \]

to the rhs, and update the VB variable coefficients:

\[ \begin{array}{ll} \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\ \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j\, bu_j = \hat{a}_{zu_j} - \hat{a}_j\, bu_j & \end{array} \]

Parameters
setglobal SCIP settings
probproblem data
mircoefarray to store MIR coefficients: must be of size nvars
mirrhspointer to store the right hand side of the MIR row
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)
f0fractional value of rhs

Definition at line 2050 of file cuts.c.

References FALSE, NULL, SCIP_Real, SCIPsetFloor(), SCIPsetIsInfinity(), SCIPsetIsSumLE(), SCIPsetIsZero(), SCIPsortDownInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsIntegral(), TRUE, and SCIP_Prob::vars.

Referenced by cutsApplyMIR(), and cutsLpCalcMIR().

◆ cutsSubstituteStrongCGRow()

static void cutsSubstituteStrongCGRow ( SCIP_SET set,
SCIP_STAT stat,
SCIP_LP lp,
SCIP_Real weights,
SCIP_Real  scale,
SCIP_Real strongcgcoef,
SCIP_Real strongcgrhs,
int *  slacksign,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  rowinds,
int  nrowinds,
SCIP_Real  f0,
SCIP_Real  k 
)
static

substitute aggregated slack variables:

The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack variable only appears in its own row: \( a^\prime_r = scale * weight[r] * slacksign[r] \).

Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:

\[ \begin{array}{rll} integers: & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) &, if \qquad f_r <= f0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + p_r/(k + 1) &, if \qquad f_r > f0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0 &, if \qquad a^\prime_r >= 0 \\ & \mbox{no strong CG cut found} &, if \qquad a^\prime_r < 0 \end{array} \]

Substitute \( \hat{a}_r * s_r \) by adding \( \hat{a}_r \) times the slack's definition to the cut.

Parameters
setglobal SCIP settings
statproblem statistics
lpLP data
weightsrow weights in row summation
scaleadditional scaling factor multiplied to all rows
strongcgcoefarray to store strong CG coefficients: must be of size nvars
strongcgrhspointer to store the right hand side of the strong CG row
slacksignstores the sign of the row's slack variable in summation
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
rowindssparsity pattern of used rows
nrowindsnumber of used rows
f0fractional value of rhs
kfactor to strengthen strongcg cut

Definition at line 2237 of file cuts.c.

References SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, SCIP_Row::rhs, SCIP_Lp::rows, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPsetCeil(), SCIPsetFeasCeil(), SCIPsetFeasFloor(), SCIPsetFloor(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPvarGetCol(), SCIPvarGetProbindex(), SCIPvarGetStatus(), TRUE, SCIP_Row::vals, SCIP_Col::var, and SCIP_Col::var_probindex.

Referenced by cutsLpCalcStrongCG().

◆ cutsSubstituteMIRRow()

static void cutsSubstituteMIRRow ( SCIP_SET set,
SCIP_STAT stat,
SCIP_LP lp,
SCIP_Real weights,
SCIP_Real  scale,
SCIP_Real mircoef,
SCIP_Real mirrhs,
int *  slacksign,
SCIP_Bool varused,
int *  varinds,
int *  nvarinds,
int *  rowinds,
int  nrowinds,
SCIP_Real  f0 
)
static

substitute aggregated slack variables:

The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack variable only appears in its own row: \( a^\prime_r = scale * weight[r] * slacksign[r]. \)

Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:

\[ \begin{array}{rll} integers : & \hat{a}_r = \tilde{a}_r = down(a^\prime_r), & \mbox{if}\qquad f_r <= f0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0, & \mbox{if}\qquad a^\prime_r >= 0 \\ & \hat{a}_r = \tilde{a}_r = a^\prime_r/(1 - f0), & \mbox{if}\qquad a^\prime_r < 0 \end{array} \]

Substitute \( \hat{a}_r \cdot s_r \) by adding \( \hat{a}_r \) times the slack's definition to the cut.

Parameters
setglobal SCIP settings
statproblem statistics
lpLP data
weightsrow weights in row summation
scaleadditional scaling factor multiplied to all rows
mircoefarray to store MIR coefficients: must be of size nvars
mirrhspointer to store the right hand side of the MIR row
slacksignstores the sign of the row's slack variable in summation
varusedarray to flag variables that appear in the MIR constraint
varindssparsity pattern of non-zero MIR coefficients
nvarindspointer to number of non-zero MIR coefficients
rowindssparsity pattern of used rows
nrowindsnumber of used rows
f0fractional value of rhs

Definition at line 2407 of file cuts.c.

References SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, SCIP_Row::rhs, SCIP_Lp::rows, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPsetFeasCeil(), SCIPsetFeasFloor(), SCIPsetFloor(), SCIPsetIsFeasIntegral(), SCIPsetIsInfinity(), SCIPsetIsLE(), SCIPsetIsZero(), SCIPvarGetCol(), SCIPvarGetProbindex(), SCIPvarGetStatus(), TRUE, SCIP_Row::vals, SCIP_Col::var, and SCIP_Col::var_probindex.

Referenced by cutsLpCalcMIR().

◆ cutsLpCalcStrongCG()

static SCIP_RETCODE cutsLpCalcStrongCG ( SCIP_LP lp,
SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_Real  boundswitch,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
int  maxmksetcoefs,
SCIP_Real  maxweightrange,
SCIP_Real  minfrac,
SCIP_Real  maxfrac,
SCIP_Real weights,
int *  rowinds,
int  nrowinds,
SCIP_Real  scale,
SCIP_Real strongcgcoef,
SCIP_Real strongcgrhs,
SCIP_Real cutactivity,
SCIP_Bool success,
SCIP_Bool cutislocal,
int *  cutrank 
)
static
Parameters
lpLP data
setglobal SCIP settings
statproblem statistics
probproblem data
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
maxmksetcoefsmaximal number of nonzeros allowed in aggregated base inequality
maxweightrangemaximal valid range max(|weights|)/min(|weights|) of row weights
minfracminimal fractionality of rhs to produce strong CG cut for
maxfracmaximal fractionality of rhs to produce strong CG cut for
weightsrow weights in row summation
rowindsarray to store indices of non-zero entries of the weights array, or NULL
nrowindsnumber of non-zero entries in weights array, -1 if rowinds is NULL
scaleadditional scaling factor multiplied to all rows
strongcgcoefarray to store strong CG coefficients: must be of size nvars
strongcgrhspointer to store the right hand side of the strong CG row
cutactivitypointer to store the activity of the resulting cut
successpointer to store whether the returned coefficients are a valid strong CG cut
cutislocalpointer to store whether the returned cut is only valid locally
cutrankpointer to store the rank of the returned cut; or NULL

Definition at line 2564 of file cuts.c.

References cutsCleanupMIRRow(), cutsRoundStrongCGRow(), cutsSubstituteStrongCGRow(), cutsSumStrongCGRow(), cutsTransformStrongCGRow(), FALSE, getMIRRowActivity(), SCIP_Lp::nrows, NULL, SCIP_Prob::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPsetAllocBufferArray, SCIPsetCeil(), SCIPsetFreeBufferArray, SCIPsetIsZero(), SCIPsetSumFloor(), SCIP_Lp::solved, and TRUE.

Referenced by SCIPcutsCalcStrongCG().

◆ cutsLpCalcMIR()

static SCIP_RETCODE cutsLpCalcMIR ( SCIP_LP lp,
SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_SOL sol,
SCIP_Real  boundswitch,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Bool  fixintegralrhs,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
int  maxmksetcoefs,
SCIP_Real  maxweightrange,
SCIP_Real  minfrac,
SCIP_Real  maxfrac,
SCIP_Real weights,
SCIP_Real  maxweight,
int *  weightinds,
int  nweightinds,
int  rowlensum,
int *  sidetypes,
SCIP_Real  scale,
SCIP_Real mksetcoefs,
SCIP_Bool mksetcoefsvalid,
SCIP_Real mircoef,
SCIP_Real mirrhs,
SCIP_Real cutactivity,
SCIP_Bool success,
SCIP_Bool cutislocal,
int *  cutrank 
)
static
Parameters
lpLP data
setglobal SCIP settings
statproblem statistics
probproblem data
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
fixintegralrhsshould complementation tried to be adjusted such that rhs gets fractional?
boundsfortransbounds that should be used for transformed variables: vlb_idx/vub_idx, -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound; NULL for using closest bound for all variables
boundtypesfortranstype of bounds that should be used for transformed variables; NULL for using closest bound for all variables
maxmksetcoefsmaximal number of nonzeros allowed in aggregated base inequality
maxweightrangemaximal valid range max(|weights|)/min(|weights|) of row weights
minfracminimal fractionality of rhs to produce MIR cut for
maxfracmaximal fractionality of rhs to produce MIR cut for
weightsrow weights in row summation
maxweightlargest magnitude of weights; set to -1 if sparsity information is unknown
weightindssparsity pattern of weights; size nrowinds; NULL if sparsity info is unknown
nweightindsnumber of nonzeros in weights; -1 if rowinds is NULL
rowlensumtotal number of non-zeros in used rows (row associated with nonzero weight coefficient); -1 if unknown
sidetypesspecify row side type (-1 = lhs, 0 = unkown, 1 = rhs) or NULL for automatic choices
scaleadditional scaling factor multiplied to all rows
mksetcoefsarray to store mixed knapsack set coefficients: size nvars; or NULL
mksetcoefsvalidpointer to store whether mixed knapsack set coefficients are valid; or NULL
mircoefarray to store MIR coefficients: must be of size nvars
mirrhspointer to store the right hand side of the MIR row
cutactivitypointer to store the activity of the resulting cut
successpointer to store whether the returned coefficients are a valid MIR cut
cutislocalpointer to store whether the returned cut is only valid locally
cutrankpointer to store the rank of the returned cut; or NULL

Definition at line 2770 of file cuts.c.

References BMScopyMemoryArray, cutsCleanupMIRRow(), cutsRoundMIRRow(), cutsSubstituteMIRRow(), cutsSumMIRRow(), cutsTransformMIRRow(), FALSE, getMIRRowActivity(), MAXCMIRSCALE, SCIP_Lp::nrows, NULL, SCIP_Prob::nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPsetAllocBufferArray, SCIPsetDuplicateBufferArray, SCIPsetFreeBufferArray, SCIPsetIsZero(), SCIPsetSumFloor(), SCIP_Lp::solved, and TRUE.

Referenced by SCIPcutsCalcLpMIR().

◆ cutsApplyMIR()

static SCIP_RETCODE cutsApplyMIR ( SCIP_SET set,
SCIP_STAT stat,
SCIP_PROB prob,
SCIP_Real  boundswitch,
SCIP_Bool  usevbds,
SCIP_Bool  allowlocal,
SCIP_Bool  fixintegralrhs,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
SCIP_Real  minfrac,
SCIP_Real  maxfrac,
SCIP_Real  scale,
SCIP_Real mksetcoefs,
SCIP_Bool mksetcoefsvalid,
SCIP_Real mircoef,
SCIP_Real mirrhs,
int *  varinds,
int *  nvarinds,
SCIP_Real minact,
SCIP_Bool varused,
SCIP_Bool success,
SCIP_Bool islocal 
)
static

applies the MIR function on a constraint; the constraint is given by pairs of variables and coefficients and a rhs

Parameters
setglobal SCIP settings
statdynamic SCIP statistics
probtransformed problem
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
fixintegralrhsshould complementation tried to be adjusted such that rhs gets fractional?
boundsfortransbounds that should be used for transformed variables: 0 vlb_idx/vub_idx, -1 for global lb/ub or -2 for local lb/ub
boundtypesfortranstype of bounds that should be used for transformed variables; NULL for using closest bound for all variables
minfracminimal fractionality of rhs to produce MIR cut for
maxfracmaximal fractionality of rhs to produce MIR cut for
scaleadditional scaling factor multiplied to all rows
mksetcoefsarray to store mixed knapsack set coefficients: size nvars; or NULL
mksetcoefsvalidpointer to store whether mixed knapsack set coefficients are valid; or NULL
mircoefarray to store MIR coefficients: must be of size SCIPgetNVars()
mirrhspointer to store the right hand side of the MIR row
varindsarray of variable indeces with a mircoef != 0
nvarindsnumber of variables indeces in varinds array
minactpointer to store the minimal activity
varusedarray to store whether a variable has a mircoef != 0
successpointer to store whether the returned coefficients are a valid MIR cut
islocalpointer to store whether the returned constraint is only valid locally

Definition at line 3007 of file cuts.c.

References cutsCleanupMIRRow(), cutsRoundMIRRow(), cutsTransformMIRRow(), FALSE, getMIRMinActivity(), MAXCMIRSCALE, NULL, SCIP_Prob::nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPsetAllocBufferArray, SCIPsetFreeBufferArray, SCIPsetIsEQ(), SCIPsetIsPositive(), SCIPsetSumFloor(), and TRUE.

Referenced by SCIPcutsApplyMIR().