44#define SEPA_NAME "rapidlearning"
45#define SEPA_DESC "rapid learning heuristic and separator"
46#define SEPA_PRIORITY -1200000
48#define SEPA_MAXBOUNDDIST 1.0
49#define SEPA_USESSUBSCIP TRUE
50#define SEPA_DELAY FALSE
52#define DEFAULT_APPLYCONFLICTS TRUE
53#define DEFAULT_APPLYBDCHGS TRUE
56#define DEFAULT_APPLYINFERVALS TRUE
57#define DEFAULT_REDUCEDINFER FALSE
58#define DEFAULT_APPLYPRIMALSOL TRUE
59#define DEFAULT_APPLYSOLVED TRUE
61#define DEFAULT_CHECKEXEC TRUE
62#define DEFAULT_CHECKDEGANERACY TRUE
63#define DEFAULT_CHECKDUALBOUND FALSE
64#define DEFAULT_CHECKLEAVES FALSE
66#define DEFAULT_CHECKOBJ FALSE
67#define DEFAULT_CHECKNSOLS TRUE
68#define DEFAULT_MINDEGENERACY 0.7
69#define DEFAULT_MININFLPRATIO 10.0
70#define DEFAULT_MINVARCONSRATIO 2.0
72#define DEFAULT_NWAITINGNODES 100L
75#define DEFAULT_MAXNVARS 10000
76#define DEFAULT_MAXNCONSS 10000
77#define DEFAULT_MAXCALLS 100
79#define DEFAULT_MINNODES 500
80#define DEFAULT_MAXNODES 5000
82#define DEFAULT_CONTVARS FALSE
83#define DEFAULT_CONTVARSQUOT 0.3
84#define DEFAULT_LPITERQUOT 0.2
85#define DEFAULT_COPYCUTS TRUE
97 SCIP_Real mindegeneracy;
98 SCIP_Real mininflpratio;
99 SCIP_Real minvarconsratio;
106 SCIP_Longint nwaitingnodes;
108 SCIP_Bool applybdchgs;
109 SCIP_Bool applyconflicts;
110 SCIP_Bool applyinfervals;
111 SCIP_Bool applyprimalsol;
112 SCIP_Bool applysolved;
113 SCIP_Bool checkdegeneracy;
114 SCIP_Bool checkdualbound;
115 SCIP_Bool checkleaves;
119 SCIP_Bool checknsols;
121 SCIP_Real contvarsquot;
124 SCIP_Bool reducedinfer;
184 SCIP_Longint nodelimit;
224 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmapfw,
NULL,
"rapid",
NULL,
NULL, 0, global,
FALSE,
FALSE,
TRUE, &
valid) );
244 SCIP_Bool infeasible;
246 if( subvars[
i] ==
NULL )
276 SCIPwarningMessage(
scip,
"unfixing parameter nodeselection/dfs/stdpriority in subscip of rapidlearning\n");
355 if( subvars[
i] !=
NULL )
377 for(
i = 0;
i < nconshdlrs; ++
i)
379 if( conshdlrs[
i] !=
NULL )
401 SCIPdebugMsg(
scip,
"proceed solving after the first 20%% of the solution process, since:\n");
424 SCIPdebugMsg(
scip,
"do not proceed solving after the first 20%% of the solution process.\n");
498 for(
i = 0;
i < nconshdlrs && nconflicts <
nmaxconfs; ++
i)
553 if( subvars[
i] ==
NULL )
627 if( subvars[
i] ==
NULL )
649 SCIP_CALL(
SCIPinitVarBranchStats(
scip,
vars[
i], 0.0, 0.0,
downvsids,
upvsids,
downconflen,
upconflen,
downinfer,
upinfer, 0.0, 0.0) );
656 SCIPdebugMsg(
scip,
"Rapidlearning detected %s infeasibility.\n", global ?
"global" :
"local");
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",
671 else if( nbdchgs > 0 )
710 SCIPdebugMsg(
scip,
"-> allow local rapid learning due to global zero objective\n");
718 SCIPdebugMsg(
scip,
"-> allow local rapid learning due to no solution found so far\n");
734 SCIPdebugMsg(
scip,
"-> allow local rapid learning due to equal dualbound\n");
741 if( !(*run) &&
sepadata->checkleaves )
747 SCIPdebugMsg(
scip,
"-> allow local rapid learning due to inf/obj leaves ratio\n");
765 for(
i = 0;
i < ndiscvars;
i++ )
782 SCIPdebugMsg(
scip,
"-> allow local rapid learning due to local zero objective\n");
789 if( !(*run) &&
sepadata->checkdegeneracy )
791 SCIP_Real degeneracy;
792 SCIP_Real varconsratio;
796 SCIPdebugMsg(
scip,
"degeneracy: %.2f ratio: %.2f\n", degeneracy, varconsratio);
798 if( degeneracy >=
sepadata->mindegeneracy || varconsratio >=
sepadata->minvarconsratio )
901 SCIPdebugMsg(
scip,
"unbounded integer variable %s (in [%g,%g]) with objective %g -> skip rapid learning\n",
948 "should the found conflicts be applied in the original SCIP?",
952 "should the found global bound deductions be applied in the original SCIP?",
956 "should the inference values be used as initialization in the original SCIP?",
960 "should the inference values only be used when " SEPA_NAME " found other reductions?",
964 "should the incumbent solution be copied to the original SCIP?",
968 "should a solved status be copied to the original SCIP?",
972 "should local LP degeneracy be checked?",
976 "should the progress on the dual bound be checked?",
980 "should the ratio of leaves proven to be infeasible and exceeding the cutoff bound be checked?",
984 "check whether rapid learning should be executed",
988 "should the (local) objective function be checked?",
992 "should the number of solutions found so far be checked?",
996 "should rapid learning be applied when there are continuous variables?",
1000 "maximal portion of continuous variables to apply rapid learning",
1004 "maximal fraction of LP iterations compared to node LP iterations",
1008 "minimal degeneracy threshold to allow local rapid learning",
1012 "minimal threshold of inf/obj leaves to allow local rapid learning",
1016 "minimal ratio of unfixed variables in relation to basis size to allow local rapid learning",
1020 "maximum problem size (variables) for which rapid learning will be called",
1024 "maximum problem size (constraints) for which rapid learning will be called",
1028 "maximum number of overall calls",
1032 "maximum number of nodes considered in rapid learning run",
1036 "minimum number of nodes considered in rapid learning run",
1040 "number of nodes that should be processed before rapid learning is executed locally based on the progress of the dualbound",
1044 "should all active cuts from cutpool be copied to constraints in subproblem?",
#define SCIP_CALL_ABORT(x)
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)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
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)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
SCIP_RETCODE SCIPupdateLocalDualbound(SCIP *scip, SCIP_Real newbound)
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
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)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNActivePricers(SCIP *scip)
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)
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
int SCIPgetNSols(SCIP *scip)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
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)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
int SCIPgetNRootboundChgs(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPgetEffectiveRootDepth(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
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)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPgetVarAvgConflictlength(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
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)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
SCIP_Real SCIPgetVarVSIDS(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
SCIP_Real SCIPgetVarAvgInferences(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPincludeSepaRapidlearning(SCIP *scip)
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for problem variables
#define DEFAULT_CHECKDUALBOUND
#define DEFAULT_MAXNCONSS
#define DEFAULT_CHECKLEAVES
#define DEFAULT_MINVARCONSRATIO
#define DEFAULT_NWAITINGNODES
#define DEFAULT_CHECKEXEC
#define DEFAULT_CHECKNSOLS
#define DEFAULT_APPLYSOLVED
#define DEFAULT_CHECKDEGANERACY
#define DEFAULT_LPITERQUOT
#define DEFAULT_REDUCEDINFER
#define DEFAULT_CONTVARSQUOT
static SCIP_RETCODE setupAndSolveSubscipRapidlearning(SCIP *scip, SCIP *subscip, SCIP_SEPADATA *sepadata, int randseed, SCIP_Bool global, SCIP_RESULT *result)
#define DEFAULT_MININFLPRATIO
#define SEPA_MAXBOUNDDIST
#define DEFAULT_APPLYCONFLICTS
static SCIP_RETCODE checkExec(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *run)
#define DEFAULT_APPLYBDCHGS
#define DEFAULT_APPLYPRIMALSOL
#define DEFAULT_MINDEGENERACY
#define DEFAULT_APPLYINFERVALS
@ SCIP_BRANCHDIR_DOWNWARDS
@ SCIP_PARAMEMPHASIS_CPSOLVER
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPACOPY(x)