OR/MS Today, October 1997
Optimization on the Internet
By Joseph Czyzyk, Jonathan H. Owen and Stephen J. Wright
Ambitious NEOS project aims to connect users of optimization technology and provide them with problem-formulating information and software
The Internet has been much in the news for the past few years, particularly since the World Wide Web exploded into 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 all kinds of useful information and lots of not-so-useful information. 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 canceled our New York Times subscription, choosing instead to read the free, enhanced Web version and saving 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 (Network-Enabled Optimization System) project in late 1994. 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, too, to give people 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 the Web, its favorite son) as the ideal vehicle for achieving all of these aims. Information about optimization algorithms and software is dynamic by nature it changes on a fairly short time scale making the Web 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 spent a lot of time thinking about how users might communicate with remote problem-solving facilities through the Internet. The current version of NEOS represents our attempt to put our 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:
As this page shows, NEOS is organized into three components: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
The NEOS Guide, whose basic structure is illustrated in Figure 1, can be found on the Web at:
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 to the casual Web surfer who wants a quick fix on the relevance of optimization to the real world.
A popular component of the Guide is the Software Guide, a listing of more than 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 package's Web site and vendor contact information. This material was drawn initially from the book of More and Wright, but has been expanded and updated many times in the past two years. (We thank SIAM Publications for their permission to reproduce the original copyright material.) This constantly changing nature of this material makes the Web an ideal home for it.
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 page in this area 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. Pages in the tree have been contributed by ourselves and our colleagues at other institutions, but coverage in some areas (such as discrete optimization and integer programming) remains light. We invite further contributions from experts in these 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, and some studies have already been used in many class assignments. Optimization problem areas currently represented and the corresponding case studies include:
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 and varied list. The user's menu is optimized for cost, subject to minimum calorie requirements and various nutritional constraints, all of which are user-adjustable. If the user's selections result in an infeasible problem, the concept of infeasibility is explained and the program suggests some additional foods that can be added to recover feasibility.
The Simplex Tool is a Java applet that demonstrates the simplex method for linear programming. Users enter a small linear program and follow the progress of the simplex algorithm in fine detail (and living color). 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 are starting to build up an area of Test Problems for linear and nonlinear programming and other areas of optimization, since we feel that good batteries of test problems and standardized testing procedures are crucial to the development of state-of-the-art software. The Guide also links to Giden, a Java-based environment for network optimization. Giden features a graphical interface for building and modifying networks, and an expandable toolkit of algorithms whose progress is illustrated by animations.
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 240 papers, an associated mailing list with about 480 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. However, issues of classification and organization by subject area become more complex with the wider scope of this project. A Web framework is in place, but we are reluctant to announce the site until we can find help in moderating and managing it.
The NEOS Server
The 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, installing and executing software on their own PCs and workstations.
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 (a number of others are on the way):
Figure 2 illustrates the operation of the Server, showing how it acts as the intermediary between the user and the solver process. The Server schedules each incoming job on one of the available workstations that can handle problems of the type in question, and activates the solver on the chosen host. It relays intermediate results and runtime messages to the user, and returns the final job results.
The automatic differentiation tools ADIFOR and ADOL-C are embedded in the Server, making it necessary for the user to supply only function evaluation code for nonlinear problems; the derivatives are computed automatically.
It is not difficult to install a new solver on the NEOS Server, particularly if one is also willing to grant access to a machine 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. The configuration file, sample problems, HTML source for web pages and contact information are submitted in this way. The Server checks this information and modifies its web site to incorporate the new solver. The NEOS Communications Package, a Perl application, can be used to set up the host machine to handle incoming jobs. The user supplies a script to assemble the input and call the solver, and to direct the output to a file called job.results, which is returned to the user upon termination.
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.
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, users can make non-blocking calls to optimization routines, allowing their code to continue executing after making the call the Server without waiting for the result of the optimization. A single user process could therefore spawn numerous jobs that would be processed by different computers in the Server simultaneously. Similarly, we are experimenting with interfaces that allow solvers to be called remotely from AMPL or Matlab sessions running on user workstations.
The Future of Optimization on the Net
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. Future directions to be taken by NEOS will depend on the involvement of colleagues in optimization, operations research and, critically, computer science.
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 identifying 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 attractive and friendly interfaces. User jobs could be executed on whichever machine in the organization is most suitable at the time, not necessarily on the user's own desktop. 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 computer cycles, buying idle time on Internet-connected computers and selling it to users of their Server. (Developments like this are contingent, of course, on the problems of security being resolved.) Like other businesses on the Internet, Server operators 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 launched the metaNEOS project, whose aim is to research the algorithms and infrastructure needed to solve very large problems by distributing the work on a networked collection of computers. 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 challenging indeed, but they are all subjects of intense research.
We would like to experiment with a wide range of interfaces to the NEOS Server. Java applets embedded in Server web pages, for instance, would be more portable than the existing Submission Tool, but slightly more restricted in functionality. We will investigate 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 also considering 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 capabilities.
1. R. Fourer, D. M. Gay, and B. W. Kernighan, "AMPL: A Modeling Language for Mathematical Programming," The Scientific Press, South San Francisco, Calif., 1993.Acknowledgments
Many people have contributed to the development of NEOS since the project started in late 1994. In particular, Mike Mesnier and Jorge More deserve most of the credit for the NEOS Server, while Rich Marynowski, Jorge Nocedal and Tim Wisniewski made major contributions to the NEOS Guide.
Joseph Czyzyk, a former research associate at Argonne National Laboratory, recently accepted a teaching position in Poland where he is also doing missionary work. Jonathan Owen is a graduate student in the Department of Industrial Engineering and Management Science at Northwestern University. Stephen Wright is a computer scientist at Argonne and director of the Optimization Technology Center, a joint venture of Argonne and Northwestern.
For more information, put the number 5 in the appropriate space on the Reader Service Form
E-mail to the Editorial Department of OR/MS Today: firstname.lastname@example.org
OR/MS Today copyright © 1997, 1998 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
2555 Cumberland Parkway, Suite 299, Atlanta, GA 30339 USA
Phone: 770-431-0867 | Fax: 770-432-6969
Web Site © Copyright 1997, 1998 by Lionheart Publishing, Inc. All rights reserved.
Web Design by Premier Web Designs, e-mail email@example.com