multistart heuristic for convex and nonconvex MINLPs
Definition in file heur_multistart.c.
#include <assert.h>
#include <string.h>
#include "scip/heur_multistart.h"
#include "scip/heur_subnlp.h"
#include "nlpi/exprinterpret.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "multistart" |
#define | HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs" |
#define | HEUR_DISPCHAR 'm' |
#define | HEUR_PRIORITY -2100000 |
#define | HEUR_FREQ 0 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_RANDSEED 131 |
#define | DEFAULT_NRNDPOINTS 100 |
#define | DEFAULT_MAXBOUNDSIZE 2e+4 |
#define | DEFAULT_MAXITER 300 |
#define | DEFAULT_MINIMPRFAC 0.05 |
#define | DEFAULT_MINIMPRITER 10 |
#define | DEFAULT_MAXRELDIST 0.15 |
#define | DEFAULT_NLPMINIMPR 0.00 |
#define | DEFAULT_GRADLIMIT 5e+6 |
#define | DEFAULT_MAXNCLUSTER 3 |
#define | DEFAULT_ONLYNLPS TRUE |
#define | MINFEAS -1e+4 |
#define | MINIMPRFAC 0.95 |
#define | GRADCOSTFAC_LINEAR 1.0 |
#define | GRADCOSTFAC_QUAD 2.0 |
#define | GRADCOSTFAC_NONLINEAR 3.0 |
Functions | |
static int | getVarIndex (SCIP_HASHMAP *varindex, SCIP_VAR *var) |
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 | getMinFeas (SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_SOL *sol, SCIP_Real *minfeas) |
static SCIP_RETCODE | computeGradient (SCIP *scip, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, SCIP_SOL *sol, SCIP_HASHMAP *varindex, SCIP_Real *grad, SCIP_Real *norm) |
static SCIP_RETCODE | improvePoint (SCIP *scip, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *varindex, SCIP_EXPRINT *exprinterpreter, SCIP_SOL *point, int maxiter, SCIP_Real minimprfac, int minimpriter, SCIP_Real *minfeas, SCIP_Real *nlrowgradcosts, SCIP_Real *gradcosts) |
static SCIP_RETCODE | filterPoints (SCIP *scip, SCIP_SOL **points, SCIP_Real *feasibilities, int npoints, int *nusefulpoints) |
static SCIP_Real | getRelDistance (SCIP *scip, SCIP_SOL *x, SCIP_SOL *y, SCIP_Real maxboundsize) |
static SCIP_RETCODE | clusterPointsGreedy (SCIP *scip, SCIP_SOL **points, int npoints, int *clusteridx, int *ncluster, SCIP_Real maxboundsize, SCIP_Real maxreldist, int maxncluster) |
static SCIP_RETCODE | solveNLP (SCIP *scip, SCIP_HEUR *heur, SCIP_HEUR *nlpheur, SCIP_SOL **points, int npoints, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Bool *success) |
static int | getExprSize (SCIP_EXPR *expr) |
static int | getExprtreeSize (SCIP_EXPRTREE *tree) |
static SCIP_RETCODE | applyHeur (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result) |
static | SCIP_DECL_HEURCOPY (heurCopyMultistart) |
static | SCIP_DECL_HEURFREE (heurFreeMultistart) |
static | SCIP_DECL_HEURINIT (heurInitMultistart) |
static | SCIP_DECL_HEUREXIT (heurExitMultistart) |
static | SCIP_DECL_HEUREXEC (heurExecMultistart) |
SCIP_RETCODE | SCIPincludeHeurMultistart (SCIP *scip) |
#define HEUR_NAME "multistart" |
Definition at line 31 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs" |
Definition at line 32 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_DISPCHAR 'm' |
Definition at line 33 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_PRIORITY -2100000 |
Definition at line 34 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_FREQ 0 |
Definition at line 35 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_FREQOFS 0 |
Definition at line 36 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_MAXDEPTH -1 |
Definition at line 37 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 38 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 39 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_RANDSEED 131 |
initial random seed
Definition at line 41 of file heur_multistart.c.
#define DEFAULT_NRNDPOINTS 100 |
default number of generated random points per call
Definition at line 42 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXBOUNDSIZE 2e+4 |
default maximum variable domain size for unbounded variables
Definition at line 43 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXITER 300 |
default number of iterations to reduce the violation of a point
Definition at line 44 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MINIMPRFAC 0.05 |
default minimum required improving factor to proceed in improvement of a point
Definition at line 45 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MINIMPRITER 10 |
default number of iteration when checking the minimum improvement
Definition at line 46 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXRELDIST 0.15 |
default maximum distance between two points in the same cluster
Definition at line 47 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_NLPMINIMPR 0.00 |
default factor by which heuristic should at least improve the incumbent
Definition at line 48 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_GRADLIMIT 5e+6 |
default limit for gradient computations for all improvePoint() calls
Definition at line 49 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXNCLUSTER 3 |
default maximum number of considered clusters per heuristic call
Definition at line 50 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_ONLYNLPS TRUE |
should the heuristic run only on continuous problems?
Definition at line 51 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define MINFEAS -1e+4 |
minimum feasibility for a point; used for filtering and improving feasibility
Definition at line 53 of file heur_multistart.c.
Referenced by filterPoints(), and improvePoint().
#define MINIMPRFAC 0.95 |
improvement factor used to discard randomly generated points with a too large objective value
Definition at line 56 of file heur_multistart.c.
Referenced by applyHeur().
#define GRADCOSTFAC_LINEAR 1.0 |
gradient cost factor for the number of linear variables
Definition at line 59 of file heur_multistart.c.
Referenced by applyHeur().
#define GRADCOSTFAC_QUAD 2.0 |
gradient cost factor for the number of quadratic terms
Definition at line 60 of file heur_multistart.c.
Referenced by applyHeur().
#define GRADCOSTFAC_NONLINEAR 3.0 |
gradient cost factor for the number of nodes in nonlinear expression
Definition at line 61 of file heur_multistart.c.
Referenced by applyHeur().
|
static |
returns an unique index of a variable in the range of 0,..,SCIPgetNVars(scip)-1
varindex | maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 |
var | variable |
Definition at line 96 of file heur_multistart.c.
References sampleRandomPoints(), SCIPhashmapExists(), and SCIPhashmapGetImage().
Referenced by computeGradient().
|
static |
samples and stores random points; stores points which have a better objective value than the current incumbent solution
scip | SCIP data structure |
rndpoints | array to store all random points |
nmaxrndpoints | maximum number of random points to compute |
maxboundsize | maximum variable domain size for unbounded variables |
randnumgen | random number generator |
bestobj | objective value in the transformed space of the current incumbent |
nstored | pointer to store the number of randomly generated points |
Definition at line 115 of file heur_multistart.c.
References getMinFeas(), MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPcreateSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfeasRound(), SCIPfreeSol(), SCIPgetNVars(), SCIPgetSolTransObj(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLE(), SCIPrandomGetReal(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetType(), and SCIPvarGetUbLocal().
Referenced by applyHeur(), and getVarIndex().
|
static |
computes the minimum feasibility of a given point; a negative value means that there is an infeasibility
scip | SCIP data structure |
nlrows | array containing all nlrows |
nnlrows | total number of nlrows |
sol | solution |
minfeas | buffer to store the minimum feasibility |
Definition at line 193 of file heur_multistart.c.
References computeGradient(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNlRowSolFeasibility(), and SCIPinfinity().
Referenced by improvePoint(), and sampleRandomPoints().
|
static |
computes the gradient for a given point and nonlinear row
scip | SCIP data structure |
nlrow | nonlinear row |
exprint | expressions interpreter |
sol | solution to compute the gradient for |
varindex | maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 uniquely |
grad | buffer to store the gradient; grad[varindex(i)] corresponds to SCIPgetVars(scip)[i] |
norm | buffer to store ||grad||^2 |
Definition at line 225 of file heur_multistart.c.
References BMSclearMemoryArray, SCIP_QuadElement::coef, getVarIndex(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, improvePoint(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSolVal(), SCIPnlrowGetExprtree(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), and TRUE.
Referenced by getMinFeas(), and improvePoint().
|
static |
use consensus vectors to improve feasibility for a given starting point
scip | SCIP data structure |
nlrows | array containing all nlrows |
nnlrows | total number of nlrows |
varindex | maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 |
exprinterpreter | expression interpreter |
point | random generated point |
maxiter | maximum number of iterations |
minimprfac | minimum required improving factor to proceed in the improvement of a single point |
minimpriter | number of iteration when checking the minimum improvement |
minfeas | pointer to store the minimum feasibility |
nlrowgradcosts | estimated costs for each gradient computation |
gradcosts | pointer to store the estimated gradient costs |
Definition at line 325 of file heur_multistart.c.
References BMSclearMemoryArray, computeGradient(), filterPoints(), getMinFeas(), MAX, MINFEAS, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNlRowSolActivity(), SCIPgetNlRowSolFeasibility(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLT(), SCIPisGT(), SCIPisHugeValue(), SCIPisInfinity(), SCIPisZero(), SCIPnlrowGetRhs(), SCIPsetSolVal(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by applyHeur(), and computeGradient().
|
static |
sorts points w.r.t their feasibilities; points with a feasibility which is too small (w.r.t. the geometric mean of all feasibilities) will be filtered out
scip | SCIP data structure |
points | array containing improved points |
feasibilities | array containing feasibility for each point (sorted) |
npoints | total number of points |
nusefulpoints | pointer to store the total number of useful points |
Definition at line 473 of file heur_multistart.c.
References getRelDistance(), MINFEAS, npoints, pow(), SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisLE(), and SCIPsortDownRealPtr().
Referenced by applyHeur(), and improvePoint().
|
static |
returns the relative distance between two points; considers a smaller bounded domain for unbounded variables
scip | SCIP data structure |
x | first point |
y | second point |
maxboundsize | maximum variable domain size for unbounded variables |
Definition at line 528 of file heur_multistart.c.
References clusterPointsGreedy(), MAX, REALABS, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisInfinity(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by clusterPointsGreedy(), and filterPoints().
|
static |
cluster useful points with a greedy algorithm
scip | SCIP data structure |
points | array containing improved points |
npoints | total number of points |
clusteridx | array to store for each point the index of the cluster |
ncluster | pointer to store the total number of cluster |
maxboundsize | maximum variable domain size for unbounded variables |
maxreldist | maximum relative distance between any two points of the same cluster |
maxncluster | maximum number of clusters to compute |
Definition at line 584 of file heur_multistart.c.
References getRelDistance(), npoints, SCIP_OKAY, and solveNLP().
Referenced by applyHeur(), and getRelDistance().
|
static |
calls the sub-NLP heuristic for a given cluster
scip | SCIP data structure |
heur | multi-start heuristic |
nlpheur | pointer to NLP local search heuristics |
points | array containing improved points |
npoints | total number of points |
itercontingent | iteration limit for NLP solver |
timelimit | time limit for NLP solver |
minimprove | desired minimal relative improvement in objective function value |
success | pointer to store if we could find a solution |
Definition at line 643 of file heur_multistart.c.
References FALSE, getExprSize(), MAX, npoints, SCIP_CALL, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPapplyHeurSubNlp(), SCIPcreateSol(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPround(), SCIProundSol(), SCIPsetSolVal(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by applyHeur(), and clusterPointsGreedy().
|
static |
recursive helper function to count the number of nodes in a sub-tree
expr | expression |
Definition at line 728 of file heur_multistart.c.
References getExprtreeSize(), SCIPexprGetChildren(), and SCIPexprGetNChildren().
Referenced by getExprtreeSize(), and solveNLP().
|
static |
returns the number of nodes in an expression tree
tree | expression tree |
Definition at line 748 of file heur_multistart.c.
References applyHeur(), getExprSize(), and SCIPexprtreeGetRoot().
Referenced by applyHeur(), and getExprSize().
|
static |
main function of the multi-start heuristic (see heur_multistart.h for more details); it consists of the following four steps:
scip | SCIP data structure |
heur | heuristic |
heurdata | heuristic data |
result | pointer to store the result |
Definition at line 769 of file heur_multistart.c.
References clusterPointsGreedy(), filterPoints(), getExprtreeSize(), GRADCOSTFAC_LINEAR, GRADCOSTFAC_NONLINEAR, GRADCOSTFAC_QUAD, improvePoint(), MINIMPRFAC, npoints, sampleRandomPoints(), SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURCOPY(), SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPexprintCreate(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolTransObj(), SCIPgetSolvingTime(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPinfinity(), SCIPisInfinity(), SCIPisStopped(), SCIPnlrowGetExprtree(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPsortIntPtr(), and solveNLP().
Referenced by getExprtreeSize().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 937 of file heur_multistart.c.
Referenced by applyHeur().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 949 of file heur_multistart.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 969 of file heur_multistart.c.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 989 of file heur_multistart.c.
|
static |
execution method of primal heuristic
Definition at line 1006 of file heur_multistart.c.