Versatile tool for global optimization
By Harold P. Benson and Erjiang Sun
A large variety of quantitative decision problems in applied mathematics, engineering, the sciences, business, and economics can be described by constrained optimization models. In many applications, including problems in production, transportation, allocation and distribution, relationships can be captured using linear functions. In other applications, including the physical, chemical, biological and environmental sciences, relationships are often described using nonlinear functions. The corresponding nonlinear optimization problems frequently possess large numbers of local optima that are not global optima. These problems, called global (or multi-extremal) optimization problems, cannot be solved by traditional methods of convex programming. This is because these methods can, at best, locate local optima for a global optimization problem. With improvements in the speed and convenience of computing resources in recent years has come an increase in research and development of algorithms for solving global optimization problems. At present, a variety of general purpose and special purpose global optimization algorithms exist. For an overview of these algorithms, see, for instance, the handbook edited by Horst and Pardalos .
The LGO system [LGO is an acronym for Lipschitz (continuous) Global Optimizer] assists in the formulation, global solution and analysis of global optimization problems in which the objective functions are Lipschitz-continuous and the constraints define bounded feasible regions that represent the closures of nonempty open sets. Typically, the feasible region for an LGO problem is a compact set that is described by constraints involving Lipschitz-continuous functions and which includes finite lower and upper bounds on all variables. By definition, the objective function may be a nonconvex function and the feasible region may be a nonconvex (or even disconnected) set. These problem requirements are very general, thus increasing the versatility of LGO.
System Requirements and Installation
The LGO system is available in several versions, depending upon the platform (PC, workstation or mainframe), the maximal problem size that can be solved (expressed as the maximal numbers of variables and constraints allowed), and the operating system used. The core LGO system is written in standard FORTRAN 77. The system is compatible with Lahey FORTRAN or one of the Lahey FORTRAN-compatible platforms, including Borland C++ and Delphi, Microsoft Visual C++ and Visual Basic. The system requirements and installation discussion to follow concentrates upon PC platforms.
Acceptable Operating Systems: The LGO system can be installed on personal computers operated under DOS 5.0, 6.0 and 6.22; Windows 3.1, 3.11, 95, 98 and NT 4.0 systems. Compatibility with all currently used Microsoft PC operating systems can be guaranteed.
Hardware Requirements: To run LGO with appropriate efficiency, a 486 DX level processor is explicitly required; Pentium versions are recommended. A minimum of 16 megabytes of RAM is needed, and more is recommended. At least 10 megabytes of available hard drive disk space is called for, and again, more is recommended. A VGA monitor or any other monitor that supports at least 640 x 480 resolution is required. In workstation environments, there is no need to explicitly set requirements since, as a rule, the hardware is adequate to handle most versions of LGO.
For this review, the LGO system was installed and tested on a Windows 95 PC with a Pentium Pro processor, 64 MB of RAM and a 4 GB hard drive. We used Standard Lahey FORTRAN 95, version 5.5, as our platform. Our version of LGO was capable of globally solving problems with up to 20 variables and 20 constraints, where the lower and upper bounds on variables are not counted as constraints. Larger versions of LGO have handled up to several hundreds of decision variables and constraints. Since LGO consists of a set of standard FORTRAN 77 routines, installation is a simple matter. In our case, Pintér Consulting Services sent us the LGO system by electronic mail. The files were unzipped and placed in a directory of our choosing.
User's Guide and Technical Assistance
Registered users receive a hard copy of the LGO user's guide with the software. In addition, users are also entitled to free technical support and to all software revisions (patches). Technical support can be obtained by contacting Pintér Consulting Services by e-mail or phone. In addition, users may consult the Pintér Consulting Services website (http://is.dal.ca/~jdpinter), where a general overview of the LGO system is provided.
The User's Guide is the main source of information on how to apply the LGO system to specific problems. The guide consists of 10 short chapters and seven appendices. It is specifically targeted to implementations of LGO for personal computers. After a brief introduction to global optimization, the User's Guide describes the types of problems that LGO can handle. In addition to handling most global optimization problems, it should be noted that LGO can also handle standard convex programming problems. Subsequently, the guide explains:
In addition, ample references and reference lists are provided concerning global optimization theory, applications and algorithms. The seven appendices are primarily concerned with giving the FORTRAN templates for each of the main LGO subroutines.
Technical Background: Solver Options
At the heart of the LGO system are four available solver options. Two are capable of conducting global searches, and two are designed for conducting local searches only. To solve a global optimization problem, the minimum requirement is to apply one of the global search solvers. The first global solver is a branch and bound-based procedure. It combines set partitioning with deterministic and randomized sampling. Used alone, this module will generate a close approximation to a global optimizer. The second global solver is a global adaptive random search procedure. This module actively combines random search with a technique that attempts to reduce the search region. The search becomes gradually more focused on a region that, on the basis of actual sample results, is thought to contain a global optimal solution. This module is recommended especially for problems with minimal structure that may have large numbers of local optima. Like the first module, used alone this module will produce a close approximation to a global optimizer.
The third module uses an unconstrained local optimization search that is based upon well-known convex programming approaches. For global optimization problems, it is recommended that this module be used only after applying one of the two global search modules. The last module is a constrained local optimization search module that, like the unconstrained module, is recommended for use only after one of the two global search modules has been used.
In spite of their names, both of the latter two modules can be used in the presence of constraints. The fourth module typically results in a more precise solution vector than the third. Thus, the fourth module can be used after any of the first three modules in order to find a more "polished" optimal solution. Consistent with the general nature of the problems solved by LGO, all modules use derivative-free techniques.
LGO has a simple and convenient menu-driven system. The main requirement for use is a familiarity basic FORTRAN language.
Problem Definition. Upon launching the LGO program system, the main menu, called the application development menu, is displayed. It consists of five menu items: Model Formulation, Model Solution, Result Analysis, Help and Exit. To begin defining the problem to be solved, the user should click the mouse on the Model Formulation menu item. At this point, five submenu items appear, one of which is called Project File Names (see Figure 1). When the user clicks on this item, the user is prompted to provide names for several program items. The first is a name for the current project or problem to be solved. The next six items are names for the key project files of LGO. Initially, default names will appear for these items that correspond to the demonstration problem provided to the user (see Figure 2). These default names should be overwritten at this point with user-defined names.
Figure 1: LGO Main (Application Development) Menu.
Figure 2: LGO Project File Names.
After closing the Project File Names screen, the user is returned to the application development (main) menu. Under Model Formulation, there are five submenu items, including one called the User Function File. Clicking on this item will activate the standard Notepad text editor program (shipped along with LGO) to display the User Function File, which is written in FORTRAN (Figure 3). This file, like the other user files, will have the name chosen in the previous menu option. Sufficient comment statements are given in this FORTRAN template file (and in all other user files) to allow the reader to understand how to change the file as necessary for the project at hand. In the displayed User Function File, the objective function and constraint functions are defined. Initially, these functions are those associated with the demonstration problem provided to the user. The user should modify these definitions to correspond to the problem at hand, then save and close the file. Except for the definition of the lower and upper bounds for the variables, this completes the problem definition. (These bounds are defined by the user after the compilation step below). Once again, the user is returned to the application development menu.
Figure 3: LGO User Function File.
Problem Compilation. After defining the problem, the LGO model must be compiled. To do so, in the application development menu, the user should choose the Model Formulation menu item. Among the five submenu items that appear will be the Compile LGO Model item. This selection prepares object files on the basis of the user source files and links these to the LGO object file system and libraries. At the end of this step, the user is prompted to return to the application development menu.
Model Parameters. Following the actions described above, the LGO executable program is ready to run, but it still needs the input parameters that describe the lower and upper bounds for the problem variables. To provide these, in the application development menu, the user should select the Model Solution menu item. An Input Parameter File submenu item will appear. Upon choosing this, a commented text file template will appear in which the user should enter the number of variables and constraints and the lower and upper bounds on the variables (Figure 4). The file should then be saved and closed, at which time control returns to the application development menu.
Figure 4: LGO Input Parameter File.
Model Solution. At this point, the user is ready to execute the run step, found under the Model Solution menu, to solve the problem. A screen will appear that gives the user the option of solving the problem in the automatic mode or the interactive mode. In the automatic mode, with the aid of the input parameters of the problem, the LGO system chooses one or more of the four solution modules available to solve the problem. In this mode, LGO automatically determines the appropriate level of search effort to utilize (via input parameter file settings). In the interactive mode, the user can decide which global and/or local search module(s) to invoke, and in which order; the only restriction being that no global search module can be invoked if a local search module has preceded it. In this mode, the maximal search effort that is used is also in control of the user. During the solution procedure itself, messages appear on the screen concerning the iteration count and improving objective function results.
Upon completion of each solver module procedure, a brief message appears summarizing actual results. The user is prompted to continue the search by selecting a new solver module, or to terminate the current run. Upon termination, the estimated global optimal value, solution feasibility, the total number of objective and constraint function evaluations and the total LGO runtime are reported. Control is then returned to the application development menu. At this point, the user may edit the problem, recompile, re-link and rerun it, or he or she may invoke the result analysis options.
Result Analysis. Two types of result files are automatically created by LGO after a run is terminated: Summary Output File and Detailed Output (Log) File. To display either of these, the user chooses the Result Analysis menu item in the application development menu. These two file names appear as submenu items. The Summary Output File gives only final results of a run, including number of function evaluations, estimated global optimal value and solution, and solution time. The Detailed Output (Log) File contains additional information. In particular, it verifies (echoes) the input parameters and traces the optimization modules used. For each solution module used, it reports the improving sequence of solutions generated and the stopping criteria met during execution. In addition, a graphical visualization of the problem can be obtained when a run is completed. This visualization graphs a subspace projection of the aggregated "merit" function (which sums the objective function and the penalized constraints, when present) and a scatterplot of improving search points.
Our experiments with the LGO system led us to conclude that it is technically sound and uses robust and accurate global and local optimization modules. We appreciated LGO's versatility and convenience, the ability of the user to manipulate the solution process, and the effort and parameters involved in this process. The documentation is easy to read and complete, and the product provider showed a strong commitment to assisting and advising us about all features of the system. To our knowledge, this is the first truly user-friendly, general global optimization system available for the personal computer environment. LGO is therefore an extremely valuable software tool for the operations research community. We highly recommend it for classroom use, research purposes, and use in applied decision-making and optimization.
Harold Benson is a professor of decision and information sciences at the University of Florida. He has published over 60 research articles in the areas of mathematical programming, multiple objective decision-making and global optimization.
Erjiang Sun is a Ph.D. student in the Department of Decision and Information Sciences at the University of Florida. He holds a B.S. degree in Mathematics from the Xian Jiao Tong University of China and an M.S. degree in Applied Mathematics for Shanghai Jiao Tong University, also of China.
OR/MS Today copyright © 2000 by the Institute for Operations Research and the Management Sciences. All rights reserved.