flow cover cuts separator
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.
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) |
#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().
|
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
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 |
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
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 |
return global or local lower bound of given variable whichever is closer to the variables current LP solution value
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 |
return global or local upper bound of given variable whichever is closer to the variables current LP solution value
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 |
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)
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(), SCIPdebugMsg, SCIPdebugMsgPrint, 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 |
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
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 1016 of file sepa_flowcover.c.
References isIntegralScalar(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfeastol(), SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisInfinity(), and SCIPselectWeightedDownRealRealInt().
Referenced by constructSNFRelaxation(), and getFlowCover().
|
static |
checks, whether the given scalar scales the given value to an integral number with error in the given bounds
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 1109 of file sepa_flowcover.c.
References getIntegralVal(), SCIP_Longint, SCIP_Real, and SCIPrelDiff().
Referenced by getFlowCover(), and SCIPsolveKnapsackApproximatelyLT().
|
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()
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 1134 of file sepa_flowcover.c.
References buildFlowCover(), SCIP_Longint, SCIP_Real, and SCIPrelDiff().
Referenced by getFlowCover(), and isIntegralScalar().
|
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
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 1163 of file sepa_flowcover.c.
References getFlowCover(), NULL, and SCIP_Real.
Referenced by getFlowCover(), and getIntegralVal().
|
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
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 1239 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(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisIntegral(), SCIPsolveKnapsackApproximatelyLT(), SCIPsolveKnapsackExactly(), and TRUE.
Referenced by buildFlowCover(), and separateCuts().
|
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.
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 1621 of file sepa_flowcover.c.
References getBoundsForSubstitution(), NULL, SCIP_Real, SCIPdebugMsg, SCIPfloor(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), and SCIPisSumLE().
Referenced by cutGenerationHeuristic(), and getFlowCover().
|
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
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 1728 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 |
stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm
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 1832 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 |
adds given cut to LP if violated
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 1940 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, SCIPdebugMsg, 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 |
calculates efficacy of the given cut
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 2044 of file sepa_flowcover.c.
References cutGenerationHeuristic(), MAX, NULL, and SCIP_Real.
Referenced by addCut(), and cutGenerationHeuristic().
|
static |
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 2065 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(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), and TRUE.
Referenced by calcEfficacy(), and separateCuts().
|
static |
comparison method for scores of lp rows
Definition at line 2350 of file sepa_flowcover.c.
Referenced by cutGenerationHeuristic().
|
static |
search and add flowcover cuts that separate the given primal solution
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 2370 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, SCIPdebugMsg, 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 |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 2716 of file sepa_flowcover.c.
Referenced by separateCuts().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 2730 of file sepa_flowcover.c.
|
static |
LP solution separation method of separator
Definition at line 2748 of file sepa_flowcover.c.
|
static |
arbitrary primal solution separation method of separator
Definition at line 2773 of file sepa_flowcover.c.