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 129 propdata->maxredcost =
MAX(propdata->maxredcost, -rootredcost);
131 if( rootlpobjval - rootredcost > cutoffbound )
150 propdata->maxredcost =
MAX(propdata->maxredcost, rootredcost);
152 if( rootlpobjval + rootredcost > cutoffbound )
165 if( !propdata->usefullimplics )
206 propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
245 if( redcost > requiredredcost )
247 SCIPdebugMsg(scip,
"variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
266 if( -redcost > requiredredcost )
268 SCIPdebugMsg(scip,
"variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
297 if( propdata->useimplics && propdata->usefullimplics )
315 if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
317 SCIPdebugMsg(scip,
"variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
322 else if( -lbredcost > requiredredcost )
324 SCIPdebugMsg(scip,
"variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
330 else if( ubredcost > requiredredcost )
332 SCIPdebugMsg(scip,
"variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
340 propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
388 newub = (cutoffbound - lpobjval) / redcost + oldlb;
398 strengthen = (newub < oldub - 0.5);
406 SCIPdebugMsg(scip,
"redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
407 SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
445 newlb = (cutoffbound - lpobjval) / redcost + oldub;
455 strengthen = (newlb > oldlb + 0.5);
464 SCIPdebugMsg(scip,
"redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
465 SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
501 assert(scip != NULL);
502 assert(prop != NULL);
520 assert(propdata != NULL);
537 assert(propdata != NULL);
539 propdata->usefullimplics =
FALSE;
540 propdata->maxredcost = 0.0;
612 assert(propdata != NULL);
626 propbinvars = (
SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
637 requiredredcost = cutoffbound - lpobjval;
639 SCIPdebugMsg(scip,
"lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
640 lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
643 for( c = 0; c < ncols && !cutoff; ++c )
677 SCIPdebugMsg(scip,
"node %" SCIP_LONGINT_FORMAT
": detected cutoff\n",
680 else if( nchgbds > 0 )
684 SCIPdebugMsg(scip,
"node %" SCIP_LONGINT_FORMAT
": %d bound changes (max redcost <%g>)\n",
711 propExecRedcost, propdata) );
713 assert(prop != NULL);
723 "should reduced cost fixing be also applied to continuous variables?",
727 "should implications be used to strength the reduced cost for binary variables?",
731 "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 SCIPisLPDualReliable(SCIP *scip)
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)