probing propagator
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) |
#define PROP_NAME "probing" |
Definition at line 60 of file prop_probing.c.
#define PROP_DESC "probing propagator on binary variables" |
Definition at line 61 of file prop_probing.c.
#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 62 of file prop_probing.c.
#define PROP_PRIORITY -100000 |
propagation priority
Definition at line 63 of file prop_probing.c.
#define PROP_FREQ -1 |
propagation frequency
Definition at line 64 of file prop_probing.c.
#define PROP_DELAY TRUE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 65 of file prop_probing.c.
#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.
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 68 of file prop_probing.c.
#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.
#define MAXDNOM 10000LL |
maximal denominator for simple rational fixed values
Definition at line 71 of file prop_probing.c.
#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().
#define DEFAULT_PROPROUNDS -1 |
maximal number of propagation rounds in probing subproblems
Definition at line 85 of file prop_probing.c.
#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().
#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().
#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().
#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().
#define DEFAULT_MAXDEPTH -1 |
maximal depth until propagation is executed(-1: no limit)
Definition at line 94 of file prop_probing.c.
#define DEFAULT_RANDSEED 59 |
random initial seed
Definition at line 95 of file prop_probing.c.
|
static |
initializes the propagator data
propdata | propagator data |
Definition at line 139 of file prop_probing.c.
References assert(), NULL, and SCIP_OKAY.
Referenced by SCIP_DECL_PROPINIT(), and SCIPincludePropProbing().
|
static |
frees the sorted vars array
scip | SCIP data structure |
propdata | propagator 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().
|
static |
sorts the binary variables starting with the given index by rounding locks and implications
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, 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().
|
static |
the main probing loop
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 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().
|
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().
|
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().
|
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.
|
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().
|
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().
|
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().
|
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().
|
static |
presolve method of propagator
Definition at line 864 of file prop_probing.c.
References applyProbing(), assert(), BMSclearMemoryArray, cutoff, nbinvars, nintvars, NULL, nvars, result, 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(), sortVariables(), and vars.
|
static |
execution method of propagator
Definition at line 998 of file prop_probing.c.
References applyProbing(), assert(), BMSclearMemoryArray, cutoff, i, nbinvars, NULL, nvars, result, 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(), sortVariables(), var, and vars.
|
static |
propagation conflict resolving method of propagator
Definition at line 1125 of file prop_probing.c.
References result, SCIP_DIDNOTRUN, and SCIP_OKAY.