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
130#define getVarIndex(varindex,var) (SCIPhashmapGetImageInt((varindex), (void*)(var)))
158 assert(nmaxrndpoints > 0);
159 assert(maxboundsize > 0.0);
169 for( niter = 0; niter < 3 * nmaxrndpoints && *nstored < nmaxrndpoints; ++niter )
180 val = (lb + ub) / 2.0;
208 assert(*nstored <= nmaxrndpoints);
237 for(
i = 0;
i < nnlrows; ++
i )
242 *minfeas =
MIN(*minfeas, tmp);
309 *norm +=
SQR(grad[
i]);
351#ifdef SCIP_DEBUG_IMPROVEPOINT
352 printf(
"start minfeas = %e\n", *minfeas);
358#ifdef SCIP_DEBUG_IMPROVEPOINT
359 printf(
"start point is feasible");
364 lastminfeas = *minfeas;
384 for(
i = 0;
i < nnlrows; ++
i )
401 *gradcosts += nlrowgradcosts[
i];
406#ifdef SCIP_DEBUG_IMPROVEPOINT
407 printf(
"gradient vanished at current point -> stop\n");
413 scale = -feasibility / nlrownorm;
421 for( j = 0; j <
nvars; ++j )
422 updatevec[j] += scale * grad[j];
426 if( nviolnlrows == 0 )
446 if(
r % minimpriter == 0 &&
r > 0 )
449 || (*minfeas-lastminfeas) /
MAX(
REALABS(*minfeas),
REALABS(lastminfeas)) < minimprfac )
451 lastminfeas = *minfeas;
456#ifdef SCIP_DEBUG_IMPROVEPOINT
457 printf(
"niter=%d minfeas=%e\n",
r, *minfeas);
491 minfeas = feasibilities[npoints - 1];
496 *nusefulpoints = npoints;
504 for(
i = 0;
i < npoints; ++
i )
506 assert(feasibilities[
i] - minfeas + 1.0 > 0.0);
507 meanfeas *= pow(feasibilities[
i] - minfeas + 1.0, 1.0 / npoints);
509 meanfeas += minfeas - 1.0;
513 for(
i = 0;
i < npoints; ++
i )
563 lb = -maxboundsize / 2.0;
564 ub = +maxboundsize / 2.0;
568 lb = ub - maxboundsize;
572 ub = lb + maxboundsize;
576 solx =
MIN(
MAX(solx, lb), ub);
577 soly =
MIN(
MAX(soly, lb), ub);
579 distance +=
REALABS(solx - soly) /
MAX(1.0, ub - lb);
582 return distance /
nvars;
604 assert(maxreldist >= 0.0);
608 for(
i = 0;
i < npoints; ++
i )
609 clusteridx[
i] = INT_MAX;
613 for(
i = 0;
i < npoints && (*ncluster < maxncluster); ++
i )
618 if( clusteridx[
i] != INT_MAX )
622 clusteridx[
i] = *ncluster;
624 for( j =
i + 1; j < npoints; ++j )
626 if( clusteridx[j] == INT_MAX &&
getRelDistance(
scip, points[
i], points[j], maxboundsize) <= maxreldist )
627 clusteridx[j] = *ncluster;
634 for(
i = 0;
i < npoints; ++
i )
637 assert(clusteridx[
i] < *ncluster || clusteridx[
i] == INT_MAX);
679 for( p = 0; p < npoints; ++p )
804 for(
i = 0;
i < nnlrows; ++
i )
815 bestobj, &nrndpoints) );
818 if( nrndpoints == 0 )
825 for( npoints = 0; npoints < nrndpoints && gradlimit >= 0 && !
SCIPisStopped(
scip); ++npoints )
833 gradlimit -= gradcosts;
834 SCIPdebugMsg(
scip,
"improve point %d / %d gradlimit = %g\n", npoints, nrndpoints, gradlimit);
836 assert(npoints >= 0 && npoints <= nrndpoints);
845 assert(nusefulpoints >= 0);
848 if( nusefulpoints == 0 )
853 assert(ncluster >= 0 && ncluster <= heurdata->maxncluster);
862 while( start < nusefulpoints && clusteridx[start] != INT_MAX && !
SCIPisStopped(
scip) )
868 while( end < nusefulpoints && clusteridx[start] == clusteridx[end] )
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
struct SCIP_Expr SCIP_EXPR
struct SCIP_ExprIter SCIP_EXPRITER
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_HashMap SCIP_HASHMAP
struct SCIP_RandNumGen SCIP_RANDNUMGEN
struct SCIP_NlRow SCIP_NLROW
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS