reduced cost strengthening using root node reduced costs and the cutoff bound
This propagator uses the root reduced cost to (globally) propagate against the cutoff bound. The propagator checks if the variables with non-zero root reduced cost can exceed the cutoff bound. If this is the case the corresponding bound can be tightened.
The propagate is performed during the search any time a new cutoff bound (primal solution) is found.
Definition in file prop_rootredcost.c.
Go to the source code of this file.
Macros | |
Propagator properties | |
#define | PROP_NAME "rootredcost" |
#define | PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound" |
#define | PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
#define | PROP_PRIORITY +10000000 |
#define | PROP_FREQ 1 |
#define | PROP_DELAY FALSE |
Default parameter values | |
#define | DEFAULT_ONLYBINARY FALSE |
#define | DEFAULT_FORCE FALSE |
Functions | |
Local methods | |
static void | propdataReset (SCIP *scip, SCIP_PROPDATA *propdata) |
static | SCIP_DECL_SORTPTRCOMP (varCompRedcost) |
static SCIP_RETCODE | propdataCreate (SCIP *scip, SCIP_PROPDATA **propdata) |
static int | countNonZeroRootRedcostVars (SCIP *scip, SCIP_VAR **vars, int nvars) |
static SCIP_RETCODE | propdataExit (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | propdataInit (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | propagateRootRedcostVar (SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Bool *infeasible, SCIP_Bool *tightened) |
static SCIP_RETCODE | propagateBinaryBestRootRedcost (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, int *nchgbds, SCIP_Bool *cutoff) |
Callback methods of propagator | |
static | SCIP_DECL_PROPCOPY (propCopyRootredcost) |
static | SCIP_DECL_PROPFREE (propFreeRootredcost) |
static | SCIP_DECL_PROPEXITSOL (propExitsolRootredcost) |
static | SCIP_DECL_PROPEXEC (propExecRootredcost) |
Interface methods | |
SCIP_RETCODE | SCIPincludePropRootredcost (SCIP *scip) |
#define PROP_NAME "rootredcost" |
Definition at line 45 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
Definition at line 46 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 47 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define PROP_PRIORITY +10000000 |
propagator priority
Definition at line 48 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define PROP_FREQ 1 |
propagator frequency
Definition at line 49 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 50 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define DEFAULT_ONLYBINARY FALSE |
should only binary variables be propagated?
Definition at line 58 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
#define DEFAULT_FORCE FALSE |
should the propagator be forced even if active pricer are present? Note that the reductions are always valid, but installing an upper bound on priced variables may lead to problems in pricing (existing variables at their upper bound may be priced again since they may have negative reduced costs)
Definition at line 59 of file prop_rootredcost.c.
Referenced by SCIPincludePropRootredcost().
|
static |
reset structure memember of propagator data structure
scip | SCIP data structure |
propdata | propagator data to reset |
Definition at line 95 of file prop_rootredcost.c.
References FALSE, SCIP_DECL_SORTPTRCOMP(), and SCIP_INVALID.
Referenced by propdataCreate(), and propdataExit().
|
static |
compare variables with non-zero reduced cost w.r.t. (i) the cutoff bound which would lead to a fixing (ii) variable problem index;
Definition at line 113 of file prop_rootredcost.c.
Referenced by propdataReset().
|
static |
create propagator data structure
scip | SCIP data structure |
propdata | pointer to store the created propagator data |
Definition at line 144 of file prop_rootredcost.c.
References countNonZeroRootRedcostVars(), propdataReset(), SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIPincludePropRootredcost().
counts the number of variables with non-zero root reduced cost
scip | SCIP data structure |
vars | variable array |
nvars | number of variables |
Definition at line 158 of file prop_rootredcost.c.
References propdataExit(), SCIP_Real, SCIPisDualfeasZero(), and SCIPvarGetBestRootRedcost().
Referenced by propdataCreate(), and propdataInit().
|
static |
free propagator data
scip | SCIP data structure |
propdata | propagator data |
Definition at line 186 of file prop_rootredcost.c.
References propdataInit(), propdataReset(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().
Referenced by countNonZeroRootRedcostVars().
|
static |
initializate the propagator
scip | SCIP data structure |
propdata | propagator data |
Definition at line 209 of file prop_rootredcost.c.
References countNonZeroRootRedcostVars(), propagateRootRedcostVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPinfinity(), SCIPisDualfeasZero(), SCIPsortDownPtr(), SCIPvarGetBestRootRedcost(), SCIPvarIsBinary(), and TRUE.
Referenced by propdataExit().
|
static |
propagates the root reduced cost against the cutoff bound for the given variable
scip | SCIP data structure |
var | variable to propagate |
cutoffbound | cutoff bound to use |
infeasible | pointer to store whether the new domain is empty |
tightened | pointer to store if the bound was tightened |
Definition at line 309 of file prop_rootredcost.c.
References FALSE, propagateBinaryBestRootRedcost(), SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPisDualfeasNegative(), SCIPisDualfeasPositive(), SCIPisDualfeasZero(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisLPDualReliable(), SCIPtightenVarLbGlobal(), SCIPtightenVarUbGlobal(), SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by propagateBinaryBestRootRedcost(), and propdataInit().
|
static |
propagate binary variables with non-zero root reduced cost
scip | SCIP data structure |
propdata | propagator data structure |
cutoffbound | cutoff bound to use |
nchgbds | pointer to store the number of bound changes |
cutoff | pointer to store if a cutoff was detected |
Definition at line 359 of file prop_rootredcost.c.
References propagateRootRedcostVar(), SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPCOPY(), SCIP_OKAY, SCIPdebugMsg, SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by propagateRootRedcostVar().
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 506 of file prop_rootredcost.c.
Referenced by propagateBinaryBestRootRedcost().
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 520 of file prop_rootredcost.c.
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 537 of file prop_rootredcost.c.
|
static |
execution method of propagator
Definition at line 552 of file prop_rootredcost.c.