MIPNLP ecpMINLP
From TomWiki
This page is part of the MIPNLP Manual. See MIPNLP Manual. 
Contents 
Purpose
ecpMINLP solves convex mixedinteger nonlinear programming problems (MINLP).
ecpMINLP solves problems of the form
where , , and
. The variables , the
index subset of 1,...,n are restricted to be integers but can be either continuously differentiable or not. An initalization routine will detect strict integer variables in the problem.
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
 
PriLevOptMIP  Print level in MIP subsolvers, (CPLEX and others, see the documentation for the solver used). Usually:  
PriLevOptNLP  Print level in NLP subsolvers, (SNOPT and others, see the documentation for the solver used). Usually:  
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.  
SolverNLP 
Name of the solver used for NLP subproblems. If packages /SOL or /SNOTP is installed, snopt is the default solver. Otherwise the default solver is found calling GetSolver('con',1);  
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 noninteger. 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 xvalues 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.

PPP  Preprocessing and probing, default is 0. 0 Not used. Default. 
ROUNDH  If nonzero, a rounding heuristics will be used on the initial NLP solution in order to obtain an initial integer solution. Requires ECPMINLP.InitBndType enabled. Default is 1, enabled. 
ECPMINLP structure
Substructure in Prob with solverspecific options.
fields used in Prob.ECPMINLP  

Field  Description  
beta  Multiplier when increasing alpha after an infeasible MILP solution.
 
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.
 
PREALLOC  Flag enabling preallocation of memory for cutting planes and linearizations.
 
InitBndType  Selects method for setting lower bound when f_Low not changed from default.
 
SET_TOL  Flag enabling changing tolerances, described below under optParam.eps_x, optParam.eps_x and optParam.eps_f.
 
IntSolLimIncr  Integer option when using CPLEX as MIP subsolver.
 
USE_CUTPOOL  Set nonzero to use a pool for the alpharegulated extended cutting planes.
 
CutDelBound  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 USE_CUTPOOL is set nonzero.
 
MaxIterWoImpr  Limit on the number of successive iterations allowed without any improvements at all to neither objective nor solution point before the solver terminates
 
USE_NLP  =1 User and NLP subsolver on the initial integerrelaxed original problem, as well as the NLP problem with fixed integer values during the main iteration. =2 Use a global subsolver on the initial integerrelaxed problem, as well as the NLP problem with fixed integer values during the main iterations. Setting UseNLP = can increase the likelihood of finding a global optimal solution for nonconvex problems.
 
RESELECT_CUTS  Set nonzero to enable cut reselection heuristics. Default is 1, enabled.  
SCALE_CUTS  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 > 2 also enables IterPrint, setting it to 1. 
eps_x  Linear constraint violation convergence tolerance. Default is 2.0e6 
eps_g  Constraint violation convergence tolerance. Default is 1.0e7 
eps_f  Optimality tolerance. Default is 1.0e8 
NOTE: For the solver to use these tolerances, the flag ECPMINLP.SET_TOL must be set to nonzero.
Outputs
Result  Structure with result from optimization. The following fields are used:  

Iter  Number of iterations.  
ExitFlag  Exit flag.
 
Inform  Inform for ExitFlag != 3
 
ExitText  Text string giving ExitFlag and Inform information.  
DualGap  Relative duality gap, set as follows:
To get the percentage duality gap, scale with 100.  
x_k  Solution.  
x  Vector of solution points, sorted on ascending order based on the correcsponding objective values returned in f. x(:,1) is always equal to x_k.  
f_k  Function value at optimum.  
f  The objective vales at all encountered solution points in x. Sorted in ascending order.  
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 pseudoconvex mixedinteger nonlinear programming problems using an extended cutting plane algorithm with cuts regulated by a parametervector 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 PseudoConvex Mixed Integer Optimization Problems by Cutting Plane Techniques' by Tapio Westerlund and Ray Pörn, published in Optimization and Engineering 3, 253280, 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 alpharegulated extended cutting planes.
 Special treatment of problems with integer variables which are not continuously differentiable.