MinlpSolve

Purpose

Branch & Bound algorithm for Mixed-Integer Nonlinear Programming (MINLP) with convex or nonconvex sub problems using NLP relaxation (Formulated as minlp-IP).

The parameter Convex (see below) determines if to assume the NLP subproblems are convex or not.

minlpSolve depends on a suitable NLP solver.

minlpSolve solves problems of the form

Failed to parse (unknown function "\multicolumn"): {\displaystyle \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} \\& & & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$} \\ \end{array} }

where Failed to parse (unknown function "\MATHSET"): {\displaystyle x,x_{L},x_{U}\in \MATHSET{R}^{n}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}} , Failed to parse (unknown function "\MATHSET"): {\displaystyle A\in \MATHSET{R}^{m_{2}\times n}} and Failed to parse (unknown function "\MATHSET"): {\displaystyle b_{L},b_{U}\in \MATHSET{R}^{m_{2}}} . The variables $x\in I$ , the index subset of $1,...,n$ are restricted to be integers.

Calling Syntax

Result = tomRun('minlpSolve',Prob,...)

Inputs

Prob	Problem description structure. The following fields are used:
	x_L	Lower bounds on x.
	x_U	Upper bounds on x.
	A	The linear constraint matrix.
	b_L	Lower bounds on linear constraints.
	b_U	Upper bounds on linear constraints.
	c_L	Lower bounds on nonlinear constraints.
	c_U	Upper bounds on nonlinear constraints.
	x_0	Starting point.
	Convex	If Convex==1, assume NLP problems are convex, and only one local NLP solver call is used at each node. If Convex==0 (Default), multiMin is used to do many calls to a local solver to determine the global minima at each node. The global minimum with most components integer valued is chosen.
	MaxCPU	Maximal CPU Time (in seconds) to be used by minlpSolve, stops with best point found
	PriLev	Print level in minlpSolve (default 1). Also see optParam.IterPrint
	PriLevOpt	Print level in sub solvers (SNOPT and other NLP solvers): =0 No output; >0 Convergence results >1 Output every iteration, >2 Output each step in the NLP alg For other NLP solvers, see the documentation for the solver
	WarmStart	If true, >0, minlpSolve reads the output from the last run from Prob.minlpSolve, if it exists. If it doesn't exist, minlpSolve attempts to open and read warm start data from mat-file minlpSolveSave.mat. minlpSolve uses the warm start information to continue from the last run. The mat-file minlp- SolveSave.mat is saved every Prob.MIP.SaveFreq iteration.
	SolverNLP	Name of the solver used for NLP subproblems. If empty, the default solver is found calling GetSolver('con',1); If TOMLAB /SOL installed, SNOPT is the default solver. If SolverNLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters
	RandState	If Convex == 0, RandState is sent to multiMin to initialize the random gen- erator. RandState is used as follows: If > 0, rand('state',RandState) is set to initialize the pseudo-random generator if < 0, rand('state',sum(100*clock)) is set to give a new set of random values each run if RandState == 0, rand('state',) is not called. Default RandState = -1
	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.
	VarWeight	Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence.
	DualGap	minlpSolve stops if the duality gap is less than DualGap. DualGap = 1, stop at first integer solution e.g. DualGap = 0.01, stop if solution < 1% from optimal solution.
	fIP	An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given.
	xIP	The x-values giving the fIP value, if a solution (xIP,fIP) is known.
	NodeSel	Node selection method in branch and bound = 0 Depth First. Priority on nodes with more integer components = 1 Breadth First. Priority on nodes with more integer components = 2 Depth First. When integer solution found, use NodeSel = 1 (default) = 3 Pure LIFO (Last in, first out) Depth First = 4 Pure FIFO (First in, first out) Breadth First = 5 Pure LIFO Depth First. When integer solution found, use NodeSel 4
	VarSel	Variable selection method in branch and bound: = 1 Use variable with most fractional value = 2 Use gradient and distance to nearest integer value
	KNAPSACK	If = 1, use a knapsack heuristic. Default 0.
	ROUNDH	If = 1, use a rounding heuristic. Default 0.
	SaveFreq	Warm start info saved on minlpSolveSave.mat every SaveFreq iteration (default -1, i.e. no warm start info is saved)
	optParam	Structure in Prob. Fields used in Prob.optParam, also in sub solvers:
	MaxIter	Maximal number of iterations, default 10000
	IterPrint	Print short information each iteration (PriLev > 0 ==> IterPrint = 1). Iter- ation number: Depth in tree (symbol L[] - empty list, symbol Gap - Dual Gap convergence), fNLP (Optimal f(x) current node), fIPMin (Best integer feasible f(x) found), LowBnd (Lower bound on optimal integer feasible f(x)), Dual Gap in absolut value and percent, The length of the node list L, -L-, The Inform and ExitFlag the solver returned at the current node, FuEv (Number of function evaluations used by solver at current node), date/time stamp.
	bTol	Linear constraint violation convergence tolerance.
	cTol	Constraint violation convergence tolerance.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	Iter	Number of iterations.
	ExitFlag	0: Global optimal solution found, or integer solution with duality gap less than user tolerance. 1: Maximal number of iterations reached. 2: Empty feasible set, no integer solution found. 4: No feasible point found running NLP relaxation. 5: Illegal x 0 found in NLP relaxation. 99: Maximal CPU Time used (cputime > Prob.MaxCPU).
	Inform	Code telling type of convergence, returned from subsolver.
	ExitText	Text string giving ExitFlag and Inform information.
	DualGap	Relative duality gap, max(0,fIPMin-fLB)/-fIPMin-, if fIPMin =0; max(0,fIPMin-fLB) if fIPMin == 0. If fIPMin =0: Scale with 100, 100*Dual- Gap, to get the percentage duality gap. For absolute value duality gap: scale with fIPMin, fIPMin * DualGap
	x_k	Solution.
	v_k	Lagrange multipliers. Bounds, Linear and Nonlinear Constraints, n + mLin + mNonLin.
	f_k	Function value at optimum.
	g_k	Gradient vector at optimum.
	x_0	Starting point x 0.
	f_0	Function value at start.
	c_k	Constraint values at optimum.
	cJac	Constraint derivative values at optimum.
	xState	State of each variable, described in TOMLAB Appendix B.
	bState	State of each constraint, described in TOMLAB Appendix B.
	cState	State of each general constraint, described in TOMLAB Appendix B.
	Solver	Solver used ('mipSolve').
	SolverAlgorithm	Text description of solver algorithm used.
	Prob	Problem structure used.
	minlpSolve	A structure with warm start information. Use with WarmDefGLOBAL, see example below.

Description

To make a restart (warm start), just set the warm start flag, and call minlpSolve once again:

Prob.WarmStart = 1;
Result = tomRun('minlpSolve', Prob,  2);

minlpSolve will read warm start information from the minlpSolveSave.mat file. Another warm start (with same MaxFunc) is made by just calling tomRun again:

Result  = tomRun('minlpSolve', Prob,  2);

To make a restart from the warm start information in the Result structure, make a call to WarmDefGLOBAL before calling minlpSolve. WarmDefGLOBAL moves information from the Result structure to the Prob structure and sets the warm start flag, Prob.WarmStart = 1;

Prob = WarmDefGLOBAL('minlpSolve', Prob,  Result);

where Result is the result structure returned by the previous run. A warm start (with same MaxIter) is done by just calling tomRun again:

Result  = tomRun('minlpSolve', Prob,  2);

To make another warm start with new MaxIter 100, say, redefine MaxIter as:

Prob.optParam.MaxIter = 100;

Then repeat the two lines:

Prob = WarmDefGLOBAL('minlpSolve', Prob,  Result); 
Result = tomRun('minlpSolve', Prob,  2);