Scippy

SCIP

Solving Constraint Integer Programs

heur_multistart.c File Reference

Detailed Description

multistart heuristic for convex and nonconvex MINLPs

Author
Benjamin Mueller

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)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "multistart"

Definition at line 31 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_DESC

#define HEUR_DESC   "multistart heuristic for convex and nonconvex MINLPs"

Definition at line 32 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'm'

Definition at line 33 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2100000

Definition at line 34 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 35 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 36 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 37 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 38 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 39 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   131

initial random seed

Definition at line 41 of file heur_multistart.c.

◆ DEFAULT_NRNDPOINTS

#define DEFAULT_NRNDPOINTS   100

default number of generated random points per call

Definition at line 42 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 43 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 44 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 45 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 46 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 47 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 48 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 49 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 50 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 51 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 53 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 56 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 59 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 60 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 61 of file heur_multistart.c.

Referenced by applyHeur().

Function Documentation

◆ getVarIndex()

static int getVarIndex ( SCIP_HASHMAP varindex,
SCIP_VAR var 
)
static

returns an unique index of a variable in the range of 0,..,SCIPgetNVars(scip)-1

Parameters
varindexmaps variables to indicies between 0,..,SCIPgetNVars(scip)-1
varvariable

Definition at line 96 of file heur_multistart.c.

References sampleRandomPoints(), SCIPhashmapExists(), and SCIPhashmapGetImage().

Referenced by computeGradient().

◆ sampleRandomPoints()

static SCIP_RETCODE sampleRandomPoints ( SCIP scip,
SCIP_SOL **  rndpoints,
int  nmaxrndpoints,
SCIP_Real  maxboundsize,
SCIP_RANDNUMGEN randnumgen,
SCIP_Real  bestobj,
int *  nstored 
)
static

samples and stores random points; stores points which have a better objective value than the current incumbent solution

Parameters
scipSCIP data structure
rndpointsarray to store all random points
nmaxrndpointsmaximum number of random points to compute
maxboundsizemaximum variable domain size for unbounded variables
randnumgenrandom number generator
bestobjobjective value in the transformed space of the current incumbent
nstoredpointer 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().

◆ getMinFeas()

static SCIP_RETCODE getMinFeas ( SCIP scip,
SCIP_NLROW **  nlrows,
int  nnlrows,
SCIP_SOL sol,
SCIP_Real minfeas 
)
static

computes the minimum feasibility of a given point; a negative value means that there is an infeasibility

Parameters
scipSCIP data structure
nlrowsarray containing all nlrows
nnlrowstotal number of nlrows
solsolution
minfeasbuffer 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().

◆ computeGradient()

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

computes the gradient for a given point and nonlinear row

Parameters
scipSCIP data structure
nlrownonlinear row
exprintexpressions interpreter
solsolution to compute the gradient for
varindexmaps variables to indicies between 0,..,SCIPgetNVars(scip)-1 uniquely
gradbuffer to store the gradient; grad[varindex(i)] corresponds to SCIPgetVars(scip)[i]
normbuffer 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().

◆ improvePoint()

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

use consensus vectors to improve feasibility for a given starting point

Parameters
scipSCIP data structure
nlrowsarray containing all nlrows
nnlrowstotal number of nlrows
varindexmaps variables to indicies between 0,..,SCIPgetNVars(scip)-1
exprinterpreterexpression interpreter
pointrandom generated point
maxitermaximum number of iterations
minimprfacminimum required improving factor to proceed in the improvement of a single point
minimpriternumber of iteration when checking the minimum improvement
minfeaspointer to store the minimum feasibility
nlrowgradcostsestimated costs for each gradient computation
gradcostspointer 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().

◆ filterPoints()

static SCIP_RETCODE filterPoints ( SCIP scip,
SCIP_SOL **  points,
SCIP_Real feasibilities,
int  npoints,
int *  nusefulpoints 
)
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
scipSCIP data structure
pointsarray containing improved points
feasibilitiesarray containing feasibility for each point (sorted)
npointstotal number of points
nusefulpointspointer 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().

◆ getRelDistance()

static SCIP_Real getRelDistance ( SCIP scip,
SCIP_SOL x,
SCIP_SOL y,
SCIP_Real  maxboundsize 
)
static

returns the relative distance between two points; considers a smaller bounded domain for unbounded variables

Parameters
scipSCIP data structure
xfirst point
ysecond point
maxboundsizemaximum 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().

◆ clusterPointsGreedy()

static SCIP_RETCODE clusterPointsGreedy ( SCIP scip,
SCIP_SOL **  points,
int  npoints,
int *  clusteridx,
int *  ncluster,
SCIP_Real  maxboundsize,
SCIP_Real  maxreldist,
int  maxncluster 
)
static

cluster useful points with a greedy algorithm

Parameters
scipSCIP data structure
pointsarray containing improved points
npointstotal number of points
clusteridxarray to store for each point the index of the cluster
nclusterpointer to store the total number of cluster
maxboundsizemaximum variable domain size for unbounded variables
maxreldistmaximum relative distance between any two points of the same cluster
maxnclustermaximum 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().

◆ solveNLP()

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

calls the sub-NLP heuristic for a given cluster

Parameters
scipSCIP data structure
heurmulti-start heuristic
nlpheurpointer to NLP local search heuristics
pointsarray containing improved points
npointstotal number of points
itercontingentiteration limit for NLP solver
timelimittime limit for NLP solver
minimprovedesired minimal relative improvement in objective function value
successpointer 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().

◆ getExprSize()

static int getExprSize ( SCIP_EXPR expr)
static

recursive helper function to count the number of nodes in a sub-tree

Parameters
exprexpression

Definition at line 728 of file heur_multistart.c.

References getExprtreeSize(), SCIPexprGetChildren(), and SCIPexprGetNChildren().

Referenced by getExprtreeSize(), and solveNLP().

◆ getExprtreeSize()

static int getExprtreeSize ( SCIP_EXPRTREE tree)
static

returns the number of nodes in an expression tree

Parameters
treeexpression tree

Definition at line 748 of file heur_multistart.c.

References applyHeur(), getExprSize(), and SCIPexprtreeGetRoot().

Referenced by applyHeur(), and getExprSize().

◆ applyHeur()

static SCIP_RETCODE applyHeur ( SCIP scip,
SCIP_HEUR heur,
SCIP_HEURDATA heurdata,
SCIP_RESULT result 
)
static

main function of the multi-start heuristic (see heur_multistart.h for more details); it consists of the following four steps:

  1. sampling points in the current domain; for unbounded variables we use a bounded box
  2. reduce infeasibility by using a gradient descent method
  3. cluster points; filter points with a too large infeasibility
  4. compute start point for each cluster and use it in the sub-NLP heuristic (heur_subnlp.h)
Parameters
scipSCIP data structure
heurheuristic
heurdataheuristic data
resultpointer 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().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyMultistart  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 937 of file heur_multistart.c.

Referenced by applyHeur().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeMultistart  )
static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 949 of file heur_multistart.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitMultistart  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 969 of file heur_multistart.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitMultistart  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 989 of file heur_multistart.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecMultistart  )
static

execution method of primal heuristic

Definition at line 1006 of file heur_multistart.c.