84#define SEPA_NAME "gomory"
85#define SEPA_DESC "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows"
86#define SEPA_PRIORITY -1000
88#define SEPA_MAXBOUNDDIST 1.0
89#define SEPA_USESSUBSCIP FALSE
90#define SEPA_DELAY FALSE
92#define DEFAULT_MAXROUNDS 5
93#define DEFAULT_MAXROUNDSROOT 10
94#define DEFAULT_MAXSEPACUTS 50
95#define DEFAULT_MAXSEPACUTSROOT 200
96#define DEFAULT_MAXRANK -1
97#define DEFAULT_MAXRANKINTEGRAL -1
98#define DEFAULT_DYNAMICCUTS TRUE
99#define DEFAULT_AWAY 0.01
100#define DEFAULT_MAKEINTEGRAL FALSE
101#define DEFAULT_FORCECUTS TRUE
102#define DEFAULT_SEPARATEROWS TRUE
103#define DEFAULT_DELAYEDCUTS FALSE
104#define DEFAULT_SIDETYPEBASIS TRUE
105#define DEFAULT_TRYSTRONGCG TRUE
106#define DEFAULT_GENBOTHGOMSCG TRUE
107#define DEFAULT_RANDSEED 53
109#define BOUNDSWITCH 0.9999
110#define POSTPROCESS TRUE
112#define FIXINTEGRALRHS FALSE
113#define MAKECONTINTEGRAL FALSE
115#define MAXAGGRLEN(nvars) (0.1*(nvars)+1000)
132 SCIP_Bool dynamiccuts;
133 SCIP_Bool makeintegral;
135 SCIP_Bool separaterows;
136 SCIP_Bool delayedcuts;
137 SCIP_Bool sidetypebasis;
138 SCIP_Bool trystrongcg;
139 SCIP_Bool genbothgomscg;
260 for( v = 0; v <
cutnnz; ++v )
295 SCIPdebugMsg(
scip,
" -> found %s cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
494 if( ncols == 0 || nrows == 0 )
536 for(
i = 0;
i < nrows; ++
i )
538 SCIP_Real
frac = 0.0;
585 maxsepacuts =
sepadata->maxsepacutsroot;
587 maxsepacuts =
sepadata->maxsepacuts;
633 SCIP_CALL(
addCut(
scip,
sepadata,
vars,
c,
maxdnom,
maxscale,
cutnnz,
cutinds,
cutcoefs,
cutefficacy,
cutrhs,
652 minfrac,
maxfrac, 1.0, aggrrow,
cutcoefs, &
cutrhs,
cutinds, &
cutnnz, &
cutefficacy, &
cutrank, &
cutislocal, &
success) );
660 SCIP_CALL(
addCut(
scip,
sepadata,
vars,
c,
maxdnom,
maxscale,
cutnnz,
cutinds,
cutcoefs,
cutefficacy,
cutrhs,
760 "separating/gomory/maxrounds",
761 "maximal number of gomory separation rounds per node (-1: unlimited)",
764 "separating/gomory/maxroundsroot",
765 "maximal number of gomory separation rounds in the root node (-1: unlimited)",
768 "separating/gomory/maxsepacuts",
769 "maximal number of gomory cuts separated per separation round",
772 "separating/gomory/maxsepacutsroot",
773 "maximal number of gomory cuts separated per separation round in the root node",
776 "separating/gomory/maxrank",
777 "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
780 "separating/gomory/maxrankintegral",
781 "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
784 "separating/gomory/away",
785 "minimal integrality violation of a basis variable in order to try Gomory cut",
788 "separating/gomory/dynamiccuts",
789 "should generated cuts be removed from the LP if they are no longer tight?",
792 "separating/gomory/makeintegral",
793 "try to scale cuts to integral coefficients",
796 "separating/gomory/forcecuts",
797 "if conversion to integral coefficients failed still consider the cut",
800 "separating/gomory/separaterows",
801 "separate rows with integral slack",
804 "separating/gomory/delayedcuts",
805 "should cuts be added to the delayed cut pool?",
808 "separating/gomory/sidetypebasis",
809 "choose side types of row (lhs/rhs) based on basis information?",
812 "separating/gomory/trystrongcg",
813 "try to generate strengthened Chvatal-Gomory cuts?",
816 "separating/gomory/genbothgomscg",
817 "Should both Gomory and strong CG cuts be generated (otherwise take best)?",
methods for the aggregation rows
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
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_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)
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)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
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)
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
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_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, 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)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
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_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(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)
int SCIProwGetRank(SCIP_ROW *row)
void SCIProwChgRank(SCIP_ROW *row, int rank)
int SCIPgetRowNumIntCols(SCIP *scip, 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)
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPgetNCutsFound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
SCIP_RETCODE SCIPincludeSepaGomory(SCIP *scip)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for separator plugins
public methods for querying solving statistics
public methods for the branch-and-bound tree
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR **vars, int c, SCIP_Longint maxdnom, SCIP_Real maxscale, int cutnnz, int *cutinds, SCIP_Real *cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_Bool strongcg, SCIP_Bool *cutoff, int *naddedcuts)
#define DEFAULT_TRYSTRONGCG
#define DEFAULT_DYNAMICCUTS
#define DEFAULT_MAKEINTEGRAL
#define DEFAULT_MAXRANKINTEGRAL
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
#define DEFAULT_MAXSEPACUTSROOT
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE evaluateCutNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW *cut, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool *useful)
#define DEFAULT_FORCECUTS
#define MAXAGGRLEN(nvars)
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXROUNDS
#define DEFAULT_SEPARATEROWS
#define DEFAULT_GENBOTHGOMSCG
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXIT(x)
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS