Detailed Description

multistart heuristic for convex and nonconvex MINLPs

Author: Benjamin Mueller

#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.

◆ HEUR_DESC

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

Definition at line 60 of file heur_multistart.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS

Definition at line 61 of file heur_multistart.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -2100000

Definition at line 62 of file heur_multistart.c.

◆ HEUR_FREQ

#define HEUR_FREQ 0

Definition at line 63 of file heur_multistart.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 64 of file heur_multistart.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 65 of file heur_multistart.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE

Definition at line 66 of file heur_multistart.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 67 of file heur_multistart.c.

◆ 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.

◆ DEFAULT_MAXBOUNDSIZE

#define DEFAULT_MAXBOUNDSIZE 2e+4

default maximum variable domain size for unbounded variables

Definition at line 71 of file heur_multistart.c.

◆ 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.

◆ 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.

◆ DEFAULT_MINIMPRITER

#define DEFAULT_MINIMPRITER 10

default number of iteration when checking the minimum improvement

Definition at line 74 of file heur_multistart.c.

◆ 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.

◆ 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.

◆ DEFAULT_MAXNCLUSTER

#define DEFAULT_MAXNCLUSTER 3

default maximum number of considered clusters per heuristic call

Definition at line 77 of file heur_multistart.c.

◆ DEFAULT_ONLYNLPS

#define DEFAULT_ONLYNLPS TRUE

should the heuristic run only on continuous problems?

Definition at line 78 of file heur_multistart.c.

◆ MINFEAS

#define MINFEAS -1e+4

minimum feasibility for a point; used for filtering and improving feasibility

Definition at line 81 of file heur_multistart.c.

◆ 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.

◆ GRADCOSTFAC_LINEAR

#define GRADCOSTFAC_LINEAR 1.0

gradient cost factor for the number of linear variables

Definition at line 84 of file heur_multistart.c.

◆ GRADCOSTFAC_NONLINEAR

#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.

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

varindex	maps variables to indicies between 0,..,SCIPgetNVars(scip)-1
var	variable

Definition at line 118 of file heur_multistart.c.

References NULL, 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

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 MAX, MIN, NULL, 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(), and SCIPvarGetUbLocal().

Referenced by applyHeur().

◆ 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

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 MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNlRowSolFeasibility(), and SCIPinfinity().

Referenced by improvePoint().

◆ 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

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 BMSclearMemoryArray, FALSE, getVarIndex(), NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPnlrowGetExpr(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), and SQR.

Referenced by 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

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 BMSclearMemoryArray, computeGradient(), getMinFeas(), MAX, MIN, 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().

◆ 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

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 MINFEAS, NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisLE(), and SCIPsortDownRealPtr().

Referenced by applyHeur().

◆ 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

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 MAX, MIN, NULL, REALABS, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), x, and y.

Referenced by clusterPointsGreedy().

◆ 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

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 getRelDistance(), NULL, and SCIP_OKAY.

Referenced by applyHeur().

◆ 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

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 FALSE, MAX, MIN, 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().

◆ getExprSize()

static int getExprSize ( SCIP_EXPR * expr )

static

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

Parameters

expr	expression

Definition at line 727 of file heur_multistart.c.

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

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:

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

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

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyMultistart )

static

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

Definition at line 907 of file heur_multistart.c.

References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurMultistart().

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

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitMultistart )

static

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

Definition at line 934 of file heur_multistart.c.

References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfindHeur(), SCIPheurGetData(), and TRUE.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitMultistart )

static

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

Definition at line 954 of file heur_multistart.c.

References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPheurGetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecMultistart )

static

execution method of primal heuristic

Definition at line 971 of file heur_multistart.c.

References applyHeur(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNNlpis(), SCIPheurGetData(), and SCIPisNLPConstructed().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_RANDSEED

◆ DEFAULT_NRNDPOINTS

◆ DEFAULT_MAXBOUNDSIZE

◆ DEFAULT_MAXITER

◆ DEFAULT_MINIMPRFAC

◆ DEFAULT_MINIMPRITER

◆ DEFAULT_MAXRELDIST

◆ DEFAULT_GRADLIMIT

◆ DEFAULT_MAXNCLUSTER

◆ DEFAULT_ONLYNLPS

◆ MINFEAS

◆ MINIMPRFAC

◆ GRADCOSTFAC_LINEAR

◆ GRADCOSTFAC_NONLINEAR

Function Documentation

◆ getVarIndex()

◆ sampleRandomPoints()

◆ getMinFeas()

◆ computeGradient()

◆ improvePoint()

◆ filterPoints()

◆ getRelDistance()

◆ clusterPointsGreedy()

◆ solveNLP()

◆ getExprSize()

◆ applyHeur()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEUREXEC()