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 1.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 20 42 #define DEFAULT_MAXSEPACUTSROOT 500 43 #define DEFAULT_DYNAMICCUTS TRUE 44 #define DEFAULT_RANDSEED 54 48 #define BOUNDSWITCH 0.9999 49 #define POSTPROCESS TRUE 54 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 97 assert(sepadata != NULL);
113 assert(sepadata != NULL);
128 assert(sepadata != NULL);
168 assert(sepa != NULL);
170 assert(
scip != NULL);
171 assert(result != NULL);
176 assert(sepadata != NULL);
186 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
187 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
208 if( ncols == 0 || nrows == 0 )
212 if( ncols >= 50*nrows )
214 if( ncols >= 5*nrows )
221 sepadata->lastncutsfound = ncutsfound;
245 for( i = 0; i < nrows; ++i )
262 frac = MIN(frac, 1.0 - frac);
270 assert(0 <= -c-1 && -c-1 < nrows);
275 frac = MIN(frac, 1.0 - frac);
296 maxsepacuts = sepadata->maxsepacutsroot;
298 maxsepacuts = sepadata->maxsepacuts;
300 SCIPdebugMsg(
scip,
"searching strong CG cuts: %d cols, %d rows, maxcuts=%d\n",
301 ncols, nrows, maxsepacuts);
310 if( basisfrac[i] == 0.0 )
334 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
336 assert(allowlocal || !cutislocal);
337 SCIPdebugMsg(
scip,
" -> success=%u: rhs: %g, efficacy: %g\n", success, cutrhs, cutefficacy);
349 SCIPdebugMsg(
scip,
" -> strong CG cut for <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d\n",
368 for( v = 0; v < cutnnz; ++v )
377 SCIPdebugMsg(
scip,
" -> strong CG cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
390 SCIPdebugMsg(
scip,
" -> found strong CG cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
459 sepadata->lastncutsfound = 0;
464 sepaExeclpStrongcg, NULL,
467 assert(sepa != NULL);
477 "separating/strongcg/maxrounds",
478 "maximal number of strong CG separation rounds per node (-1: unlimited)",
481 "separating/strongcg/maxroundsroot",
482 "maximal number of strong CG separation rounds in the root node (-1: unlimited)",
485 "separating/strongcg/maxsepacuts",
486 "maximal number of strong CG cuts separated per separation round",
489 "separating/strongcg/maxsepacutsroot",
490 "maximal number of strong CG cuts separated per separation round in the root node",
493 "separating/strongcg/dynamiccuts",
494 "should generated cuts be removed from the LP if they are no longer tight?",
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
static SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
#define DEFAULT_MAXROUNDS
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
static SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
#define DEFAULT_MAXROUNDSROOT
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
const char * SCIProwGetName(SCIP_ROW *row)
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
SCIP_Real SCIPgetVectorEfficacyNorm(SCIP *scip, SCIP_Real *vals, int nvals)
#define SCIPfreeBlockMemory(scip, ptr)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
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 SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
static SCIP_DECL_SEPAINIT(sepaInitStrongcg)
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)
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
#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)
static SCIP_DECL_SEPAEXIT(sepaExitStrongcg)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, 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)
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
void SCIProwChgRank(SCIP_ROW *row, int rank)
#define DEFAULT_DYNAMICCUTS
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Strong CG Cuts (Letchford & Lodi)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define MAXAGGRLEN(nvars)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
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)