45 #define PROP_NAME "rootredcost" 46 #define PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound" 47 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP 48 #define PROP_PRIORITY +10000000 50 #define PROP_DELAY FALSE 58 #define DEFAULT_ONLYBINARY FALSE 59 #define DEFAULT_FORCE FALSE 97 propdata->redcostvars =
NULL;
99 propdata->nredcostvars = 0;
100 propdata->nredcostbinvars = 0;
101 propdata->glbfirstnonfixed = 0;
102 propdata->initialized =
FALSE;
129 else if( key1 > key2 )
167 for( v = 0; v < nvars; ++v )
171 assert(vars[v] !=
NULL);
191 for( v = 0; v < propdata->nredcostvars; ++v )
218 assert(scip !=
NULL);
219 assert(propdata !=
NULL);
222 if( propdata->initialized )
232 SCIPdebugMsg(scip,
"There are %d (poor) binary variables with non-zero root reduced cost <%s>.\n", nredcostbinvars,
SCIPgetProbName(scip));
237 nredcostvars += nredcostbinvars;
240 if( nredcostvars > 0 )
247 SCIPdebugMsg(scip,
"Store non-zero root reduced cost variables at address <%p>.\n", (
void*)propdata->redcostvars);
249 for( v = 0; v < nvars; ++v )
260 assert(k < nredcostvars);
266 propdata->redcostvars[k] = propdata->redcostvars[nredcostbinvars];
269 propdata->redcostvars[nredcostbinvars] = var;
273 propdata->redcostvars[k] = var;
281 if( k == nredcostvars )
288 SCIPsortDownPtr((
void**)propdata->redcostvars, varCompRedcost, nredcostbinvars);
290 assert(k == nredcostvars);
292 SCIPdebugMsg(scip,
"variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars);
295 propdata->nredcostvars = nredcostvars;
296 propdata->nredcostbinvars = nredcostbinvars;
297 propdata->glbfirstnonfixed = 0;
299 propdata->initialized =
TRUE;
327 newbd = rootsol + (cutoffbound - rootlpobjval) / rootredcost;
366 redcostvars = propdata->redcostvars;
367 assert(redcostvars !=
NULL);
378 for( v = 1; v < propdata->nredcostbinvars; ++v )
379 assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1);
382 for( v = 0; v < propdata->glbfirstnonfixed; ++v )
386 var = redcostvars[v];
394 for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v )
399 var = redcostvars[v];
417 SCIPdebugMsg(scip,
"globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
442 SCIPdebugMsg(scip,
"interrupt propagation for binary variables after %d from %d binary variables\n",
443 v, propdata->nredcostbinvars);
447 SCIPdebugMsg(scip,
"detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
456 propdata->glbfirstnonfixed = v;
464 for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v )
469 var = redcostvars[v];
499 assert(scip !=
NULL);
517 assert(propdata !=
NULL);
518 assert(propdata->redcostvars ==
NULL);
533 assert(propdata !=
NULL);
585 assert(propdata !=
NULL);
600 assert(cutoffbound <= propdata->lastcutoffbound);
602 if( cutoffbound == propdata->lastcutoffbound )
606 redcostvars = propdata->redcostvars;
607 nredcostvars = propdata->nredcostvars;
610 if( nredcostvars == 0 )
616 propdata->lastcutoffbound = cutoffbound;
618 SCIPdebugMsg(scip,
"searching for root reduced cost fixings\n");
619 SCIPdebugMsg(scip,
"-> cutoffbound <%g>\n", cutoffbound);
620 SCIPdebugMsg(scip,
"-> LP objective value <%g>\n", lpobjval);
629 if( !propdata->onlybinary )
632 for( v = propdata->nredcostbinvars; v < nredcostvars && !cutoff; ++v )
637 var = redcostvars[v];
655 else if( nchgbds > 0 )
658 SCIPdebugMsg(scip,
"tightened %d variable domains (%u cutoff)\n", nchgbds, cutoff);
683 propExecRootredcost, propdata) );
685 assert(prop !=
NULL);
694 "should only binary variables be propagated?",
698 "should the propagator be forced even if active pricer are present?",
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static int countNonZeroRootRedcostVars(SCIP *scip, SCIP_VAR **vars, int nvars)
reduced cost strengthening using root node reduced costs and the cutoff bound
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_ONLYBINARY
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
SCIP_RETCODE SCIPincludePropRootredcost(SCIP *scip)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_DECL_PROPCOPY(propCopyRootredcost)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE propagateBinaryBestRootRedcost(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, int *nchgbds, SCIP_Bool *cutoff)
static SCIP_RETCODE propagateRootRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
int SCIPgetDepth(SCIP *scip)
static SCIP_DECL_SORTPTRCOMP(varCompRedcost)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
int SCIPgetNObjVars(SCIP *scip)
static SCIP_DECL_PROPFREE(propFreeRootredcost)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
int SCIPgetNBinVars(SCIP *scip)
static void propdataReset(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPinProbing(SCIP *scip)
const char * SCIPpropGetName(SCIP_PROP *prop)
int SCIPgetNVars(SCIP *scip)
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
static SCIP_DECL_PROPEXEC(propExecRootredcost)
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
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)
SCIP_Real SCIPgetLPRootObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
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)