60#define PROP_NAME "probing"
61#define PROP_DESC "probing propagator on binary variables"
62#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
63#define PROP_PRIORITY -100000
65#define PROP_DELAY TRUE
67#define PROP_PRESOL_PRIORITY -100000
68#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
69#define PROP_PRESOL_MAXROUNDS -1
71#define MAXDNOM 10000LL
84#define DEFAULT_MAXRUNS 1
85#define DEFAULT_PROPROUNDS -1
86#define DEFAULT_MAXFIXINGS 25
88#define DEFAULT_MAXUSELESS 1000
90#define DEFAULT_MAXTOTALUSELESS 50
92#define DEFAULT_MAXSUMUSELESS 0
94#define DEFAULT_MAXDEPTH -1
95#define DEFAULT_RANDSEED 59
120 int lastsortstartidx;
129 SCIP_Longint lastnode;
145 propdata->sortedvars =
NULL;
146 propdata->nprobed =
NULL;
147 propdata->noldtotalvars = 0;
148 propdata->nsortedvars = 0;
149 propdata->nsortedbinvars = 0;
150 propdata->startidx = 0;
151 propdata->lastsortstartidx = -1;
152 propdata->nfixings = 0;
153 propdata->naggregations = 0;
154 propdata->nimplications = 0;
155 propdata->nbdchgs = 0;
156 propdata->nuseless = 0;
157 propdata->ntotaluseless = 0;
158 propdata->nsumuseless = 0;
159 propdata->lastnode = -2;
160 propdata->randnumgen =
NULL;
174 if( propdata->sortedvars !=
NULL )
179 for(
i = 0;
i < propdata->nsortedvars; ++
i )
184 propdata->nsortedvars = 0;
185 propdata->nsortedbinvars = 0;
189 propdata->noldtotalvars = 0;
222 nsortedvars =
nvars - firstidx;
223 if( nsortedvars <= 0 )
228 sortedvars = &(
vars[firstidx]);
260 tmp = -
MAX(nlocksdown, nlocksup)
264 tmp = -
ABS(nlocksdown - nlocksup)
265 +
MIN(nlocksdown, nlocksup)
291 for(
i = 0;
i < nsortedvars; ++
i )
317 -
MAX(nlocksdown, nlocksup)
323 -
ABS(nlocksdown - nlocksup)
324 +
MIN(nlocksdown, nlocksup)
383 maxfixings = (propdata->maxfixings > 0 ? propdata->maxfixings :
INT_MAX);
384 maxuseless = (propdata->maxuseless > 0 ? propdata->maxuseless :
INT_MAX);
385 maxtotaluseless = (propdata->maxtotaluseless > 0 ? propdata->maxtotaluseless :
INT_MAX);
386 maxsumuseless = (propdata->maxsumuseless > 0 ? propdata->maxsumuseless :
INT_MAX);
414 if( propdata->nuseless >= maxuseless || propdata->ntotaluseless >= maxtotaluseless || propdata->nsumuseless >= maxsumuseless ||
SCIPisStopped(
scip) )
417 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
419 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
423 if( propdata->nuseless >= maxuseless )
427 propdata->nuseless, maxuseless);
429 else if( propdata->ntotaluseless >= maxtotaluseless )
433 propdata->ntotaluseless, maxtotaluseless);
435 else if( propdata->nsumuseless >= maxsumuseless )
439 propdata->nsumuseless, maxsumuseless);
467 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
469 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
477 if( propdata->nuseless > 0 )
478 propdata->nsumuseless++;
480 propdata->nsumuseless =
MAX(propdata->nsumuseless-1, 0);
481 propdata->nuseless++;
482 propdata->ntotaluseless++;
516 propdata->nfixings++;
517 propdata->nuseless = 0;
518 propdata->ntotaluseless = 0;
522 SCIPdebugMsg(
scip,
"tightening upper bound of probing variable <%s> to 0.0 led to a cutoff\n",
567 propdata->nfixings++;
568 propdata->nuseless = 0;
569 propdata->ntotaluseless = 0;
573 SCIPdebugMsg(
scip,
"tightening lower bound of probing variable <%s> to 1.0 led to a cutoff\n",
595 nvars,
vars,
zeroimpllbs,
zeroimplubs,
zeroproplbs,
zeropropubs,
oneimpllbs,
oneimplubs,
oneproplbs,
onepropubs,
610 propdata->nuseless = 0;
611 propdata->ntotaluseless = 0;
614 propdata->ntotaluseless = 0;
640 for( v = propdata->nsortedvars - 1; v >= 0; --v )
645 propdata->nsortedvars = 0;
646 propdata->nsortedbinvars = 0;
652 propdata->nsortedvars = nnewvars;
671 vars = propdata->sortedvars;
672 nvars = propdata->nsortedvars;
688 for( v = propdata->nsortedvars - 1; v >= 0; --v )
696 propdata->lastsortstartidx = -1;
697 propdata->nuseless = 0;
698 propdata->ntotaluseless = 0;
705 propdata->lastsortstartidx = 0;
757 assert(propdata->nsortedvars == 0);
758 assert(propdata->nsortedbinvars == 0);
797 assert(propdata->nsortedvars == 0);
798 assert(propdata->nsortedbinvars == 0);
815 propdata->lastnode = -2;
835 assert(propdata->nsortedvars == 0);
836 assert(propdata->nsortedbinvars == 0);
854 propdata->nuseless = 0;
855 propdata->ntotaluseless = 0;
856 propdata->nsumuseless = 0;
908 propdata->nuseless -= propdata->nuseless/10;
909 propdata->ntotaluseless -= propdata->ntotaluseless/10;
912 if( propdata->sortedvars ==
NULL )
918 assert(propdata->startidx == 0);
923 propdata->nsortedvars =
nvars;
927 for( v =
nbinvars; v < lastidx; ++v )
935 propdata->nsortedbinvars =
nbinvars;
938 for( v = propdata->nsortedvars - 1; v >= 0 ; --v )
944 if( propdata->nsortedbinvars == 0 )
958 propdata->lastnode = -1;
961 if( propdata->lastsortstartidx < 0 || propdata->startidx - propdata->lastsortstartidx >= 100 )
964 propdata->lastsortstartidx = propdata->startidx;
984 propdata->lastnode = -2;
1100 SCIP_CALL(
applyProbing(
scip, propdata, binvars,
nbinvars,
nbinvars, &startidx, &nfixedvars, &naggrvars, &nchgbds,
oldnfixedvars,
oldnaggrvars, &delay, &
cutoff) );
1101 SCIPdebug(
SCIPdebugMsg(
scip,
"probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n",
1102 nfixedvars, naggrvars, nchgbds, (propdata->nimplications) -
oldnimplications); )
1107 propdata->lastnode = -2;
1170 "maximal number of runs, probing participates in (-1: no limit)",
1174 "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
1178 "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)",
1182 "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)",
1185 "propagating/" PROP_NAME "/maxtotaluseless",
1186 "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)",
1189 "propagating/" PROP_NAME "/maxsumuseless",
1190 "maximal number of probings without fixings, until probing is aborted (0: don't abort)",
1194 "maximal depth until propagation is executed(-1: no limit)",
1226 SCIPdebugMsg(
scip,
"applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
1282 SCIPdebugMsg(
scip,
"propagating probing implications after <%s> to %g led to a cutoff\n",
1446 SCIP_Bool tightened;
1455 SCIPdebugMsg(
scip,
"fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1463 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible fixing of variable <%s> to %g\n",
1474 SCIP_Bool tightened;
1501 SCIPdebugMsg(
scip,
"tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1509 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1520 SCIPdebugMsg(
scip,
"tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1528 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1561 SCIP_Bool redundant;
1569 SCIPdebugMsg(
scip,
"aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n",
1579 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible aggregation: %g<%s> - %g<%s> == %g\n",
1600 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible vlb: %g<%s> - %g<%s> == %g\n",
1612 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible vub: %g<%s> - %g<%s> == %g\n",
1653 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1672 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1692 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1711 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1732 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> <= %g\n",
1748 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> >= %g\n",
1764 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1780 SCIPdebugMsg(
scip,
"analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
#define SCIP_LONGINT_FORMAT
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
int SCIPgetNTotalVars(SCIP *scip)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
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)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
void SCIPswapPointers(void **pointer1, void **pointer2)
SCIP_RETCODE SCIPincludePropProbing(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeMemoryArrayNull(scip, ptr)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop,)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop,)
SCIP_Real SCIPpropGetTime(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
int SCIPgetNRuns(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarVub(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vubvar, SCIP_Real vubcoef, SCIP_Real vubconstant, SCIP_Bool *infeasible, int *nbdchgs)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
void SCIPenableVarHistory(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define DEFAULT_MAXUSELESS
#define DEFAULT_MAXTOTALUSELESS
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)
#define DEFAULT_PROPROUNDS
static SCIP_RETCODE initPropdata(SCIP_PROPDATA *propdata)
static SCIP_RETCODE freeSortedvars(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_MAXSUMUSELESS
static SCIP_RETCODE sortVariables(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int firstidx)
#define PROP_PRESOL_PRIORITY
#define DEFAULT_MAXFIXINGS
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for random numbers
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
enum SCIP_BoundType SCIP_BOUNDTYPE
enum SCIP_VerbLevel SCIP_VERBLEVEL
#define SCIP_DECL_PROPCOPY(x)
#define SCIP_DECL_PROPEXITPRE(x)
#define SCIP_DECL_PROPINITSOL(x)
#define SCIP_DECL_PROPINIT(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXIT(x)
#define SCIP_DECL_PROPPRESOL(x)
#define SCIP_DECL_PROPINITPRE(x)
#define SCIP_DECL_PROPRESPROP(x)
struct SCIP_PropData SCIP_PROPDATA
#define SCIP_DECL_PROPEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS