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 61 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ PROP_DESC

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

Definition at line 62 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 63 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ PROP_PRIORITY

#define PROP_PRIORITY +10000000

propagator priority

Definition at line 64 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 65 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 66 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ DEFAULT_ONLYBINARY

#define DEFAULT_ONLYBINARY FALSE

should only binary variables be propagated?

Definition at line 74 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

◆ 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 75 of file prop_rootredcost.c.

Referenced by SCIPincludePropRootredcost().

Function Documentation

◆ propdataReset()

static void propdataReset ( SCIP_PROPDATA * propdata )

static

reset structure memember of propagator data structure

Parameters

propdata propagator data to reset

Definition at line 111 of file prop_rootredcost.c.

References FALSE, NULL, SCIP_DECL_SORTPTRCOMP(), 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 128 of file prop_rootredcost.c.

Referenced by propdataReset().

◆ propdataCreate()

static SCIP_RETCODE propdataCreate	(	SCIP *	scip,
		SCIP_PROPDATA **	propdata
	)

static

create propagator data structure

Parameters

scip	SCIP data structure
propdata	pointer to store the created propagator data

Definition at line 159 of file prop_rootredcost.c.

References countNonZeroRootRedcostVars(), 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

scip	SCIP data structure
vars	variable array
nvars	number of variables

Definition at line 173 of file prop_rootredcost.c.

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

Referenced by propdataCreate(), and propdataInit().

◆ propdataExit()

static SCIP_RETCODE propdataExit	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

free propagator data

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 201 of file prop_rootredcost.c.

References propdataInit(), propdataReset(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseVar().

Referenced by countNonZeroRootRedcostVars().

◆ propdataInit()

static SCIP_RETCODE propdataInit	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

initializate the propagator

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 224 of file prop_rootredcost.c.

References countNonZeroRootRedcostVars(), NULL, propagateRootRedcostVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetProbName(), SCIPgetVars(), SCIPinfinity(), SCIPisDualfeasZero(), SCIPsortDownPtr(), SCIPvarGetBestRootRedcost(), SCIPvarIsBinary(), and TRUE.

Referenced by propdataExit().

◆ 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

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 324 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().

◆ 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

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 374 of file prop_rootredcost.c.

References NULL, propagateRootRedcostVar(), SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPCOPY(), SCIP_OKAY, SCIPdebugMsg, SCIPvarGetBestRootLPObjval(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootSol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by propagateRootRedcostVar().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyRootredcost )

static

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

Definition at line 521 of file prop_rootredcost.c.

Referenced by propagateBinaryBestRootRedcost().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeRootredcost )

static

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

Definition at line 535 of file prop_rootredcost.c.

◆ 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 552 of file prop_rootredcost.c.

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecRootredcost )

static

execution method of propagator

Definition at line 567 of file prop_rootredcost.c.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ DEFAULT_ONLYBINARY

◆ DEFAULT_FORCE

Function Documentation

◆ propdataReset()

◆ SCIP_DECL_SORTPTRCOMP()

◆ propdataCreate()

◆ countNonZeroRootRedcostVars()

◆ propdataExit()

◆ propdataInit()

◆ propagateRootRedcostVar()

◆ propagateBinaryBestRootRedcost()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPEXITSOL()

◆ SCIP_DECL_PROPEXEC()