GlcDirect

Purpose

Solve global mixed-integer nonlinear programming problems.

glcDirect 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}\\&&&x_{i}\mathrm {\ \ integer} &&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. Recommendation: Put the integers as the first variables. Put low range integers before large range integers. Linear constraints are specially treated. Equality constraints are added as penalties to the objective. Weights are computed automatically, assuming f(x) scaled to be roughly 1 at optimum. Otherwise scale f(x).

glcDirect is a Fortran MEX implementation of glcSolve.

Calling Syntax

Result = glcDirectTL(Prob,varargin) 
Result = tomRun('glcDirect', Prob);

Inputs

Prob	Problem description structure. The following fields are used:
	Name	Problem name. Used for safety when doing warm starts.
	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).
	A	Linear constraints matrix.
	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 finite to restrict the search space.
	x_U	Upper bounds for x, must be finite to restrict the search space.
	PriLevOpt	Print Level. This controls both regular printing from glcDirect and the amount of iteration log information to print. 0 = Silent. 1 = Warnings and errors printed. Iteration log on iterations im- proving function value. 2 = Iteration log on all iterations. 3 = Log for each function evaluation. 4 = Print list of parameter settings. See optParam.IterPrint for more information on iteration log printing.
	WarmStart	If true, > 0, glcDirect reads the output from the last run from Prob.glcDirect.WarmStartInfo if it exists. If it doesn't exist, glcDirect attempts to open and read warm start data from mat-file glcDirectSave.mat. glcDirect uses this warm start information to continue from the last run.
	MaxCPU	Maximum CPU Time (in seconds) to be used.
	MIP	Structure in Prob, Prob.MIP.
	Intvars	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.
	fIP	An upper bound on the optimal f(x) value. If empty, set as Inf.
	xIP	The x-values giving the fIP value. If fIP empty and xIP given, fIP will be computed if xIP nonempty, its feasibility is checked
	glcDirect	Structure with DIRECT algorithm specific parameters. Fields used:
	fcALL	=0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point. =1 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Do not update rates of change for the constraints. =2 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints.
	useRoC	=1 (Default). Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide. =0 Avoid RoC, giving equal weights to all constraint violations. Suggested if difficulty to find feasible points. For problems where linear constraints have been added among the nonlinear (NOT RECOMMENDED; AVOID!!!), then option useRoc=0 has been successful, whereas useRoC completely fails. =2 Avoid RoC for linear constraints, giving weight one to these constraint violations, whereas the nonlinear constraints use RoC. =3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use.
	BRANCH	=0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT paper strategy. =1 First branch the integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. DEFAULT! Normally much more efficient than =0 for mixed- integer problems. =2 First branch the integer variables with 1,2 or 3 possible values, e.g [0,1], [0,2] variables, selecting the variable with least splits. Then branch the other integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. =3 Like =2, but use priorities on the variables, similar to mipSolve, see Prob.MIP.VarWeight.
	RECTIE	When minimizing the measure to find which new rectangle to try to get feasible, there are often ties, several rectangles have the same minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles with low index are often larger then the rectangles with higher index. Selecting one of each type could help, but often =0 is fastest. =0 Use the rectangle with value a, with lowest index (original). =1 (Default): Use 1 of the smallest and 1 of largest rectangles. =2 Use the last rectangle with the same value a, not the 1st. =3 Use one of the smallest rectangles with same value a. =4 Use all rectangles with the same value a, not just the 1st.
	EqConFac	Weight factor for equality constraints when adding to objective function f(x) (Default value 10). The weight is computed as EqConFac/"right or left hand side constant value", e.g. if the constraint is Ax <= b, the weight is EqCon- Fac/b If DIRECT just is pushing down the f(x) value instead of fulfilling the equality constraints, increase EqConFac.
	AxFeas	Set nonzero to make glcDirect skip f(x) evaluations, when the linear constraints are infeasible, and still no feasible point has been found. The default is 0. Value 1 demands fcALL == 0. This option could save some time if f(x) is a bit costly, however overall performance could on some problems be dramatically worse.
	fEqual	All points with function values within tolerance fEqual are considered to be global minima and returned. Default 1E-10.
	LinWeight	RateOfChange= LinWeight * ||a(i, :)|| for linear constraints. Balance be- tween linear and nonlinear constraints. Default 0.1. The higher value, the less influence from linear constraints.
	alpha	Exponential forgetting factor in RoC computation, default 0.9.
	AvIter	How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used by glcDirect are: IterPrint, bTol, cTol, MaxIter, MaxFunc, EpsGlob, fGoal, eps f, eps x.
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. 0 = Normal termination, max number of iterations func.evals reached. 2 = Some upper bounds below lower bounds. 4 = Numerical trouble, and cannot continue. 7 = Reached maxFunc or maxIter, NOT feasible. 8 = Empty domain for integer variables. 10= Input errors.
	Inform	1 = Function value f is less than fGoal. 2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f-fGoal)/abs(fGoal) <= fTol. 3 = Maximum number of iterations done. 4 = Maximum number of function evaluations done. 5 = Maximum number of function evaluations would most likely be too many in the next iteration, save warm start info, stop. 6 = Maximum number of function evaluations would most likely be too many in the next iteration, because 2 * sLen >= maxFDim - nFunc, save warm start info, stop. 7 = Space is dense. 8 = Either space is dense, or MIP is dense. 10= No progress in this run, return solution from previous one. 91= Infeasible. 92= No rectangles to work on. 93= sLen = 0, no feasible integer solution exists. 94= All variables are fixed. 95= There exist free constraints.
	glcDirect	Substructure for glcDirect specific result data.
	convFlag	Converge status flag from solver. Structure with warm start information. Use WarmDefDIRECT to reuse this
	WarmStartInfo	information in another run.
	glcDirectSave.mat	To make a warm start possible, glcDirect saves the following information in the structure Result.glcDirect.WarmStartInfo and file glcDirectSave.mat (for internal solver use only):
	C	Matrix with all rectangle centerpoints, in [0,1]-space.
	D	Vector with distances from centerpoint to the vertices.
	F	Vector with function values.
	G	Matrix with constraint values for each point.
	Iter	Number of iterations.
	Name	Name of the problem. Used for security if doing warm start.
	Split	Split(i, j) is the number of splits along dimension i of rectangle j.
	Tr	T r(i) is the number of times rectangle i has been trisected.
	fMinIdx	Indices of the currently best points.
	fMinEQ	sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
	glcfMin	Best function value found at a feasible point.
	feasible	Flag indicating if a feasible point has been found.
	ignoreidx	Rectangles to be ignored in the rectangle selection procedure.
	roc	Rate of change s, for each constraint.
	s0	Sum of observed rate of change s0 in the objective.
	t	t(i) is the total number of splits along dimension i.

Description

The routine glcDirect implements an extended version of DIRECT that handles problems with both nonlinear and integer constraints. The algorithm in glcDirect is a Fortran MEX implementation of the algorithm in glcSolve.

DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glcDirect is run for a predefined number of function evaluations and considers the best function value found as the optimal one. It is possible for the user to restart glcDirect with the final status of all parameters from the previous run, a so called warm start. Assume that a run has been made with glcDirect on a certain problem for 500 function evaluations. Then a run of e.g. 200 function evaluations more should give the same result as if the run had been using 700 function evaluations in the first place. To do a warm start of glcDirect a flag Prob.WarmStart should be set to one. Then glcDirect will use output previously written to the file glcDirectSave.mat (or the warm start structure) to make the restart.

DIRECT does not explicitly handle equality constraints. It works best when the integer variables describe an ordered quantity and is less effective when they are categorical.

M-files Used

iniSolve.m, endSolve.m and glcSolve.m.

Warnings

A significant portion of glcDirect is coded in Fortran MEX format. If the solver is aborted, it may have allocated memory for the computations which is not returned. This may lead to unpredictable behavior if glcDirect is started again. To reduce the risk of trouble, do "clear mex" if a run has been aborted.