Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

multistart heuristic for convex and nonconvex MINLPs

Author
Benjamin Mueller

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)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "multistart"

Definition at line 59 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_DESC

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

Definition at line 60 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS

Definition at line 61 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -2100000

Definition at line 62 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 63 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 64 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 65 of file heur_multistart.c.

Referenced by SCIPincludeHeurMultistart().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

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

Referenced by SCIPincludeHeurMultistart().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   131

initial random seed

Definition at line 69 of file heur_multistart.c.

◆ DEFAULT_NRNDPOINTS

#define DEFAULT_NRNDPOINTS   100

default number of generated random points per call

Definition at line 70 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 71 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 72 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 73 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 74 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 75 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 76 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 77 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 78 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 80 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 83 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 86 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 87 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 120 of file heur_multistart.c.

References NULL, sampleRandomPoints(), SCIPhashmapExists(), and SCIPhashmapGetImageInt().

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 139 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 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 217 of file heur_multistart.c.

References computeGradient(), NULL, 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_SOL sol,
SCIP_HASHMAP varindex,
SCIP_EXPRITER exprit,
SCIP_Real grad,
SCIP_Real norm 
)
static

computes the gradient for a given point and nonlinear row

Parameters
scipSCIP data structure
nlrownonlinear row
solsolution to compute the gradient for
varindexmaps variables to indicies between 0,..,SCIPgetNVars(scip)-1 uniquely
expritexpression iterator that can be used
gradbuffer to store the gradient; grad[varindex(i)] corresponds to SCIPgetVars(scip)[i]
normbuffer to store ||grad||^2

Definition at line 249 of file heur_multistart.c.

References BMSclearMemoryArray, FALSE, getVarIndex(), improvePoint(), NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPnlrowGetExpr(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), and SCIPnlrowGetNLinearVars().

Referenced by getMinFeas(), and improvePoint().

◆ improvePoint()

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

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
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 315 of file heur_multistart.c.

References BMSclearMemoryArray, computeGradient(), filterPoints(), getMinFeas(), MAX, MINFEAS, NULL, 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(), 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 471 of file heur_multistart.c.

References getRelDistance(), MINFEAS, NULL, 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 526 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 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 586 of file heur_multistart.c.

References getRelDistance(), NULL, 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_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
successpointer to store if we could find a solution

Definition at line 645 of file heur_multistart.c.

References FALSE, getExprSize(), MAX, 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 int getExprSize ( SCIP_EXPR expr)
static

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

Parameters
exprexpression

Definition at line 726 of file heur_multistart.c.

References applyHeur(), NULL, SCIPexprGetChildren(), and SCIPexprGetNChildren().

Referenced by applyHeur(), and solveNLP().

◆ 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 756 of file heur_multistart.c.

References clusterPointsGreedy(), filterPoints(), getExprSize(), GRADCOSTFAC_LINEAR, GRADCOSTFAC_NONLINEAR, improvePoint(), MINIMPRFAC, NULL, sampleRandomPoints(), SCIP_Bool, SCIP_CALL, SCIP_DECL_HEURCOPY(), 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 getExprSize().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyMultistart  )
static

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

Definition at line 906 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 918 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 933 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 953 of file heur_multistart.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecMultistart  )
static

execution method of primal heuristic

Definition at line 970 of file heur_multistart.c.