Detailed Description
multistart heuristic for convex and nonconvex MINLPs
Definition in file heur_multistart.c.
#include "blockmemshell/memory.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/pub_expr.h"
#include "scip/heur_multistart.h"
#include "scip/heur_subnlp.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_timing.h"
#include <string.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 SCIP_HEURDISPCHAR_LNS |
#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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "multistart" |
Definition at line 49 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_DESC
#define HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs" |
Definition at line 50 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 51 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -2100000 |
Definition at line 52 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_FREQ
#define HEUR_FREQ 0 |
Definition at line 53 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 54 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 55 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 56 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 57 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 131 |
initial random seed
Definition at line 59 of file heur_multistart.c.
◆ DEFAULT_NRNDPOINTS
#define DEFAULT_NRNDPOINTS 100 |
default number of generated random points per call
Definition at line 60 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MAXBOUNDSIZE
#define DEFAULT_MAXBOUNDSIZE 2e+4 |
default maximum variable domain size for unbounded variables
Definition at line 61 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MAXITER
#define DEFAULT_MAXITER 300 |
default number of iterations to reduce the violation of a point
Definition at line 62 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MINIMPRFAC
#define DEFAULT_MINIMPRFAC 0.05 |
default minimum required improving factor to proceed in improvement of a point
Definition at line 63 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MINIMPRITER
#define DEFAULT_MINIMPRITER 10 |
default number of iteration when checking the minimum improvement
Definition at line 64 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MAXRELDIST
#define DEFAULT_MAXRELDIST 0.15 |
default maximum distance between two points in the same cluster
Definition at line 65 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_NLPMINIMPR
#define DEFAULT_NLPMINIMPR 0.00 |
default factor by which heuristic should at least improve the incumbent
Definition at line 66 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_GRADLIMIT
#define DEFAULT_GRADLIMIT 5e+6 |
default limit for gradient computations for all improvePoint() calls
Definition at line 67 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_MAXNCLUSTER
#define DEFAULT_MAXNCLUSTER 3 |
default maximum number of considered clusters per heuristic call
Definition at line 68 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ DEFAULT_ONLYNLPS
#define DEFAULT_ONLYNLPS TRUE |
should the heuristic run only on continuous problems?
Definition at line 69 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
◆ MINFEAS
#define MINFEAS -1e+4 |
minimum feasibility for a point; used for filtering and improving feasibility
Definition at line 71 of file heur_multistart.c.
Referenced by filterPoints(), and improvePoint().
◆ MINIMPRFAC
#define MINIMPRFAC 0.95 |
improvement factor used to discard randomly generated points with a too large objective value
Definition at line 74 of file heur_multistart.c.
Referenced by applyHeur().
◆ GRADCOSTFAC_LINEAR
#define GRADCOSTFAC_LINEAR 1.0 |
gradient cost factor for the number of linear variables
Definition at line 77 of file heur_multistart.c.
Referenced by applyHeur().
◆ GRADCOSTFAC_QUAD
#define GRADCOSTFAC_QUAD 2.0 |
gradient cost factor for the number of quadratic terms
Definition at line 78 of file heur_multistart.c.
Referenced by applyHeur().
◆ GRADCOSTFAC_NONLINEAR
#define GRADCOSTFAC_NONLINEAR 3.0 |
gradient cost factor for the number of nodes in nonlinear expression
Definition at line 79 of file heur_multistart.c.
Referenced by applyHeur().
Function Documentation
◆ getVarIndex()
|
static |
returns an unique index of a variable in the range of 0,..,SCIPgetNVars(scip)-1
- Parameters
-
varindex maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 var variable
Definition at line 114 of file heur_multistart.c.
References NULL, sampleRandomPoints(), SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by computeGradient().
◆ sampleRandomPoints()
|
static |
samples and stores random points; stores points which have a better objective value than the current incumbent solution
- Parameters
-
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 133 of file heur_multistart.c.
References getMinFeas(), MAX, NULL, 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().
◆ getMinFeas()
|
static |
computes the minimum feasibility of a given point; a negative value means that there is an infeasibility
- Parameters
-
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 211 of file heur_multistart.c.
References computeGradient(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNlRowSolFeasibility(), and SCIPinfinity().
Referenced by improvePoint(), and sampleRandomPoints().
◆ computeGradient()
|
static |
computes the gradient for a given point and nonlinear row
- Parameters
-
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 243 of file heur_multistart.c.
References BMSclearMemoryArray, SCIP_QuadElement::coef, getVarIndex(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, improvePoint(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetSolVal(), SCIPnlrowGetExprtree(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), TRUE, and x.
Referenced by getMinFeas(), and improvePoint().
◆ improvePoint()
|
static |
use consensus vectors to improve feasibility for a given starting point
- Parameters
-
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 344 of file heur_multistart.c.
References BMSclearMemoryArray, computeGradient(), filterPoints(), getMinFeas(), MAX, MINFEAS, NULL, r, 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().
◆ filterPoints()
|
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
- Parameters
-
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 492 of file heur_multistart.c.
References getRelDistance(), MINFEAS, npoints, NULL, pow(), SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisLE(), and SCIPsortDownRealPtr().
Referenced by applyHeur(), and improvePoint().
◆ getRelDistance()
|
static |
returns the relative distance between two points; considers a smaller bounded domain for unbounded variables
- Parameters
-
scip SCIP data structure x first point y second point maxboundsize maximum variable domain size for unbounded variables
Definition at line 547 of file heur_multistart.c.
References clusterPointsGreedy(), MAX, NULL, REALABS, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisInfinity(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by clusterPointsGreedy(), and filterPoints().
◆ clusterPointsGreedy()
|
static |
cluster useful points with a greedy algorithm
- Parameters
-
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 603 of file heur_multistart.c.
References getRelDistance(), npoints, NULL, SCIP_OKAY, and solveNLP().
Referenced by applyHeur(), and getRelDistance().
◆ solveNLP()
|
static |
calls the sub-NLP heuristic for a given cluster
- Parameters
-
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 662 of file heur_multistart.c.
References FALSE, getExprSize(), MAX, npoints, NULL, 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().
◆ getExprSize()
|
static |
recursive helper function to count the number of nodes in a sub-tree
- Parameters
-
expr expression
Definition at line 747 of file heur_multistart.c.
References getExprtreeSize(), NULL, SCIPexprGetChildren(), and SCIPexprGetNChildren().
Referenced by getExprtreeSize(), and solveNLP().
◆ getExprtreeSize()
|
static |
returns the number of nodes in an expression tree
- Parameters
-
tree expression tree
Definition at line 767 of file heur_multistart.c.
References applyHeur(), getExprSize(), NULL, and SCIPexprtreeGetRoot().
Referenced by applyHeur(), and getExprSize().
◆ applyHeur()
|
static |
main function of the multi-start heuristic (see heur_multistart.h for more details); it consists of the following four steps:
- sampling points in the current domain; for unbounded variables we use a bounded box
- reduce infeasibility by using a gradient descent method
- cluster points; filter points with a too large infeasibility
- compute start point for each cluster and use it in the sub-NLP heuristic (heur_subnlp.h)
- Parameters
-
scip SCIP data structure heur heuristic heurdata heuristic data result pointer to store the result
Definition at line 788 of file heur_multistart.c.
References clusterPointsGreedy(), filterPoints(), getExprtreeSize(), GRADCOSTFAC_LINEAR, GRADCOSTFAC_NONLINEAR, GRADCOSTFAC_QUAD, improvePoint(), MINIMPRFAC, npoints, NULL, 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(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPisInfinity(), SCIPisStopped(), SCIPnlrowGetExprtree(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPsortIntPtr(), and solveNLP().
Referenced by getExprtreeSize().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 956 of file heur_multistart.c.
Referenced by applyHeur().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 968 of file heur_multistart.c.
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 988 of file heur_multistart.c.
◆ SCIP_DECL_HEUREXIT()
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 1008 of file heur_multistart.c.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 1025 of file heur_multistart.c.