« Previous « Start » Next »
6 Solver Reference
Detailed descriptions of the TOMNET solvers, driver routines and
some utilities are given in the following sections. Also see the
help for each solver. All solvers except for the TOMNET Base Module
are described in separate manuals.
6.1 TOMNET /BASE
For a description of solvers, see the help in the the User's Guide
for the particular solver.
Purpose
Solve box-bounded global optimization problems.
glbDirect solves problems of the form
where
f 
R and
x,
xL,
xU R n.
glbDirect was originally a Fortran implementation.
Calling Syntax
glbDirect solver = new glbDirect();
solver.Solve(Prob, out result);
Description of Inputs
| Prob |
Problem description. The following members are used: |
| |
|
|
x_L |
Lower bounds for x, must be given to restrict
the search space. |
| |
x_U |
Upper bounds for x, must be given to restrict
the search space. |
| |
| |
Name |
Name of the problem. Used for security if doing warm start. |
| |
f |
The objective function f(x) is used. |
| |
Description of Outputs
| Result |
Object
with result from optimization.
The following fields are of special interest: |
| |
| |
| |
x_k |
Optimal point. |
| |
f_k |
Function value at optimum. |
| |
| |
Iter |
Number of iterations. |
| |
FuncEv |
Number function evaluations. |
| |
ExitText |
Text string giving ExitFlag and Inform information. |
| |
ExitFlag |
Exit code. |
| |
|
0 = Normal termination, max number of iterations /func.evals reached. |
| |
|
1 = Some bound, lower or upper is missing. |
| |
|
2 = Some bound is inf, must be finite. |
| |
|
4 = Numerical trouble determining optimal rectangle, empty set and cannot continue. |
| |
Inform |
Inform code. |
| |
|
1 = Function value f is less than fGoal. |
| |
|
2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f−fGoal)/abs(fGoal) <= fTol. |
| |
|
3 = Maximum number of iterations done. |
| |
|
4 = Maximum number of function evaluations done. |
| |
|
91= Numerical trouble, did not find element in list. |
| |
|
92= Numerical trouble, No rectangle to work on. |
| |
|
99= Other error, see ExitFlag. |
Description of Options
| Options available for glbDirect |
| |
| |
| LogFile |
File for log information. |
| |
| PrintLevel |
Print Level. 0 = Silent. 1 = Errors. 2 = Termination message and warm start info. 3 = Option summary. |
| |
| MaxFunc |
Maximal number of function evaluations, default 10000 (roughly). |
| |
| Maxiter |
Maximal number of iterations, default 200. |
| |
| Parallel |
Set to 1 in order to have glbDirect to call
Prob.FUNCS.f with a matrix x of points to let the user function
compute function values in parallel. Default: 0. Not currently active. |
| |
| WarmStart |
If true, >0, glbDirect reads the output
from the last run if it exists. glbDirect uses this warm
start information to continue from the last run. |
| |
| IterPrint |
Print iteration log every ITERPRINT iteration. Set
to 0 for no iteration log. PRILEV must be set to at
least 1 to have iteration log to be printed. |
| |
| FunTol |
Relative accuracy for function value. Stop if abs(f−FGOAL) <= abs(FGOAL) * FUNTOL , if FGOAL =0. Stop if abs(f−FGOAL) <= FUNTOL , if FGOAL == 0. |
| |
| VarTol |
Convergence tolerance in x. All possible rectangles are less than this tolerance (scaled to (0,1) ). See the output field MAXTRI. |
| |
| GLWeight |
Global/local weight parameter, default 1E-4. |
| |
| FGoal |
Goal for function value, if empty not used. |
| |
Description
The global optimization routine
glbDirect is an
implementation of the DIRECT algorithm presented in
[
5].The algorithm in
glbDirect is a Fortran
implementation of the Matlab algorithm in
glbSolve . DIRECT is a modification of the standard Lipschitzian approach that
eliminates the need to specify a Lipschitz constant. Since no such
constant is used, there is no natural way of defining convergence
(except when the optimal function value is known). Therefore
glbDirect runs a predefined number of iterations and
considers the best function value found as the optimal one. It is
possible for the user to
restart glbDirect with the
final status of all parameters from the previous run, a so called
warm start. Assume that a run has been made with
glbDirect on a certain problem for 50 iterations. Then a run
of e.g. 40 iterations more should give the same result as if the run
had been using 90 iterations in the first place. To do a warm start
of
glbDirect an option
WARMSTART should be set to one
and warm start information defined. Then
glbDirect is using
output previously obtained to make the restart. The code also
includes the subfunction
conhull (embedded) which is an
implementation of the algorithm GRAHAMHULL in [
22, page
108] with the modifications proposed on page 109.
conhull is used to identify all points lying on the convex
hull defined by a set of points in the plane.
Purpose
Solve global mixed-integer nonlinear programming problems.
glcDirect solves problems of the form
|
|
|
f(x) |
|
|
|
|
| s/t |
xL |
≤ |
x |
≤ |
xU |
| |
bL |
≤ |
Ax |
≤ |
bU |
| |
cL |
≤ |
c(x) |
≤ |
cU |
| |
|
|
xi integer |
|
i I |
|
where
x,
xL,
xU Rn,
c(
x),
cL,
cU Rm1,
A Rm2× n and
bL,
bU Rm2.
The variables
x I, the index subset of 1,...,
n are
restricted to be integers. Recommendation: Put the integers as the
first variables. Put low range integers before large range integers.
Linear constraints are specially treated. Equality constraints are
added as penalties to the objective. Weights are computed
automatically, assuming f(x) scaled to be roughly 1 at optimum.
Otherwise scale f(x).
glcDirect is originally a Fortran implementation that has
been embedded in .NET.
Calling Syntax
glcDirect solver = new glcDirect();
solver.Solve(Prob, out result);
Description of Inputs
| Prob |
Problem description. The following members are used: |
| |
| |
Name |
Problem name. Used for safety when doing warm starts. |
| |
| |
f |
The objective function f(x) is used. |
| |
c |
The nonlinear constraints c(x) is used. |
| |
| |
A |
Linear constraints matrix. |
| |
b_L |
Lower bounds on the linear constraints. |
| |
b_U |
Upper bounds on the linear constraints. |
| |
| |
c_L |
Lower bounds on the nonlinear constraints. |
| |
c_U |
Upper bounds on the nonlinear constraints. |
| |
x_L |
Lower bounds for x, must be finite to restrict the search space. |
| |
x_U |
Upper bounds for x, must be finite to restrict the search space. |
| |
| |
IntVars |
IntVars is assumed to be a set of indices.
It is advised to number the integer values as the first
variables, before the continuous. The tree search will then
be executed more efficiently. |
| |
Description of Outputs
| Result |
Object
with result from optimization.
The following fields are of special interest: |
| |
| |
| |
x_k |
Optimal point. |
| |
f_k |
Function value at optimum. |
| |
c_k |
Nonlinear constraints values at x_k. |
| |
| |
Iter |
Number of iterations. |
| |
FuncEv |
Number function evaluations. |
| |
ExitText |
Text string giving ExitFlag and Inform information. |
| |
ExitFlag |
0 = Normal termination, max number of iterations func.evals reached. |
| |
|
2 = Some upper bounds below lower bounds. |
| |
|
4 = Numerical trouble, and cannot continue. |
| |
|
7 = Reached maxFunc or maxIter, NOT feasible. |
| |
|
8 = Empty domain for integer variables. |
| |
|
10= Input errors. |
| |
| |
Inform |
1 = Function value f is less than fGoal. |
| |
|
2 = Absolute function value f is less than
fTol, only if fGoal = 0 or Relative error in function value f is
less than fTol, i.e.
abs(f-fGoal)/abs(fGoal) <= fTol. |
| |
|
3 = Maximum number of iterations done. |
| |
|
4 = Maximum number of function evaluations done. |
| |
|
5 = Maximum number of function evaluations
would most likely be too many in the next iteration, save warm start
info, stop. |
| |
|
6 = Maximum number of function
evaluations would most likely be too many in the next iteration,
because 2*sLen >= maxFDim - nFunc, save warm start
info, stop. |
| |
|
7 = Space is dense. |
| |
|
8 = Either space is dense, or MIP is dense. |
| |
|
10= No progress in this run, return solution from previous one. |
| |
|
91= Infeasible. |
| |
|
92= No rectangles to work on. |
| |
|
93= sLen = 0, no feasible integer solution exists. |
| |
|
94= All variables are fixed. |
| |
|
95= There exist free constraints. |
| |
Description of Options
| Options available for glcDirect |
| |
| |
| LogFile |
File for log information. |
| |
| PrintLevel |
Print Level. This controls both regular printing
from glcDirect and the amount of iteration log information to print. |
| |
0 = Silent. 1 = Warnings and errors printed. Iteration log on
iterations improving function value. 2 = Iteration log on all
iterations. 3 = Log for
each function evaluation. 4 = Print list of parameter settings. |
| |
See ITERPRINT for more information on iteration log
printing. |
| |
| WarmStart |
If true, >0, glcDirect reads the output from the
last run if it exists. glcDirect uses this warm start
information to continue from the last run. |
| |
| MaxCpu |
Maximum CPU Time (in seconds) to be used. Default 36000. |
| |
| FCall |
=0 (Default). If linear constraints cannot be
feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point. |
| |
=1 Always compute f(x) and c(x), even if linear
constraints are
not feasible anywhere in rectangle. Do not update rates of change
for the constraints. |
| |
=2 Always compute f(x) and c(x), even if linear
constraints are not feasible anywhere in rectangle. Update rates of
change constraints. |
| |
| UseRoC |
=1 (Default). Use original Rate of Change
(RoC) for constraints to weight the constraint violations in
selecting which rectangle divide. |
| |
=0 Avoid RoC, giving equal weights to all
constraint violations.
Suggested if difficulty to find feasible points. For problems
where linear constraints have been added among the nonlinear
(NOT RECOMMENDED; AVOID!!!), then option useRoc=0 has been
successful, whereas useRoC completely fails. |
| |
=2 Avoid RoC for linear constraints, giving
weight one to these
constraint violations, whereas the nonlinear constraints use RoC. |
| |
=3 Use RoC for nonlinear constraints, but
linear constraints are not used to determine which rectangle to use. |
| |
| Branch |
=0 Divide rectangle by selecting the longest
side, if ties use the lowest index. This is the Jones DIRECT paper strategy. |
| |
=1 First branch the integer variables,
selecting the variable
with the least splits. If all integer variables are split, split
on the continuous variables as in BRANCH=0. DEFAULT!
Normally much more efficient than =0 for mixed-integer problems. |
| |
=2 First branch the integer variables with 1,2
or 3 possible values,
e.g [0,1],[0,2] variables, selecting the variable with least splits.
Then branch the other integer variables, selecting the variable
with the least splits. If all integer variables are split, split
on the continuous variables as in BRANCH=0. |
| |
=3 Like =2, but use priorities on the
variables. |
| |
| RecTie |
When minimizing the measure to find which new
rectangle to try to
get feasible, there are often ties, several rectangles have the same
minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles with low
index are often larger then the rectangles with higher index.
Selecting one of each type could help, but often =0 is fastest. |
| |
=0 Use the rectangle with value a, with lowest index (original). |
| |
=1 (Default): Use 1 of the smallest and 1 of largest rectangles. |
| |
=2 Use the last rectangle with the same value a, not the 1st. |
| |
=3 Use one of the smallest rectangles with same value a. |
| |
=4 Use all rectangles with the same value a, not just the 1st. |
| |
| EqConFac |
Weight factor for equality constraints when
adding to objective
function f(x) (Default value 10). The weight is computed as
EQCONFAC/"right or left hand side constant value", e.g. if
the constraint is Ax <= b, the weight is EQCONFAC/b
If DIRECT just is pushing down the f(x) value instead of
fulfilling the equality constraints, increase EQCONFAC. |
| |
| AxFeas |
Set nonzero to make glcDirect skip f(x)
evaluations, when the
linear constraints are infeasible, and still no feasible point
has been found. The default is 0. Value 1 demands FCALL == 0.
This option could save some time if f(x) is a bit costly, however
overall performance could on some problems be dramatically worse. |
| |
| FEqual |
All points with function values within
tolerance FEQUAL are considered to be global minima and returned. Default 1E-10. |
| |
| LinWeight |
RateOfChange = LINWEIGHT*||a(i,:)|| for linear
constraints. Balance between linear and nonlinear
constraints. Default 0.1. The higher value, the less influence from linear constraints. |
| |
| Alpha |
Exponential forgetting factor in RoC computation, default 0.9. |
| |
| AvIter |
How many values to use in startup of RoC computation
before switching to exponential smoothing with
forgetting factor alpha. Default 50. |
| |
| FGoal |
Goal for function value, if empty not used. |
| |
| MaxFunc |
Maximal number of function evaluations, default 10000 (roughly). |
| |
| MaxIter |
Maximal number of iterations, default 10000. |
| |
| IterPrint |
Print iteration log every ITERPRINT iteration. Set
to 0 for no iteration log. PRILEV must be set to at
least 1 to have iteration log to be printed. |
| |
| FunTol |
Relative accuracy for function value. Stop if abs(f−FGOAL) <= abs(FGOAL) * FUNTOL , if FGOAL =0. Stop if abs(f−FGOAL) <= FUNTOL , if FGOAL == 0. Default 1E-2. |
| |
| VarTol |
Convergence tolerance in x. All possible rectangles are less than this tolerance (scaled to (0,1) ). See the output field MAXTRI. Default 1E-11. |
| |
| GLWeight |
Global/local weight parameter. Default 1E-4. |
| |
| NLContol |
Nonlinear constraint tolerance. Default 1E-5. |
| |
| LContol |
Linear constraint tolerance. Default 1E-7. |
| |
| FIP |
An upper bound on the optimal f(x) value. If empty, set as Inf. |
| |
Description
The routine
glcDirect implements an extended version of
DIRECT, see [
16], that handles problems with both
nonlinear and integer constraints. The algorithm in
glcDirect
is a Fortran implementation of the Matlab algorithm in
glcSolve .
DIRECT is a modification of the standard Lipschitzian
approach that eliminates the need to specify a Lipschitz constant.
Since no such constant is used, there is no natural way of defining
convergence (except when the optimal function value is known).
Therefore
glcDirect is run for a predefined number of
function evaluations and considers the best function value found as
the optimal one. It is possible for the user to
restart
glcDirect with the final status of all parameters from the
previous run, a so called
warm start. Assume that a run has
been made with
glcDirect on a certain problem for 500
function evaluations. Then a run of e.g. 200 function evaluations
more should give the same result as if the run had been using 700
function evaluations in the first place. To do a warm start of
glcDirect an option
WARMSTART should be set to one.
DIRECT does not explicitly handle equality constraints. It
works best when the integer variables describe an ordered quantity
and is less effective when they are categorical.
Warnings
A significant portion of
glcDirect is coded in Fortran
format. If the solver is aborted, it may have allocated memory for
the computations which is not returned. This may lead to
unpredictable behavior if
glcDirect is started again.
6.2 TOMNET /MINOS
Includes MINOS and QPOPT. This package is included in the following
three as well.
6.3 TOMNET /NPSOL
The following solvers are included in this package: LSSOL, LSQR,
NLSSOL and NPSOL. A separate manual is available from the TOMNET
home page.
6.4 TOMNET /SNOPT
The following solvers are included in this package: SNOPT and SQOPT.
A separate manual is available from the TOMNET home page.
6.5 TOMNET /SOL
All three packaged listed above (MINOS, NPSOL and SNOPT).
« Previous « Start » Next »
TOMNET
