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
where , , and
. The variables , the
index subset of 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
| ||||||||||||||||||||||||||||||
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.
|
PPP | Pre-processing 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.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.
| ||||||||||
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.
| ||||||||||
INIT_BND | Selects method for setting lower bound when f_Low not changed from default.
| ||||||||||
SETTOL | Flag enabling changing tolerances, described below under optParam.eps_x, optParam.eps_x and optParam.eps_f.
| ||||||||||
INTSOLLIM_INCR | Integer option when using CPLEX as MIP subsolver.
| ||||||||||
USECUTPOOL | Set nonzero to use a pool for the alpha-regulated extended cutting planes.
| ||||||||||
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.
| ||||||||||
MAXITNOIMP | Limit on the number of successive iterations allowed without any improvements at all to neither objective nor solution point before the solver terminates
| ||||||||||
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.
| |
Inform | Inform for ExitFlag != 3
| |
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.