by Joseph Czyzyk, Jonathan H. Owen, and Stephen J. Wright
The Internet has been much in the news for the past few years, particularly since the World Wide Web exploded into the popular consciousness in 1994-95. Companies now routinely include their URLs in TV advertisements, billboards, and on the sides of trucks. The NBA displays its nba.com in huge letters at courtside at the United Center, home of the Chicago Bulls.
For many of us, the Web has become the first place to turn to for every kind of useful information---and lots of not-so-useful information as well. We routinely use the Web to check weather forecasts and movie listings, obtain driving directions, and get up-to-the-minute golf or basketball scores. One of us recently cancelled our New York Times subscription, choosing instead to read the free, enhanced Web version and to save the trouble of stuffing recycling bins.
Certainly the Web has changed our personal lives, but what of our professional lives? What kinds of information on the Web would be useful for OR professionals? For academics in the field, what kinds of educational tools are appropriate? Does it make sense to provide computational services for optimization and OR through the Internet to complement these information/education resources? What of Intranets, the intra-organizational networks of computers that are proving to be a major source of revenue for providers of Web technology?
To explore these issues, our group at Argonne National Laboratory and Northwestern University launched the NEOS project in late 1994 (NEOS="Network-Enabled Optimization System"). For the most part, our background was at the theoretical end of the OR spectrum---the analysis, development, and software implementation of optimization algorithms---and we wanted to make stronger and more effective connections with users of optimization technology, in engineering and basic science as well as in more familiar OR applications. We wanted to give users all the information they need to formulate their problems correctly and to choose the right pieces of software for solving them. We wanted also to give users ready access to a wide collection of state-of-the-art optimization software, without subjecting them to the delays associated with buying software and hardware.
We saw the Internet (and its favorite son, the World-Wide Web) as the ideal vehicle for achieving all these aims. Information about optimization algorithms and software is dynamic by nature---it changes on a fairly short time scale---and the Web is the obvious way to deliver such information since it is easily accessed and easily updated. In fact, the power and reach of the Web caused us to expand our vision for NEOS as the project progressed. We saw that interactive case studies to demonstrate practical applications of optimization could be useful to educators and students, and that online repositories of technical reports and test problems could improve the flow of information in the research community, leading to faster development of algorithms and software. On the problem-solving side, we thought about how users might communicate with remote problem-solving facilities through the Internet. The current version of NEOS represents our attempt to put these ideas into practice and to test their effectiveness and usefulness to the broad community of optimization users.
The home page of NEOS (or, more accurately, of its parent organization, the Optimization Technology Center) can be found at http://www.mcs.anl.gov/otc/ As this page shows, NEOS is organized into three components:
A library of freely available optimization software written by researchers in the NEOS project. Current tools are PCx \cite{PCx96} (an interior-point linear programming code) and LBFGS-B (a limited-memory code for optimization with bounds). Codes from Minpack-2, the next generation of the popular Minpack collection, will be available shortly.
A collection of informational and educational material about optimization, including a guide to optimization software, thumbnail sketches of algorithms for different optimization problems, applications case studies, FAQs (answers to frequently asked questions) for linear and nonlinear programming, and collections of test problems and technical reports.
A facility for solving optimization problems remotely over the Internet. Users submit their problems through email, the World-Wide Web, or an Xwindows tool. Their problems are automatically scheduled and solved on workstations at Argonne, Northwestern, and the University of Wisconsin.
In the remainder of this article, we describe the Guide and Server in a little more detail, and give a view of possible future developments in network resources for Optimization and Operations Research.
The NEOS Guide, whose basic structure is illustrated in Figure 1, can be found on the Web at http://www.mcs.anl.gov/otc/Guide/
The Guide contains information and educational material for many types of Web users, from the experienced OR practitioner who wants information on a nonlinear programming code through the casual Web surfer who knows little about optimization or OR but is curious about what it can do in the real world.
A popular component of the Guide is the Software Guide, a listing of over 100 software packages for optimization, organized by problem category (linear programming, integer programming, nonlinear equations, and so on). The entry for each package describes the capabilities, interfaces, platforms and hardware requirements, together with pointers to the Web site for the package (if available) and vendor contact information for users who need to know more. This material was drawn initially from the book of Mor\'e and Wright~\cite{MorW93}, but has been expanded and updated many times in the past two years. This constantly changing nature of this material makes the Web an ideal home for it. We welcome contributions from software authors and vendors whose products are not currently listed on the Guide.
For background on optimization algorithms, there is the Optimization Tree, named for the navigator graphic on its home page that shows a tree-like relationship between the various subdisciplines. Each ``leaf'' page of the tree contains the problem definition, a thumbnail sketch of the most important algorithms, and pointers to software and review literature. The purpose is to help users recognize, formulate, and classify their application under one of the optimization categories for which software exists. The Tree also gives existing users a little background on the algorithms that underlie their favorite pieces of software. Again, raw material from Mor\'e and Wright~\cite{MorW93} was enhanced and restructured for the Web to provide the initial basis of the Tree. (We thank SIAM Publications for their permission to reproduce this copyrighted material.) We have expanded the Tree somewhat by using material supplied by colleagues who are experts on particular topics (such as multiobjective optimization and semidefinite programming). Coverage of some areas remains light (particularly in discrete optimization), and we invite further contributions from experts in the missing areas.
The Case Studies area shows how optimization methodology can be used to solve practical problems. It is aimed mostly at uninitiated users and at students who are curious about how optimization and OR relate to the real world. We aim to have one case study for each major problem class. The areas currently represented and their corresponding case study include
In each study, we describe the application and how it is formulated as an optimization problem (showing the AMPL formulation \cite{AMPL} explicitly in some cases), and show how the results of the optimization process can be interpreted in terms of the original application.
Each of the five studies mentioned above is interactive: Users enter some input on the web page, and the solution of the problem is displayed graphically. In the diet problem, for instance, users choose foods they are willing to eat from a large menu. The menu is optimized for cost, subject to minimum calorie requirements and a set of nutritional constraints (all user-adjustable) being satisfied. If the user chooses foods or constraints for which the optimization problem is infeasible, the concept of infeasibility is explained and the program suggests some additional foods that can be added to make the menu feasible. The diet problem and other case studies have been used as class projects in many OR departments during the past year.
The Simplex Tool is a Java applet within the Guide that demonstrates the simplex method for linear programming. Users enter a small linear program---up to $7$ variables and $3$ constraints---and follow the progress of the simplex algorithm in fine detail (and living color) as it solves the problem. If they wish, users can override the default choices for variables to enter the basis, from among those variables with negative reduced costs.
The FAQs for Linear and Nonlinear Programming, founded and maintained by John Gregory for some years, are now maintained by Bob Fourer as components of the NEOS Guide. These popular pages give a practitioner's viewpoint on software, modeling, and algorithmic issues in these broadly defined areas. We also maintain a roster of Test Problems for linear programming, that currently includes the netlib set of feasible and infeasible problems together with some larger problems. MPS files and solution information are provided in each case, and AMPL models \cite{AMPL} are available for some problems. We hope to develop this area much further to include refined test batteries for other problem classes, since we feel that good test problem batteries and standardized testing procedures are crucial to the development of state-of-the-art software. This opinion is shared by many, but the work involved is hard and unrewarding and, unfortunately, not glamorous enough to attract much support.
The Guide also links to Giden, a Java-based environment for network optimization. Giden~\cite{GIDEN2} features a graphical interface for building and modifying networks, and an expandable toolkit of animated solution algorithm implementations.
Finally, we have plans for an archive of new Technical Reports in optimization and OR. We already maintain an archive of this nature for interior-point methods which, after 30 months of operation, contains about 220 papers, an associated mailing list with about 425 members, and a directory of researchers in the area. Interior-point people have found this site invaluable for keeping track of developments in this fast-moving area, and we feel that a similar facility will provide the same stimulus to the broader optimization community. Issues of classification and organization by subject area become more complex, however. The web framework is in place, but we are waiting until more help becomes available to moderate and manage the site.
The Server \cite{Server} is the most ambitious component of NEOS. It explores the use of computer networks as computational devices rather than just sources of information, and points the way for similar facilities in other areas of numerical computation. The central aim of the Server project is to give users ready access to a wide range of optimization software, relieving them of the burdens associated with obtaining (purchasing?), installing, and executing software on their own PCs and workstations.
Our work on the Server has caused us to think hard about many issues, including the design of interfaces that are more user-friendly than the subroutine-call interfaces that are still ubiquitous in many areas of numerical computation, and about the computer science issues of Server implementation, resource management and scheduling, secure data transmission, and so on.
Solvers within the Server are a combination of new production-quality codes and a few research codes and older, standard public-domain codes. The following problem areas are currently supported; with a number of others on the way.
A person with prior experience with optimization software might use the Server in the following way. First, she browses the Web pages of the NEOS Guide and Server to identify the algorithm and code best suited to her problem. She then looks at the Server web site for the chosen code to see how it expects the problem to be specified: the form of the function and constraint evaluation routines, the meaning of various user-supplied parameters, and so on. After spending some time if necessary to massage her problem specification into the required form, she fires up the NEOS Submission tool, which pops up windows on her workstation screen, including a window for the solver she needs. She enters the file names containing her problem specification in this window and chooses to enter one or two tolerances and parameters as well, leaving the others at their default values. She clicks ``submit'' and another window appears on the screen that informs her about the progress of her job through the Server: its position in the queue, the input parsing and job scheduling, and finally the execution and run-time output from the solver. She examines the results and, if necessary, goes through the whole process again.
Of course, different people use optimization software in different ways, so the Server supports many variants on the procedure just outlined. In addition to using the NEOS Submission tool (an Xwindows application implemented in Perl and Tcl/Tk that uses Unix sockets to connect direction to the server), the user can choose to submit jobs through Web pages or even by email. Email submission consists of a single message mailed to the address neos@mcs.anl.gov in which code fragments, parameters, and data are separated by keywords and tokens. For instance, the email message for submitting an MPS data file to the PCx linear programming solver would be as follows.
TYPE LP SOLVER PCx BEGIN.MPS (data file here) END.MPS
Sample data is provided for each solver so that a user can see how the Server operates without having to make up a problem.
Figure 2 illustrates the operation of the Server. Essentially, it is the intermediary between the user and the solver process. It accepts and logs the incoming job, noting the means of submission: email, web, or submission tool. The incoming data (which takes the form of an ASCII file, regardless of how it was submitted) is parsed and dissected into its component pieces. The Server determines the problem and solver type, and schedules the job on a computational resource that is (a) currently available, and (b) is equipped to process jobs of the given type. After activating the solver on the chosen host, the Server maintains contact with the user so that it can transfer runtime messages and the final job results.
The host computer chosen to execute a Server job executes its own solve script to process the input. For linear programs, this script simply stores the MPS-formatted data in a file, activates the solver, and bundles the output for return to the user. For the nonlinear solvers, the role of the solve script it a little more complicated. The routines that evaluate objectives, constraints, and starting points are stored. If necessary, the automatic differentiation tools ADIFOR and ADOL-C are called to generate code for evaluating the derivatives. The function and gradient code is then compiled and linked to the solver code, and execution begins.
It is not difficult to install a new solver on the NEOS Server provided that one is also willing to grant access to a computer resource to run the solver. The submission tool can be used to submit information about the new solver to the Server, in much the same way that a user submits an optimization problem through the tool. The configuration file, sample problems, HTML source for web pages, and contact information are submitted in this way. The Server checks this information and automatically generates new web pages for the new solver, as well as changing information in existing web pages and in the submission tool to include the new solver. The solving computer must also be set up to listen for incoming jobs, and download and execute them when they arrive in the queue. Except for the solver-specific aspects, this process is handled by the NEOS Communications Package, a perl application that is easy to install. For most contributors, the most difficult step of the installation procedure is to prepare a solver script for their code. This script should check the validity of the input and notify the user if any information is missing. It should then invoke the solver and store the output in a file called job.results, which is returned to the user upon termination.
The Server is fundamentally a batch processing device, but we are developing other interfaces--- functional interfaces---that allow more interactivity. Using these interfaces, Server solvers can be called from user code in much the same way that optimization software libraries are called today. This change will be almost invisible to the user; the main difference is that a call is made to a communications routine that talks to the Server, rather than to a subroutine library on the user's machine. In fact, more power is given to users in that they can make non-blocking calls, in which their code continues executing without waiting for the optimization routine to terminate. Such a mode allows simultaneous processing of numerous jobs on the Server, all of them called from a single user process. Similarly, we are experimenting with interfaces that allow solvers to be called remotely from AMPL or Matlab sessions running on user workstations.
The NEOS project is a shoestring operation that depends mainly on the enthusiasm and dedication of its student interns, postdoc, and staff. Besides the group at Argonne and Northwestern, a number of colleagues from the optimization community have been actively involved by making their codes available through the Server or by contributing to the Guide. We encourage participation of this kind since it makes NEOS truly a community resource. There are many more research directions that NEOS could explore. Our future activities will depend on greater involvement of colleagues in optimization, operations research and, critically, computer science. Our activities are also contingent, of course, on financial support.
We are often asked ``What's in it for you to provide this free service?'' A partial answer is that we are in the proof-of-concept business: We are trying to determine the technical possibility of providing different kinds of services in a networked computational environment, and indentifying the services that are useful and the classes of users that they help. To give a more complete answer, we briefly describe how technologies and services demonstrated by NEOS might be used in a commercial or scientific setting, and discuss the incentives that might exist for providing such services and developing the technology further.
Intranets provide one possible commercial application of NEOS technology. Organizations currently use intranets to provide uniform access to data and information resources across the organization through familiar and friendly web browser interfaces. Facilities like NEOS would allow the technical software, including optimization and OR software, to be centrally maintained within an organization, while remaining accessible to all members of that organization through nice interfaces. Users would no longer run jobs only on their desktop machine or the company mainframe. Instead, the server would schedule their jobs on whichever machine in the organization is most suitable at the time. Jobs could even be split into tasks that are executed in parallel around the intranet, as we describe below. Accounting and security---critical issues in Internet commerce---are not so important in the intranet setting.
A second commercial model for NEOS involves the Internet. Help for solving OR and optimization problems is currently provided by vendors of software and by consultants. Using a NEOS-like interface, a firm could instead provide comprehensive problem-solving services. Alongside their consulting expertise and software tools, they could provide remote access to computers that actually solve the problems. They could even act as brokers for compute cycles, buying idle time on Internet-connected computers and selling it to users of their Server. (Developments like this can only occur, of course, if security is assured.) Like other businesses on the Internet, they could make a subset of their services freely available: restricted versions of their software, for instance, or an informational resource like the NEOS Guide.
In scientific applications, we anticipate that much of the demand for NEOS-like facilities will be driven by very large problems. Examples in optimization include large mixed integer programming problems, large scheduling and logistics problems that must be solved by many organizations, and the difficult global optimization problems arising in computational biology. Recently, in collaboration with specialists in the area of heterogeneous distributed computing, we have proposed a facility called metaNEOS, which will process very large jobs in parallel by splitting them into tasks and distributing the tasks around its collection of computing resources. This type of facility makes good sense from an economic point of view, since it makes productive use of networked computers that would otherwise be idle, and is much cheaper and more flexible than a supercomputer of equivalent power. The computer science issues in managing this collection of resources, performing efficient task-to-processor allocation, handling communications between tasks, ensuring robustness, and guaranteeing security are very challenging, but they are subject of active research, and several of the leading groups in the area will be working with us on metaNEOS. Of course, not all optimization problems lend themselves to this type of environment, and a lot of research is still needed to devise suitable algorithms and codes, but certain large and important applications would benefit greatly from developments in this area.
Current plans for the NEOS Guide include widening the scope of the Optimization Tree to cover all areas of optimization and OR, filling out the Software Guide, and developing the Case Studies area into a comprehensive educational resource. We also hope to activate the web archive of new technical reports in optimization and OR.
We would like to experiment with a wide range of interfaces to the NEOS Server. Java applets embedded in Server web pages are an obvious candidate (which would be more portable than the submission tool, but slightly more restricted in functionality). We also plan to look at interfaces that allow users to run AMPL sessions or spreadsheets locally on their own machines, while invoking solvers for complex optimization operations by calls to the Server, remotely over the network. (Such interfaces would be equally interesting in an intranet setting, for the reasons mentioned above.) We are considering too a ``shrink-wrapped'' version of the Server that runs locally on a workstation. This version would retain the nice interfaces and problem solving power of the Server, while discarding the network communications capability.
Many people have contributed to the development of NEOS since the project started in late 1994. In particular, Mike Mesnier and Jorge Mor\'e deserve most of the credit for the NEOS Server, while Rich Marynowski, Jorge Nocedal, and Tim Wisniewski made major contributions to the NEOS Guide.
We gratefully acknowledge the support of Northwestern University and the Office of Energy Research of the U.S. Department of Energy.
R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, The Scientific Press, South San Francisco, Calif., 1993.
J. Czyzyk, M. Mesnier, and J. Mor\'e, The NEOS (Network-Enabled Optimization System) Server, Technical Report 97/02, Optimization Technology Center, February 1997.
J. Czyzyk, S. Mehrotra, and S. J. Wright, PCx User Guide, May 1996. Updated February 1997. Available from http://www.mcs.anl.gov/otc/Tools/PCx/
J. J. Mor\'e and S. J. Wright, Optimization Software Guide, SIAM Publications, Philadelphia, Penn., 1993.
J. H. Owen, C. R. Coullard, and D. S. Dilworth, A User Guide for GIDEN, A Graphical Environment for Network Optimization, Department of Industrial Engineering and Management Sciences, Northwestern University, May 1997.
