GlcSolve

Purpose

Solve general constrained mixed-integer global optimization problems.

glcSolve 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).

Calling Syntax

Result = glcSolve(Prob, varargin) 
Result = tomRun('glcSolve', Prob);

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.
	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
	x_L	Lower bounds for x, must be given to restrict the search space. Any lower bounds that are inf are changed to -10000.
	x_U	Upper bounds for x, must be given to restrict the search space. Any upper bounds that are inf are changed to 10000.
	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).
	Name	Name of the problem. Used for security if doing warm start.
	PriLevOpt	Print level. 0 = silent. 1 = some printing. 2 = print each iteration.
	WarmStart	If true (> 0), glcSolve reads the output from the last run from the mat-file glcSave.mat, and continues from the last run. NOTE: All rectangles that are fathomed in the previous run are deleted. This saves space and computational time and enables solving larger problems and more function evaluations to be done.
	MaxCPU	Maximal CPU Time (in seconds) to be used.
	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 glcSolve 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 f cALL == 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.
	If WarmStart is chosen, the following fields in glcSave.mat are also used and contains information from the previous run:
	C	Matrix with all rectangle centerpoints.
	D	Vector with distances from centerpoint to the vertices.
	F	Vector with function values.
	G	Matrix with constraint values for each point.
	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.
	T	T (i) is the number of times rectangle i has been trisected.
	fMinEQ	sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
	fMinIdx	Indices of the currently best points.
	feasible	Flag indicating if a feasible point has been found.
	glcfmin	Best function value found at a feasible point.
	iL	iL(i, j) is the lower bound for rectangle j in integer dimension I (i).
	iU	iU (i, j) is the upper bound for rectangle j in integer dimension I (i).
	ignoreidx	Rectangles to be ignored in the rectangle selection procedure.
	s	s(j) is the sum of observed rates of change for constraint j.
	s_0	s_0 is used as s(0).
	t	t(i) is the total number of splits along dimension i.
	SubRes	Additional output from nlp f, if suboptimization done.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A.
		Fields used by glcSolve are: IterPrint, bTol, cTol, MaxIter (defaultmax(5000, n * 1000)), MaxFunc (default max(10000, n * 2000)), 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.
	glcSave.mat	Special file containing:
	C	Matrix with all rectangle centerpoints.
	D	Vector with distances from centerpoint to the vertices.
	F	Vector with function values.
	G	Matrix with constraint values for each point.
	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.
	T	T (i) is the number of times rectangle i has been trisected.
	fMinEQ	sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
	fMinIdx	Indices of the currently best points.
	feasible	Flag indicating if a feasible point has been found.
	glcf min	Best function value found at a feasible point.
	iL	iL(i, j) is the lower bound for rectangle j in integer dimension I (i).
	iU	iU (i, j) is the upper bound for rectangle j in integer dimension I (i).
	ignoreidx	Rectangles to be ignored in the rectangle selection procedure.
	s	s(j) is the sum of observed rates of change for constraint j.
	s_0	s_0 is used as s(0).
	t	t(i) is the total number of splits along dimension i.
	Iter	Number of iterations.
	FuncEv	Number function evaluations.
	maxTri	Maximum size of any triangle.
	ExitText	Text string giving ExitFlag and Inform information.
	ExitFlag	0 - Reached maxFunc or maxIter. 2 - Some upper bounds below lower bounds. 7 - Reached maxFunc or maxIter, NOT feasible. 8 - Empty domain for integer variables.
	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. 9 = Max CPU Time reached. 91= Infeasible. 99= Input error, see ExitFlag.

Description

The routine glcSolve implements an extended version of DIRECT that handles problems with both nonlinear and integer constraints.

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 glcSolve 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 glcSolve with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glcSolve 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 glcSolve a flag Prob.WarmStart should be set to one. Then glcSolve is using output previously written to the file glcSave.mat 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