MIPNLP ecpMINLP: Difference between revisions
m (→Purpose) |
|||
(9 intermediate revisions by the same user not shown) | |||
Line 99: | Line 99: | ||
|} | |} | ||
|-valign="top" | |-valign="top" | ||
|'' | |''PriLevOptMIP''||Print level in MIP sub-solvers, (CPLEX and others, see the documentation for the solver used).<br> | ||
Usually:<br> | |||
=0 No output<br> | |||
>0 Convergence results<br> | |||
>1 Output every iteration<br> | |||
>2 Output each step in the algorithm | |||
|-valign="top" | |||
|''PriLevOptNLP''||Print level in NLP sub-solvers, (SNOPT and others, see the documentation for the solver used).<br> | |||
Usually:<br> | |||
=0 No output<br> | |||
>0 Convergence results<br> | |||
>1 Output every iteration<br> | |||
>2 Output each step in the algorithm | |||
|-valign="top" | |-valign="top" | ||
|''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. | |''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. | ||
|-valign="top" | |||
|''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 | |''SolverLP''||Name of the solver used for LP subproblems when SolverMIP == mipSolve | ||
Line 134: | Line 149: | ||
0 Not used. Default.<br> | 0 Not used. Default.<br> | ||
1 Apply initially on MINLP problem.<br> | 1 Apply initially on MINLP problem.<br> | ||
2 Apply each iteration before solving MILP | 2 Apply each iteration before solving MILP sub-problem. | ||
|- | |- | ||
|''ROUNDH''||If nonzero, a rounding heuristics will be used on the initial NLP solution in order to obtain an initial integer solution. Requires ECPMINLP. | |''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. | ||
|} | |} | ||
Line 157: | Line 172: | ||
<br>1 Preallocate arrays. | <br>1 Preallocate arrays. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''InitBndType''||Selects method for setting lower bound when f_Low not changed from default. | ||
{|class="wikitable" | {|class="wikitable" | ||
!value||method | !value||method | ||
Line 165: | Line 180: | ||
|1 ||Use default TOMLAB NLP solver on problem with relaxed integer constraints. Add a linearization if a feasible MINLP solution was found. | |1 ||Use default TOMLAB NLP solver on problem with relaxed integer constraints. Add a linearization if a feasible MINLP solution was found. | ||
|-valign="top" | |-valign="top" | ||
|2 ||Add an initial linearization as long as a | |2 ||Add an initial linearization as long as a feasible NLP solution was found. The linearization is a simple lower bound on the MILP objective. Default. | ||
|} | |} | ||
|-valign="top" | |-valign="top" | ||
|'' | |''SET_TOL''||Flag enabling changing tolerances, described below under optParam.eps_x, optParam.eps_x and optParam.eps_f. | ||
<br>0 Default. Using the recommended solver default values, 1.0e-3. | <br>0 Default. Using the recommended solver default values, 1.0e-3. | ||
<br>1 Tolerances can be changed, taken from Prob.optParam. | <br>1 Tolerances can be changed, taken from Prob.optParam. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''IntSolLimIncr''||Integer option when using [[CPLEX]] as MIP subsolver. | ||
<br>Define how much the CPLEX parameter | <br>Define how much the [[CPLEX]] parameter IntSolLimIncr increases when a feasible solution is not optimal and all alpha values have met their criteria. | ||
<br> | <br>When set to zero, the optimal strategy will instead be used immediately, without any gradual increase of INTSOLLIM. | ||
<br>Default is 1. | <br>Default is 1. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''USE_CUTPOOL''||Set nonzero to use a pool for the alpha-regulated extended cutting planes. | ||
<br>Cuts not active in the MILP-solution for | <br>Cuts not active in the MILP-solution for CutDelBound iterations in a row will be inactivated (removed from the MILP-problem) until they are violated in a new solution. | ||
<br>Default is 0, not used. | <br>Default is 0, not used. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''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. | ||
<br>Default is 15 times. | <br>Default is 15 times. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''MaxIterWoImpr''||Limit on the number of successive iterations allowed without any improvements at all to neither objective nor solution point before the solver terminates | ||
<br>Default is 2. | <br>Default is 2. | ||
|-valign="top" | |-valign="top" | ||
|'' | |''USE_NLP''||=1 User and NLP sub-solver on the initial integer-relaxed original problem, as well as the NLP problem with fixed integer values during the main iteration.<br> | ||
=2 Use a global sub-solver on the initial integer-relaxed 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. | |||
<br>Default is 1<br> | |||
<br> | |||
{|class="wikitable" | |||
!colspan="2"|If UseNLP is set to 2, the following parameters in the Prob-struct are used: | |||
|- | |||
|'''Field'''||'''Description''' | |||
|-valign="top" | |-valign="top" | ||
|'' | |''Prob.RandState''||See help rngset for how to initialize the random generator.<br> | ||
Default randState = -1<br> | |||
If Convex == 0 and globalSolver == 'multiMin', RandState is sent to [[multiMin]] to initialize the random generator. | |||
|-valign="top" | |-valign="top" | ||
|'' | |''Prob.xInit''||Parameter sent to the solver [[multiMin]] which is used to solve relaxed sub-problems for nonconvex problems (with Prob.Convex set to false).<br> | ||
xInit determines the way initial points are generated and is set as follows:<br> | |||
<br> | |||
Either<br> | |||
1x1 number<br> | |||
If > 0, the number of random initial points, default min(3000,30*n);<br> | |||
If < 0, generate |xInit| points with Latin Hypercube design<br> | |||
<br> | |||
d x m matrix - Every column is an initial point (of length d = Prob.N)<br> | |||
<br> | |||
Default value for xInit is min(3000,max(60,N*6)) except for the initial problem. | |||
|-valign="top" | |||
|''Prob.xInit0''||Parameter sent to the solver [[multiMin]] when solving the initial relaxed NLP problem. Default value for xInit0 is min(3000,max(100,N*10)).<br> | |||
See xInit for more information. | |||
|-valign="top" | |||
|''Prob.globalSolver''||Used to solve the NLP subproblem for nonconvex problems (when Prob.Convex set to false). Default is [[multiMin]].<br> | |||
[[multiMin]] is using SolverNLP and SolverNLP0 as the NLP sub-solver. | |||
|} | |||
|-valign="top" | |||
|''RESELECT_CUTS''||Set nonzero to enable cut reselection heuristics. Default is 1, enabled. | |||
|-valign="top" | |||
|''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. | |||
|} | |} | ||
Line 206: | Line 251: | ||
|''MaxIter''||Maximal number of iterations, default 10000 | |''MaxIter''||Maximal number of iterations, default 10000 | ||
|-valign="top" | |-valign="top" | ||
|''IterPrint''||Print short information each iteration. Setting PriLev > | |''IterPrint''||Print short information each iteration. Setting PriLev > 2 also enables IterPrint, setting it to 1. | ||
|-valign="top" | |-valign="top" | ||
|''eps_x''||Linear constraint violation convergence tolerance. Default is 2.0e-6 | |''eps_x''||Linear constraint violation convergence tolerance. Default is 2.0e-6 | ||
Line 215: | Line 260: | ||
|} | |} | ||
''NOTE:'' For the solver to use these tolerances, the flag ''ECPMINLP. | ''NOTE:'' For the solver to use these tolerances, the flag ''ECPMINLP.SET_TOL'' must be set to nonzero. | ||
==Outputs== | ==Outputs== | ||
{| class="wikitable" | {| class="wikitable" | ||
!''Result''||colspan="2"|Structure with result from optimization. The following fields are | !''Result''||colspan="2"|Structure with result from optimization. The following fields are used: | ||
|- | |- | ||
|||''Iter ''||Number of iterations. | |||''Iter ''||Number of iterations. | ||
Line 239: | Line 284: | ||
|||''ExitText''||Text string giving ''ExitFlag'' and ''Inform'' information. | |||''ExitText''||Text string giving ''ExitFlag'' and ''Inform'' information. | ||
|-valign="top" | |-valign="top" | ||
|||''DualGap''||Relative duality gap, max(0,fIPMin-fLB)/ | |||''DualGap''||Relative duality gap, set as follows: | ||
{| class="wikitable" | |||
!''Condition fulfilled''||DualGap value set | |||
|- | |||
||fIPMin ~= 0||max(0,fIPMin-fLB)/|fIPMin| | |||
|- | |||
||fIPMin == 0||max(0,fIPMin-fLB) | |||
|} | |||
To get the percentage duality gap, scale with 100.<br> | |||
PercentageGap = 100*Dual- Gap.<br> | |||
To get the absolute value duality gap, scale with fIPMin.<br> | |||
AbsoluteGap = fIPMin * DualGap | |||
|- | |- | ||
|||''x_k''||Solution. | |||''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. | |||
|-valign="top" | |-valign="top" | ||
|||''f_k''||Function value at optimum. | |||''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. | |||''g_k''||Gradient vector at optimum. | ||
Line 275: | Line 336: | ||
* A rounding heuristics performed on the initial NLP solution in order to obtain an initial upper bound on the initial solutions. | * 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. | * Optional use of a cutpool for the alpha-regulated extended cutting planes. | ||
* Special treatment of problems with integer variables which are not continuously differentiable. | |||
[[Category:MIPNLP]] | [[Category:MIPNLP]] |
Latest revision as of 10:25, 9 March 2015
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 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 sub-solvers, (CPLEX and others, see the documentation for the solver used). Usually: | ||||||||||||||||||||||||||||||
PriLevOptNLP | Print level in NLP sub-solvers, (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 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.InitBndType 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.
| ||||||||||||
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 alpha-regulated 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 sub-solver on the initial integer-relaxed original problem, as well as the NLP problem with fixed integer values during the main iteration. =2 Use a global sub-solver on the initial integer-relaxed 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.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.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 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.
- Special treatment of problems with integer variables which are not continuously differentiable.