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.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaFlowcover().

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

Definition at line 33 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define SEPA_PRIORITY   -4000

Definition at line 34 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define SEPA_FREQ   0

Definition at line 35 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 36 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 37 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define SEPA_DELAY   FALSE

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

Definition at line 38 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXROUNDS   5

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

Definition at line 40 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXROUNDSROOT   15

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

Definition at line 41 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#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.

Referenced by SCIPincludeSepaFlowcover().

#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 44 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXFAILS   50

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

Definition at line 46 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXFAILSROOT   100

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

Definition at line 48 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXSEPACUTS   100

maximal number of flow cover cuts separated per separation round

Definition at line 50 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXSEPACUTSROOT   200

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

Definition at line 51 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXSLACK   SCIP_REAL_MAX

maximal slack of rows to separate flow cover cuts for

Definition at line 52 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXSLACKROOT   SCIP_REAL_MAX

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

Definition at line 53 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_SLACKSCORE   1e-03

weight of slack in the scoring of the rows

Definition at line 54 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXROWDENSITY   1.0

maximal density of rows to separate flow cover cuts for

Definition at line 55 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 56 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define DEFAULT_MAXTESTDELTA   10

cut generation heuristic: maximal number of different deltas to try

Definition at line 57 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#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 58 of file sepa_flowcover.c.

Referenced by SCIPincludeSepaFlowcover().

#define BOUNDSWITCH   0.5

Definition at line 60 of file sepa_flowcover.c.

Referenced by constructSNFRelaxation(), and cutGenerationHeuristic().

#define ALLOWLOCAL   TRUE

Definition at line 61 of file sepa_flowcover.c.

Referenced by constructSNFRelaxation(), cutGenerationHeuristic(), getBoundsForSubstitution(), and separateCuts().

#define DENSSCORE   1e-04

Definition at line 62 of file sepa_flowcover.c.

Referenced by separateCuts().

#define MINFRAC   0.01

Definition at line 64 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define MAXFRAC   0.95

Definition at line 65 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define FIXINTEGRALRHS   FALSE

Definition at line 66 of file sepa_flowcover.c.

Referenced by cutGenerationHeuristic().

#define MAXDNOM   1000LL

Definition at line 67 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MINDELTA   1e-03

Definition at line 68 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXDELTA   1e-09

Definition at line 69 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXSCALE   1000.0

Definition at line 70 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXDYNPROGSPACE   1000000

Definition at line 71 of file sepa_flowcover.c.

Referenced by getFlowCover().

#define MAXAGGRLEN

(

nvars

)

(0.1*(nvars)+1000)

maximal length of base inequality

Definition at line 73 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 74 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 75 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

scip	SCIP data structure
var	given active problem variable
bestsub	closest simple upper bound of given variable
rowcoef	coefficient of given variable in current row
rowcoefsbinary	coefficient of all binary problem variables in current row
varsolvals	LP solution value of all active problem variables
assoctransvars	associated var in relaxed set for all vars of row; construction is not finished yet
closestvlb	pointer to store the LP sol value of the closest variable lower bound
closestvlbidx	pointer to store the index of the closest vlb; -1 if no vlb was found

Definition at line 117 of file sepa_flowcover.c.

References FALSE, 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

scip	SCIP data structure
var	given active problem variable
bestslb	closest simple lower bound of given variable
rowcoef	coefficient of given variable in current row
rowcoefsbinary	coefficient of all binary problem variables in current row
varsolvals	LP solution value of all active problem variables
assoctransvars	associated var in relaxed set for all vars of row; construction is not finished yet
closestvub	pointer to store the LP sol value of the closest variable upper bound
closestvubidx	pointer to store the index of the closest vub; -1 if no vub was found

Definition at line 235 of file sepa_flowcover.c.

References FALSE, 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().

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

scip	SCIP data structure
var	active problem variable
allowlocal	should local information allowed to be used, resulting in a local cut?
closestlb	pointer to store the value of the closest variable lower bound
closestlbtype	pointer to store type of closest bound; -1 if global lb, -2 otherwise

Definition at line 348 of file sepa_flowcover.c.

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

Referenced by constructSNFRelaxation(), and getBoundsForSubstitution().

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

scip	SCIP data structure
var	active problem variable
allowlocal	should local information allowed to be used, resulting in a local cut?
closestub	pointer to store the value of the closest upper bound
closestubtype	pointer to store type of closest bound; -1 if global ub, -2 otherwise

Definition at line 381 of file sepa_flowcover.c.

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

Referenced by constructSNFRelaxation(), and getBoundsForSubstitution().

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

scip	SCIP data structure
vars	active problem variables
nvars	number of active problem variables
varsolvals	solution values of active problem variables
row	given row
rowweight	weight of given row; can be +1 or -1
scale	additional scaling factor for given row
boundsfortrans	pointer to store bound used for all non-binary vars of row
boundtypesfortrans	pointer to store type of bound used for all non-binary vars of row
assoctransvars	pointer to store associated var in relaxed set for all vars of row
transvarcoefs	pointer to store coefficient of all vars in relaxed set
transbinvarsolvals	pointer to store sol val of bin var in vub of all vars in relaxed set
transcontvarsolvals	pointer to store sol val of all real vars in relaxed set
transvarvubcoefs	pointer to store coefficient in vub of all vars in relaxed set
ntransvars	pointer to store number of vars in relaxed set
transrhs	pointer to store rhs in relaxed set
success	pointer to store whether a relaxation was constructed

Definition at line 421 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(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsBinary(), and TRUE.

Referenced by 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

scip	SCIP data structure
nitems	number of available items
weights	item weights
profits	item profits
capacity	capacity of knapsack
items	item numbers
solitems	array to store items in solution, or NULL
nonsolitems	array to store items not in solution, or NULL
nsolitems	pointer to store number of items in solution, or NULL
nnonsolitems	pointer to store number of items not in solution, or NULL
solval	pointer to store optimal solution value, or NULL

Definition at line 1013 of file sepa_flowcover.c.

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

Referenced by 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

val	value that should be scaled to an integral value
scalar	scalar that should be tried
mindelta	minimal relative allowed difference of scaled coefficient s*c and integral i
maxdelta	maximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 1085 of file sepa_flowcover.c.

References SCIP_Real, and SCIPrelDiff().

Referenced by getFlowCover().

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

val	value that should be scaled to an integral value
scalar	scalar that should be tried
mindelta	minimal relative allowed difference of scaled coefficient s*c and integral i
maxdelta	maximal relative allowed difference of scaled coefficient s*c and integral i

Definition at line 1110 of file sepa_flowcover.c.

References SCIP_Longint, SCIP_Real, and SCIPrelDiff().

Referenced by getFlowCover().

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

scip	SCIP data structure
coefs	coefficient of all real variables in N1&N2
vubcoefs	coefficient in vub of all real variables in N1&N2
rhs	right hand side of 0-1 single node flow constraint
solitems	items in knapsack
nonsolitems	items not in knapsack
nsolitems	number of items in knapsack
nnonsolitems	number of items not in knapsack
nflowcovervars	pointer to store number of variables in flow cover
nnonflowcovervars	pointer to store number of variables not in flow cover
flowcoverstatus	pointer to store whether variable is in flow cover (+1) or not (-1)
flowcoverweight	pointer to store weight of flow cover
lambda	pointer to store lambda

Definition at line 1139 of file sepa_flowcover.c.

References NULL.

Referenced by getFlowCover().

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

scip	SCIP data structure
coefs	coefficient of all real variables in N1&N2
solvals	LP solution value of binary variable in vub of all real vars in N1&N2
vubcoefs	coefficient in vub of all real variables in N1&N2
nvars	number of real variables in N1&N2
rhs	right hand side of 0-1 single node flow constraint
nflowcovervars	pointer to store number of variables in flow cover
nnonflowcovervars	pointer to store number of variables not in flow cover
flowcoverstatus	pointer to store whether variable is in flow cover (+1) or not (-1)
lambda	pointer to store lambda
found	pointer to store whether a cover was found

Definition at line 1215 of file sepa_flowcover.c.

References BMSclearMemoryArray, buildFlowCover(), FALSE, getIntegralVal(), 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 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

scip	SCIP data structure
ntransvars	number of continuous variables in N1 & N2
transvarcoefs	coefficient of all continuous variables in N1 & N2
transbinvarsolvals	LP solution value of bin var in vub of all continuous vars in N1 & N2
transcontvarsolvals	LP solution value of all continuous vars in N1 & N2
transvarvubcoefs	coefficient of vub of all continuous variables in N1 & N2
transvarflowcoverstatus	pointer to store whether non-binary var is in L2 (2) or not (-1 or 1)
delta	delta
lambda	lambda

Definition at line 1596 of file sepa_flowcover.c.

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

Referenced by cutGenerationHeuristic().

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

scip	SCIP data structure
vars	active problem variables
nvars	number of active problem variables
boundsfortrans	bound used for transformation for all non-binary vars of current row
boundtypesfortrans	type of bound used for transform. for all non-binary vars of current row
assoctransvars	associated var in transformed problem for all vars of current row
transvarcoefs	coefficient of all vars in transformed problem
flowcoverstatus	flow 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)
ntransvars	number of vars in transformed problem
boundsforsubst	pointer to store bounds that should be used for substitution in c-mir for vars
boundtypesforsubst	pointer to store types of bounds that should be used for substitution in c-mir

Definition at line 1703 of file sepa_flowcover.c.

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

Referenced by cutGenerationHeuristic().

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

scip	SCIP data structure
nvars	number of problem variables
vars	problem variables
cutcoefs	dense coefficient vector
varsolvals	dense variable LP solution vector
normtype	type of norm to use for efficacy norm calculation
cutvars	array to store variables of sparse cut vector
cutvals	array to store coefficients of sparse cut vector
cutlen	pointer to store number of nonzero entries in cut
cutact	pointer to store activity of cut
cutnorm	pointer to store norm of cut vector

Definition at line 1807 of file sepa_flowcover.c.

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

Referenced by addCut().

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

scip	SCIP data structure
sepa	separator
sepadata	separator data
vars	problem variables
nvars	number of problem variables
sol	the solution that should be separated, or NULL for LP solution
varsolvals	solution values of active variables
cutcoefs	coefficients of active variables in cut
cutrhs	right hand side of cut
cutislocal	is the cut only locally valid?
cutrank	rank of the cut
normtype	type of norm to use for efficacy norm calculation
cutoff	whether a cutoff has been detected
ncuts	pointer to count the number of added cuts

Definition at line 1915 of file sepa_flowcover.c.

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

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

static

calculates efficacy of the given cut

Parameters

nvars	number of variables in the problem
cutcoefs	dense vector of cut coefficients
cutrhs	right hand side of cut
cutact	activity of cut

Definition at line 2019 of file sepa_flowcover.c.

References MAX, NULL, and SCIP_Real.

Referenced by 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

scip	SCIP data structure
sepa	separator
sepadata	separator data
vars	active problem variables
nvars	number of active problem variables
sol	the solution that should be separated, or NULL for LP solution
varsolvals	solution values of active variables
rowweights	weight of rows in aggregated row
scalar	additional scaling factor of rows in aggregation
boundsfortrans	bound used for all non-bin vars of row
boundtypesfortrans	type of bound used for all non-binary vars of row
assoctransvars	associated var in relaxed set for all vars of row
ntransvars	number of real variables in N1&N2
transvarcoefs	coefficient of all continuous variables in N1 & N2
transbinvarsolvals	LP solution value of binary variable in vub of all real vars in N1&N2
transcontvarsolvals	LP solution value of all real vars in N1&N2
transvarvubcoefs	coefficient of vub of all continuous variables in N1 & N2
transvarflowcoverstatus	pointer to store whether non-binary var is in L2 (2) or not (-1 or 1)
lambda	lambda
normtype	type of norm to use for efficacy norm calculation
cutoff	whether a cutoff has been detected
ncuts	pointer to count the number of generated cuts

Definition at line 2040 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_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPcalcMIR(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by separateCuts().

static SCIP_DECL_SORTINDCOMP ( rowScoreComp  )

static

comparison method for scores of lp rows

Definition at line 2326 of file sepa_flowcover.c.

References NULL, and SCIP_Real.

static SCIP_RETCODE separateCuts ( SCIP *  scip, SCIP_SEPA *  sepa, SCIP_SOL *  sol, SCIP_RESULT *  result  )

static

search and add flowcover cuts that separate the given primal solution

Parameters

scip	SCIP data structure
sepa	the flowcover separator
sol	the solution that should be separated, or NULL for LP solution
result	pointer to store the result

Definition at line 2346 of file sepa_flowcover.c.

References ALLOWLOCAL, BMSclearMemoryArray, constructSNFRelaxation(), cutGenerationHeuristic(), DENSSCORE, FALSE, getFlowCover(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPallocBufferArray, SCIPdebug, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCharParam(), SCIPgetDepth(), SCIPgetLPRowsData(), SCIPgetNSepaRounds(), SCIPgetNVars(), SCIPgetObjNorm(), SCIPgetRowSolActivity(), SCIPgetSolVals(), SCIPgetVars(), SCIPisFeasGT(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPisStopped(), SCIPprintRow(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPsortInd(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

static SCIP_DECL_SEPACOPY ( sepaCopyFlowcover  )

static

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

Definition at line 2693 of file sepa_flowcover.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaFlowcover(), SCIPsepaGetName(), and SEPA_NAME.

static SCIP_DECL_SEPAFREE ( sepaFreeFlowcover  )

static

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

Definition at line 2707 of file sepa_flowcover.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), and SCIPsepaSetData().

static SCIP_DECL_SEPAEXECLP ( sepaExeclpFlowcover  )

static

LP solution separation method of separator

Definition at line 2725 of file sepa_flowcover.c.

References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolFlowcover  )

static

arbitrary primal solution separation method of separator

Definition at line 2750 of file sepa_flowcover.c.

References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().

SCIP_RETCODE SCIPincludeSepaFlowcover

(

SCIP *

scip

)

creates the flowcover separator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2766 of file sepa_flowcover.c.

References DEFAULT_DYNAMICCUTS, DEFAULT_MAXFAILS, DEFAULT_MAXFAILSROOT, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXROWDENSITY, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_MAXSLACK, DEFAULT_MAXSLACKROOT, DEFAULT_MAXTESTDELTA, DEFAULT_MAXTRIES, DEFAULT_MAXTRIESROOT, DEFAULT_MULTBYMINUSONE, DEFAULT_SLACKSCORE, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SCIPsetSepaFree(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and TRUE.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeDefaultPlugins().