56 #define SEPA_NAME "gomory" 57 #define SEPA_DESC "Gomory MIR cuts separator" 58 #define SEPA_PRIORITY -1000 60 #define SEPA_MAXBOUNDDIST 0.0 61 #define SEPA_USESSUBSCIP FALSE 62 #define SEPA_DELAY FALSE 64 #define DEFAULT_MAXROUNDS 5 65 #define DEFAULT_MAXROUNDSROOT 10 66 #define DEFAULT_MAXSEPACUTS 50 67 #define DEFAULT_MAXSEPACUTSROOT 200 68 #define DEFAULT_MAXRANK 3 69 #define DEFAULT_MAXRANKINTEGRAL -1 70 #define DEFAULT_DYNAMICCUTS TRUE 71 #define DEFAULT_MAXWEIGHTRANGE 1e+04 72 #define DEFAULT_AWAY 0.01 73 #define DEFAULT_MAKEINTEGRAL TRUE 74 #define DEFAULT_FORCECUTS TRUE 75 #define DEFAULT_SEPARATEROWS TRUE 76 #define DEFAULT_DELAYEDCUTS TRUE 77 #define DEFAULT_SIDETYPEBASIS FALSE 78 #define DEFAULT_RANDSEED 53 80 #define BOUNDSWITCH 0.9999 82 #define ALLOWLOCAL TRUE 83 #define FIXINTEGRALRHS FALSE 84 #define MAKECONTINTEGRAL FALSE 86 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 124 madeintegral =
FALSE;
127 if( sepadata->makeintegral )
133 if( !madeintegral && !sepadata->forcecuts )
143 if( madeintegral && sepadata->maxrankintegral != -1 && (
SCIProwGetRank(cut) > sepadata->maxrankintegral) )
147 if( !madeintegral && (sepadata->maxrank != -1) && (
SCIProwGetRank(cut) > sepadata->maxrank) )
165 assert(sepa !=
NULL);
185 assert(sepadata !=
NULL);
214 int* sidetypes =
NULL;
229 assert(sepa !=
NULL);
232 assert(result !=
NULL);
237 assert(sepadata !=
NULL);
242 minfrac = sepadata->away;
243 maxfrac = 1.0 - sepadata->away;
250 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
251 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
272 if( ncols == 0 || nrows == 0 )
276 if( ncols >= 50*nrows )
279 if( ncols >= 5*nrows )
286 sepadata->lastncutsfound = ncutsfound;
303 else if( depth <= maxdepth/4 )
308 else if( depth <= maxdepth/2 )
324 if ( sepadata->sidetypebasis )
337 maxsepacuts = sepadata->maxsepacutsroot;
339 maxsepacuts = sepadata->maxsepacuts;
341 SCIPdebugMsg(
scip,
"searching gomory cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT
", maxscale=%g, maxcuts=%d\n",
342 ncols, nrows, maxdnom, maxscale, maxsepacuts);
348 for( i = 0; i < nrows && naddedcuts < maxsepacuts && !
SCIPisStopped(
scip) && !cutoff; ++i )
374 else if( sepadata->separaterows )
378 assert(0 <= -c-1 && -c-1 < nrows);
405 if ( sepadata->sidetypebasis )
409 assert( sidetypes !=
NULL );
410 for (k = 0; k < nrows; ++k)
416 assert( row !=
NULL );
447 if( inds !=
NULL && ninds > -1 )
451 (
int)
MAXAGGRLEN(nvars), sepadata->maxweightrange, minfrac, maxfrac, binvrow, -1.0, inds, ninds, -1,
452 sidetypes, 1.0,
NULL,
NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
458 (
int)
MAXAGGRLEN(nvars), sepadata->maxweightrange, minfrac, maxfrac, binvrow, -1.0,
NULL, -1, -1,
459 sidetypes, 1.0,
NULL,
NULL, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
485 cutislocal,
FALSE, sepadata->dynamiccuts) );
494 for( v = 0; v < nvars; ++v )
505 SCIPdebugMsg(
scip,
" -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
525 assert(success ==
TRUE);
537 SCIPdebugMsg(
scip,
" -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
549 if( sepadata->delayedcuts )
576 if ( sepadata->sidetypebasis )
585 SCIPdebugMsg(
scip,
"end searching gomory cuts: found %d cuts\n", naddedcuts);
592 else if ( naddedcuts > 0 )
615 sepadata->lastncutsfound = 0;
624 sepaExeclpGomory,
NULL,
627 assert(sepa !=
NULL);
635 "separating/gomory/maxrounds",
636 "maximal number of gomory separation rounds per node (-1: unlimited)",
639 "separating/gomory/maxroundsroot",
640 "maximal number of gomory separation rounds in the root node (-1: unlimited)",
643 "separating/gomory/maxsepacuts",
644 "maximal number of gomory cuts separated per separation round",
647 "separating/gomory/maxsepacutsroot",
648 "maximal number of gomory cuts separated per separation round in the root node",
651 "separating/gomory/maxrank",
652 "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
655 "separating/gomory/maxrankintegral",
656 "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
659 "separating/gomory/away",
660 "minimal integrality violation of a basis variable in order to try Gomory cut",
663 "separating/gomory/maxweightrange",
664 "maximal valid range max(|weights|)/min(|weights|) of row weights",
667 "separating/gomory/dynamiccuts",
668 "should generated cuts be removed from the LP if they are no longer tight?",
671 "separating/gomory/makeintegral",
672 "try to scale cuts to integral coefficients",
675 "separating/gomory/forcecuts",
676 "if conversion to integral coefficients failed still consider the cut",
679 "separating/gomory/separaterows",
680 "separate rows with integral slack",
683 "separating/gomory/delayedcuts",
684 "should cuts be added to the delayed cut pool?",
687 "separating/gomory/sidetypebasis",
688 "choose side types of row (lhs/rhs) based on basis information?",
#define DEFAULT_MAXSEPACUTSROOT
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
static SCIP_RETCODE evaluateCutNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
enum SCIP_BaseStat SCIP_BASESTAT
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
#define DEFAULT_MAXROUNDSROOT
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
int SCIPgetMaxDepth(SCIP *scip)
#define DEFAULT_DELAYEDCUTS
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
#define DEFAULT_MAXROUNDS
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
#define SEPA_MAXBOUNDDIST
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
#define DEFAULT_MAKEINTEGRAL
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, SCIP_Real maxweight, int *weightinds, int nweightinds, int rowlensum, int *sidetypes, SCIP_Real scale, SCIP_Real *mksetcoefs, SCIP_Bool *mksetcoefsvalid, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#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)
#define DEFAULT_MAXRANKINTEGRAL
static SCIP_DECL_SEPAEXECLP(sepaExeclpGomory)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXSEPACUTS
int SCIPgetNCutsFound(SCIP *scip)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define DEFAULT_FORCECUTS
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
#define DEFAULT_SEPARATEROWS
#define DEFAULT_SIDETYPEBASIS
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)
#define DEFAULT_DYNAMICCUTS
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)
int SCIPgetDepth(SCIP *scip)
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
public methods for LP management
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)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
#define DEFAULT_MAXWEIGHTRANGE
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define MAXAGGRLEN(nvars)
int SCIProwGetRank(SCIP_ROW *row)
static SCIP_DECL_SEPACOPY(sepaCopyGomory)
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)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
static SCIP_DECL_SEPAFREE(sepaFreeGomory)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
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)