GlcCluster

Purpose

Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.

glcCluster solves problems of the form

${\begin{array}{cccccc}\min \limits _{x}&f(x)&&&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\&b_{L}&\leq &Ax&\leq &b_{U}\\&c_{L}&\leq &c(x)&\leq &c_{U}\\&&&{c}{x_{i}\in \mathbb {N} \;\forall i\in I}\\\end{array}}$

where $x,x_{L},x_{U}\in \mathbb {R} ^{n}$, $c(x),c_{L},c_{U}\in \mathbb {R} ^{m_{1}}$, $A\in \mathbb {R} ^{m_{2}\times n}$ and $b_{L},b_{U}\in \mathbb {R} ^{m_{2}}$.

The variables $x\in I$, the index subset of $1,...,n$ are restricted to be integers.

Calling Syntax

Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
Result = tomRun('glcCluster', Prob, PriLev) (driver call)

Inputs

Prob	Problem description structure. The following fields are used:
	A	Constraint matrix for linear constraints.
	b_L	Lower bounds on the linear constraints.
	b_U	Upper bounds on the linear constraints.
	c_L	Lower bounds on the general constraints.
	c_U	Upper bounds on the general constraints.
	x_L	Lower bounds for x, must be given to restrict the search space.
	x_U	Upper bounds for x, must be given to restrict the search space.
	FUNCS.f	Name of m-file computing the objective function f (x).
	FUNCS.c	Name of m-file computing the vector of constraint functions c(x).
	PriLevOpt	Print level. 0=Silent. 1=Some output from each glcCluster phase. 2=More output from each phase. 3=Further minor output from each phase. 6=Use PrintResult( ,1) to print summary from each global and local run. 7 = Use PrintResult( ,2) to print summary from each global and local run. 8 = Use PrintResult( ,3) to print summary from each global and local run.
	WarmStart	If true, > 0, glcCluster warm starts the DIRECT solver. The DIRECT solver will utilize all points sampled in last run, from one or two calls, dependent on the success in last run. Note: The DIRECT solver may not be changed if doing WarmStart mat-file glcFastSave.mat, and continues from the last run.
	Name	Name of the problem. glcCluster uses the warmstart capability in glcFast and needs the name for security reasons.
	GO	Structure in Prob, Prob.GO. Fields used:
	maxFunc1	Number of function evaluations in 1st call to glcFast. Should be odd number (automatically corrected). Default 100 * dim(x) + 1.
	maxFunc2	Number of function evaluations in 2nd call to glcFast.
	maxFunc3	If glcFast is not feasible after maxFunc1 function evaluations, it will be repeat- edly called (warm start) doing maxFunc1 function evaluations until maxFunc3 function evaluations reached.
	ProbL	Structure to be used in the local search. By default the same problem structure as in the global search is used, Prob (see below). Using a second structure is important if optimal continuous variables may take values on bounds. glcFast used for the global search only converges to the simple bounds in the limit, and therefore the simple bounds may be relaxed a bit in the global search. Also, if the global search has difficulty fulfilling equality constraints exactly, the lower and upper bounds may be slightly relaxed. But being exact in the local search. Note that the local search is using derivatives, and can utilize given analytic derivatives. Otherwise the local solver is using numerical derivatives or automatic differentiation. If routines to provide derivatives are given in ProbL, they are used. If only one structure Prob is given, glcCluster uses the derivative routines given in the this structure.
	localSolver	Optionally change local solver used ('snopt' or 'npsol' etc.).
	DIRECT	DIRECT subsolver, either glcSolve or glcFast (default).
	localTry	Maximal number of local searches from cluster points. If <= 0, glcCluster stops after clustering. Default 100.
	maxDistmin	The minimal number used for clustering, default 0.05.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: PriLev, cTol, IterPrint, MaxIter, MaxFunc, EpsGlob, fGoal, eps_f, eps_x.
	MIP.IntVars	Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem). If length(IntVars) > 1 ==> length(IntVars) == length(c) should hold. Then IntVars(i) == 1 ==> x(i) integer. IntVars(i) == 0 ==> x(i) real. If length(IntVars) < n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
varargin	Other parameters directly sent to low level routines.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Matrix with all points giving the function value f_k.
	f_k	Function value at optimum.
	c_k	Nonlinear constraints values at x_k.
	Iter	Number of iterations.
	FuncEv	Number function evaluations.
	maxTri	Maximum size of any triangle.
	ExitText	Text string giving ExitFlag and Inform information.
	Cluster	Subfield with clustering information
	x_k	Matrix with best cluster points.
	f_k	Row vector with f(x) values for each column in Cluster.x_k.
	maxDist	maxDist used for clustering.
	minDist	vector of all minimal distances between points.

Description

glcCluster is a global optimization algorithm, developed by Prof.Dr. Kenneth Holmström. It is a hybrid algorithm, combining the DIRECT global optimization algorithm, a clustering algorithm and local search.

glcCluster is using one of the following DIRECT algorithms: glcDirect (default), glcFast or glcSolve, for global search (Step 1). Step 2 is an adaptive clustering algorithm to find a suitable number of clusters, where the best point in each cluster is then used as an initial point for a local search (Step 3). The 4th step is to run the DIRECT algoirithm once again, to possibly improve. If the DIRECT algorithm improves the best point, a local search is finally made as Step 5 with the new best point(s) as starting points. The routine glcCluster implements an extended version of DIRECT that handles problems with both nonlinear and integer constraints.

M-files Used

iniSolve.m, endSolve.m, glcFast.m