Elias at 12:10, 16 January 2012

2012-01-16T12:10:49Z

← Older revision		Revision as of 08:10, 16 January 2012
Line 24:		Line 24:
	==Calling Syntax==		==Calling Syntax==

	<~~syntaxhighlight~~ lang="matlab">		<source lang="matlab">
	Result = glcDirectTL(Prob,varargin)		Result = glcDirectTL(Prob,varargin)
	Result = tomRun('glcDirect', Prob);		Result = tomRun('glcDirect', Prob);
	</~~syntaxhighlight~~>		</source>

	==Inputs==		==Inputs==

Elias at 09:35, 7 December 2011

2011-12-07T09:35:22Z

Show changes

Elias at 09:32, 7 December 2011

2011-12-07T09:32:08Z

Show changes

Elias at 23:11, 6 December 2011

2011-12-06T23:11:01Z

← Older revision		Revision as of 19:11, 6 December 2011
Line 15:		Line 15:


	where <math>$x,x_{L},x_{U}\in \~~MATHSET~~{R}^{n}$</math>,		where <math>x,x_{L},x_{U}\in \mathbb{R}^{n}</math>,
	<math>$c(x),c_{L},c_{U}\in \~~MATHSET~~{R}^{m_{1}}$</math>,		<math>c(x),c_{L},c_{U}\in \mathbb{R}^{m_{1}}</math>,
	<math>$A\in \~~MATHSET~~{R}^{m_{2}\times n}$</math> and <math>$b_{L},b_{U}\in \~~MATHSET~~{R}^{m_{2}}$</math>.		<math>A\in \mathbb{R}^{m_{2}\times n}</math> and <math>b_{L},b_{U}\in \mathbb{R}^{m_{2}}</math>.
	The variables <math>$x \in I$, the index subset of $1,...,n$</math> 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).		The variables <math>x \in I</math>, the index subset of <math>1,...,n</math> 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''.		''glcDirect'' is a Fortran MEX implementation of ''glcSolve''.

Elias: /* Outputs */

2011-07-20T14:08:50Z

Outputs

← Older revision		Revision as of 10:08, 20 July 2011
Line 138:		Line 138:

	{\| class="wikitable"		{\| class="wikitable"
	\|''Result''\|\|colspan="2"\|Structure with result from optimization. The following fields are changed:		!''Result''\|\|colspan="2"\|Structure with result from optimization. The following fields are changed:
	\|-		\|-
	\|\|\|''x_k''\|\|Matrix with all points giving the function value ''f_k''.		\|\|\|''x_k''\|\|Matrix with all points giving the function value ''f_k''.

Elias: /* Inputs */

2011-07-20T14:08:40Z

Inputs

← Older revision		Revision as of 10:08, 20 July 2011
Line 32:		Line 32:

	{\| class="wikitable"		{\| class="wikitable"
	\|''Prob''\|\|colspan="2"\|Problem description structure. The following fields are used:		!''Prob''\|\|colspan="2"\|Problem description structure. The following fields are used:
	\|-		\|-
	\|\|\|''Name''\|\|Problem name. Used for safety when doing warm starts.		\|\|\|''Name''\|\|Problem name. Used for safety when doing warm starts.

Elias at 11:39, 20 July 2011

2011-07-20T11:39:14Z

Show changes

Elias at 10:05, 20 July 2011

2011-07-20T10:05:12Z

Show changes

Elias at 12:20, 11 July 2011

2011-07-11T12:20:52Z

← Older revision		Revision as of 08:20, 11 July 2011
Line 1:		Line 1:
			[[Category:Solvers]]
			{{cleanup\|Clean this article.}}

	==Purpose==		==Purpose==

Elias: Created page with "==Purpose== Solve global mixed-integer nonlinear programming problems. ''glcDirect ''solves problems of the form $\begin{array}{cccccc} \min\limits_{x} & f(x) & & & ..."$

2011-07-10T11:14:04Z

Created page with "==Purpose== Solve global mixed-integer nonlinear programming problems. ''glcDirect ''solves problems of the form <math> \begin{array}{cccccc} \min\limits_{x} & f(x) & & & ..."

New page

==Purpose==

Solve global mixed-integer nonlinear programming problems.

''glcDirect ''solves problems of the form

<math>
\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}
</math>

where <math>$x,x_{L},x_{U}\in \MATHSET{R}^{n}$</math>,
<math>$c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}$</math>,
<math>$A\in \MATHSET{R}^{m_{2}\times n}$</math> and <math>$b_{L},b_{U}\in \MATHSET{R}^{m_{2}}$</math>.
The variables <math>$x \in I$, the index subset of $1,...,n$</math> 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);

===Description of Inputs===

{|
|''Prob''||colspan="2"|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.
|-valign="top"
|||''PriLevOpt''||Print Level. This controls both regular printing from glcDirect and the amount of iteration log information to print.
|-
|||||0 = Silent.
|-valign="top"
|||||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.
|-valign="top"
|||||See optParam.IterPrint for more information on iteration log printing.
|-valign="top"
|||''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''.
|-valign="top"
|||''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:
|-valign="top"
|||''fcALL''||=0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point.
|-valign="top"
|||||=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.
|-valign="top"
|||||=2 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints.
|-valign="top"
|||''useRoC''||=1 (Default). Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide.
|-valign="top"
|||||=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.
|-valign="top"
|||||=2 Avoid RoC for linear constraints, giving weight one to these constraint violations, whereas the nonlinear constraints use RoC.
|-valign="top"
|||||=3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use.
|-valign="top"
|||''BRANCH''||=0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT paper strategy.
|-valign="top"
|||||=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.
|-valign="top"
|||||=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.
|-valign="top"
|||||=3 Like =2, but use priorities on the variables, similar to ''mipSolve'', see Prob.MIP.VarWeight.
|-valign="top"
|||''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.
|-valign="top"
|||''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.
|-valign="top"
|||''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
|-valign="top"
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.
|-valign="top"
|||''fEqual''||All points with function values within tolerance fEqual are considered to be global minima and returned. Default 1E-10.
|-valign="top"
|||''LinWeight''||''RateOf C hange''= ''LinW eight * \|\|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.
|-valign="top"
|||''AvIter''||How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50.
|-valign="top"
|||''optParam''||Structure with special fields for optimization parameters, see Table 141 on page 229.
|-valign="top"
|||||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.
|}

===Description of Outputs===

{|
|''Result''||colspan="2"|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.
|-valign="top"
|||''ExitFlag''||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.
|-valign="top"
|||||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.
|-valign="top"
|||||5 = Maximum number of function evaluations would most likely be too many in the next iteration, save warm start info, stop.
|-valign="top"
|||||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.
|-valign="top"
|||||Structure with warm start information. Use WarmDefDIRECT to reuse this
|-
|||''WarmStartInfo''||information in another run.
|-valign="top"
|||''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.
|-valign="top"
|||''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, see \[52\], 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.

GlcDirect - Revision history

Elias at 12:10, 16 January 2012

Elias at 09:35, 7 December 2011

Elias at 09:32, 7 December 2011

Elias at 23:11, 6 December 2011

Elias: /* Outputs */

Elias: /* Inputs */

Elias at 11:39, 20 July 2011

Elias at 10:05, 20 July 2011

Elias at 12:20, 11 July 2011

Elias: Created page with "==Purpose== Solve global mixed-integer nonlinear programming problems. ''glcDirect ''solves problems of the form \begin{array}{cccccc} \min\limits_{x} & f(x) & & & ..."

Elias: Created page with "==Purpose== Solve global mixed-integer nonlinear programming problems. ''glcDirect ''solves problems of the form $\begin{array}{cccccc} \min\limits_{x} & f(x) & & & ..."$