Scippy

SCIP

Solving Constraint Integer Programs

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 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
propdatapropagator 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
scipSCIP data structure
propdatapropagator 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
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, 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
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 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()

◆ SCIP_DECL_PROPEXEC()

◆ 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.