40 #define PROP_NAME "redcost" 41 #define PROP_DESC "reduced cost strengthening propagator" 42 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP 43 #define PROP_PRIORITY +1000000 45 #define PROP_DELAY FALSE 55 #define DEFAULT_CONTINUOUS FALSE 56 #define DEFAULT_USEIMPLICS TRUE 57 #define DEFAULT_FORCE FALSE 124 propdata->maxredcost =
MAX(propdata->maxredcost, -rootredcost);
126 if( rootlpobjval - rootredcost > cutoffbound )
140 propdata->maxredcost =
MAX(propdata->maxredcost, rootredcost);
142 if( rootlpobjval + rootredcost > cutoffbound )
155 if( !propdata->usefullimplics )
184 propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
217 if( redcost > requiredredcost )
219 SCIPdebugMsg(scip,
"variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
232 if( -redcost > requiredredcost )
234 SCIPdebugMsg(scip,
"variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
258 if( propdata->useimplics && propdata->usefullimplics )
268 if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
270 SCIPdebugMsg(scip,
"variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
275 else if( -lbredcost > requiredredcost )
277 SCIPdebugMsg(scip,
"variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
283 else if( ubredcost > requiredredcost )
285 SCIPdebugMsg(scip,
"variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
293 propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
334 newub = (cutoffbound - lpobjval) / redcost + oldlb;
344 strengthen = (newub < oldub - 0.5);
352 SCIPdebugMsg(scip,
"redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
353 SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
384 newlb = (cutoffbound - lpobjval) / redcost + oldub;
394 strengthen = (newlb > oldlb + 0.5);
403 SCIPdebugMsg(scip,
"redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
404 SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
435 assert(scip !=
NULL);
454 assert(propdata !=
NULL);
471 assert(propdata !=
NULL);
473 propdata->usefullimplics =
FALSE;
474 propdata->maxredcost = 0.0;
546 assert(propdata !=
NULL);
560 propbinvars = (
SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
571 requiredredcost = cutoffbound - lpobjval;
573 SCIPdebugMsg(scip,
"lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
574 lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
577 for( c = 0; c < ncols && !cutoff; ++c )
611 SCIPdebugMsg(scip,
"node %" SCIP_LONGINT_FORMAT
": detected cutoff\n",
614 else if( nchgbds > 0 )
618 SCIPdebugMsg(scip,
"node %" SCIP_LONGINT_FORMAT
": %d bound changes (max redcost <%g>)\n",
645 propExecRedcost, propdata) );
647 assert(prop !=
NULL);
657 "should reduced cost fixing be also applied to continuous variables?",
661 "should implications be used to strength the reduced cost for binary variables?",
665 "should the propagator be forced even if active pricer are present?",
static SCIP_RETCODE propagateRedcostBinvar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real requiredredcost, int *nchgbds, SCIP_Bool *cutoff)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPgetColRedcost(SCIP *scip, SCIP_COL *col)
int SCIPgetNPseudoBranchCands(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
#define DEFAULT_CONTINUOUS
int SCIPgetNActivePricers(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_DECL_PROPEXEC(propExecRedcost)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
#define SCIPallocBlockMemory(scip, ptr)
static SCIP_RETCODE propagateRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_COL *col, SCIP_Real lpobjval, SCIP_Real cutoffbound, int *nchgbds)
#define DEFAULT_USEIMPLICS
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_Bool SCIPisLPRelax(SCIP *scip)
static SCIP_DECL_PROPFREE(propFreeRedcost)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
propagator using the LP reduced cost and the cutoff bound
static SCIP_DECL_PROPCOPY(propCopyRedcost)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_Real SCIPcolGetMinPrimsol(SCIP_COL *col)
int SCIPgetNVars(SCIP *scip)
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Real SCIPgetVarImplRedcost(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
static SCIP_RETCODE propagateRootRedcostBinvar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real cutoffbound, int *nchgbds)
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
struct SCIP_PropData SCIP_PROPDATA
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPincludePropRedcost(SCIP *scip)
SCIP_Real SCIPcolGetMaxPrimsol(SCIP_COL *col)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Bool SCIPisExactSolve(SCIP *scip)
static SCIP_DECL_PROPINITSOL(propInitsolRedcost)
SCIP_Bool SCIPallowObjProp(SCIP *scip)
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_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)