MIPNLP ecpMINLP

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

Purpose

ecpMINLP solves convex mixed-integer nonlinear programming problems (MINLP).

ecpMINLP 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

Driver call, including printing with level 2:

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

Direct solver call:

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

Warm Start

Warm start is currently not supported, but might be included in a future release.

Inputs

Prob structure

The TOMLAB problem structure

The following fields are used in the problem description structure Prob
Field	Description
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.
f_Low	Lower bound on solution.
x_0	Starting point.
MaxCPU	Maximal CPU Time (in seconds) to be used by ecpMINLP, stops with best point found
PriLev	Print level in ecpMINLP (default 1). Also see optParam.IterPrint value output =0 Silent. >0 Initial information and convergence results. >1 Output a line whenever the solution has improved, containing: nIterations, nCuts, nCuts with criteria fulfilled, nLinearizations, nSpecialCuts, best solution. >2 Output a line every iteration with the following information: label description It Iterations nECP Number of extended cutting planes (ECP) nAlpha>=lim Number of ECP with criteria fulfilled nL Number of linearizations nSECP Number of special case ECP (created from constraint on bound) fIPMin Objective of best solution at current iteration >3 Output a description of each step in the MINLP algorithm >4 Output additional numerical information in some algorithm steps >5 Output information in substeps (preprocessing, line search)
PriLevOpt	Print level in sub-solvers, see the documentation for the solver
SolverMIP	Name of the solver used for MIP subproblems. If TOMLAB /gurobi is installed, gurobi is the default solver. If TOMLAB /CPLEX is installed, CPLEX is second choice as default. Otherwise the default solver is found calling GetSolver('mip',1); Supported as subsolvers are gurobi, CPLEX, mipSolve, milpSolve and cutplane.
SolverLP	Name of the solver used for LP subproblems when SolverMIP == mipSolve
MIP	Structure with parameters specific to mixed integer optimization. See the table below describing the fields used in the MIP structure.
ECPMINLP	Structure with parameters specific to the ecpMINLP solver. See the table below describing the fields used in the ECPMINLP structure.
optParam	Structure with general optimization parameters. See the table below describing the fields used in the optParam structure.

MIP structure

Substructure in Prob with parameters related to mixed integer programming.

fields used in Prob.MIP:
Field	Description
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.
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.
DualGap	ecpMINLP 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. The lower bound Prob.f_Low is used, (default -1.0e300), which can also be set by the user. If f_Low has not been changed from default the lower bound is obtained from the initial solution of a relaxed problem, but only when ECPMINLP.INIT_BND is 1 or 2 (default). Default DualGap is -1, not used.
PPP	Pre-processing and probing, default is 0. 0 Not used. Default. 1 Apply initially on MINLP problem. 2 Apply each iteration before solving MILP subproblem.
ROUNDH	If nonzero, a rounding heuristics will be used on the initial NLP solution in order to obtain an initial integer solution. Requires ECPMINLP.INIT_BND enabled. Default is 1, enabled.

ECPMINLP structure

Substructure in Prob with solver-specific options.

fields used in Prob.ECPMINLP
Field	Description
beta	Multiplier when increasing alpha after an infeasible MILP solution. Alpha is a parameter individually adjusting each cutting plane, starting at 1.0 and increasing until meeting a certain criterion. Default value for beta is 1.3.
gamma	Multiplier when increasing alpha when MILP solution does not violate any nonlinear contraints, but still does not decrease the upper bound of the objective. Alpha is a parameter individually adjusting each cutting plane, starting at 1.0 and increasing until meeting a certain criterion. Default value for gamma is 2.0.
PREALLOC	Flag enabling preallocation of memory for cutting planes and linearizations. 0 No preallocation, dynamic growth of arrays. Current default. 1 Preallocate arrays.
INIT_BND	Selects method for setting lower bound when f_Low not changed from default. value method 0 No extra initial lower bound. 1 Use default TOMLAB NLP solver on problem with relaxed integer constraints. Add a linearization if a feasible MINLP solution was found. 2 Add an initial linearization as long as a feasdbile NLP solution was found. The linearization is a simple lower bound on the MILP objective. Default. 3 Same as 2, but also use the gradient in the linearization. This might improve the solution process for some problems where no solution can be found otherwise. But for many problems, using this initial linearization cuts off a feasbiel region and slows down or even hinders the solver completely. Recommended to only use as a last resort.
SETTOL	Flag enabling changing tolerances, described below under optParam.eps_x, optParam.eps_x and optParam.eps_f. 0 Default. Using the recommended solver default values, 1.0e-3. 1 Tolerances can be changed, taken from Prob.optParam.
INTSOLLIM_INCR	Integer option when using CPLEX as MIP subsolver. Define how much the CPLEX parameter INTSOLLIM increases when a feasible solution is not optimal and all alpha values have met their criteria. If set to zero, optimal strategy will be used immediately instead, without any gradual increase of INTSOLLIM. Default is 1.
USECUTPOOL	Set nonzero to use a pool for the alpha-regulated extended cutting planes. Cuts not active in the MILP-solution for CUTDELBND iterations in a row will be inactivated (removed from the MILP-problem) until they are violated in a new solution. Default is 0, not used.
CUTDELBND	The number of consecutive times an extended cutting plane can be inactive before it gets removed and put into the inactive pool, if the option USECUTPOOL is set nonzero. Default is 15 times.
MAXITNOIMP	Limit on the number of successive iterations allowed without any improvements at all to neither objective nor solution point before the solver terminates Default is 2.
USENLP	Set nonzero to use an NLP sub-solver on the original problem with the integer variables fixed at values from the latest MILP solution. Default is 1, enabled.
USERESELECT	Set nonzero to enable cut reselection heuristics. Default is 1, enabled.
SCALECUTS	Set nonzero to scale cuts before they are added to the MILP problem. Scaling is done by dividing the cut with its norm. Default is 1, enabled.

optParam Structure

Substructure in Prob with general optimization parameters.

fields used in Prob.optParam
Field	Value
MaxIter	Maximal number of iterations, default 10000
IterPrint	Print short information each iteration. Setting PriLev > 1 also enables IterPrint, setting it to 1.
eps_x	Linear constraint violation convergence tolerance. Default is 2.0e-6
eps_g	Constraint violation convergence tolerance. Default is 1.0e-7
eps_f	Optimality tolerance. Default is 1.0e-8

NOTE: For the solver to use these tolerances, the flag ECPMINLP.SETTOL must be set to nonzero.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	Iter	Number of iterations.
	ExitFlag	Exit flag. 0: 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. 3: Problem in subsolver, see Inform value. 99: Maximal CPU Time used (cputime > Prob.maxCPU
	Inform	Inform for ExitFlag != 3 0: Global solution found. 1: Local solution found. 2: No solution found. >2: Inform value 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.
	f_k	Function value at optimum.
	g_k	Gradient vector at optimum.
	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.
	x_0	Starting point x_0.
	Solver	Solver used ('ecpMINLP').
	SolverAlgorithm	Description of method used.
	Prob	Problem structure used.

Algorithm

ecpMINLP Solves convex or pseudo-convex mixed-integer nonlinear programming problems using an extended cutting plane algorithm with cuts regulated by a parameter-vector alpha. Cuts and linearizations are added to MIP subproblem which is then solved by a subsolver in each iteration.

The solver algorithm is mainly based on the paper 'Solving Pseudo-Convex Mixed Integer Optimization Problems by Cutting Plane Techniques' by Tapio Westerlund and Ray Pörn, published in Optimization and Engineering 3, 253-280, 2002, with some modifications.

Most prominent features in addition to the ones described in the main reference above are

• Solving the relaxed NLP problem initially to obtain a lower bound on the solution.
• A rounding heuristics performed on the initial NLP solution in order to obtain an initial upper bound on the initial solutions.
• Optional use of a cutpool for the alpha-regulated extended cutting planes.