59#define HEUR_NAME "multistart"
60#define HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs"
61#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
62#define HEUR_PRIORITY -2100000
65#define HEUR_MAXDEPTH -1
66#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
67#define HEUR_USESSUBSCIP TRUE
69#define DEFAULT_RANDSEED 131
70#define DEFAULT_NRNDPOINTS 100
71#define DEFAULT_MAXBOUNDSIZE 2e+4
72#define DEFAULT_MAXITER 300
73#define DEFAULT_MINIMPRFAC 0.05
74#define DEFAULT_MINIMPRITER 10
75#define DEFAULT_MAXRELDIST 0.15
76#define DEFAULT_GRADLIMIT 5e+6
77#define DEFAULT_MAXNCLUSTER 3
78#define DEFAULT_ONLYNLPS TRUE
82#define MINIMPRFAC 0.95
84#define GRADCOSTFAC_LINEAR 1.0
85#define GRADCOSTFAC_NONLINEAR 3.0
95 SCIP_Real maxboundsize;
100 SCIP_Real minimprfac;
103 SCIP_Real maxreldist;
130#define getVarIndex(varindex,var) (SCIPhashmapGetImageInt((varindex), (void*)(var)))
141 SCIP_Real maxboundsize,
159 assert(maxboundsize > 0.0);
180 val = (lb + ub) / 2.0;
237 for(
i = 0;
i < nnlrows; ++
i )
323 SCIP_Real minimprfac,
351#ifdef SCIP_DEBUG_IMPROVEPOINT
358#ifdef SCIP_DEBUG_IMPROVEPOINT
359 printf(
"start point is feasible");
384 for(
i = 0;
i < nnlrows; ++
i )
406#ifdef SCIP_DEBUG_IMPROVEPOINT
407 printf(
"gradient vanished at current point -> stop\n");
446 if(
r % minimpriter == 0 &&
r > 0 )
456#ifdef SCIP_DEBUG_IMPROVEPOINT
531 SCIP_Real maxboundsize
563 lb = -maxboundsize / 2.0;
564 ub = +maxboundsize / 2.0;
568 lb = ub - maxboundsize;
572 ub = lb + maxboundsize;
582 return distance /
nvars;
593 SCIP_Real maxboundsize,
594 SCIP_Real maxreldist,
604 assert(maxreldist >= 0.0);
613 for(
i = 0;
i <
npoints && (*ncluster < maxncluster); ++
i )
804 for(
i = 0;
i < nnlrows; ++
i )
818 if( nrndpoints == 0 )
886 for(
i = nrndpoints - 1;
i >= 0 ; --
i )
1028 "number of random points generated per execution call",
1032 "maximum variable domain size for unbounded variables",
1036 "number of iterations to reduce the maximum violation of a point",
1040 "minimum required improving factor to proceed in improvement of a single point",
1044 "number of iteration when checking the minimum improvement",
1048 "maximum distance between two points in the same cluster",
1052 "limit for gradient computations for all improvePoint() calls (0 for no limit)",
1056 "maximum number of considered clusters per heuristic call",
1060 "should the heuristic run only on continuous problems?",
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_SOL *resultsol)
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 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 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 SCIPincludeHeurMultistart(SCIP *scip)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNNlpis(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPgetNlRowSolFeasibility(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *feasibility)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPgetNlRowSolActivity(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *activity)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
SCIP_RETCODE SCIPclearSol(SCIP *scip, SCIP_SOL *sol)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Real getRelDistance(SCIP *scip, SCIP_SOL *x, SCIP_SOL *y, SCIP_Real maxboundsize)
static SCIP_RETCODE getMinFeas(SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_SOL *sol, SCIP_Real *minfeas)
#define GRADCOSTFAC_NONLINEAR
#define DEFAULT_MINIMPRFAC
#define DEFAULT_MAXNCLUSTER
#define DEFAULT_MINIMPRITER
static SCIP_RETCODE sampleRandomPoints(SCIP *scip, SCIP_SOL **rndpoints, int nmaxrndpoints, SCIP_Real maxboundsize, SCIP_RANDNUMGEN *randnumgen, SCIP_Real bestobj, int *nstored)
static SCIP_RETCODE filterPoints(SCIP *scip, SCIP_SOL **points, SCIP_Real *feasibilities, int npoints, int *nusefulpoints)
static SCIP_RETCODE improvePoint(SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *varindex, SCIP_SOL *point, int maxiter, SCIP_Real minimprfac, int minimpriter, SCIP_Real *minfeas, SCIP_Real *nlrowgradcosts, SCIP_Real *gradcosts)
#define DEFAULT_MAXRELDIST
#define GRADCOSTFAC_LINEAR
static SCIP_RETCODE computeGradient(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_HASHMAP *varindex, SCIP_EXPRITER *exprit, SCIP_Real *grad, SCIP_Real *norm)
static SCIP_RETCODE applyHeur(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result)
#define DEFAULT_NRNDPOINTS
static SCIP_RETCODE solveNLP(SCIP *scip, SCIP_HEUR *heur, SCIP_HEUR *nlpheur, SCIP_SOL **points, int npoints, SCIP_Bool *success)
#define DEFAULT_GRADLIMIT
static SCIP_RETCODE clusterPointsGreedy(SCIP *scip, SCIP_SOL **points, int npoints, int *clusteridx, int *ncluster, SCIP_Real maxboundsize, SCIP_Real maxreldist, int maxncluster)
static int getExprSize(SCIP_EXPR *expr)
#define DEFAULT_MAXBOUNDSIZE
multistart heuristic for convex and nonconvex MINLPs
NLP local search primal heuristic using sub-SCIPs.
memory allocation routines
#define BMSclearMemory(ptr)
#define BMSclearMemoryArray(ptr, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public functions to work with algebraic expressions
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for NLP management
public methods for problem variables
public functions to work with algebraic expressions
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for NLPI solver interfaces
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for timing
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS