sepa_rapidlearning.c
Go to the documentation of this file.
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
50#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
52#define DEFAULT_APPLYCONFLICTS TRUE /**< should the found conflicts be applied in the original SCIP? */
53#define DEFAULT_APPLYBDCHGS TRUE /**< should the found global bound deductions be applied in the original SCIP?
56#define DEFAULT_APPLYINFERVALS TRUE /**< should the inference values be used as initialization in the original SCIP? */
57#define DEFAULT_REDUCEDINFER FALSE /**< should the inference values only be used when rapid learning found other reductions? */
58#define DEFAULT_APPLYPRIMALSOL TRUE /**< should the incumbent solution be copied to the original SCIP? */
64#define DEFAULT_CHECKLEAVES FALSE /**< should the ratio of leaves proven to be infeasible and exceeding the
68#define DEFAULT_MINDEGENERACY 0.7 /**< minimal degeneracy threshold to allow local rapid learning */
69#define DEFAULT_MININFLPRATIO 10.0 /**< minimal threshold of inf/obj leaves to allow local rapid learning */
70#define DEFAULT_MINVARCONSRATIO 2.0 /**< minimal ratio of unfixed variables in relation to basis size to
72#define DEFAULT_NWAITINGNODES 100L /**< number of nodes that should be processed before rapid learning is
75#define DEFAULT_MAXNVARS 10000 /**< maximum problem size (variables) for which rapid learning will be called */
76#define DEFAULT_MAXNCONSS 10000 /**< maximum problem size (constraints) for which rapid learning will be called */
82#define DEFAULT_CONTVARS FALSE /**< should rapid learning be applied when there are continuous variables? */
83#define DEFAULT_CONTVARSQUOT 0.3 /**< maximal portion of continuous variables to apply rapid learning */
84#define DEFAULT_LPITERQUOT 0.2 /**< maximal fraction of LP iterations compared to node LP iterations */
98 SCIP_Real mininflpratio; /**< minimal threshold of inf/obj leaves to allow local rapid learning */
102 int maxnconss; /**< maximum problem size (constraints) for which rapid learning will be called */
106 SCIP_Longint nwaitingnodes; /**< number of nodes that should be processed before rapid learning is executed locally
108 SCIP_Bool applybdchgs; /**< should the found global bound deductions be applied in the original SCIP? */
110 SCIP_Bool applyinfervals; /**< should the inference values be used as initialization in the original SCIP? */
115 SCIP_Bool checkleaves; /**< should the ratio of leaves proven to be infeasible and exceeding the
120 SCIP_Bool contvars; /**< should rapid learning be applied when there are continuous variables? */
124 SCIP_Bool reducedinfer; /**< should the inference values only be used when rapid learning found other reductions? */
181 SCIP_CONSHDLR** conshdlrs = NULL; /* array of constraint handler's that might that might obtain conflicts */
204 SCIP_Bool disabledualreductions; /* TRUE, if dual reductions in sub-SCIP are not valid for original SCIP,
224 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapfw, NULL, "rapid", NULL, NULL, 0, global, FALSE, FALSE, TRUE, &valid) );
256 * If the copy is not valid, it should be a relaxation of the problem (constraints might have failed to be copied,
258 * By disabling dual presolving, conflicts and bound changes found in a relaxation are still valid for the original problem.
276 SCIPwarningMessage(scip, "unfixing parameter nodeselection/dfs/stdpriority in subscip of rapidlearning\n");
361 /* allocate memory for constraints storage. Each constraint that will be created from now on will be a conflict.
394 SCIPdebugMsg(scip, "finish after %" SCIP_LONGINT_FORMAT " successful conflict calls.\n", SCIPgetNConflictConssApplied(subscip));
397 else if( (sepadata->applyprimalsol && SCIPgetNSols(subscip) > 0 && SCIPisFeasLT(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
403 if( SCIPgetNSols(subscip) > 0 && SCIPisFeasLE(scip, SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip) ) )
405 SCIPdebugMsg(scip, " - there was a better solution (%f < %f)\n",SCIPgetUpperbound(subscip), SCIPgetUpperbound(scip));
409 SCIPdebugMsg(scip, " - there were %d changed variables bounds\n", SCIPgetNRootboundChgs(subscip) );
413 SCIPdebugMsg(scip, " - there were %" SCIP_LONGINT_FORMAT " conflict constraints created\n", SCIPgetNConflictConssApplied(subscip));
443 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until was declared to be feasible
457 if( !soladded || !SCIPisEQ(scip, SCIPgetSolOrigObj(subscip, subsols[i-1]), SCIPgetSolOrigObj(subscip, subsols[0])) )
464 && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL || SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE) )
472 SCIP_CALL( SCIPupdateLocalDualbound(scip, SCIPretransformObj(scip, SCIPgetDualbound(subscip))) );
478 if( sepadata->applyconflicts && !disabledualreductions && SCIPgetNConflictConssApplied(subscip) > 0 )
522 SCIP_CALL( SCIPgetConsCopy(subscip, scip, cons, &conscopy, conshdlrs[i], varmapbw, consmap, NULL,
523 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons),
536 SCIPdebugMsg(scip, "failed to copy conflict constraint %s back to original SCIP\n", SCIPconsGetName(cons));
571 SCIP_CALL( SCIPtightenVarUbGlobal(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
581 SCIP_CALL( SCIPtightenVarLbGlobal(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
593 SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
603 SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, &cutoff, &tightened) );
615 /* @todo use different nbranching counters for pseudo cost and inference values and update inference values in the tree */
616 if( sepadata->applyinfervals && global && (!sepadata->reducedinfer || soladded || nbdchgs + nconflicts > 0) )
649 SCIP_CALL( SCIPinitVarBranchStats(scip, vars[i], 0.0, 0.0, downvsids, upvsids, downconflen, upconflen, downinfer, upinfer, 0.0, 0.0) );
659 SCIPdebugMsg(scip, "Rapidlearning added %d %s conflicts, changed %d bounds, %s primal solution, %s dual bound improvement.\n",
660 nconflicts, global ? "global" : "local", nbdchgs, soladded ? "found" : "no", dualboundchg ? "found" : "no");
662 SCIPdebugMsg(scip, "YYY Infervalues initialized on one side: %5.2f %% of variables, %5.2f %% on both sides\n",
848 if( sepadata->contvars && SCIPgetNContVars(scip) > sepadata->contvarsquot * SCIPgetNVars(scip) )
855 /* if the separator should be exclusive to the root node, this prevents multiple calls due to restarts */
863 /* the information deduced from rapid learning is globally valid only if we are at the root node; thus we can't use
871 /* @todo check whether we want to run at the root node again, e.g., inf/obj ratio is large enough */
888 /* skip rapid learning when the sub-SCIP would contain an integer variable with an infinite bound in direction of the
889 * objective function; this might lead to very bad branching decisions when enforcing a pseudo solution (#1439)
901 SCIPdebugMsg(scip, "unbounded integer variable %s (in [%g,%g]) with objective %g -> skip rapid learning\n",
911 retcode = setupAndSolveSubscipRapidlearning(scip, subscip, sepadata, (int)SCIPsepaGetNCalls(sepa)+1, global, result);
935 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
980 "should the ratio of leaves proven to be infeasible and exceeding the cutoff bound be checked?",
1040 "number of nodes that should be processed before rapid learning is executed locally based on the progress of the dualbound",
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2969
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1591
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2130
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1408
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPupdateLocalDualbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:3646
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3228
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
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)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
Definition: scip_lp.c:2792
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3050
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1432
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
Definition: scip_solvingstats.c:1450
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
Definition: scip_solvingstats.c:292
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:4186
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
Definition: scip_solvingstats.c:1152
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
Definition: scip_solvingstats.c:319
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
Definition: scip_solvingstats.c:1093
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:446
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_RETCODE SCIPinitVarBranchStats(SCIP *scip, SCIP_VAR *var, SCIP_Real downpscost, SCIP_Real uppscost, SCIP_Real downvsids, SCIP_Real upvsids, SCIP_Real downconflen, SCIP_Real upconflen, SCIP_Real downinfer, SCIP_Real upinfer, SCIP_Real downcutoff, SCIP_Real upcutoff)
Definition: scip_var.c:9537
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_Real SCIPgetVarAvgConflictlength(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9365
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8176
SCIP_Real SCIPgetVarVSIDS(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9177
SCIP_Real SCIPgetVarAvgInferences(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:9419
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
SCIP_RETCODE SCIPincludeSepaRapidlearning(SCIP *scip)
Definition: sepa_rapidlearning.c:924
methods commonly used by primal heuristics
Definition: objbenders.h:44
public methods for problem variables
default SCIP plugins
static SCIP_DECL_SEPACOPY(sepaCopyRapidlearning)
Definition: sepa_rapidlearning.c:133
static SCIP_RETCODE setupAndSolveSubscipRapidlearning(SCIP *scip, SCIP *subscip, SCIP_SEPADATA *sepadata, int randseed, SCIP_Bool global, SCIP_RESULT *result)
Definition: sepa_rapidlearning.c:167
static SCIP_DECL_SEPAFREE(sepaFreeRapidlearning)
Definition: sepa_rapidlearning.c:147
static SCIP_DECL_SEPAEXECLP(sepaExeclpRapidlearning)
Definition: sepa_rapidlearning.c:811
static SCIP_RETCODE checkExec(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *run)
Definition: sepa_rapidlearning.c:690
rapidlearning separator
Definition: struct_cons.h:47
Definition: struct_cons.h:127
Definition: struct_misc.h:138
Definition: struct_sepa.h:47
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70