The Optimization package takes advantage of built-in library routines provided by the Numerical Algorithms Group (NAG). The package performs computations in either the hardware floating-point environment or the arbitrary-precision software floating-point environment. Additionally, Maple offers an interactive Optimization Assistant that supports model formulation and solution, and (through its Optimization Plotter) enables the visualization of the objective function and constraints.

In order to load the Optimization package, the following Maple input statement is used:
> with(Optimization):

Interactive Usage
The interactive Optimization Assistant Maplet provides access to a model-editing dialog, as well as to Maple's built-in local search methods. The objective function and the constraints are defined as algebraic expressions. In order to launch the Maplet, the following Maple input is given:
> Interactive():

As a very simple example, I shall consider a tiny linear optimization problem:

The corresponding screen-shot and solution (by clicking on the Solve button and using the linear solver with default settings) are shown in Figure 1.

Figure 1: Optimization package: Optimization Assistant.

Clicking next on the Plot button displays the objective function in the neighborhood of the solution. The objective function surface plot projections also show the constraint lines, as well as the projected location of the computed extremum point as indicated by a small green dot (Figure 2).

Figure 2: Optimization Plotter in the Optimization package.

Command-line Usage
In command-line usage, optimization problems in Maple can be specified in several (algebraic, operator and matrix) forms.

Algebraic Model Form. The algebraic form is perhaps the most commonly used method to specify optimization problems. The objective function and the constraints are simply given as algebraic expressions. (This form is accepted also by the interactive Maplet.)
> objective:=2*x+4*y:
> constraints:={x+5*y<=80,x+y=10}:
> bounds:=x=0..infinity, y=0..infinity:

The Optimization package can be used to solve this problem (using default settings) with the single command-line:
> solution:=LPSolve(objective, constraints, bounds);
solution := [20., [x = 10., y = 0.]]

Maple returns the solution as a list containing the final minimum (or maximum) value and the computed optimal point; the point is given as a list containing the values of the decision variables.

Note that the Minimize command automatically selects the most appropriate solver for the optimization problem that has been formalized. Also, if the bounds for all decision variables are of the form [0, *), the assume=nonnegative option can be used.
> solution:=Minimize(objective, constraints, assume=nonnegative);
solution := [20., [x = 10., y = 0.]]

Matrix Model Form. The Optimization package is also able to accept optimization problems formulated in the more traditional matrix notation form (denoted in Maple as matrix form):

The matrix form is the one used by the internal solvers and generally results in best performance. Consider the matrix form of the optimization problem above:
> c := Vector([2,4], datatype = float):
> A := Matrix([[1,5],[-4,-2]], datatype = float):
> b := Vector([80,-20], datatype = float):
> > Aeq := Matrix([[1,1]], datatype = float):
> beq := Vector([10], datatype = float):

The Optimization package can be used to solve this problem (using default settings) with the single command-line:
> LPSolve(c, [A, b, Aeq, beq], assume=nonnegative);

The Optimization package offers a command that imports a linear program from a standard MPS data file. This form of the problem may be sent directly to the linear programming solver.

I will mention the nonlinear solver components of the Optimization package briefly, as part of the review on the Global Optimization Toolbox for Maple in the following section.

Global Optimization Toolbox


Global optimization (GO) problems arise in many areas of applied science, business, economics and engineering. Such models can be extraordinarily difficult to solve, due to the existence of multiple local optima (possibly of very different quality) that differ from the global solution. GO problems typically cannot be solved by classical local nonlinear optimization techniques, and hence genuine GO methodology is needed. For thorough discussions of the most prominent GO model types and solution strategies, consult e.g. the GO handbooks edited by Horst and Pardalos (1995) and by Pardalos and Romeijn (2002).

In recent years, several general purpose global solution strategies have been developed and implemented and matured into reliable systems that work either as stand-alone packages or as solver engines that can be connected to various modeling environments. These new implementations make global solvers available to professionals and students, even outside the global optimization research community.

The Global Optimization Toolbox (GOT), released by Maplesoft in 2004, is the result of a joint development effort by Maplesoft and Pintér Consulting Services. The GOT incorporates a suite of nonlinear optimization methods combined with the modeling power and numerous additional features of Maple (Maplesoft, 2005). The core of the Toolbox is the Lipschitz Global Optimizer (LGO) integrated solver suite. For a current detailed technical description, refer to Pintér (2005); for a software review of the LGO, consult Benson and Sun (2000). In summary, the LGO combines (theoretically) rigorous deterministic and stochastic global search methods with traditional constrained local search methodology, to find solutions to constrained GO problems with continuous or Lipschitz model structure.

Customized versions of the LGO have been successfully implemented as stand-alone compiler-based development environments and as solver engines (currently) for AIMMS, Excel, GAMS, MPL, Mathematica and MATLAB (via a link to TOMLAB). In particular, the Global Optimization Toolbox is a tailored implementation of the LGO that has been fully integrated with Maple. Thus, the GOT can, in principle, utilize and handle all real-valued (continuous) functions that can be defined using Maple. This fact supports considerable generality and flexibility in model development, especially in nonlinear systems modeling.


Hardware and Software Requirements


Both Maple and the GOT are available for all current major hardware platforms and operating systems. The minimum system requirements for the GOT are defined by those of Maple and depend on the actual platform and operating system. For instance, for a PC with Windows XP, the minimum system requirements are Intel Pentium III 650 MHz, 128 MB of RAM (512 MB of RAM are recommended), and (for Maple itself) 400 MB of hard disk space. For this review, Maple and the GOT were installed and tested on a Windows XP PC with a Centrino 2.00 GHz processor and 2 GB of RAM.

As expected, GO problems implemented as Maple worksheets retain their portability across platforms and operating systems. Moreover, the use of Maple not only supports full project documentation and model development, but also allows professionals to gain problem insight symbolically, numerically and visually.


Using the Global Optimization Toolbox


The GOT installs in a few seconds by opening the installation file within Maple. Once installed, the GOT can be used in interactive and command-line modes. All of the GOT options are well documented (including readily reusable code examples) in Maple's interactive help system. In order to load the GOT, the following Maple input statement is used:
> with(GlobalOptimization):

Interactive Usage
Similarly to the Optimization package, the GOT offers an interactive Maplet interface. The GOT also offers the more traditional command-line mode, which can be used in various forms.

The interactive Maplet provides access to the GOT's global search solution strategies, as well as to Maple's built-in local search methods. The objective function and the constraints are defined as algebraic expressions. In order to launch the Maplet, the following Maple input is given (as before):
> Interactive():

As an example, I shall consider a small nonconvex optimization problem.

The corresponding screen-shot and solution (by clicking on the Solve button, and using the GOT with default settings) are shown in Figure 3.

Figure 3: Global Optimization Toolbox: Optimization Assistant.

The solution found is close to the theoretical optimum (0 attained at the origin). Notice also that the GOT Optimization Assistant also offers access to Maple's local search methods that are in principle applicable to this model.

Clicking next on the Plot button provides visual cues about the nonlinear nature of the objective function and constraints (Figure 4). The plot displays the objective function in the region of the solution with respect to either one (2-D plot) or two (3-D plot) of the decision variables, fixing all other decision variables to their values at the computed optimum. The Optimization Plotter allows the possibility of looking at different subspace projections when pairing (x, y), (x, z), and (y, z) as needed. The objective function surface plot projections also show the constraint curves, as well as the projected location of the computed extremum point as (again) indicated by a small green dot. All such projections can also be rotated, to enhance the visual analysis.

Figure 4: Global Optimization Toolbox: Optimization Plotter.

Note that the user could also generate similar plots (independently of the Plotter Assistant) using the command-line mode after the solution has been obtained, using standard Maple input. The interactive Maplet simply facilitates and automates the generation of plots.

Command-line Usage
As discussed above, in command-line mode, optimization problems can be specified in several forms: algebraic, operator and matrix.

Algebraic Model Form. Consider the algebraic form of the optimization problem formulated above:
> objective := x^2+(y-z)^2+10*sin((y*z-x-y))^2:
> constraints := {x^2-y^2+z^2<=1,x*z^2+y-z<=0}:
> bounds := x=-1..2,y=-3..3,z=-2..4:

The GOT can be used to solve this problem (using default settings) with the single command-line:
> solution:=GlobalSolve(objective, constraints, bounds);
> solution := [0.3601310221e-25, [x = -0.1764942348e-12, y = 0.1985369434e-12, z = 0.2005561616e-12]]

Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a list containing the values of the decision variables.

Note that the second constraint is active at the computed solution:
> eval(constraints, solution[2]);
{0.3195607099e-25 <= 1, -0.20192182e-14 <= 0}

Note also that Maple's built-in local search method finds an inferior (local) solution, as can be expected:
> localsolution:=Minimize(objective, constraints, bounds);
localsolution := [0.0470477514199914709,
[x = -0.189611136130685226,
y = 0.456702084630705608,
z = 0.543297915369292395]]
> eval(constraints,localsolution[2]);
{0.1225482137 <= 1, -0.1425638476 <= 0}

Operator Model Form. When using the operator form, the objective function and the constraints are provided as procedures: each can take one or more parameters as input and returns a scalar. This form of input is accepted by the command-line GlobalSolve, but not by the interactive Maplet.

The operator form of the optimization problem above is:
> objective:=proc(x,y,z)
   x^2+(y-z)^2+10*sin((y*z-x-y))^2
end proc:
> constraints:=proc(x,y,z)
   x^2-y^2+z^2-1:
   x*z^2+y-z:
end proc:
> bounds:=-1..2,-3..3,-2..4:

The GOT can be used to solve the problem using default settings with the command-line:
> GlobalSolve(objective, {constraints}, bounds);

As shown above, Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a vector containing the values of the decision variables.

Matrix Model Form. All computations performed by the solvers in the Toolbox use floating-point vectors and matrices. Optimization problems specified in algebraic and operator forms are converted internally to matrix form.

In matrix form, the objective function and the constraints are specified as procedures taking vector and matrix parameters. The matrix form is the one used by the internal solvers and generally results in best performance. As with the operator form, this form of input is accepted by the command-line, but not by the interactive Maplet.

Here is the matrix form of the optimization problem defined above:
> objective:=proc(v)
   v[1]^2+(v[2]-v[3])^2+10*sin((v[2]*v[3]-v[1]-v[2]))^2
end proc:
> constraints:=proc(v, w)
   w[1]:=v[1]^2-v[2]^2+v[3]^2-1:
   w[2]:=v[1]*v[3]^2+v[2]-v[3]
end proc:
> bl:=Vector([-1,-3,-2],datatype=float):
> bu:=Vector([2,3,4],datatype=float):
> bounds:=[bl,bu]:

Given that there are three decision variables and [2, 0] is the list defining the number of inequality and equality constraints respectively, the GOT now can be used to solve the problem using default settings with the command-line statement.
> GlobalSolve(3, objective, [2,0], constraints, bounds);

As with the operator form, Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a vector containing the values of the decision variables.

Note that for large problem instances, the elegance and compactness of the matrix form can be retained using multiple Maple worksheets, one for the model and one (or several) for data. Data can also be stored in Excel and accessed via the Excel to Maple add-in link.


GOT Solver Srategies


The Toolbox offers three global search strategies and a constrained local search method. The theoretical foundations of the globally convergent methods in the GOT are discussed by Pintér (1996).

The first global strategy is based on the classical branch-and-bound algorithm that combines set partitioning steps with deterministic and randomized sampling. In order to ensure computing deterministic bounds for the global solution, this algorithm assumes that the objective function and constraints are Lipschitz continuous.

The second global strategy is a single-start random search algorithm that adaptively reduces the search region on the basis of sample results, gradually focusing the global search on the region that is estimated to contain the global solution. This algorithm assumes continuity of the objective function and the constraints, which guarantees convergence with probability one.

The third strategy uses an adaptive multi-start random search where the total sampling effort is distributed among several local searches. The results of each search leads to a corresponding initial point for the subsequent local search. Again, this algorithm assumes continuity of the model functions, and converges with probability one. This is the default strategy used by the GOT.

The local search method is based on the generalized reduced gradient algorithm and assumes that the objective function and the constraints are smooth in the neighborhood of the approximate global solution. Selecting the local search option of the GOT disables the global search phase so that only a local search is performed.

Regardless of the mode used to formalize and solve an optimization problem, the GOT calls the LGO external code that uses hardware floating precision. However, the model functions can be evaluated within Maple with higher precision (even with arbitrary precision if necessary). This interaction typically leads to high overall precision of the solution obtained.

GOT Solver Options
It is evident that the conditions required by the different solution strategies are needed to make formal statements about their convergence. It is possible to formulate optimization problems that do not satisfy the theoretical conditions or are extremely difficult, but — as practice shows — one can still expect a good quality, if not strictly optimal, numerical solution using a reasonable amount of computational time.

In general, the quality of the solution depends on the stopping criteria set by the user. This is due to the fact that the global solution strategies search for the numerical solution until one of the stopping criteria is met. The stopping criteria include:

• a limit on the number of model function evaluations performed,
  
  
• a limit on the number of model function evaluations performed with no improvement,
  
  
• an acceptable target for the merit (exact penalty) function during the global search phase,
  
  
• the tolerance for the first-order (numerically computed) optimality conditions, as well as for constraint satisfaction during the local search phase, and
  
  
• the program execution (solver) time limit.

Information regarding the progress of the solver during the solution of an optimization problem is not displayed by default. However, it is possible to receive additional runtime information for both the global and local searches, by setting the information level option higher than its default level 0. The information provided can give indications about the quality of the solution and provide some guidance about the solver options that can be adjusted, if the solution obtained with the given settings is not satisfactory.

The GOT can, in principle, handle all the functions that are defined in Maple. The evaluation of some functions, however, might cause the solver to stop if either the objective function or one of the constraints evaluates to a non-numeric result. The solution procedure also fails if an infeasible or unbounded solution is found (the latter theoretically may not occur, and thus indicates a model error). Finally, as expected, although global search solution strategies do not rely on initial values of the decision variables, the GOT is able to accept initial values if provided.

Application Perspectives and Further Information
The Optimization and GOT packages address the solution of a very broad range of problems. Illustrative examples and applications are discussed in several documents provided by the developers. In particular, GOT examples include e.g., optimization models with embedded Maple functions, systems of nonlinear equations, model calibration, chemical equilibrium modeling, an alkylation process model, circuit design, perfume bottle design, an automotive suspension model, and a nonconvex portfolio management model.

General information about Maple, with extensive links to related products, services, examples, tutorials, books and other resources, is available at Maplesoft's Web site: www.maplesoft.com/.


Concluding Remarks


Maple is a powerful integrated computing system that combines symbolic, numerical and visual methods. Maple has more than 2,700 built-in commands and over 40 packages (such as linear algebra, integral transforms, Boolean logic, financial statistics, etc.) that can be used in a wide variety of fields. Given Maple's broad applicability to O.R., as described in Parlar (2000), many O.R. professionals and students will find Maple to be the one-stop shop for modeling and problem-solving.

Regarding the GOT add-on, the code is technically sound with robust and efficient global solution strategies. The integration of the LGO solver suite with Maple gives access to a combination of unique modeling and solver capabilities, within a single computing environment.

The GOT can be valuable to O.R. professionals and students who are comfortable with Maple or are willing to learn a little bit of Maple programming. The interactive Maplet interface is intuitive and lends itself well to classroom use and for demonstration and research purposes. The matrix form input to formalize GO problems is elegant and could be quite compact, lending itself well for larger-scale modeling purposes. Future GOT developments could include algorithms to solve mixed-integer global optimization problems (in general, the current GOT handles only small size models within this category). The LGO and its tailored versions have been successfully used in applied decision-making and optimization over the past decade, and it is anticipated that the GOT will also prove to be an effective global/local solver suite.

Product Information Single user licenses of Maple 10 are available for $1,995, and the academic price is $995. Volume and upgrade discounts also apply. Maple is available directly from the Maplesoft Web Store at http://webstore.maplesoft.com. Outside of the United States and Canada, Maple is available from Maplesoft reseller partners. A list of partners is available online at www.maplesoft.com/contact/international/index.aspx. Single user commercial licenses of the Global Optimization Toolbox are currently available for $1,695; research licenses are priced at $795. Group/department/site licenses are also available from Maplesoft at www.maplesoft.com.

1. Benson, H. P. and Sun, E., 2000, "LGO: Versatile Tool for Global Optimization," OR/MS Today, Vol. 27, No. 5, pgs. 52-55. See www.lionhrtpub.com/orms/orms-10-00/swr.html.
   
   
2. Horst, R. and Pardalos, P. M. (eds.), 1995, "Handbook of Global Optimization," Volume 1, Kluwer Academic Publishers, Dordrecht.
   
   
3. Maplesoft, 2004, "Global Optimization Toolbox for Maple," Maplesoft, Inc., Waterloo, Ontario. See www.maplesoft.com/products/toolboxes/globaloptimization.
   
   
4. Maplesoft, 2005, "Maple 10," Maplesoft, Inc., Waterloo, Ontario. See http://www.maplesoft.com.
   
   
5. Pardalos, P. M. and Romeijn, H. E. (eds.), 2002, "Handbook of Global Optimization," Volume 2, Kluwer Academic Publishers, Dordrecht.
   
   
6. Parlar, M., 2000, "Interactive Operations Research with Maple: Methods and Models," Springer-Verlag, New York.
   
   
7. Pintér, J.D., 1996, "Global Optimization in Action," Kluwer Academic Publishers, Dordrecht
   
   
8. Pintér, J. D., 2005, "LGO: A Model Development System for Continuous Global Optimization. User's Guide," Pintér Consulting Services, Inc., Halifax, Nova Scotia. See also www.pinterconsulting.com.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2005 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.