Scippy

SCIP

Solving Constraint Integer Programs

sepa_flowcover.c File Reference

Detailed Description

flow cover cuts separator

Author
Kati Wolter
Tobias Achterberg

Definition in file sepa_flowcover.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_flowcover.h"
#include "scip/cons_knapsack.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "flowcover"
 
#define SEPA_DESC   "flow cover cuts separator (c-MIR approach)"
 
#define SEPA_PRIORITY   -4000
 
#define SEPA_FREQ   0
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   15
 
#define DEFAULT_MAXTRIES   100
 
#define DEFAULT_MAXTRIESROOT   -1
 
#define DEFAULT_MAXFAILS   50
 
#define DEFAULT_MAXFAILSROOT   100
 
#define DEFAULT_MAXSEPACUTS   100
 
#define DEFAULT_MAXSEPACUTSROOT   200
 
#define DEFAULT_MAXSLACK   SCIP_REAL_MAX
 
#define DEFAULT_MAXSLACKROOT   SCIP_REAL_MAX
 
#define DEFAULT_SLACKSCORE   1e-03
 
#define DEFAULT_MAXROWDENSITY   1.0
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_MAXTESTDELTA   10
 
#define DEFAULT_MULTBYMINUSONE   TRUE
 
#define BOUNDSWITCH   0.5
 
#define ALLOWLOCAL   TRUE
 
#define DENSSCORE   1e-04
 
#define MINFRAC   0.01
 
#define MAXFRAC   0.95
 
#define FIXINTEGRALRHS   FALSE
 
#define MAXDNOM   1000LL
 
#define MINDELTA   1e-03
 
#define MAXDELTA   1e-09
 
#define MAXSCALE   1000.0
 
#define MAXDYNPROGSPACE   1000000
 
#define MAXAGGRLEN(nvars)    (0.1*(nvars)+1000)
 
#define MAXABSVBCOEF   1e+5
 
#define MAXBOUND   1e+10
 

Functions

static SCIP_RETCODE getClosestVlb (SCIP *scip, SCIP_VAR *var, SCIP_Real bestsub, SCIP_Real rowcoef, SCIP_Real *rowcoefsbinary, SCIP_Real *varsolvals, int *assoctransvars, SCIP_Real *closestvlb, int *closestvlbidx)
 
static SCIP_RETCODE getClosestVub (SCIP *scip, SCIP_VAR *var, SCIP_Real bestslb, SCIP_Real rowcoef, SCIP_Real *rowcoefsbinary, SCIP_Real *varsolvals, int *assoctransvars, SCIP_Real *closestvub, int *closestvubidx)
 
static void getClosestLb (SCIP *scip, SCIP_VAR *var, SCIP_Bool allowlocal, SCIP_Real *closestlb, int *closestlbtype)
 
static void getClosestUb (SCIP *scip, SCIP_VAR *var, SCIP_Bool allowlocal, SCIP_Real *closestub, int *closestubtype)
 
static SCIP_RETCODE constructSNFRelaxation (SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Real *varsolvals, SCIP_ROW *row, SCIP_Real rowweight, SCIP_Real scale, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *ntransvars, SCIP_Real *transrhs, SCIP_Bool *success)
 
static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT (SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
 
static SCIP_Bool isIntegralScalar (SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
 
static SCIP_Longint getIntegralVal (SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
 
static void buildFlowCover (SCIP *scip, int *coefs, SCIP_Real *vubcoefs, SCIP_Real rhs, int *solitems, int *nonsolitems, int nsolitems, int nnonsolitems, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *flowcoverweight, SCIP_Real *lambda)
 
static SCIP_RETCODE getFlowCover (SCIP *scip, int *coefs, SCIP_Real *solvals, SCIP_Real *vubcoefs, int nvars, SCIP_Real rhs, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
 
static void getL1L2 (SCIP *scip, int ntransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *transvarflowcoverstatus, SCIP_Real delta, SCIP_Real lambda)
 
static SCIP_RETCODE getBoundsForSubstitution (SCIP *scip, SCIP_VAR **vars, int nvars, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int *transvarcoefs, int *flowcoverstatus, int ntransvars, int *boundsforsubst, SCIP_BOUNDTYPE *boundtypesforsubst)
 
static SCIP_RETCODE storeCutInArrays (SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
 
static SCIP_RETCODE addCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *cutcoefs, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, char normtype, SCIP_Bool *cutoff, int *ncuts)
 
static SCIP_Real calcEfficacy (int nvars, SCIP_Real *cutcoefs, SCIP_Real cutrhs, SCIP_Real cutact)
 
static SCIP_RETCODE cutGenerationHeuristic (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *rowweights, SCIP_Real scalar, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *assoctransvars, int ntransvars, int *transvarcoefs, SCIP_Real *transbinvarsolvals, SCIP_Real *transcontvarsolvals, SCIP_Real *transvarvubcoefs, int *transvarflowcoverstatus, SCIP_Real lambda, char normtype, SCIP_Bool *cutoff, int *ncuts)
 
static SCIP_DECL_SORTINDCOMP (rowScoreComp)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
 
static SCIP_DECL_SEPACOPY (sepaCopyFlowcover)
 
static SCIP_DECL_SEPAFREE (sepaFreeFlowcover)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpFlowcover)
 
static SCIP_DECL_SEPAEXECSOL (sepaExecsolFlowcover)
 
SCIP_RETCODE SCIPincludeSepaFlowcover (SCIP *scip)
 

Macro Definition Documentation

#define SEPA_NAME   "flowcover"

Definition at line 32 of file sepa_flowcover.c.

#define SEPA_DESC   "flow cover cuts separator (c-MIR approach)"

Definition at line 33 of file sepa_flowcover.c.

#define SEPA_PRIORITY   -4000

Definition at line 34 of file sepa_flowcover.c.

#define SEPA_FREQ   0

Definition at line 35 of file sepa_flowcover.c.

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 36 of file sepa_flowcover.c.

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 37 of file sepa_flowcover.c.

#define SEPA_DELAY   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 38 of file sepa_flowcover.c.

#define DEFAULT_MAXROUNDS   5

maximal number of separation rounds per node (-1: unlimited)

Definition at line 40 of file sepa_flowcover.c.

#define DEFAULT_MAXROUNDSROOT   15

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 41 of file sepa_flowcover.c.

#define DEFAULT_MAXTRIES   100

maximal number of rows to separate flow cover cuts for per separation round (-1: unlimited)

Definition at line 42 of file sepa_flowcover.c.

#define DEFAULT_MAXTRIESROOT   -1

maximal number of rows to separate flow cover cuts for per separation round in the root (-1: unlimited)

Definition at line 45 of file sepa_flowcover.c.

#define DEFAULT_MAXFAILS   50

maximal number of consecutive fails to generate a cut per separation round (-1: unlimited)

Definition at line 48 of file sepa_flowcover.c.

#define DEFAULT_MAXFAILSROOT   100

maximal number of consecutive fails to generate a cut per separation round in the root (-1: unlimited)

Definition at line 51 of file sepa_flowcover.c.

#define DEFAULT_MAXSEPACUTS   100

maximal number of flow cover cuts separated per separation round

Definition at line 54 of file sepa_flowcover.c.

#define DEFAULT_MAXSEPACUTSROOT   200

maximal number of flow cover cuts separated per separation round in the root

Definition at line 55 of file sepa_flowcover.c.

#define DEFAULT_MAXSLACK   SCIP_REAL_MAX

maximal slack of rows to separate flow cover cuts for

Definition at line 56 of file sepa_flowcover.c.

#define DEFAULT_MAXSLACKROOT   SCIP_REAL_MAX

maximal slack of rows to separate flow cover cuts for in the root

Definition at line 57 of file sepa_flowcover.c.

#define DEFAULT_SLACKSCORE   1e-03

weight of slack in the scoring of the rows

Definition at line 58 of file sepa_flowcover.c.

#define DEFAULT_MAXROWDENSITY   1.0

maximal density of rows to separate flow cover cuts for

Definition at line 59 of file sepa_flowcover.c.

#define DEFAULT_DYNAMICCUTS   TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 60 of file sepa_flowcover.c.

#define DEFAULT_MAXTESTDELTA   10

cut generation heuristic: maximal number of different deltas to try

Definition at line 61 of file sepa_flowcover.c.

#define DEFAULT_MULTBYMINUSONE   TRUE

should flow cover cuts be separated for 0-1 single node flow set with reversed arcs in addition?

Definition at line 62 of file sepa_flowcover.c.

#define BOUNDSWITCH   0.5

Definition at line 64 of file sepa_flowcover.c.

Referenced by constructSNFRelaxation(), and cutGenerationHeuristic().

#define ALLOWLOCAL   TRUE
#define DENSSCORE   1e-04

Definition at line 66 of file sepa_flowcover.c.

Referenced by separateCuts().

#define MINFRAC   0.01

Definition at line 68 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define MAXFRAC   0.95

Definition at line 69 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define FIXINTEGRALRHS   FALSE

Definition at line 70 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define MAXDNOM   1000LL

Definition at line 71 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MINDELTA   1e-03

Definition at line 72 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXDELTA   1e-09

Definition at line 73 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXSCALE   1000.0

Definition at line 74 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXDYNPROGSPACE   1000000

Definition at line 75 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXAGGRLEN (   nvars)    (0.1*(nvars)+1000)

maximal length of base inequality

Definition at line 77 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define MAXABSVBCOEF   1e+5

maximal absolute coefficient in variable bounds used for snf relaxation

Definition at line 78 of file sepa_flowcover.c.

Referenced by getClosestVlb(), and getClosestVub().

#define MAXBOUND   1e+10

maximal value of normal bounds used for snf relaxation

Definition at line 79 of file sepa_flowcover.c.

Referenced by getClosestLb(), and getClosestUb().

Function Documentation

static SCIP_RETCODE getClosestVlb ( SCIP scip,
SCIP_VAR var,
SCIP_Real  bestsub,
SCIP_Real  rowcoef,
SCIP_Real rowcoefsbinary,
SCIP_Real varsolvals,
int *  assoctransvars,
SCIP_Real closestvlb,
int *  closestvlbidx 
)
static

get LP solution value and index of variable lower bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable

Parameters
scipSCIP data structure
vargiven active problem variable
bestsubclosest simple upper bound of given variable
rowcoefcoefficient of given variable in current row
rowcoefsbinarycoefficient of all binary problem variables in current row
varsolvalsLP solution value of all active problem variables
assoctransvarsassociated var in relaxed set for all vars of row; construction is not finished yet
closestvlbpointer to store the LP sol value of the closest variable lower bound
closestvlbidxpointer to store the index of the closest vlb; -1 if no vlb was found

Definition at line 121 of file sepa_flowcover.c.

References FALSE, getClosestVub(), MAXABSVBCOEF, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetNVlbs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by constructSNFRelaxation().

static SCIP_RETCODE getClosestVub ( SCIP scip,
SCIP_VAR var,
SCIP_Real  bestslb,
SCIP_Real  rowcoef,
SCIP_Real rowcoefsbinary,
SCIP_Real varsolvals,
int *  assoctransvars,
SCIP_Real closestvub,
int *  closestvubidx 
)
static

get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable

Parameters
scipSCIP data structure
vargiven active problem variable
bestslbclosest simple lower bound of given variable
rowcoefcoefficient of given variable in current row
rowcoefsbinarycoefficient of all binary problem variables in current row
varsolvalsLP solution value of all active problem variables
assoctransvarsassociated var in relaxed set for all vars of row; construction is not finished yet
closestvubpointer to store the LP sol value of the closest variable upper bound
closestvubidxpointer to store the index of the closest vub; -1 if no vub was found

Definition at line 239 of file sepa_flowcover.c.

References FALSE, getClosestLb(), MAXABSVBCOEF, NULL, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by constructSNFRelaxation(), and getClosestVlb().

static void getClosestLb ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  allowlocal,
SCIP_Real closestlb,
int *  closestlbtype 
)
static

return global or local lower bound of given variable whichever is closer to the variables current LP solution value

Parameters
scipSCIP data structure
varactive problem variable
allowlocalshould local information allowed to be used, resulting in a local cut?
closestlbpointer to store the value of the closest variable lower bound
closestlbtypepointer to store type of closest bound; -1 if global lb, -2 otherwise

Definition at line 352 of file sepa_flowcover.c.

References getClosestUb(), MAXBOUND, NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPisGT(), SCIPvarGetLbGlobal(), and SCIPvarGetLbLocal().

Referenced by constructSNFRelaxation(), getBoundsForSubstitution(), and getClosestVub().

static void getClosestUb ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  allowlocal,
SCIP_Real closestub,
int *  closestubtype 
)
static

return global or local upper bound of given variable whichever is closer to the variables current LP solution value

Parameters
scipSCIP data structure
varactive problem variable
allowlocalshould local information allowed to be used, resulting in a local cut?
closestubpointer to store the value of the closest upper bound
closestubtypepointer to store type of closest bound; -1 if global ub, -2 otherwise

Definition at line 385 of file sepa_flowcover.c.

References constructSNFRelaxation(), MAXBOUND, NULL, SCIP_Real, SCIPinfinity(), SCIPisLT(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by constructSNFRelaxation(), getBoundsForSubstitution(), and getClosestLb().

static SCIP_RETCODE constructSNFRelaxation ( SCIP scip,
SCIP_VAR **  vars,
int  nvars,
SCIP_Real varsolvals,
SCIP_ROW row,
SCIP_Real  rowweight,
SCIP_Real  scale,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
int *  assoctransvars,
int *  transvarcoefs,
SCIP_Real transbinvarsolvals,
SCIP_Real transcontvarsolvals,
SCIP_Real transvarvubcoefs,
int *  ntransvars,
SCIP_Real transrhs,
SCIP_Bool success 
)
static

construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set corresponding to the given row lhs <= a * x + const <= rhs; depending on the given values rowweight and scale the mixed integer set which should be used is defined by the mixed integer constraint a * (x,y) <= rhs - const if (rowweight = 1, scale = 1) or (rowweight = -1, scale = -1, rhs < infinity)

  • a * (x,y) <= - (lhs - const) if (rowweight = -1, scale = 1) or (rowweight = 1, scale = -1, lhs > -infinity)
  • a * (x,y) - s <= - (rhs - const) if (rowweight = 1, scale = -1, lhs = -infinity) a * (x,y) - s <= (lhs - const) if (rowweight = -1, scale = -1, rhs = infinity)
Parameters
scipSCIP data structure
varsactive problem variables
nvarsnumber of active problem variables
varsolvalssolution values of active problem variables
rowgiven row
rowweightweight of given row; can be +1 or -1
scaleadditional scaling factor for given row
boundsfortranspointer to store bound used for all non-binary vars of row
boundtypesfortranspointer to store type of bound used for all non-binary vars of row
assoctransvarspointer to store associated var in relaxed set for all vars of row
transvarcoefspointer to store coefficient of all vars in relaxed set
transbinvarsolvalspointer to store sol val of bin var in vub of all vars in relaxed set
transcontvarsolvalspointer to store sol val of all real vars in relaxed set
transvarvubcoefspointer to store coefficient in vub of all vars in relaxed set
ntransvarspointer to store number of vars in relaxed set
transrhspointer to store rhs in relaxed set
successpointer to store whether a relaxation was constructed

Definition at line 425 of file sepa_flowcover.c.

References ALLOWLOCAL, BMSclearMemoryArray, BOUNDSWITCH, FALSE, getClosestLb(), getClosestUb(), getClosestVlb(), getClosestVub(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetVar(), SCIPdebugMessage, SCIPdebugPrintf, SCIPfreeBufferArray, SCIPinfinity(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPsolveKnapsackApproximatelyLT(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsBinary(), and TRUE.

Referenced by getClosestUb(), and separateCuts().

static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT ( SCIP scip,
int  nitems,
SCIP_Real weights,
SCIP_Real profits,
SCIP_Real  capacity,
int *  items,
int *  solitems,
int *  nonsolitems,
int *  nsolitems,
int *  nnonsolitems,
SCIP_Real solval 
)
static

solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide arrays to store all selected items and all not selected items

Parameters
scipSCIP data structure
nitemsnumber of available items
weightsitem weights
profitsitem profits
capacitycapacity of knapsack
itemsitem numbers
solitemsarray to store items in solution, or NULL
nonsolitemsarray to store items not in solution, or NULL
nsolitemspointer to store number of items in solution, or NULL
nnonsolitemspointer to store number of items not in solution, or NULL
solvalpointer to store optimal solution value, or NULL

Definition at line 1017 of file sepa_flowcover.c.

References isIntegralScalar(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisInfinity(), and SCIPsortDownRealRealRealInt().

Referenced by constructSNFRelaxation(), and getFlowCover().

static SCIP_Bool isIntegralScalar ( SCIP_Real  val,
SCIP_Real  scalar,
SCIP_Real  mindelta,
SCIP_Real  maxdelta 
)
static

checks, whether the given scalar scales the given value to an integral number with error in the given bounds

Parameters
valvalue that should be scaled to an integral value
scalarscalar that should be tried
mindeltaminimal relative allowed difference of scaled coefficient s*c and integral i
maxdeltamaximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 1089 of file sepa_flowcover.c.

References getIntegralVal(), SCIP_Longint, SCIP_Real, and SCIPrelDiff().

Referenced by getFlowCover(), and SCIPsolveKnapsackApproximatelyLT().

static SCIP_Longint getIntegralVal ( SCIP_Real  val,
SCIP_Real  scalar,
SCIP_Real  mindelta,
SCIP_Real  maxdelta 
)
static

get integral number with error in the bounds which corresponds to given value scaled by a given scalar; should be used in connection with isIntegralScalar()

Parameters
valvalue that should be scaled to an integral value
scalarscalar that should be tried
mindeltaminimal relative allowed difference of scaled coefficient s*c and integral i
maxdeltamaximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 1114 of file sepa_flowcover.c.

References buildFlowCover(), SCIP_Longint, SCIP_Real, and SCIPrelDiff().

Referenced by getFlowCover(), and isIntegralScalar().

static void buildFlowCover ( SCIP scip,
int *  coefs,
SCIP_Real vubcoefs,
SCIP_Real  rhs,
int *  solitems,
int *  nonsolitems,
int  nsolitems,
int  nnonsolitems,
int *  nflowcovervars,
int *  nnonflowcovervars,
int *  flowcoverstatus,
SCIP_Real flowcoverweight,
SCIP_Real lambda 
)
static

build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished flow cover contains variables which have been fixed in advance

Parameters
scipSCIP data structure
coefscoefficient of all real variables in N1&N2
vubcoefscoefficient in vub of all real variables in N1&N2
rhsright hand side of 0-1 single node flow constraint
solitemsitems in knapsack
nonsolitemsitems not in knapsack
nsolitemsnumber of items in knapsack
nnonsolitemsnumber of items not in knapsack
nflowcovervarspointer to store number of variables in flow cover
nnonflowcovervarspointer to store number of variables not in flow cover
flowcoverstatuspointer to store whether variable is in flow cover (+1) or not (-1)
flowcoverweightpointer to store weight of flow cover
lambdapointer to store lambda

Definition at line 1143 of file sepa_flowcover.c.

References getFlowCover(), NULL, and SCIP_Real.

Referenced by getFlowCover(), and getIntegralVal().

static SCIP_RETCODE getFlowCover ( SCIP scip,
int *  coefs,
SCIP_Real solvals,
SCIP_Real vubcoefs,
int  nvars,
SCIP_Real  rhs,
int *  nflowcovervars,
int *  nnonflowcovervars,
int *  flowcoverstatus,
SCIP_Real lambda,
SCIP_Bool found 
)
static

get a flow cover (C1, C2) for a given 0-1 single node flow set {(x,y) in {0,1}^n x R^n : sum_{j in N1} y_j - sum_{j in N2} y_j <= b, 0 <= y_j <= u_j x_j}, i.e., get sets C1 subset N1 and C2 subset N2 with sum_{j in C1} u_j - sum_{j in C2} u_j = b + lambda and lambda > 0

Parameters
scipSCIP data structure
coefscoefficient of all real variables in N1&N2
solvalsLP solution value of binary variable in vub of all real vars in N1&N2
vubcoefscoefficient in vub of all real variables in N1&N2
nvarsnumber of real variables in N1&N2
rhsright hand side of 0-1 single node flow constraint
nflowcovervarspointer to store number of variables in flow cover
nnonflowcovervarspointer to store number of variables not in flow cover
flowcoverstatuspointer to store whether variable is in flow cover (+1) or not (-1)
lambdapointer to store lambda
foundpointer to store whether a cover was found

Definition at line 1219 of file sepa_flowcover.c.

References BMSclearMemoryArray, buildFlowCover(), FALSE, getIntegralVal(), getL1L2(), isIntegralScalar(), MAXDELTA, MAXDNOM, MAXDYNPROGSPACE, MAXSCALE, MIN, MINDELTA, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisIntegral(), SCIPsolveKnapsackApproximatelyLT(), SCIPsolveKnapsackExactly(), and TRUE.

Referenced by buildFlowCover(), and separateCuts().

static void getL1L2 ( SCIP scip,
int  ntransvars,
int *  transvarcoefs,
SCIP_Real transbinvarsolvals,
SCIP_Real transcontvarsolvals,
SCIP_Real transvarvubcoefs,
int *  transvarflowcoverstatus,
SCIP_Real  delta,
SCIP_Real  lambda 
)
static

for a given flow cover and a given value of delta, choose L1 subset N1 \ C1 and L2 subset N2 \ C2 by comparison such that the violation of the resulting c-MIRFCI is maximized.

Parameters
scipSCIP data structure
ntransvarsnumber of continuous variables in N1 & N2
transvarcoefscoefficient of all continuous variables in N1 & N2
transbinvarsolvalsLP solution value of bin var in vub of all continuous vars in N1 & N2
transcontvarsolvalsLP solution value of all continuous vars in N1 & N2
transvarvubcoefscoefficient of vub of all continuous variables in N1 & N2
transvarflowcoverstatuspointer to store whether non-binary var is in L2 (2) or not (-1 or 1)
deltadelta
lambdalambda

Definition at line 1600 of file sepa_flowcover.c.

References getBoundsForSubstitution(), NULL, SCIP_Real, SCIPdebugMessage, SCIPfloor(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), and SCIPisSumLE().

Referenced by cutGenerationHeuristic(), and getFlowCover().

static SCIP_RETCODE getBoundsForSubstitution ( SCIP scip,
SCIP_VAR **  vars,
int  nvars,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
int *  assoctransvars,
int *  transvarcoefs,
int *  flowcoverstatus,
int  ntransvars,
int *  boundsforsubst,
SCIP_BOUNDTYPE boundtypesforsubst 
)
static

get for all problem variables with nonzero coefficient in current row the bound which should be used for the substitution routine in the c-MIR routine; this bound depends on the bound used for each variable to get associated variable in transformed problem

Parameters
scipSCIP data structure
varsactive problem variables
nvarsnumber of active problem variables
boundsfortransbound used for transformation for all non-binary vars of current row
boundtypesfortranstype of bound used for transform. for all non-binary vars of current row
assoctransvarsassociated var in transformed problem for all vars of current row
transvarcoefscoefficient of all vars in transformed problem
flowcoverstatusflow cover status of all non-binary vars in transformed problem; 1 if in C1 & C2, 2 if in L2, -1 N1 \ C1 & N2 \ (C2&L2)
ntransvarsnumber of vars in transformed problem
boundsforsubstpointer to store bounds that should be used for substitution in c-mir for vars
boundtypesforsubstpointer to store types of bounds that should be used for substitution in c-mir

Definition at line 1707 of file sepa_flowcover.c.

References ALLOWLOCAL, getClosestLb(), getClosestUb(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), SCIPvarGetProbindex(), SCIPvarIsBinary(), and storeCutInArrays().

Referenced by cutGenerationHeuristic(), and getL1L2().

static SCIP_RETCODE storeCutInArrays ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real cutcoefs,
SCIP_Real varsolvals,
char  normtype,
SCIP_VAR **  cutvars,
SCIP_Real cutvals,
int *  cutlen,
SCIP_Real cutact,
SCIP_Real cutnorm 
)
static

stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm

Parameters
scipSCIP data structure
nvarsnumber of problem variables
varsproblem variables
cutcoefsdense coefficient vector
varsolvalsdense variable LP solution vector
normtypetype of norm to use for efficacy norm calculation
cutvarsarray to store variables of sparse cut vector
cutvalsarray to store coefficients of sparse cut vector
cutlenpointer to store number of nonzero entries in cut
cutactpointer to store activity of cut
cutnormpointer to store norm of cut vector

Definition at line 1811 of file sepa_flowcover.c.

References addCut(), MAX, NULL, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().

Referenced by addCut(), and getBoundsForSubstitution().

static SCIP_RETCODE addCut ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
SCIP_VAR **  vars,
int  nvars,
SCIP_SOL sol,
SCIP_Real varsolvals,
SCIP_Real cutcoefs,
SCIP_Real  cutrhs,
SCIP_Bool  cutislocal,
int  cutrank,
char  normtype,
SCIP_Bool cutoff,
int *  ncuts 
)
static

adds given cut to LP if violated

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
varsproblem variables
nvarsnumber of problem variables
solthe solution that should be separated, or NULL for LP solution
varsolvalssolution values of active variables
cutcoefscoefficients of active variables in cut
cutrhsright hand side of cut
cutislocalis the cut only locally valid?
cutrankrank of the cut
normtypetype of norm to use for efficacy norm calculation
cutoffwhether a cutoff has been detected
ncutspointer to count the number of added cuts

Definition at line 1919 of file sepa_flowcover.c.

References calcEfficacy(), FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPsnprintf(), SCIPsumepsilon(), storeCutInArrays(), and TRUE.

Referenced by cutGenerationHeuristic(), and storeCutInArrays().

static SCIP_Real calcEfficacy ( int  nvars,
SCIP_Real cutcoefs,
SCIP_Real  cutrhs,
SCIP_Real  cutact 
)
static

calculates efficacy of the given cut

Parameters
nvarsnumber of variables in the problem
cutcoefsdense vector of cut coefficients
cutrhsright hand side of cut
cutactactivity of cut

Definition at line 2023 of file sepa_flowcover.c.

References cutGenerationHeuristic(), MAX, NULL, and SCIP_Real.

Referenced by addCut(), and cutGenerationHeuristic().

static SCIP_RETCODE cutGenerationHeuristic ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
SCIP_VAR **  vars,
int  nvars,
SCIP_SOL sol,
SCIP_Real varsolvals,
SCIP_Real rowweights,
SCIP_Real  scalar,
int *  boundsfortrans,
SCIP_BOUNDTYPE boundtypesfortrans,
int *  assoctransvars,
int  ntransvars,
int *  transvarcoefs,
SCIP_Real transbinvarsolvals,
SCIP_Real transcontvarsolvals,
SCIP_Real transvarvubcoefs,
int *  transvarflowcoverstatus,
SCIP_Real  lambda,
char  normtype,
SCIP_Bool cutoff,
int *  ncuts 
)
static
Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
varsactive problem variables
nvarsnumber of active problem variables
solthe solution that should be separated, or NULL for LP solution
varsolvalssolution values of active variables
rowweightsweight of rows in aggregated row
scalaradditional scaling factor of rows in aggregation
boundsfortransbound used for all non-bin vars of row
boundtypesfortranstype of bound used for all non-binary vars of row
assoctransvarsassociated var in relaxed set for all vars of row
ntransvarsnumber of real variables in N1&N2
transvarcoefscoefficient of all continuous variables in N1 & N2
transbinvarsolvalsLP solution value of binary variable in vub of all real vars in N1&N2
transcontvarsolvalsLP solution value of all real vars in N1&N2
transvarvubcoefscoefficient of vub of all continuous variables in N1 & N2
transvarflowcoverstatuspointer to store whether non-binary var is in L2 (2) or not (-1 or 1)
lambdalambda
normtypetype of norm to use for efficacy norm calculation
cutoffwhether a cutoff has been detected
ncutspointer to count the number of generated cuts

Definition at line 2044 of file sepa_flowcover.c.

References addCut(), ALLOWLOCAL, BMScopyMemoryArray, BOUNDSWITCH, calcEfficacy(), FALSE, FIXINTEGRALRHS, getBoundsForSubstitution(), getL1L2(), MAX, MAXAGGRLEN, MAXFRAC, MIN, MINFRAC, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_SORTINDCOMP(), SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPcalcMIR(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by calcEfficacy(), and separateCuts().

static SCIP_DECL_SORTINDCOMP ( rowScoreComp  )
static

comparison method for scores of lp rows

Definition at line 2330 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

static SCIP_DECL_SEPACOPY ( sepaCopyFlowcover  )
static

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

Definition at line 2697 of file sepa_flowcover.c.

Referenced by separateCuts().

static SCIP_DECL_SEPAFREE ( sepaFreeFlowcover  )
static

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

Definition at line 2711 of file sepa_flowcover.c.

static SCIP_DECL_SEPAEXECLP ( sepaExeclpFlowcover  )
static

LP solution separation method of separator

Definition at line 2729 of file sepa_flowcover.c.

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolFlowcover  )
static

arbitrary primal solution separation method of separator

Definition at line 2754 of file sepa_flowcover.c.

SCIP_RETCODE SCIPincludeSepaFlowcover ( SCIP scip)

creates the flowcover separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 2770 of file sepa_flowcover.c.

Referenced by SCIPincludeDefaultPlugins().