MinlpSolve

Purpose

Solve mixed-integer nonlinear programming problems (MINLP).

minlpSolve 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

Recommended is to first set IterPrint, to get information each iteration

Prob.optParam.IterPrint = 1;

Driver call, including printing with level 2:

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

Direct solver call:

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

Warm Start

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);

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 generator. 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 is RandState = -1
	MIP	Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used:
	MIP.IntVars	If empty, all variables are assumed non-integer. If islogical(IntVars) (=all elements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables.
	MIP.VarWeight	Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence.
	MIP.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.
	MIP.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.
	MIP.xIP	The x-values giving the fIP value, if a solution (xIP,fIP) is known.
	MIP.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
	MIP.VarSel	Variable selection method in branch and bound: = 1 Use variable with most fractional value = 2 Use gradient and distance to nearest integer value
	MIP.KNAPSACK	If = 1, use a knapsack heuristic. Default 0.
	MIP.ROUNDH	If = 1, use a rounding heuristic. Default 0.
	MIP.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:
	optParam.MaxIter	Maximal number of iterations, default 10000
	optParam.IterPrint	Print short information each iteration (PriLev > 0 ==> IterPrint = 1). Print one line each iteration with: Iteration 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.
	optParam.bTol	Linear constraint violation convergence tolerance.
	optParam.cTol	Constraint violation convergence tolerance.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	Iter	Number of iterations.
	ExitFlag	Exit flag. 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, size 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 ('minlpSolve').
	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

minlpSolve implements a 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 above) determines if to assume the NLP subproblems are convex or not.

minlpSolve depends on a suitable NLP solver.