multistart heuristic for convex and nonconvex MINLPs
Definition in file heur_multistart.c.
#include "blockmemshell/memory.h"
#include "scip/scip_expr.h"
#include "scip/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_nlpi.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_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_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_SOL *sol, SCIP_HASHMAP *varindex, SCIP_EXPRITER *exprit, SCIP_Real *grad, SCIP_Real *norm) |
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) |
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_Bool *success) |
static int | getExprSize (SCIP_EXPR *expr) |
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 59 of file heur_multistart.c.
#define HEUR_DESC "multistart heuristic for convex and nonconvex MINLPs" |
Definition at line 60 of file heur_multistart.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 61 of file heur_multistart.c.
#define HEUR_PRIORITY -2100000 |
Definition at line 62 of file heur_multistart.c.
#define HEUR_FREQ 0 |
Definition at line 63 of file heur_multistart.c.
#define HEUR_FREQOFS 0 |
Definition at line 64 of file heur_multistart.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 65 of file heur_multistart.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 66 of file heur_multistart.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 67 of file heur_multistart.c.
#define DEFAULT_RANDSEED 131 |
initial random seed
Definition at line 69 of file heur_multistart.c.
#define DEFAULT_NRNDPOINTS 100 |
default number of generated random points per call
Definition at line 70 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXBOUNDSIZE 2e+4 |
default maximum variable domain size for unbounded variables
Definition at line 71 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 72 of file heur_multistart.c.
#define DEFAULT_MINIMPRFAC 0.05 |
default minimum required improving factor to proceed in improvement of a point
Definition at line 73 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MINIMPRITER 10 |
default number of iteration when checking the minimum improvement
Definition at line 74 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 75 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 76 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_MAXNCLUSTER 3 |
default maximum number of considered clusters per heuristic call
Definition at line 77 of file heur_multistart.c.
Referenced by SCIPincludeHeurMultistart().
#define DEFAULT_ONLYNLPS TRUE |
should the heuristic run only on continuous problems?
Definition at line 78 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 80 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 82 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 84 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 85 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 118 of file heur_multistart.c.
References assert(), NULL, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and var.
|
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 137 of file heur_multistart.c.
References assert(), i, MAX, MIN, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPclearSol(), SCIPcreateSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfeasRound(), SCIPfreeSol(), SCIPgetNVars(), SCIPgetSolTransObj(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisLE(), SCIPrandomGetReal(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), sol, and vars.
Referenced by applyHeur().
|
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 218 of file heur_multistart.c.
References assert(), i, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNlRowSolFeasibility(), SCIPinfinity(), and sol.
Referenced by improvePoint().
|
static |
computes the gradient for a given point and nonlinear row
scip | SCIP data structure |
nlrow | nonlinear row |
sol | solution to compute the gradient for |
varindex | maps variables to indicies between 0,..,SCIPgetNVars(scip)-1 uniquely |
exprit | expression iterator that can be used |
grad | buffer to store the gradient; grad[varindex(i)] corresponds to SCIPgetVars(scip)[i] |
norm | buffer to store ||grad||^2 |
Definition at line 250 of file heur_multistart.c.
References assert(), BMSclearMemoryArray, FALSE, getVarIndex, i, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIP_Real, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPnlrowGetExpr(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), sol, SQR, and var.
Referenced by 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 |
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 316 of file heur_multistart.c.
References assert(), BMSclearMemoryArray, computeGradient(), getMinFeas(), i, MAX, MIN, MINFEAS, NULL, nvars, r, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateExpriter(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetNlRowSolActivity(), SCIPgetNlRowSolFeasibility(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLT(), SCIPisGT(), SCIPisHugeValue(), SCIPisInfinity(), SCIPisZero(), SCIPnlrowGetRhs(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and vars.
Referenced by applyHeur().
|
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 472 of file heur_multistart.c.
References assert(), i, MINFEAS, NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisLE(), and SCIPsortDownRealPtr().
Referenced by applyHeur().
|
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 527 of file heur_multistart.c.
References assert(), i, MAX, MIN, NULL, nvars, REALABS, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), vars, x, and y.
Referenced by clusterPointsGreedy().
|
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 587 of file heur_multistart.c.
References assert(), getRelDistance(), i, NULL, SCIP_OKAY, and SCIP_Real.
Referenced by applyHeur().
|
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 |
success | pointer to store if we could find a solution |
Definition at line 646 of file heur_multistart.c.
References assert(), FALSE, i, MAX, MIN, nbinvars, nintvars, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPapplyHeurSubNlp(), SCIPcreateSol(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPround(), SCIProundSol(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and vars.
Referenced by applyHeur().
|
static |
recursive helper function to count the number of nodes in a sub-expr
expr | expression |
Definition at line 727 of file heur_multistart.c.
References assert(), getExprSize(), i, NULL, SCIPexprGetChildren(), and SCIPexprGetNChildren().
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 757 of file heur_multistart.c.
References assert(), clusterPointsGreedy(), filterPoints(), getExprSize(), GRADCOSTFAC_LINEAR, GRADCOSTFAC_NONLINEAR, heurdata, i, improvePoint(), MINIMPRFAC, NULL, result, sampleRandomPoints(), SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSolTransObj(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPisStopped(), SCIPnlrowGetExpr(), SCIPnlrowGetNLinearVars(), SCIPsortIntPtr(), and solveNLP().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 907 of file heur_multistart.c.
References assert(), HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMultistart().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 919 of file heur_multistart.c.
References heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 934 of file heur_multistart.c.
References assert(), DEFAULT_RANDSEED, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfindHeur(), SCIPheurGetData(), and TRUE.
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 954 of file heur_multistart.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 971 of file heur_multistart.c.
References applyHeur(), assert(), heurdata, NULL, result, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNNlpis(), SCIPheurGetData(), and SCIPisNLPConstructed().