70#define PROP_NAME "rootredcost"
71#define PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound"
72#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
73#define PROP_PRIORITY +10000000
75#define PROP_DELAY FALSE
83#define DEFAULT_ONLYBINARY FALSE
84#define DEFAULT_FORCE FALSE
103 int glbfirstnonfixed;
121 propdata->redcostvars =
NULL;
123 propdata->nredcostvars = 0;
124 propdata->nredcostbinvars = 0;
125 propdata->glbfirstnonfixed = 0;
126 propdata->initialized =
FALSE;
153 else if( key1 > key2 )
191 for( v = 0; v <
nvars; ++v )
215 for( v = 0; v < propdata->nredcostvars; ++v )
246 if( propdata->initialized )
261 nredcostvars += nredcostbinvars;
264 if( nredcostvars > 0 )
271 SCIPdebugMsg(
scip,
"Store non-zero root reduced cost variables at address <%p>.\n", (
void*)propdata->redcostvars);
273 for( v = 0; v <
nvars; ++v )
290 propdata->redcostvars[k] = propdata->redcostvars[nredcostbinvars];
293 propdata->redcostvars[nredcostbinvars] =
var;
297 propdata->redcostvars[k] =
var;
305 if( k == nredcostvars )
312 SCIPsortDownPtr((
void**)propdata->redcostvars, varCompRedcost, nredcostbinvars);
314 assert(k == nredcostvars);
316 SCIPdebugMsg(
scip,
"variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars);
319 propdata->nredcostvars = nredcostvars;
320 propdata->nredcostbinvars = nredcostbinvars;
321 propdata->glbfirstnonfixed = 0;
323 propdata->initialized =
TRUE;
357 newbd =
rootsol + (cutoffbound - rootlpobjval) / rootredcost;
396 redcostvars = propdata->redcostvars;
408 for( v = 1; v < propdata->nredcostbinvars; ++v )
409 assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1);
412 for( v = 0; v < propdata->glbfirstnonfixed; ++v )
416 var = redcostvars[v];
424 for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v )
429 var = redcostvars[v];
447 SCIPdebugMsg(
scip,
"globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
472 SCIPdebugMsg(
scip,
"interrupt propagation for binary variables after %d from %d binary variables\n",
473 v, propdata->nredcostbinvars);
477 SCIPdebugMsg(
scip,
"detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
486 propdata->glbfirstnonfixed = v;
488#ifdef SCIP_DISABLED_CODE
495 for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v )
500 var = redcostvars[v];
631 assert(cutoffbound <= propdata->lastcutoffbound);
633 if( cutoffbound == propdata->lastcutoffbound )
637 redcostvars = propdata->redcostvars;
638 nredcostvars = propdata->nredcostvars;
641 if( nredcostvars == 0 )
647 propdata->lastcutoffbound = cutoffbound;
660 if( !propdata->onlybinary )
663 for( v = propdata->nredcostbinvars; v < nredcostvars && !
cutoff; ++v )
668 var = redcostvars[v];
686 else if( nchgbds > 0 )
710 propExecRootredcost, propdata) );
721 "should only binary variables be propagated?",
725 "should the propagator be forced even if active pricer are present?",
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(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 SCIPincludePropRootredcost(SCIP *scip)
SCIP_Real SCIPgetLPRootObjval(SCIP *scip)
SCIP_Bool SCIPisLPDualReliable(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop,)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
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)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
assert(minobj< SCIPgetCutoffbound(scip))
#define DEFAULT_ONLYBINARY
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)
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
static void propdataReset(SCIP_PROPDATA *propdata)
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
static int countNonZeroRootRedcostVars(SCIP *scip, SCIP_VAR **vars, int nvars)
reduced cost strengthening using root node reduced costs and the cutoff bound
public methods for message output
methods for sorting joint arrays of various types
public methods for propagators
public methods for problem variables
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 variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_PROPCOPY(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXITSOL(x)
struct SCIP_Prop SCIP_PROP
struct SCIP_PropData SCIP_PROPDATA
#define SCIP_DECL_PROPEXEC(x)
enum SCIP_Retcode SCIP_RETCODE