85#define SEPA_NAME "gomory"
86#define SEPA_DESC "separator for Gomory mixed-integer and strong CG cuts from LP tableau rows"
87#define SEPA_PRIORITY -1000
89#define SEPA_MAXBOUNDDIST 1.0
90#define SEPA_USESSUBSCIP FALSE
91#define SEPA_DELAY FALSE
93#define DEFAULT_MAXROUNDS 5
94#define DEFAULT_MAXROUNDSROOT 10
95#define DEFAULT_MAXSEPACUTS 50
96#define DEFAULT_MAXSEPACUTSROOT 200
97#define DEFAULT_MAXRANK -1
98#define DEFAULT_MAXRANKINTEGRAL -1
99#define DEFAULT_DYNAMICCUTS TRUE
100#define DEFAULT_AWAY 0.01
101#define DEFAULT_MAKEINTEGRAL FALSE
102#define DEFAULT_FORCECUTS TRUE
103#define DEFAULT_SEPARATEROWS TRUE
104#define DEFAULT_DELAYEDCUTS FALSE
105#define DEFAULT_SIDETYPEBASIS TRUE
106#define DEFAULT_TRYSTRONGCG TRUE
107#define DEFAULT_GENBOTHGOMSCG TRUE
108#define DEFAULT_RANDSEED 53
110#define BOUNDSWITCH 0.9999
111#define POSTPROCESS TRUE
113#define FIXINTEGRALRHS FALSE
114#define MAKECONTINTEGRAL FALSE
116#define MAXAGGRLEN(nvars) (0.1*(nvars)+1000)
167 if( !madeintegral && !
sepadata->forcecuts )
216 SCIPdebugMsg(
scip,
" -> gomory cut detected infeasibility with cut 0 <= %g.\n", cutrhs);
261 for( v = 0; v < cutnnz; ++v )
272 SCIPdebugMsg(
scip,
" -> gomory cut detected infeasibility with cut 0 <= %g.\n", cutrhs);
290 SCIPdebugMsg(
scip,
" -> %s cut <%s>: rhs=%f, eff=%f\n", strongcg ?
"strong-CG" :
"gomory", cutname, cutrhs, cutefficacy);
296 SCIPdebugMsg(
scip,
" -> found %s cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
420 int* colindsproducedcut;
480 separatescg = (
depth % freq == 0);
482 separatescg = (freq ==
depth);
487 separategmi = (
depth % freq == 0);
489 separategmi = (freq ==
depth);
491 if( !separatescg && !separategmi )
500 if( ncols == 0 || nrows == 0 )
544 for(
i = 0;
i < nrows; ++
i )
549 cutefficacies[
i] = 0.0;
553 colindsproducedcut[
i] = -1;
578 if(
frac >= minfrac )
594 maxsepacuts =
sepadata->maxsepacutsroot;
596 maxsepacuts =
sepadata->maxsepacuts;
599 ncols, nrows, maxdnom, maxscale, maxsepacuts);
616 if( basisfrac[
i] == 0.0 )
635 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &strongcgsuccess) );
638 if( strongcgsuccess &&
sepadata->genbothgomscg )
640 assert(allowlocal || !cutislocal);
641 SCIP_CALL(
addCut(
scip,
sepadata,
vars,
c, maxdnom, maxscale, cutnnz, cutinds, cutcoefs, cutefficacy, cutrhs,
642 cutislocal, cutrank,
TRUE, &
cutoff, &naddedcuts) );
645 cutefficacies[
i] = cutefficacy;
646 colindsproducedcut[
i] =
c;
649 strongcgsuccess =
FALSE;
665 minfrac, maxfrac, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
667 if( success || strongcgsuccess )
669 assert(allowlocal || !cutislocal);
671 strongcgsuccess =
FALSE;
673 SCIP_CALL(
addCut(
scip,
sepadata,
vars,
c, maxdnom, maxscale, cutnnz, cutinds, cutcoefs, cutefficacy, cutrhs,
674 cutislocal, cutrank, strongcgsuccess, &
cutoff, &naddedcuts) );
677 cutefficacies[
i] = cutefficacy;
678 colindsproducedcut[
i] =
c;
685 maxcutefficacy = 0.0;
686 for(
i = 0;
i < nrows; ++
i )
688 if( cutefficacies[
i] > maxcutefficacy && colindsproducedcut[
i] >= 0 )
690 maxcutefficacy = cutefficacies[
i];
694 for(
i = 0;
i < nrows; ++
i )
698 assert( maxcutefficacy > 0.0 );
717 SCIPdebugMsg(
scip,
"end searching gomory cuts: found %d cuts\n", naddedcuts);
724 else if ( naddedcuts > 0 )
774 sepaExeclpGomory,
NULL,
801 "separating/gomory/maxrounds",
802 "maximal number of gomory separation rounds per node (-1: unlimited)",
805 "separating/gomory/maxroundsroot",
806 "maximal number of gomory separation rounds in the root node (-1: unlimited)",
809 "separating/gomory/maxsepacuts",
810 "maximal number of gomory cuts separated per separation round",
813 "separating/gomory/maxsepacutsroot",
814 "maximal number of gomory cuts separated per separation round in the root node",
817 "separating/gomory/maxrank",
818 "maximal rank of a gomory cut that could not be scaled to integral coefficients (-1: unlimited)",
821 "separating/gomory/maxrankintegral",
822 "maximal rank of a gomory cut that could be scaled to integral coefficients (-1: unlimited)",
825 "separating/gomory/away",
826 "minimal integrality violation of a basis variable in order to try Gomory cut",
829 "separating/gomory/dynamiccuts",
830 "should generated cuts be removed from the LP if they are no longer tight?",
833 "separating/gomory/makeintegral",
834 "try to scale cuts to integral coefficients",
837 "separating/gomory/forcecuts",
838 "if conversion to integral coefficients failed still consider the cut",
841 "separating/gomory/separaterows",
842 "separate rows with integral slack",
845 "separating/gomory/delayedcuts",
846 "should cuts be added to the delayed cut pool?",
849 "separating/gomory/sidetypebasis",
850 "choose side types of row (lhs/rhs) based on basis information?",
853 "separating/gomory/trystrongcg",
854 "try to generate strengthened Chvatal-Gomory cuts?",
857 "separating/gomory/genbothgomscg",
858 "Should both Gomory and strong CG cuts be generated (otherwise take best)?",
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDS
methods for the aggregation rows
#define SCIP_LONGINT_FORMAT
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_RETCODE SCIPincVarGMISumScore(SCIP *scip, SCIP_VAR *var, SCIP_Real gmieff)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPsetVarLastGMIScore(SCIP *scip, SCIP_VAR *var, SCIP_Real gmieff)
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
public methods for SCIP variables
#define DEFAULT_DYNAMICCUTS
#define SEPA_MAXBOUNDDIST
#define MAXAGGRLEN(nvars)
#define DEFAULT_MAXRANKINTEGRAL
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_MAKEINTEGRAL
#define DEFAULT_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
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 DEFAULT_SEPARATEROWS
#define DEFAULT_GENBOTHGOMSCG
struct SCIP_AggrRow SCIP_AGGRROW
struct SCIP_RandNumGen SCIP_RANDNUMGEN
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)
struct SCIP_Sepa SCIP_SEPA
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS