SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
complemented mixed integer rounding cuts separator (Marchand's version)
Definition in file sepa_cmir.c.
Go to the source code of this file.
Functions | |
| static SCIP_RETCODE | storeCutInArrays (SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact) |
| static SCIP_RETCODE | addCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *cutcoefs, SCIP_Real cutrhs, SCIP_Bool cutislocal, SCIP_Bool cutremovable, int cutrank, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts) |
| static void | updateNActiveConts (SCIP *scip, SCIP_Real *varsolvals, SCIP_Real *bestcontlbs, SCIP_Real *bestcontubs, int nintvars, SCIP_VAR *var, int delta, int *nactiveconts) |
| static void | decreaseRowScore (SCIP *scip, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int rowidx) |
| static SCIP_RETCODE | tryDelta (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_Real *rowweights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, SCIP_Real *cutcoefs, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *testeddeltas, int *ntesteddeltas, SCIP_Real delta, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *bestdelta, SCIP_Real *bestefficacy) |
| SCIP_RETCODE | SCIPcutGenerationHeuristicCmir (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *varsolvals, int maxtestdelta, SCIP_Real *rowweights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Bool trynegscaling, SCIP_Bool cutremovable, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts, SCIP_Real *delta, SCIP_Bool *deltavalid) |
| static SCIP_Bool | varIsContinuous (SCIP_VAR *var) |
| static SCIP_Real | getBounddist (SCIP *scip, int nintvars, SCIP_Real *varsolvals, SCIP_Real *bestcontlbs, SCIP_Real *bestcontubs, SCIP_VAR *var) |
| static SCIP_RETCODE | aggregation (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *varsolvals, SCIP_Real *bestcontlbs, SCIP_Real *bestcontubs, SCIP_Real *contvarscorebounds, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int startrow, int maxaggrs, SCIP_Real maxslack, int maxconts, SCIP_Bool *wastried, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result) |
| static | SCIP_DECL_SEPACOPY (sepaCopyCmir) |
| static | SCIP_DECL_SEPAFREE (sepaFreeCmir) |
| static | SCIP_DECL_SEPAEXECLP (sepaExeclpCmir) |
| static | SCIP_DECL_SEPAEXECSOL (sepaExecsolCmir) |
| SCIP_RETCODE | SCIPincludeSepaCmir (SCIP *scip) |
| #define SEPA_NAME "cmir" |
Definition at line 31 of file sepa_cmir.c.
| #define SEPA_DESC "complemented mixed integer rounding cuts separator (Marchand's version)" |
Definition at line 32 of file sepa_cmir.c.
| #define SEPA_PRIORITY -3000 |
Definition at line 33 of file sepa_cmir.c.
| #define SEPA_FREQ 0 |
Definition at line 34 of file sepa_cmir.c.
| #define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 35 of file sepa_cmir.c.
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 36 of file sepa_cmir.c.
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 37 of file sepa_cmir.c.
| #define DEFAULT_MAXROUNDS 3 |
maximal number of cmir separation rounds per node (-1: unlimited)
Definition at line 39 of file sepa_cmir.c.
| #define DEFAULT_MAXROUNDSROOT 10 |
maximal number of cmir separation rounds in the root node (-1: unlimited)
Definition at line 40 of file sepa_cmir.c.
| #define DEFAULT_MAXTRIES 100 |
maximal number of rows to start aggregation with per separation round (-1: unlimited)
Definition at line 41 of file sepa_cmir.c.
| #define DEFAULT_MAXTRIESROOT -1 |
maximal number of rows to start aggregation with per round in the root node (-1: unlimited)
Definition at line 44 of file sepa_cmir.c.
| #define DEFAULT_MAXFAILS 20 |
maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)
Definition at line 47 of file sepa_cmir.c.
| #define DEFAULT_MAXFAILSROOT 100 |
maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)
Definition at line 48 of file sepa_cmir.c.
| #define DEFAULT_MAXAGGRS 3 |
maximal number of aggregations for each row per separation round
Definition at line 51 of file sepa_cmir.c.
| #define DEFAULT_MAXAGGRSROOT 6 |
maximal number of aggregations for each row per round in the root node
Definition at line 52 of file sepa_cmir.c.
| #define DEFAULT_MAXSEPACUTS 100 |
maximal number of cmir cuts separated per separation round
Definition at line 53 of file sepa_cmir.c.
| #define DEFAULT_MAXSEPACUTSROOT 500 |
maximal number of cmir cuts separated per separation round in root node
Definition at line 54 of file sepa_cmir.c.
| #define DEFAULT_MAXSLACK 0.0 |
maximal slack of rows to be used in aggregation
Definition at line 55 of file sepa_cmir.c.
| #define DEFAULT_MAXSLACKROOT 0.1 |
maximal slack of rows to be used in aggregation in the root node
Definition at line 56 of file sepa_cmir.c.
| #define DEFAULT_DENSITYSCORE 1e-04 |
weight of row density in the aggregation scoring of the rows
Definition at line 57 of file sepa_cmir.c.
| #define DEFAULT_SLACKSCORE 1e-03 |
weight of slack in the aggregation scoring of the rows
Definition at line 58 of file sepa_cmir.c.
| #define DEFAULT_MAXAGGDENSITY 0.20 |
maximal density of aggregated row
Definition at line 59 of file sepa_cmir.c.
| #define DEFAULT_MAXROWDENSITY 0.05 |
maximal density of row to be used in aggregation
Definition at line 60 of file sepa_cmir.c.
| #define DEFAULT_DENSITYOFFSET 100 |
additional number of variables allowed in row on top of density
Definition at line 61 of file sepa_cmir.c.
| #define DEFAULT_MAXROWFAC 1e+4 |
maximal row aggregation factor
Definition at line 62 of file sepa_cmir.c.
| #define DEFAULT_MAXTESTDELTA -1 |
maximal number of different deltas to try (-1: unlimited)
Definition at line 63 of file sepa_cmir.c.
| #define DEFAULT_MAXCONTS 10 |
maximal number of active continuous variables in aggregated row
Definition at line 64 of file sepa_cmir.c.
| #define DEFAULT_MAXCONTSROOT 10 |
maximal number of active continuous variables in aggregated row in the root
Definition at line 65 of file sepa_cmir.c.
| #define DEFAULT_AGGRTOL 0.1 |
aggregation heuristic: tolerance for bound distances used to select real variable in current aggregated constraint to be eliminated
Definition at line 66 of file sepa_cmir.c.
| #define DEFAULT_TRYNEGSCALING TRUE |
should negative values also be tested in scaling?
Definition at line 69 of file sepa_cmir.c.
| #define DEFAULT_FIXINTEGRALRHS TRUE |
should an additional variable be complemented if f0 = 0?
Definition at line 70 of file sepa_cmir.c.
| #define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 71 of file sepa_cmir.c.
| #define BOUNDSWITCH 0.5 |
Definition at line 73 of file sepa_cmir.c.
Referenced by aggregation().
| #define USEVBDS TRUE |
Definition at line 74 of file sepa_cmir.c.
Referenced by aggregation().
| #define ALLOWLOCAL TRUE |
Definition at line 75 of file sepa_cmir.c.
Referenced by aggregation(), and separateCuts().
| #define MINFRAC 0.05 |
Definition at line 76 of file sepa_cmir.c.
Referenced by aggregation().
| #define MAXFRAC 0.999 |
Definition at line 77 of file sepa_cmir.c.
Referenced by aggregation().
| #define MAKECONTINTEGRAL FALSE |
Definition at line 78 of file sepa_cmir.c.
Referenced by addCut().
| #define IMPLINTSARECONT |
Definition at line 79 of file sepa_cmir.c.
| #define MAXAGGRLEN | ( | nvars | ) | (0.1*(nvars)+1000) |
maximal length of base inequality
Definition at line 81 of file sepa_cmir.c.
Referenced by aggregation().
|
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 |
| 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 |
Definition at line 129 of file sepa_cmir.c.
References addCut(), NULL, SCIP_OKAY, SCIP_Real, and SCIPisZero().
Referenced by addCut().
|
static |
adds given cut to LP if violated
| scip | SCIP data structure |
| sepa | separator |
| 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? |
| cutremovable | should the cut be removed from the LP due to aging or cleanup? |
| cutrank | rank of the cut |
| cutclassname | name of cut class to use for row names |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to count the number of added cuts |
Definition at line 176 of file sepa_cmir.c.
References FALSE, MAKECONTINTEGRAL, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugMsg, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetVarsData(), SCIPgetVectorEfficacyNorm(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPsnprintf(), SCIPsumepsilon(), storeCutInArrays(), TRUE, and updateNActiveConts().
Referenced by SCIPcutGenerationHeuristicCmir(), and storeCutInArrays().
|
static |
adds delta to active continuous variables counter
| scip | SCIP data structure |
| varsolvals | LP solution value of all variables in LP |
| bestcontlbs | best lower (variable or standard) bounds of continuous variables |
| bestcontubs | best upper (variable or standard) bounds of continuous variables |
| nintvars | number of integer variables |
| var | continuous variable |
| delta | delta value of counters |
| nactiveconts | pointer to count number of active continuous variables |
Definition at line 285 of file sepa_cmir.c.
References decreaseRowScore(), NULL, SCIP_Real, SCIPisInfinity(), SCIPisLT(), SCIPvarGetProbindex(), and SCIPvarIsIntegral().
Referenced by addCut(), and aggregation().
|
static |
decreases the score of a row in order to not aggregate it again too soon
| scip | SCIP data structure |
| rowlhsscores | aggregation scores for left hand sides of row |
| rowrhsscores | aggregation scores for right hand sides of row |
| rowidx | index of row to decrease score for |
Definition at line 319 of file sepa_cmir.c.
References NULL, and tryDelta().
Referenced by aggregation(), and updateNActiveConts().
|
static |
calculates the c-MIR cut for the given rowweights and delta value, and updates testeddeltas, bestdelta, and bestefficacy
| scip | SCIP data structure |
| sol | the solution that should be separated, or NULL for LP solution |
| nvars | number of problem variables |
| rowweights | weight of rows in aggregated row |
| maxweight | largest magnitude of weights; set to -1 if sparsity information is unknown |
| weightinds | sparsity pattern of weights; size nrowinds; NULL if sparsity info is unknown |
| nweightinds | number of nonzeros in weights; -1 if rowinds is NULL |
| rowlensum | total number of non-zeros in used rows (row associated with nonzero weight coefficient); -1 if unknown |
| cutcoefs | array to store the cut coefficients |
| mksetcoefs | array to store mixed knapsack set coefficients: size nvars; or NULL |
| mksetcoefsvalid | pointer to store whether mixed knapsack set coefficients are valid; or NULL |
| testeddeltas | array with already tested deltas |
| ntesteddeltas | pointer to the number of elements in testeddeltas |
| delta | delta value to scale mixed knapsack equation with |
| boundswitch | fraction of domain up to which lower bound is used in transformation |
| usevbds | should variable bounds be used in bound transformation? |
| allowlocal | should local information allowed to be used, resulting in a local cut? |
| fixintegralrhs | should complementation tried to be adjusted such that rhs gets fractional? |
| maxmksetcoefs | maximal number of nonzeros allowed in aggregated base inequality |
| maxweightrange | maximal valid range max(|weights|)/min(|weights|) of row weights |
| minfrac | minimal fractionality of rhs to produce MIR cut for |
| maxfrac | maximal fractionality of rhs to produce MIR cut for |
| bestdelta | pointer to the currently best delta value |
| bestefficacy | pointer to the currently best efficacy |
Definition at line 339 of file sepa_cmir.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMIR(), SCIPcutGenerationHeuristicCmir(), SCIPdebugMsg, SCIPgetVectorEfficacyNorm(), SCIPisEQ(), SCIPisFeasGT(), and SCIPisFeasZero().
Referenced by decreaseRowScore(), and SCIPcutGenerationHeuristicCmir().
returns whether the variable should be tried to be aggregated out
| var | problem variable |
Definition at line 636 of file sepa_cmir.c.
Referenced by aggregation(), getBounddist(), and SCIPcutGenerationHeuristicCmir().
|
static |
returns the minimal distance of the solution of a continuous variable to its bounds
| scip | SCIP data structure |
| nintvars | number of integer variables in the problem |
| varsolvals | LP solution value of all variables in LP |
| bestcontlbs | best lower (variable or standard) bounds of continuous variables |
| bestcontubs | best upper (variable or standard) bounds of continuous variables |
| var | continuous variable to get bound distance for |
Definition at line 653 of file sepa_cmir.c.
References aggregation(), MIN, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPisGE(), SCIPisLE(), SCIPvarGetLbGlobal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and varIsContinuous().
Referenced by aggregation().
|
static |
aggregates different single mixed integer constraints by taking linear combinations of the rows of the LP
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data |
| sol | the solution that should be separated, or NULL for LP solution |
| varsolvals | LP solution value of all variables in LP |
| bestcontlbs | best lower (variable or standard) bounds of continuous variables |
| bestcontubs | best upper (variable or standard) bounds of continuous variables |
| contvarscorebounds | bounds on the maximal rowlhsscores and rowrhsscores the variable is contained in |
| rowlhsscores | aggregation scores for left hand sides of row |
| rowrhsscores | aggregation scores for right hand sides of row |
| startrow | index of row to start aggregation |
| maxaggrs | maximal number of aggregations |
| maxslack | maximal slack of rows to be used in aggregation |
| maxconts | maximal number of active continuous variables in aggregated row |
| wastried | pointer to store whether the given startrow was actually tried |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to count the number of generated cuts |
Definition at line 692 of file sepa_cmir.c.
References ALLOWLOCAL, BMSclearMemoryArray, BOUNDSWITCH, decreaseRowScore(), FALSE, getBounddist(), MAX, MAXAGGRLEN, MAXFRAC, MIN, MINFRAC, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPcutGenerationHeuristicCmir(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNImplVars(), SCIPgetRowSolActivity(), SCIPgetVarsData(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisGT(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsModifiable(), SCIPsortedvecInsertDownRealInt(), SCIPsortedvecInsertInt(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarIsIntegral(), separateCuts(), TRUE, updateNActiveConts(), USEVBDS, and varIsContinuous().
Referenced by getBounddist(), and separateCuts().
|
static |
searches and adds c-MIR cuts that separate the given primal solution
| scip | SCIP data structure |
| sepa | the c-MIR separator |
| sol | the solution that should be separated, or NULL for LP solution |
| result | pointer to store the result |
Definition at line 1226 of file sepa_cmir.c.
References aggregation(), ALLOWLOCAL, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPACOPY(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_SEPARATED, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetLPRowsData(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNSepaRounds(), SCIPgetNVars(), SCIPgetObjNorm(), SCIPgetRowSolActivity(), SCIPgetSolVals(), SCIPgetVarClosestVlb(), SCIPgetVarClosestVub(), SCIPgetVars(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPisStopped(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by aggregation().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 1536 of file sepa_cmir.c.
Referenced by separateCuts().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 1550 of file sepa_cmir.c.
|
static |
LP solution separation method of separator
Definition at line 1568 of file sepa_cmir.c.
|
static |
arbitrary primal solution separation method of separator
Definition at line 1593 of file sepa_cmir.c.