MultiMINLP

This page is part of the MIPNLP Manual. See MIPNLP.

Purpose

multiMINLP solves general constrained mixed-integer global nonlinear optimization problems.

It is aimed for problems where the number of integer combinations nMax is huge and relaxation of the integer constraint is possible.

If no integer variables, multiMINLP calls multiMin. If nMax <= min(Prob.optParam.MaxFunc,5000), glcDirect is used. Otherwise, multiMINLP first finds a set M of local minima calling multiMin with no integer restriction on any variable. The best local minimum is selected. glcDirect is called to find the best integer feasible solution fIP in a small area (< +- 2 units) around the best local minimum found.

The other local minima are pruned, if fOpt(i) > fIP, no integer feasible solution could be found close to this local minimum i.

The area close to the remaining candidate local minima are searched one by one by calling glcDirect to find any fIPi < fIP.

multiMINLP 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_{j}\in \mathbb {N} \ \ \forall j\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 = tomRun('multiMINLP',Prob,...)

Inputs

Prob is a structure, defined as to solve a standard MINLP problem. The Prob structure is fed to the localSolver. See e.g. minlpAssign. See multiMin and glcDirect for input to the subsolvers e.g. Prob.xInit is used in multiMin (and fCut, RandState, xEQTol).

Prob	Problem description structure. The following fields are used:
	x_L	Lower bounds for each element in x. If generating random points, -inf elements of x_L are set to min(-L,xMin,x U-L) xMin is the minimum of the finite x_L values.
	x_U	Upper bounds for each element in x. If generating random points, inf elements of x_U are set to max(L,xMax,x L+L) xMax is the maximum of the finite x_U values. L is 100 for nonlinear least squares, otherwise 1000.
	b_L	Lower bounds on linear constraints.
	b_U	Upper bounds on linear constraints.
	A	The linear constraint matrix.
	c_L	Lower bounds on nonlinear constraints.
	c_U	Upper bounds on nonlinear constraints.
	PriLev	Print Level: 0 = Silent 1 = Display 2 summary rows 2 = Display some extra summary rows 5 = Print level 1 in tomRun call 6 = Print level 2 in tomRun call 7 = Print level 3 in tomRun call
	xInit	Used in multiMin. See help for multiMin.
	GO.localSolver	The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
	optParam	Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
	MaxFunc	Max number of function evaluations in each subproblem
	fGoal	Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done
	eps_f	Relative accuracy for function value, fTol == eps_f. Stop if abs(f-fGoal) <= abs(fGoal) * fTol , if fGoal = 0. Stop if abs(f-fGoal) <= fTol , if fGoal ==0. Default 1e-8.
	bTol	Linear constraint feasibility tolerance. Default 1e-6
	cTol	Nonlinear constraint feasibility tolerance. Default 1e-6
	MIP	Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used:
	IntVars	If empty, all variables are assumed non-integer. If islogical(IntVars) (=all el- ements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables.
	nMax	Number of integer combinations possible, if empty multiMINLP computes nMax.
	Rfac	Reduction factor for real variables in MINLP subproblem close to local multiMINLP minimum. Bounds set to x_L = max(x_L,x-Rfac*(x_U-x_L)) and x_U= min(x_U,x+Rfac*(x_U-x_L)). Default 0.25.

Outputs

Result	Structure with result from optimization. The following fields are changed:
		Result structure from the last good optimization step giving the best f(x) value, the possible global MINLP minimum. The following fields in Result are changed by multiMINLP before return:
	ExitFlag	= 0 normal output, of if fGoal set and found. = 1 A solution reaching the user defined fGoal was not found. = 2 Unbounded problem. =4 Infeasible problem. The Solver, SolverAlgorithm and ExitText fields are also reset. A special field in Result is also returned, Result.multiMINLP:
	xOpt	Prob.N x k matrix with k distinct local optima, the test being norm(x k- xOpt(:,i)) <= xEqTol*max(1,norm(x k)) that if fulfilled assumes x_k to be to close to xOpt(:,i).
	fOpt	The k function values in the local optima xOpt(:,i),i=1,...,k.
	Inform	The Inform value returned by the local solver when finding each of the local optima xOpt(:,i); i=1,...,k. The Inform value can be used to judge the validity of the local minimum reported.
	localTry	Total number of local searches.
	Iter	Total number of iterations.
	FuncEv	Total number of function evaluations.
	GradEv	Total number of gradient evaluations.
	HessEv	Total number of Hessian evaluations.
	ConstrEv	Total number of constraint function evaluations.
	ExitText	Text string giving Inform information.