Detailed Description

flow cover cuts separator

Author: Kati Wolter; Tobias Achterberg

#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

Definition at line 65 of file sepa_flowcover.c.

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

#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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 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_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 2350 of file sepa_flowcover.c.

References ALLOWLOCAL, BMSclearMemoryArray, constructSNFRelaxation(), cutGenerationHeuristic(), DENSSCORE, FALSE, getFlowCover(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPACOPY(), 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.

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

scip	SCIP data structure

Definition at line 2770 of file sepa_flowcover.c.

Referenced by SCIPincludeDefaultPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation