# TOMNET  
# REGISTER (TOMNET)
# LOGIN  
# myTOMNET
TOMLAB LOGO

« Previous « Start » Next »

3  Problem types and Solver Routines

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

3.1  Definition of Problem Types

3.1.1  Unconstrained Optimization

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: TOMNET /NPSOL and TOMNET /SNOPT.

3.1.2  Quadratic Programming

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: TOMNET /QPOPT, TOMNET /SNOPT and TOMNET /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 [17], 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 TOMNET /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 TOMNET /CPLEX.

3.1.3  Constrained Nonlinear Optimization

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: TOMNET /SNOPT, TOMNET /NPSOL and TOMNET /MINOS.

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

3.1.4  Box-Bounded Global Optimization

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: TOMNET /LGO.

The TOMNET Base Module solver glbDirect  implements the DIRECT algorithm [5], 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.

3.1.5  Global Mixed-Integer Nonlinear Programming

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 TOMNET Base Module solver glcDirect  implements an extended version of the DIRECT algorithm [16], that handles problems with both nonlinear and integer constraints.

3.1.6  Linear Programming

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: TOMNET /CPLEX.

The TOMNET 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 TOMNET Base Module solver milpsolve . MINOS  is efficient for solving large, sparse LP problems. Dense problems are solved by QPOPT . The TOMNET /SOL extension gives the additional possibility of using SQOPT  to solve large, sparse LP.

The recommended solver normally outperforms all other solvers.

3.1.7  Mixed-Integer Programming

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: TOMNET /CPLEX.

Mixed-integer programs can be solved using the TOMNET Base Module routine milpsolve  that implements a standard branch-and-bound algorithm, see Nemhauser and Wolsey [19, chap. 8]. milpsolve  also implements user defined priorities for variable selection, and different tree search strategies. The TOMNET /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.

3.1.8  Linear Least Squares Problems

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: TOMNET /LSSOL or TOMNET /LSQR.

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

3.1.9  Constrained Nonlinear 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: TOMNET /NLSSOL.

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

3.2  Solver functionality

3.2.1  TOMNET Base Module

TOMNET 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) [14]. Since then they have been improved e.g. to handle TOMNET sparse arrays and been further developed. Table 4 lists the main set of TOM optimization solvers in all versions of TOMNET.


Table 4: The optimization solvers in TOMNET Base Module .
Function Description Section
glbDirect  Box-bounded global optimization, using only function values. Fortran/C implementation. 6.1.1
glcDirect  Constrained global optimization, using objective function linear, integer and nonlinear constraints. Fortran/C implementation. 6.1.2
 

3.2.2  TOMNET /MINOS

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


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

3.2.3  TOMNET /NPSOL

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

3.2.4  TOMNET /SNOPT

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

3.2.5  TOMNET /SOL

The extension toolbox TOMNET /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 TOMNET /SOL toolbox.
Function Description Reference
NPSOL 5.02  Dense linear and nonlinear programming with linear and nonlinear constraints. [13]
SNOPT 7.1-1  Large, sparse linear and nonlinear programming with linear and nonlinear constraints. [12, 10]
SQOPT 7.1-1  Sparse convex quadratic programming. [11]
NLSSOL 5.0-2  Constrained nonlinear least squares. NLSSOL is based on NPSOL. No reference except for general NPSOL reference. [13]
LSSOL 1.05-4  Dense linear and quadratic programs (convex), and constrained linear least squares problems. [8]
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). See table 1 for an explanation on problem types.


  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 »