70 #define SEPA_NAME "gmi" 71 #define SEPA_DESC "Gomory Mixed-Integer cuts separator" 72 #define SEPA_PRIORITY -1000 74 #define SEPA_MAXBOUNDDIST 0.0 75 #define SEPA_USESSUBSCIP FALSE 76 #define SEPA_DELAY FALSE 78 #define DEFAULT_MAXROUNDS 5 79 #define DEFAULT_MAXROUNDSROOT 30 80 #define DEFAULT_MAXSEPACUTS -1 81 #define DEFAULT_MAXSEPACUTSROOT -1 82 #define DEFAULT_DYNAMICCUTS TRUE 83 #define DEFAULT_SEPARATEROWS TRUE 86 #define MIN_VIOLATION 0.00 87 #define EPS_COEFF 1e-11 88 #define EPS_RELAX_ABS 1e-11 89 #define EPS_RELAX_REL 1e-13 90 #define MAX_DYN 1.0e+6 91 #define MAX_SUPP_ABS 1000 92 #define MAX_SUPP_REL 0.1 142 assert(scip !=
NULL);
143 assert(cols !=
NULL);
144 assert(densecoefs !=
NULL);
145 assert(sparsecoefs !=
NULL);
146 assert(cutind !=
NULL);
147 assert(cutnz !=
NULL);
148 assert(cutrhs !=
NULL);
153 for( c = 0; c < ncols; ++c )
161 if(
EPSZ(densecoefs[i], sepadata->epscoeff) && !
SCIPisZero(scip, densecoefs[i]) )
163 if( densecoefs[i] > 0.0 )
172 else if( (densecoefs[i] < 0.0) )
182 else if( !
EPSZ(densecoefs[i], sepadata->epscoeff) )
185 sparsecoefs[*cutnz] = densecoefs[i];
192 *cutrhs +=
REALABS(*cutrhs) * sepadata->epsrelaxrel + sepadata->epsrelaxabs;
220 assert(scip !=
NULL);
221 assert(cols !=
NULL);
222 assert(cutcoefs !=
NULL);
223 assert(cutind !=
NULL);
224 assert(cutnz !=
NULL);
225 assert(cutrhs !=
NULL);
226 assert(cutact !=
NULL);
230 if( *cutnz > (ncols)*(sepadata->maxsupprel) + sepadata->maxsuppabs )
232 SCIPdebugMsg(scip,
"Cut too dense (%d > %d).\n", *cutnz, (
int) ((ncols)*(sepadata->maxsupprel) + sepadata->maxsuppabs));
241 for( i = 0; i < *cutnz; ++i )
249 if( maxcoef > mincoef * sepadata->maxdynamism )
251 SCIPdebugMsg(scip,
"Cut too dynamic (%g > %g).\n", maxcoef, mincoef * sepadata->maxdynamism);
256 violation = *cutact - *cutrhs;
260 return (violation >= sepadata->minviolation) ?
TRUE :
FALSE;
297 assert(scip !=
NULL);
298 assert(cols !=
NULL);
299 assert(rows !=
NULL);
300 assert(binvrow !=
NULL);
301 assert(binvarow !=
NULL);
302 assert(cutcoefs !=
NULL);
303 assert(cutind !=
NULL);
304 assert(cutnz !=
NULL);
305 assert(cutrhs !=
NULL);
306 assert(cutact !=
NULL);
307 assert(workcoefs !=
NULL);
311 ratiof0compl = f0/(1-f0);
321 for( c = 0; c < ncols; ++ c)
324 assert( col !=
NULL );
331 rowelem = binvarow[c];
335 rowelem = -binvarow[c];
355 cutelem = -((1.0 - cutelem) * ratiof0compl);
369 cutelem = rowelem * ratiof0compl;
395 for( c = 0; c < nrows; ++c )
398 assert( row !=
NULL );
417 SCIPdebugMsg(scip,
"Free nonbasic slack variable, this should not happen!\n");
435 cutelem = -((1.0 - cutelem) * ratiof0compl);
448 cutelem = rowelem * ratiof0compl;
471 assert(
SCIPisLE(scip, rlhs, rrhs) );
479 rhsslack = rrhs - act;
510 success =
modifyAndPackCut(scip, sepadata, ncols, cols, workcoefs, cutcoefs, cutind, cutnz, cutrhs);
513 success =
checkNumerics(scip, sepadata, ncols, cols, cutcoefs, cutind, cutnz, cutrhs, cutact);
514 SCIPdebugMsg(scip,
"checkNumerics returned: %u.\n", success);
517 SCIPdebugMsg(scip,
"modifyAndPackCut was not successful.\n");
532 assert(sepa !=
NULL);
548 assert(sepa !=
NULL);
553 assert(sepadata !=
NULL);
590 assert(sepa !=
NULL);
593 assert(result !=
NULL);
614 assert(sepadata !=
NULL);
620 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
631 if( ncols == 0 || nrows == 0 )
649 maxsepacuts = sepadata->maxsepacutsroot;
651 maxsepacuts = sepadata->maxsepacuts;
653 if( maxsepacuts == -1 )
654 maxsepacuts = INT_MAX;
672 assert(cols[c] !=
NULL);
686 else if( sepadata->separaterows )
689 assert(0 <= -c-1 && -c-1 < nrows);
725 cutislocal = (depth != 0) ?
TRUE :
FALSE;
728 success =
getGMIFromRow(
scip, sepadata, ncols, nrows, cols, rows, binvrow, binvarow, primsol, cutcoefs, cutind, &cutnz, &cutrhs, &cutact, workcoefs);
730 SCIPdebugMsg(
scip,
" -> success = %u: %g <= %g\n", success, cutact, cutrhs);
750 for( j = 0; j < cutnz; ++j )
758 SCIPdebugMsg(
scip,
" -> gomory cut detected infeasibility with cut 0 <= %f\n", cutrhs);
773 SCIPdebugMsg(
scip,
" -> found gomory cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
833 sepadata->lastncutsfound = 0;
839 assert(sepa !=
NULL);
847 "separating/gmi/maxrounds",
848 "maximal number of gmi separation rounds per node (-1: unlimited)",
851 "separating/gmi/maxroundsroot",
852 "maximal number of gmi separation rounds in the root node (-1: unlimited)",
855 "separating/gmi/maxsepacuts",
856 "maximal number of gmi cuts separated per separation round (-1: unlimited)",
859 "separating/gmi/maxsepacutsroot",
860 "maximal number of gmi cuts separated per separation round in the root node (-1: unlimited)",
863 "separating/gmi/dynamiccuts",
864 "should generated cuts be removed from the LP if they are no longer tight?",
867 "separating/gmi/separaterows",
868 "separate rows with integral slack",
871 "separating/gmi/away",
872 "minimal fractionality of a basic variable in order to try GMI cut",
875 "separating/gmi/minviolation",
876 "minimal violation to accept cut",
879 "separating/gmi/epscoeff",
880 "tolerance for zeroing out small coefficients",
883 "separating/gmi/epsrelaxabs",
884 "absolute cut rhs relaxation",
887 "separating/gmi/epsrelaxrel",
888 "relative cut rhs relaxation",
891 "separating/gmi/maxdynamism",
892 "maximal valid range max(|weights|)/min(|weights|) of cut coefficients",
895 "separating/gmi/maxsuppabs",
896 "maximum cut support - absolute value in the formula",
899 "separating/gmi/maxsupprel",
900 "maximum cut support - relative value in the formula",
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
static SCIP_DECL_SEPACOPY(sepaCopyGMI)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
#define DEFAULT_SEPARATEROWS
static SCIP_DECL_SEPAFREE(sepaFreeGMI)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
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 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 SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
#define DEFAULT_MAXSEPACUTSROOT
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
static SCIP_Bool modifyAndPackCut(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *densecoefs, SCIP_Real *sparsecoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
int SCIPgetNCutsFound(SCIP *scip)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
static SCIP_DECL_SEPAEXECLP(sepaExeclpGMI)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPincludeSepaGMI(SCIP *scip)
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_COL ** SCIProwGetCols(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)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
public data structures and miscellaneous methods
#define DEFAULT_MAXROUNDSROOT
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static SCIP_Bool getGMIFromRow(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real rowrhs, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact, SCIP_Real *workcoefs)
Gomory Mixed-Integer Cuts.
static SCIP_Bool checkNumerics(SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact)
#define DEFAULT_DYNAMICCUTS
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXROUNDS
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 SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
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)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIPisStopped(SCIP *scip)
#define SEPA_MAXBOUNDDIST
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
#define DEFAULT_MAXSEPACUTS
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)