Scippy

SCIP

Solving Constraint Integer Programs

prop_probing.c File Reference

Detailed Description

probing propagator

Author
Tobias Achterberg
Matthias Miltenberger
Michael Winkler

Definition in file prop_probing.c.

#include <assert.h>
#include <string.h>
#include "scip/prop_probing.h"
#include "scip/pub_misc.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 *scip, 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 32 of file prop_probing.c.

Referenced by applyProbing().

◆ PROP_DESC

#define PROP_DESC   "probing propagator on binary variables"

Definition at line 33 of file prop_probing.c.

◆ PROP_TIMING

#define PROP_TIMING   SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 34 of file prop_probing.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY   -100000

propagation priority

Definition at line 35 of file prop_probing.c.

◆ PROP_FREQ

#define PROP_FREQ   -1

propagation frequency

Definition at line 36 of file prop_probing.c.

◆ PROP_DELAY

#define PROP_DELAY   TRUE

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

Definition at line 37 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 40 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 41 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 42 of file prop_probing.c.

◆ MAXDNOM

#define MAXDNOM   10000LL

maximal denominator for simple rational fixed values

Definition at line 45 of file prop_probing.c.

Referenced by SCIPanalyzeDeductionsProbing().

◆ DEFAULT_MAXRUNS

#define DEFAULT_MAXRUNS   1

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

Definition at line 58 of file prop_probing.c.

◆ DEFAULT_PROPROUNDS

#define DEFAULT_PROPROUNDS   -1

maximal number of propagation rounds in probing subproblems

Definition at line 59 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 60 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 63 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 66 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 69 of file prop_probing.c.

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH   -1

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

Definition at line 72 of file prop_probing.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   59

random initial seed

Definition at line 73 of file prop_probing.c.

Function Documentation

◆ initPropdata()

static SCIP_RETCODE initPropdata ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

initializes the propagator data

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 117 of file prop_probing.c.

◆ freeSortedvars()

static SCIP_RETCODE freeSortedvars ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

frees the sorted vars array

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 146 of file prop_probing.c.

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

Referenced by 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
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 175 of file prop_probing.c.

References applyProbing(), FALSE, MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPinfinity(), SCIPrandomGetReal(), SCIPsortDownRealPtr(), SCIPvarGetIndex(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.

Referenced by applyProbing(), and freeSortedvars().

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

References FALSE, MAX, PROP_NAME, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_DECL_PROPCOPY(), 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(), SCIPpropGetName(), SCIPreallocBufferArray, SCIPreleaseVar(), SCIPswapPointers(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsDeleted(), SCIPverbMessage(), sortVariables(), and TRUE.

Referenced by sortVariables().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyProbing  )
static

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

Definition at line 712 of file prop_probing.c.

Referenced by applyProbing().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeProbing  )
static

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

Definition at line 727 of file prop_probing.c.

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitProbing  )
static

initialization method of propagator (called after problem was transformed)

Definition at line 748 of file prop_probing.c.

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitProbing  )
static

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

Definition at line 768 of file prop_probing.c.

◆ SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreProbing  )
static

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

Definition at line 788 of file prop_probing.c.

References SCIPpropGetData().

◆ SCIP_DECL_PROPEXITPRE()

static SCIP_DECL_PROPEXITPRE ( propExitpreProbing  )
static

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

Definition at line 803 of file prop_probing.c.

References freeSortedvars(), SCIP_CALL, SCIP_DECL_PROPINITSOL(), SCIP_OKAY, 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 825 of file prop_probing.c.

Referenced by SCIP_DECL_PROPEXITPRE().

◆ SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolProbing  )
static

presolve method of propagator

Definition at line 844 of file prop_probing.c.

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecProbing  )
static

execution method of propagator

Definition at line 978 of file prop_probing.c.

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropProbing  )
static

propagation conflict resolving method of propagator

Definition at line 1104 of file prop_probing.c.