reduced cost / dual fixing for SDPs More...

Macros
Propagator properties
#define	PROP_NAME "sdpredcost"

#define	PROP_DESC "sdp reduced cost strengthening propagator"

#define	PROP_TIMING (SCIP_PROPTIMING_DURINGLPLOOP \| SCIP_PROPTIMING_AFTERLPLOOP)

#define	PROP_PRIORITY +1000000

#define	PROP_FREQ 1

#define	PROP_DELAY FALSE

#define	DEFAULT_SDPRCBIN TRUE

#define	DEFAULT_SDPRCINTCONT TRUE

Functions
static SCIP_RETCODE	sdpRedcostFixingBinary (SCIP scip, SCIP_VAR var, SCIP_Real primallbval, SCIP_Real primalubval, SCIP_Real cutoffbound, SCIP_Real relaxval, SCIP_RESULT *result)

static SCIP_RETCODE	sdpRedcostFixingIntCont (SCIP scip, SCIP_VAR var, SCIP_Real primallbval, SCIP_Real primalubval, SCIP_Real cutoffbound, SCIP_Real relaxval, SCIP_RESULT *result)

static	SCIP_DECL_PROPEXEC (propExecSdpredcost)

static	SCIP_DECL_PROPFREE (propFreeSdpredcost)

static	SCIP_DECL_PROPINITSOL (propInitsolSdpredcost)

static	SCIP_DECL_PROPCOPY (propCopySdpredcost)

SCIP_RETCODE	SCIPincludePropSdpredcost (SCIP *scip)

Detailed Description

reduced cost / dual fixing for SDPs

Author: Tristan Gally

Definition in file prop_sdpredcost.c.

Macro Definition Documentation

#define PROP_NAME "sdpredcost"

Definition at line 55 of file prop_sdpredcost.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropSdpredcost().

#define PROP_DESC "sdp reduced cost strengthening propagator"

Definition at line 56 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define PROP_TIMING (SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP)

Definition at line 57 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define PROP_PRIORITY +1000000

propagator priority

Definition at line 58 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define PROP_FREQ 1

propagator frequency

Definition at line 59 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define PROP_DELAY FALSE

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

Definition at line 60 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define DEFAULT_SDPRCBIN TRUE

Should sdp reduced cost fixing be executed for binary variables?

Definition at line 61 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

#define DEFAULT_SDPRCINTCONT TRUE

Should sdp reduced cost fixing be executed for integer and continuous variables?

Definition at line 62 of file prop_sdpredcost.c.

Referenced by SCIPincludePropSdpredcost().

Function Documentation

static SCIP_RETCODE sdpRedcostFixingBinary	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	primallbval,
		SCIP_Real	primalubval,
		SCIP_Real	cutoffbound,
		SCIP_Real	relaxval,
		SCIP_RESULT *	result
	)

static

reduced cost fixing for binary variables

If the corresponding primal variable for the lower bound is bigger than the cutoff bound minus the current relaxation value, then the variable can be fixed to zero, if the primal variable for the upper bound is bigger than this value, then it can be fixed to one.

Parameters

scip	pointer to SCIP data structure
var	variable to propagate
primallbval	value of the primal variable corresponding to the lower bound
primalubval	value of the primal variable corresponding to the upper bound
cutoffbound	current cutoffbound in SCIP
relaxval	optimal objective value of the current relaxation
result	pointer to return result

Definition at line 84 of file prop_sdpredcost.c.

Referenced by SCIP_DECL_PROPEXEC().

static SCIP_RETCODE sdpRedcostFixingIntCont	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	primallbval,
		SCIP_Real	primalubval,
		SCIP_Real	cutoffbound,
		SCIP_Real	relaxval,
		SCIP_RESULT *	result
	)

static

reduced cost fixing for non-binary variables

We propagate the new bounds

$y_j \leq \ell_j + \frac{v_{CO} - \bar{v}}{\bar{X}_{n+m+j,n+m+j}}$ ,

$y_j \geq u_j - \frac{v_{CO} - \bar{v}}{\bar{X}_{n+j,n+j}}$

where $\bar{v}$ is the value of the current relaxation, $v_{CO}$ is the cutoffbound and $\bar{X}_{n+m+j,n+m+j}$ the value of the corresponding primal solution

Parameters

scip	pointer to SCIP data structure
var	variable to propagate
primallbval	value of the primal variable corresponding to the lower bound
primalubval	value of the primal variable corresponding to the upper bound
cutoffbound	current cutoffbound in SCIP
relaxval	optimal objective value of the current relaxation
result	pointer to return result