31 #define SEPA_NAME "strongcg" 32 #define SEPA_DESC "Strong CG cuts separator (Letchford and Lodi)" 33 #define SEPA_PRIORITY -2000 35 #define SEPA_MAXBOUNDDIST 0.0 36 #define SEPA_USESSUBSCIP FALSE 37 #define SEPA_DELAY FALSE 39 #define DEFAULT_MAXROUNDS 5 40 #define DEFAULT_MAXROUNDSROOT 20 41 #define DEFAULT_MAXSEPACUTS 50 42 #define DEFAULT_MAXSEPACUTSROOT 500 43 #define DEFAULT_DYNAMICCUTS TRUE 44 #define DEFAULT_MAXWEIGHTRANGE 1e+04 46 #define MAKECUTINTEGRAL 48 #define FORCECUTINTEGRAL 51 #define BOUNDSWITCH 0.9999 53 #define ALLOWLOCAL TRUE 54 #define MAKECONTINTEGRAL FALSE 58 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 102 assert(nvars == 0 || cutcoefs !=
NULL);
103 assert(nvars == 0 || varsolvals !=
NULL);
104 assert(cutvars !=
NULL);
105 assert(cutvals !=
NULL);
106 assert(cutlen !=
NULL);
107 assert(cutact !=
NULL);
108 assert(cutnorm !=
NULL);
117 for( v = 0; v < nvars; ++v )
122 act += val * varsolvals[v];
123 cutsqrnorm += SQR(val);
124 cutvars[len] = vars[v];
129 norm = SQRT(cutsqrnorm);
132 for( v = 0; v < nvars; ++v )
137 act += val * varsolvals[v];
139 norm =
MAX(norm, absval);
140 cutvars[len] = vars[v];
147 for( v = 0; v < nvars; ++v )
152 act += val * varsolvals[v];
154 cutvars[len] = vars[v];
161 for( v = 0; v < nvars; ++v )
166 act += val * varsolvals[v];
168 cutvars[len] = vars[v];
196 assert(sepa !=
NULL);
215 assert(sepadata !=
NULL);
258 assert(sepa !=
NULL);
261 assert(result !=
NULL);
266 assert(sepadata !=
NULL);
276 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
277 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
298 if( ncols == 0 || nrows == 0 )
302 if( ncols >= 50*nrows )
304 if( ncols >= 5*nrows )
311 sepadata->lastncutsfound = ncutsfound;
331 else if( depth <= maxdepth/4 )
336 else if( depth <= maxdepth/2 )
361 maxsepacuts = sepadata->maxsepacutsroot;
363 maxsepacuts = sepadata->maxsepacuts;
365 SCIPdebugMsg(
scip,
"searching strong CG cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT
", maxscale=%g, maxcuts=%d\n",
366 ncols, nrows, maxdnom, maxscale, maxsepacuts);
401 assert(0 <= -c-1 && -c-1 < nrows);
429 binvrow, inds, ninds, 1.0, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
442 if( varsolvals ==
NULL )
447 for( v = 0; v < nvars; ++v )
453 assert(varsolvals !=
NULL);
461 cutvars, cutvals, &cutlen, &cutact, &cutnorm) );
463 SCIPdebugMsg(
scip,
" -> strong CG cut for <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d\n",
465 cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm, cutrank);
483 #ifdef MAKECUTINTEGRAL 488 #ifdef MAKEINTCUTINTEGRAL 505 #ifndef FORCECUTINTEGRAL 513 SCIPdebugMsg(
scip,
" -> strong CG cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
523 SCIPdebugMsg(
scip,
" -> found strong CG cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
545 SCIPdebugMsg(
scip,
" -> strong CG cut <%s> couldn't be scaled to integral coefficients: act=%f, rhs=%f, norm=%f, eff=%f\n",
589 sepadata->lastncutsfound = 0;
594 sepaExeclpStrongcg,
NULL,
597 assert(sepa !=
NULL);
605 "separating/strongcg/maxrounds",
606 "maximal number of strong CG separation rounds per node (-1: unlimited)",
609 "separating/strongcg/maxroundsroot",
610 "maximal number of strong CG separation rounds in the root node (-1: unlimited)",
613 "separating/strongcg/maxsepacuts",
614 "maximal number of strong CG cuts separated per separation round",
617 "separating/strongcg/maxsepacutsroot",
618 "maximal number of strong CG cuts separated per separation round in the root node",
621 "separating/strongcg/maxweightrange",
622 "maximal valid range max(|weights|)/min(|weights|) of row weights",
625 "separating/strongcg/dynamiccuts",
626 "should generated cuts be removed from the LP if they are no longer tight?",
static SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
#define DEFAULT_MAXROUNDS
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
static SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, int *inds, int ninds, SCIP_Real scale, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
#define DEFAULT_MAXROUNDSROOT
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIPgetMaxDepth(SCIP *scip)
static SCIP_DECL_SEPAEXECLP(sepaExeclpStrongcg)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_Real SCIPinfinity(SCIP *scip)
#define DEFAULT_MAXSEPACUTSROOT
int SCIPsnprintf(char *t, int len, const char *s,...)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_RETCODE SCIPincludeSepaStrongcg(SCIP *scip)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
int SCIPgetNCutsFound(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SEPA_MAXBOUNDDIST
#define DEFAULT_MAXSEPACUTS
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
#define DEFAULT_MAXWEIGHTRANGE
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
void SCIProwChgRank(SCIP_ROW *row, int rank)
#define DEFAULT_DYNAMICCUTS
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIPisStopped(SCIP *scip)
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)
Strong CG Cuts (Letchford & Lodi)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define MAXAGGRLEN(nvars)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
struct SCIP_SepaData SCIP_SEPADATA
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)