SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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.