Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

reduced cost strengthening using root node reduced costs and the cutoff bound

Author
Tobias Achterberg
Stefan Heinz

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

#define PROP_DESC   "reduced cost strengthening using root node reduced costs and the cutoff bound"

Definition at line 71 of file prop_rootredcost.c.

◆ PROP_TIMING

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 void propdataReset ( SCIP_PROPDATA propdata)
static

reset structure memember of propagator data structure

Parameters
propdatapropagator 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 SCIP_DECL_SORTPTRCOMP ( varCompRedcost  )
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 SCIP_RETCODE propdataCreate ( SCIP scip,
SCIP_PROPDATA **  propdata 
)
static

create propagator data structure

Parameters
scipSCIP data structure
propdatapointer 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()

static int countNonZeroRootRedcostVars ( SCIP scip,
SCIP_VAR **  vars,
int  nvars 
)
static

counts the number of variables with non-zero root reduced cost

Parameters
scipSCIP data structure
varsvariable array
nvarsnumber of variables

Definition at line 179 of file prop_rootredcost.c.

References NULL, SCIP_Real, SCIPisDualfeasZero(), and SCIPvarGetBestRootRedcost().

Referenced by propdataInit().

◆ propdataExit()

static SCIP_RETCODE propdataExit ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

free propagator data

Parameters
scipSCIP data structure
propdatapropagator 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 SCIP_RETCODE propdataInit ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

◆ propagateRootRedcostVar()

static SCIP_RETCODE propagateRootRedcostVar ( SCIP scip,
SCIP_VAR var,
SCIP_Real  cutoffbound,
SCIP_Bool infeasible,
SCIP_Bool tightened 
)
static

propagates the root reduced cost against the cutoff bound for the given variable

Parameters
scipSCIP data structure
varvariable to propagate
cutoffboundcutoff bound to use
infeasiblepointer to store whether the new domain is empty
tightenedpointer 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 SCIP_RETCODE propagateBinaryBestRootRedcost ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_Real  cutoffbound,
int *  nchgbds,
SCIP_Bool cutoff 
)
static

propagate binary variables with non-zero root reduced cost

Parameters
scipSCIP data structure
propdatapropagator data structure
cutoffboundcutoff bound to use
nchgbdspointer to store the number of bound changes
cutoffpointer 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 SCIP_DECL_PROPCOPY ( propCopyRootredcost  )
static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 527 of file prop_rootredcost.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropRootredcost(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeRootredcost  )
static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 541 of file prop_rootredcost.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolRootredcost  )
static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 558 of file prop_rootredcost.c.

References NULL, propdataExit(), SCIP_CALL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXEC()