SCIP
Solving Constraint Integer Programs
prop_rootredcost.c File Reference
Detailed Description
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.
#include "scip/prop_rootredcost.h"#include "scip/pub_message.h"#include "scip/pub_misc_sort.h"#include "scip/pub_prop.h"#include "scip/pub_var.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_pricer.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_prop.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include <string.h>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 | |
| SCIP_RETCODE | SCIPincludePropRootredcost (SCIP *scip) |
Local methods | |
| static void | propdataReset (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) |
Macro Definition Documentation
◆ PROP_NAME
| #define PROP_NAME "rootredcost" |
Definition at line 70 of file prop_rootredcost.c.
◆ PROP_DESC
Definition at line 71 of file prop_rootredcost.c.
◆ PROP_TIMING
| #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 72 of file prop_rootredcost.c.
◆ PROP_PRIORITY
| #define PROP_PRIORITY +10000000 |
propagator priority
Definition at line 73 of file prop_rootredcost.c.
◆ PROP_FREQ
| #define PROP_FREQ 1 |
propagator frequency
Definition at line 74 of file prop_rootredcost.c.
◆ PROP_DELAY
| #define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 75 of file prop_rootredcost.c.
◆ DEFAULT_ONLYBINARY
| #define DEFAULT_ONLYBINARY FALSE |
should only binary variables be propagated?
Definition at line 83 of file prop_rootredcost.c.
◆ DEFAULT_FORCE
| #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 87 of file prop_rootredcost.c.
Function Documentation
◆ propdataReset()
|
static |
reset structure memember of propagator data structure
- Parameters
-
propdata propagator data to reset
Definition at line 117 of file prop_rootredcost.c.
References FALSE, NULL, and SCIP_INVALID.
Referenced by propdataCreate(), and propdataExit().
◆ SCIP_DECL_SORTPTRCOMP()
|
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 134 of file prop_rootredcost.c.
References REALABS, SCIP_Real, SCIPvarCompare(), SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), and SCIPvarIsBinary().
◆ propdataCreate()
|
static |
create propagator data structure
- Parameters
-
scip SCIP data structure propdata pointer to store the created propagator data
Definition at line 165 of file prop_rootredcost.c.
References propdataReset(), SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIPincludePropRootredcost().
◆ countNonZeroRootRedcostVars()
counts the number of variables with non-zero root reduced cost
- Parameters
-
scip SCIP data structure vars variable array nvars number of variables
Definition at line 179 of file prop_rootredcost.c.
References NULL, SCIP_Real, SCIPisDualfeasZero(), and SCIPvarGetBestRootRedcost().
Referenced by propdataInit().
◆ propdataExit()
|
static |
free propagator data
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 207 of file prop_rootredcost.c.
References propdataReset(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().
Referenced by SCIP_DECL_PROPEXITSOL().
◆ propdataInit()
|
static |
initializate the propagator
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 230 of file prop_rootredcost.c.
References countNonZeroRootRedcostVars(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPinfinity(), SCIPisDualfeasZero(), SCIPsortDownPtr(), SCIPvarGetBestRootRedcost(), SCIPvarIsBinary(), and TRUE.
Referenced by SCIP_DECL_PROPEXEC().
◆ propagateRootRedcostVar()
|
static |
propagates the root reduced cost against the cutoff bound for the given variable
- Parameters
-
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 330 of file prop_rootredcost.c.
References FALSE, 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 SCIP_DECL_PROPEXEC().
◆ propagateBinaryBestRootRedcost()
|
static |
propagate binary variables with non-zero root reduced cost
- Parameters
-
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 380 of file prop_rootredcost.c.
References NULL, propagateRootRedcostVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_PROPCOPY()
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 528 of file prop_rootredcost.c.
References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropRootredcost(), and SCIPpropGetName().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 542 of file prop_rootredcost.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 559 of file prop_rootredcost.c.
References NULL, propdataExit(), SCIP_CALL, SCIP_OKAY, and SCIPpropGetData().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 574 of file prop_rootredcost.c.
References FALSE, NULL, propagateBinaryBestRootRedcost(), propagateRootRedcostVar(), propdataInit(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPallowWeakDualReds(), SCIPcutoffNode(), SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPRootObjval(), SCIPgetNActivePricers(), SCIPgetNObjVars(), SCIPgetRootNode(), SCIPgetStage(), SCIPinProbing(), SCIPisInfinity(), and SCIPpropGetData().