Detailed Description

probing propagator

Author: Tobias Achterberg; Matthias Miltenberger; Michael Winkler

#include "blockmemshell/memory.h"
#include "scip/prop_probing.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_prop.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.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_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_prop.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	PROP_NAME "probing"

#define	PROP_DESC "probing propagator on binary variables"

#define	PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

#define	PROP_PRIORITY -100000

#define	PROP_FREQ -1

#define	PROP_DELAY TRUE

#define	PROP_PRESOL_PRIORITY -100000

#define	PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

#define	PROP_PRESOL_MAXROUNDS -1

#define	MAXDNOM 10000LL

#define	DEFAULT_MAXRUNS 1

#define	DEFAULT_PROPROUNDS -1

#define	DEFAULT_MAXFIXINGS 25

#define	DEFAULT_MAXUSELESS 1000

#define	DEFAULT_MAXTOTALUSELESS 50

#define	DEFAULT_MAXSUMUSELESS 0

#define	DEFAULT_MAXDEPTH -1

#define	DEFAULT_RANDSEED 59

Functions
static SCIP_RETCODE	initPropdata (SCIP_PROPDATA *propdata)

static SCIP_RETCODE	freeSortedvars (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_RETCODE	sortVariables (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR **vars, int nvars, int firstidx)

static SCIP_RETCODE	applyProbing (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR *vars, int nvars, int nbinvars, int startidx, int nfixedvars, int naggrvars, int nchgbds, int oldnfixedvars, int oldnaggrvars, SCIP_Bool delay, SCIP_Bool *cutoff)

static	SCIP_DECL_PROPCOPY (propCopyProbing)

static	SCIP_DECL_PROPFREE (propFreeProbing)

static	SCIP_DECL_PROPINIT (propInitProbing)

static	SCIP_DECL_PROPEXIT (propExitProbing)

static	SCIP_DECL_PROPINITPRE (propInitpreProbing)

static	SCIP_DECL_PROPEXITPRE (propExitpreProbing)

static	SCIP_DECL_PROPINITSOL (propInitsolProbing)

static	SCIP_DECL_PROPPRESOL (propPresolProbing)

static	SCIP_DECL_PROPEXEC (propExecProbing)

static	SCIP_DECL_PROPRESPROP (propRespropProbing)

SCIP_RETCODE	SCIPincludePropProbing (SCIP *scip)

SCIP_RETCODE	SCIPapplyProbingVar (SCIP scip, SCIP_VAR vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real impllbs, SCIP_Real implubs, SCIP_Real proplbs, SCIP_Real propubs, SCIP_Bool cutoff)

SCIP_RETCODE	SCIPanalyzeDeductionsProbing (SCIP scip, SCIP_VAR probingvar, SCIP_Real leftub, SCIP_Real rightlb, int nvars, SCIP_VAR *vars, SCIP_Real leftimpllbs, SCIP_Real leftimplubs, SCIP_Real leftproplbs, SCIP_Real leftpropubs, SCIP_Real rightimpllbs, SCIP_Real rightimplubs, SCIP_Real rightproplbs, SCIP_Real rightpropubs, int nfixedvars, int naggrvars, int nimplications, int nchgbds, SCIP_Bool cutoff)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "probing"

Definition at line 60 of file prop_probing.c.

◆ PROP_DESC

#define PROP_DESC "probing propagator on binary variables"

Definition at line 61 of file prop_probing.c.

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 62 of file prop_probing.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY -100000

propagation priority

Definition at line 63 of file prop_probing.c.

◆ PROP_FREQ

#define PROP_FREQ -1

propagation frequency

Definition at line 64 of file prop_probing.c.

◆ PROP_DELAY

#define PROP_DELAY TRUE

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

Definition at line 66 of file prop_probing.c.

◆ PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY -100000

priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers

Definition at line 67 of file prop_probing.c.

◆ PROP_PRESOLTIMING

#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

Definition at line 68 of file prop_probing.c.

◆ PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 70 of file prop_probing.c.

◆ MAXDNOM

#define MAXDNOM 10000LL

maximal denominator for simple rational fixed values

Definition at line 71 of file prop_probing.c.

◆ DEFAULT_MAXRUNS

#define DEFAULT_MAXRUNS 1

maximal number of runs, probing participates in (-1: no limit)

Definition at line 84 of file prop_probing.c.

◆ DEFAULT_PROPROUNDS

#define DEFAULT_PROPROUNDS -1

maximal number of propagation rounds in probing subproblems

Definition at line 85 of file prop_probing.c.

◆ DEFAULT_MAXFIXINGS

#define DEFAULT_MAXFIXINGS 25

maximal number of fixings found, until probing is interrupted (0: don't interrupt)

Definition at line 87 of file prop_probing.c.

◆ DEFAULT_MAXUSELESS

#define DEFAULT_MAXUSELESS 1000

maximal number of successive probings without fixings, until probing is aborted (0: don't abort)

Definition at line 89 of file prop_probing.c.

◆ DEFAULT_MAXTOTALUSELESS

#define DEFAULT_MAXTOTALUSELESS 50

maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)

Definition at line 91 of file prop_probing.c.

◆ DEFAULT_MAXSUMUSELESS

#define DEFAULT_MAXSUMUSELESS 0

maximal number of probings without fixings, until probing is aborted (0: don't abort)

Definition at line 93 of file prop_probing.c.

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH -1

maximal depth until propagation is executed(-1: no limit)

Definition at line 94 of file prop_probing.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 59

random initial seed

Definition at line 95 of file prop_probing.c.

Function Documentation

◆ initPropdata()

static SCIP_RETCODE initPropdata ( SCIP_PROPDATA * propdata )

static

initializes the propagator data

Parameters

propdata propagator data

Definition at line 139 of file prop_probing.c.

References NULL, and SCIP_OKAY.

Referenced by SCIP_DECL_PROPINIT(), and SCIPincludePropProbing().

◆ freeSortedvars()

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

static

frees the sorted vars array

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 167 of file prop_probing.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().

Referenced by SCIP_DECL_PROPEXIT(), and SCIP_DECL_PROPEXITPRE().

◆ sortVariables()

static SCIP_RETCODE sortVariables	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR **	vars,
		int	nvars,
		int	firstidx
	)

static

sorts the binary variables starting with the given index by rounding locks and implications

Parameters

scip	SCIP data structure
propdata	propagator data
vars	problem variables to be sorted
nvars	number of problem variables to be sorted
firstidx	first index that should be subject to sorting

Definition at line 196 of file prop_probing.c.

References ABS, FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPinfinity(), SCIPrandomGetReal(), SCIPsortDownRealPtr(), SCIPvarGetIndex(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by applyProbing(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

◆ applyProbing()

static SCIP_RETCODE applyProbing	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR **	vars,
		int	nvars,
		int	nbinvars,
		int *	startidx,
		int *	nfixedvars,
		int *	naggrvars,
		int *	nchgbds,
		int	oldnfixedvars,
		int	oldnaggrvars,
		SCIP_Bool *	delay,
		SCIP_Bool *	cutoff
	)

static

the main probing loop

Parameters

scip	SCIP data structure
propdata	propagator data
vars	problem variables
nvars	number of problem variables
nbinvars	number of binary variables
startidx	pointer to store starting variable index of next call
nfixedvars	pointer to store number of fixed variables
naggrvars	pointer to store number of aggregated variables
nchgbds	pointer to store number of changed bounds
oldnfixedvars	number of previously fixed variables
oldnaggrvars	number of previously aggregated variables
delay	pointer to store whether propagator should be delayed
cutoff	pointer to store whether cutoff occured

Definition at line 343 of file prop_probing.c.

References FALSE, MAX, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPanalyzeDeductionsProbing(), SCIPapplyProbingVar(), SCIPcaptureVar(), SCIPdebugMsg, SCIPduplicateMemoryArray, SCIPfixVar(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPgetCurrentNode(), SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPgetStage(), SCIPgetVars(), SCIPisStopped(), SCIPnodeGetDepth(), SCIPreallocBufferArray, SCIPreleaseVar(), SCIPswapPointers(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsDeleted(), SCIPverbMessage(), sortVariables(), and TRUE.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyProbing )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 734 of file prop_probing.c.

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

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeProbing )

static

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

Definition at line 749 of file prop_probing.c.

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

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitProbing )

static

initialization method of propagator (called after problem was transformed)

Definition at line 769 of file prop_probing.c.

References DEFAULT_RANDSEED, initPropdata(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPpropGetData(), and TRUE.

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitProbing )

static

deinitialization method of propagator (called before transformed problem is freed)

Definition at line 788 of file prop_probing.c.

References freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpropGetData().

◆ SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreProbing )

static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 808 of file prop_probing.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXITPRE()

static SCIP_DECL_PROPEXITPRE ( propExitpreProbing )

static

presolving deinitialization method of propagator (called after presolving has been finished)

Definition at line 823 of file prop_probing.c.

References freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetNRuns(), and SCIPpropGetData().

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolProbing )

static

solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 845 of file prop_probing.c.

References NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolProbing )

static

presolve method of propagator

Definition at line 864 of file prop_probing.c.

References applyProbing(), BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPcaptureVar(), SCIPdebugMsg, SCIPduplicateMemoryArray, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPgetNTotalVars(), SCIPgetNVars(), SCIPgetVars(), SCIPpropGetData(), SCIPpropGetTime(), SCIPreallocMemoryArray, SCIPswapPointers(), SCIPvarIsBinary(), and sortVariables().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecProbing )

static

execution method of propagator

Definition at line 998 of file prop_probing.c.

References applyProbing(), BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPBranchCands(), SCIPgetLPSolstat(), SCIPgetNTotalVars(), SCIPgetProbName(), SCIPinProbing(), SCIPnodeGetNumber(), SCIPpropGetData(), SCIPreallocMemoryArray, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and sortVariables().

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropProbing )

static

propagation conflict resolving method of propagator

Definition at line 1125 of file prop_probing.c.

References SCIP_DIDNOTRUN, and SCIP_OKAY.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ PROP_PRESOL_PRIORITY

◆ PROP_PRESOLTIMING

◆ PROP_PRESOL_MAXROUNDS

◆ MAXDNOM

◆ DEFAULT_MAXRUNS

◆ DEFAULT_PROPROUNDS

◆ DEFAULT_MAXFIXINGS

◆ DEFAULT_MAXUSELESS

◆ DEFAULT_MAXTOTALUSELESS

◆ DEFAULT_MAXSUMUSELESS

◆ DEFAULT_MAXDEPTH

◆ DEFAULT_RANDSEED

Function Documentation

◆ initPropdata()

◆ freeSortedvars()

◆ sortVariables()

◆ applyProbing()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINIT()

◆ SCIP_DECL_PROPEXIT()

◆ SCIP_DECL_PROPINITPRE()

◆ SCIP_DECL_PROPEXITPRE()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()