SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

probing propagator

Author
Tobias Achterberg
Matthias Miltenberger
Michael Winkler

Definition in file prop_probing.c.

#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 65 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 69 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.

Referenced by SCIPincludePropProbing().

◆ 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 86 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

◆ DEFAULT_MAXUSELESS

#define DEFAULT_MAXUSELESS   1000

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

Definition at line 88 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

◆ 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 90 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

◆ DEFAULT_MAXSUMUSELESS

#define DEFAULT_MAXSUMUSELESS   0

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

Definition at line 92 of file prop_probing.c.

Referenced by SCIPincludePropProbing().

◆ 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()

SCIP_RETCODE initPropdata ( SCIP_PROPDATA * propdata)
static

initializes the propagator data

Parameters
propdatapropagator data

Definition at line 139 of file prop_probing.c.

References assert(), NULL, and SCIP_OKAY.

Referenced by SCIP_DECL_PROPINIT(), and SCIPincludePropProbing().

◆ freeSortedvars()

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

frees the sorted vars array

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 167 of file prop_probing.c.

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

Referenced by SCIP_DECL_PROPEXIT(), and SCIP_DECL_PROPEXITPRE().

◆ sortVariables()

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
scipSCIP data structure
propdatapropagator data
varsproblem variables to be sorted
nvarsnumber of problem variables to be sorted
firstidxfirst index that should be subject to sorting

Definition at line 196 of file prop_probing.c.

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

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

◆ applyProbing()

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
scipSCIP data structure
propdatapropagator data
varsproblem variables
nvarsnumber of problem variables
nbinvarsnumber of binary variables
startidxpointer to store starting variable index of next call
nfixedvarspointer to store number of fixed variables
naggrvarspointer to store number of aggregated variables
nchgbdspointer to store number of changed bounds
oldnfixedvarsnumber of previously fixed variables
oldnaggrvarsnumber of previously aggregated variables
delaypointer to store whether propagator should be delayed
cutoffpointer to store whether cutoff occured

Definition at line 343 of file prop_probing.c.

References assert(), cutoff, FALSE, i, MAX, nbinvars, NULL, nvars, 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(), TRUE, and vars.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

◆ SCIP_DECL_PROPCOPY()

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 assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropProbing(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

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 assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPINIT()

SCIP_DECL_PROPINIT ( propInitProbing )
static

initialization method of propagator (called after problem was transformed)

Definition at line 769 of file prop_probing.c.

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

◆ SCIP_DECL_PROPEXIT()

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 assert(), freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeRandom(), and SCIPpropGetData().

◆ SCIP_DECL_PROPINITPRE()

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 assert(), NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPEXITPRE()

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 assert(), freeSortedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetNRuns(), and SCIPpropGetData().

◆ SCIP_DECL_PROPINITSOL()

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 assert(), NULL, SCIP_OKAY, and SCIPpropGetData().

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()

SCIP_DECL_PROPRESPROP ( propRespropProbing )
static

propagation conflict resolving method of propagator

Definition at line 1125 of file prop_probing.c.

References result, SCIP_DIDNOTRUN, and SCIP_OKAY.