# TOMVIEW  
# REGISTER (TOMVIEW)
# LOGIN  
# myTOMVIEW
TOMLAB LOGO

« Previous « Start » Next »

3  Problem types and Solver Routines

Table 1 defines all problem types in TOMVIEW. Each formal problem definition below is accompanied by brief suggestions on suitable solvers. This is followed in Section 3.2 by a complete list of the available solver routines in TOMVIEW and the various available extensions, such as /SOL.

3.1  Definition of Problem Types

The unconstrained optimization (uc) problem is defined as
 
min
x
f(x)
   
s/t
xL ≤ x ≤ xU,
    (1)
where x, xL, xU ∈ Rn and f(x) ∈ R. For unbounded variables, the corresponding elements of xL,xU may be set to ± ∞.

Recommended solvers: TOMVIEW /NPSOL and TOMVIEW /SNOPT.

The quadratic programming (qp) problem is defined as
 
min
x
f(x) =
1
2
xT F x + cT x
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (2)
where c, x, xL, xU ∈ Rn, F ∈ Rn × n, A ∈ Rm1 × n, and bL,bU ∈ Rm1.

Recommended solvers: TOMVIEW /QPOPT, TOMVIEW /SNOPT and TOMVIEW /SQOPT.

A positive semidefinite F-matrix gives a convex QP, otherwise the problem is nonconvex. Nonconvex quadratic programs are solved with a standard active-set method [20], implemented in for example routine SNOPT. It converges to a local minimum for indefinite quadratic programs.

MINOS, or the dense QP solver QPOPT may be used. In the TOMVIEW /SOL extension the SQOPT solver is suitable for both dense and large, sparse convex QP and SNOPT works fine for dense or sparse nonconvex QP.

For very large-scale problems, an interior point solver is recommended, such as TOMVIEW /CPLEX.

The constrained nonlinear optimization problem (con) is defined as
 
min
x
f(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
cL ≤ c(x) ≤ cU
    (3)
where x, xL, xU ∈ Rn, f(x) ∈ R, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

Recommended solvers: TOMVIEW /SNOPT, TOMVIEW /NPSOL and TOMVIEW /MINOS.

TOMVIEW /MINOS solves constrained nonlinear programs. The TOMVIEW /SOL extension gives an additional set of general solvers for dense or sparse problems.

The box-bounded global optimization (glb) problem is defined as
 
min
x
f(x)
   
s/t
−∞ < xL ≤ x ≤ xU < ∞ ,
    (4)
where x, xL, xU ∈ Rn, f(x) ∈ R, i.e. problems of the form (1) that have finite simple bounds on all variables.

Recommended solver: TOMVIEW /LGO.

The TOMVIEW Base Module solver glbDirect implements the DIRECT algorithm [6], which is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. In glbDirect no derivative information is used. For global optimization problems with expensive function evaluations the TOMVIEW /CGO routine ego implements the Efficient Global Optimization (EGO) algorithm [7]. The idea of the EGO algorithm is to first fit a response surface to data collected by evaluating the objective function at a few points. Then, EGO balances between finding the minimum of the surface and improving the approximation by sampling where the prediction error may be high.

The global mixed-integer nonlinear programming (glc) problem is defined as
 
min
x
f(x)
   
s/t
−∞ < xL ≤ x ≤ xU < ∞
  bL ≤ A x ≤ bU  
  cL ≤ c(x) ≤ cU,  xj ∈ N   ∀ j ∈ I,
    (5)
where x, xL, xU ∈ Rn, f(x) ∈ R, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2. The variables x ∈ I, the index subset of 1,...,n, are restricted to be integers.

Recommended solvers: glcDirect.

The TOMVIEW Base Module solver glcDirect implements an extended version of the DIRECT algorithm [19], that handles problems with both nonlinear and integer constraints.

The linear programming (lp) problem is defined as
 
min
x
f(x) = cT x
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (6)
where c, x, xL, xU ∈ Rn, A ∈ Rm1 × n, and bL,bU ∈ Rm1.

Recommended solvers: TOMVIEW /CPLEX.

The TOMVIEW Base Module solver milpsolve implements simplex algorithms for lp problems.

When a dual feasible point is known in (6) it is efficient to use the dual simplex algorithm implemented in the TOMVIEW Base Module solver milpsolve. MINOS is efficient for solving large, sparse LP problems. Dense problems are solved by QPOPT. The TOMVIEW /SOL extension gives the additional possibility of using SQOPT to solve large, sparse LP.

The recommended solver normally outperforms all other solvers.

The mixed-integer programming problem (mip) is defined as
 
min
x
f(x) = cT x
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU,  xj ∈ N   ∀ j ∈ I
    (7)
where c, x, xL, xU ∈ Rn, A ∈ Rm1 × n, and bL,bU ∈ Rm1. The variables x ∈ I, the index subset of 1,...,n are restricted to be integers. Equality constraints are defined by setting the lower bound equal to the upper bound, i.e. for constraint i: bL(i) = bU(i).

Recommended solver: TOMVIEW /CPLEX.

Mixed-integer programs can be solved using the TOMVIEW Base Module routine milpsolve that implements a standard branch-and-bound algorithm, see Nemhauser and Wolsey [22, chap. 8]. milpsolve also implements user defined priorities for variable selection, and different tree search strategies. The TOMVIEW /CPLEX extension gives access to the state-of-the-art LP, QP, MILP and MIQP solver CPLEX. For many MIP problems, it is necessary to use such a powerful solver, if the solution needs be obtained in any reasonable time frame.

The linear least squares (lls) problem is defined as
 
min
x
f(x) =
1
2
|| C x − d ||
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
    (8)
where x, xL, xU ∈ Rn, d ∈ RM, C ∈ RM × n, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

Recommended solvers: TOMVIEW /LSSOL or TOMVIEW /LSQR.

LSQR solves unconstrained sparse lls problems. In the TOMVIEW /NPSOL or TOMVIEW /SOL extension the LSSOL solver is suitable for dense linear least squares problems.

The constrained nonlinear least squares (cls) problem is defined as
 
min
x
f(x) =
1
2
r(x)T r(x)
   
s/t
xL ≤ x ≤ xU,
bL ≤ A x ≤ bU
cL ≤ c(x) ≤ cU
    (9)
where x, xL, xU ∈ Rn, r(x) ∈ RM, A ∈ Rm1 × n, bL,bU ∈ Rm1 and cL,c(x),cU ∈ Rm2.

Recommended solvers: TOMVIEW /NLSSOL.

A fast and robust solver is NLSSOL, available in the TOMVIEW /NPSOL or the TOMVIEW /SOL extension toolbox.

3.2  Solver functionality

3.2.1  TOMVIEW Base Module

TOMVIEW includes a set of optimization solvers and routines that convert problems to a smooth format. Most of them were originally developed by the Applied Optimization and Modeling group (TOM) [17]. Since then they have been improved e.g. to handle TOMVIEW sparse arrays and been further developed. Table 3 lists the main set of TOM optimization solvers in all versions of TOMVIEW.


Table 3: The optimization solvers in TOMVIEW Base Module.
Function Description Section
glbDirect Box-bounded global optimization, using only function values. Fortran/C implementation. 6.1.1
glcDirect Box-bounded global optimization, using only function values. Fortran/C implementation. 6.1.2
goalsolve Solves sparse multi-objective goal attainment problems. Reformulates problem and calls any suitable nonlinear solver. 6.1.3
inflinsolve Linearly constrained minimax optimization. Reformulates problem and calls any suitable LP solver. 6.1.4
infsolve Constrained minimax optimization. Reformulates problem and calls any suitable nonlinear solver. 6.1.5
L1linsolve Linearly constrained L1 optimization. Reformulates problem and calls any suitable LP solver. 6.1.6
L1solve Constrained L1 optimization. Reformulates problem and calls any suitable nonlinear solver. 6.1.7
MILPSOLVE Mixed-integer programming using branch and bound. 6.1.8
QLD Dense quadratic programming. 6.1.9
slssolve Sparse constrained nonlinear least squares. Reformulates problem and calls any suitable sparse nonlinear solver. 6.1.10
 

3.2.2  TOMVIEW /CGO

The add-on toolbox TOMVIEW /CGO solves costly global optimization problems. The solvers are listed in Table 4. They are written in a combination of LabVIEW and C code.


Table 4: Additional solvers in TOMVIEW /CGO.
Function Description Reference
rbfSolve Costly constrained box-bounded optimization using a RBF algorithm. [4]
ego Costly constrained box-bounded optimization using the Efficient Global Optimization (EGO) algorithm. [7]

3.2.3  TOMVIEW /CPLEX

The add-on toolbox TOMVIEW /CPLEX solves large-scale mixed-integer linear and quadratic programming problems. The solver package was developed in co-operation with ILOG S.A. The TOMVIEW /CPLEX solver package and interface are described in a manual available at http://tomopt.com.

3.2.4  TOMVIEW /KNITRO

The add-on toolbox TOMVIEW /KNITRO solves large-scale nonlinear programming problems with interior (barrier) point trust-region methods. The solver package was developed in co-operation with Ziena Optimization Inc. The TOMVIEW /KNITRO manual is available at http://tomopt.com.

3.2.5  TOMVIEW /LGO

The add-on toolbox TOMVIEW /LGO solves global nonlinear programming problems. The LGO solver package is developed by Pintér Consulting Services, Inc. [24] The TOMVIEW /LGO manual is available at http://tomopt.com.

3.2.6  TOMVIEW /MINOS

Table 5 lists the solvers included in TOMVIEW /MINOS. All functionality of the SOL solvers are available and changeable in the TOMVIEW framework in LabVIEW.


Table 5: The SOL optimization solvers in TOMVIEW /MINOS.
Function Description Reference
MINOS 5.51 Sparse linear and nonlinear programming with linear and nonlinear constraints. [21]
QPOPT 1.0-10 Non-convex quadratic programming with dense constraint matrix and sparse or dense quadratic matrix. [12]

3.2.7  TOMVIEW /NPSOL

The add-on toolbox TOMVIEW /NPSOL is a sub package of TOMVIEW /SOL. The package includes the MINOS solvers as well as NPSOL, LSSOL, LSQR and NLSSOL. The TOMVIEW /NPSOL manual is available at http://tomopt.com.

3.2.8  TOMVIEW /SNOPT

The add-on toolbox TOMVIEW /SNOPT is a sub package of TOMVIEW /SOL. The package includes the MINOS solvers as well as SNOPT and SQOPT. The TOMVIEW /SNOPT manual is available at http://tomopt.com.

3.2.9  TOMVIEW /SOL

The extension toolbox TOMVIEW /SOL gives access to the complete set of Fortran solvers developed by the Stanford Systems Optimization Laboratory (SOL). These solvers are listed in Table 5 and 6.


Table 6: The optimization solvers in the TOMVIEW /SOL toolbox.
Function Description Reference
NPSOL 5.02 Dense linear and nonlinear programming with linear and nonlinear constraints. [16]
SNOPT 7.1-1 Large, sparse linear and nonlinear programming with linear and nonlinear constraints. [15, 13]
SQOPT 7.1-1 Sparse convex quadratic programming. [14]
NLSSOL 5.0-2 Constrained nonlinear least squares. NLSSOL is based on NPSOL. No reference except for general NPSOL reference. [16]
LSSOL 1.05-4 Dense linear and quadratic programs (convex), and constrained linear least squares problems. [11]

3.2.10  TOMVIEW /XA

The add-on toolbox TOMVIEW /XA solves large-scale linear, binary, integer and semi-continuous linear programming problems, as well as quadratic programming problems. The solver package was developed in co-operation with Sunset Software Technology. The TOMVIEW /XA package is described in a separate manual available at http://tomopt.com.

3.2.11  Finding Available Solvers

To get a list of all available solvers see the drop down list in the quick guide example for the problem type of interest.

Table 1.

Note that solvers for a more general problem type may be used to solve the problem. In Table 7 an attempt has been made to classify these relations.


Table 7: The problem classes (probType) possible to solve with each type of solver (solvType) is marked with an x. When the solver is in theory possible to use, but from a practical point of view is probably not suitable, parenthesis are added (x).


  solvType
probType uc qp con ls lls cls mip lp glb glc
uc x   x           x (x)
qp   x x             (x)
con     x             (x)
ls     x x   x       (x)
lls   x x x x x       (x)
cls     x     x       (x)
mip             x     (x)
lp   x x       x x   (x)
glb     (x)           x x
glc     (x)             x
exp x   x (x)   x       (x)

« Previous « Start » Next »