Developments in computing technology (both hardware and software) are emerging thick and fast, too much so to cover all the important ones in a short article. This article is an attempt to survey some developments that are important to OR/MS practitioners and researchers. Space constraints barely permit me to provide enough detail to add some of the latest buzzwords to your vocabulary, much less make them part of your toolkit. It is also inevitable that topics are omitted that some people consider important. If I missed one of your favorites, I apologize in advance.
Hardware for Parallel Computation
The power of multiple processors can be put to use in a couple of ways of interest to operations researchers. First, there are applications in raw data storage, retrieval and analysis (data mining). Second, large-scale numerical problems can be partitioned or decomposed into parts that can be solved in parallel, then reconstructed to form a solution to the original problem.
There seems to be a "convergent evolution" of parallel computing architectures, particularly at the lower and middle price ranges. Most systems in this range share the following features (though there are exceptions in each category):
What distinguishes products with these features (aside from processor choice) is primarily the architecture of the interconnection network. A sort of "poor man's parallel computer" can be constructed using a network of workstations interconnected via Ethernet, and programmed using publicly available tools, such as PVM (Parallel Virtual Machine) or MPI (Message Passing Interface). If the communication load is high or tightly scheduled, however, Ethernet is a poor solution, since each message between two processors ties up the entire network, effectively serializing communication. If processors of different types or speeds are used, then dynamically balancing the computational load becomes an important programming issue. Actual multiprocessor machines rely on special, high-speed networks that allow simultaneous transmission of messages among several processors, yet scale up relatively inexpensively to accommodate increasing numbers of processors.
Programming shared-memory machines is often much simpler than programming in a message-passing environment, and the run-time cost of getting information between processors is much lower, so performance on machines with comparable numbers of processors may be much better on shared memory than with distributed memory. On the other hand, shared-memory architectures do not scale well. Shared-memory machines typically contain processors numbering in the tens, whereas distributed machines may number their processors in the hundreds.
Information Technology
The World Wide Web. According to the World Wide Web Consortium, the World Wide Web (WWW) is the "universe of network-accessible information, an embodiment of human knowledge." The project to organize this information and make it universally accessible was begun in 1989 at CERN (the European particle physics lab). Despite this inclusive definition, most people think of the Web primarily as the collection of interlinked "home pages" written in Hypertext Markup Language (HTML) and accessible using browsing programs such as NCSA's Mosaic or Netscape's Navigator.
The Web is a massive implementation of a "client-server" architecture. An information provider on the Web requires a server program supporting the appropriate protocol (Hypertext Transfer Protocol, or HTTP, for HTML; FTP for file transfer, etc.). The client runs a browser, which sends requests to servers and receives copies of files in return. The browser formats HTML source into graphic displays (possibly including images and sound). HTML files may contain hypertext links, which can take the client to other files on the same machine or on other machines. They can also launch display programs on the client for images or sound, or link to mailers or servers for other protocols.
Currently under development is a programming language called Java, which is designed to allow distributed execution of programs over a network. A Java-aware browser would be able to import programs (called applets) to the client machine and execute them there. The potential for providing Web-based interactive services is great, but the potential security problems are great as well, and remain unresolved. Unresolved security issues also affect the conduct of financial transactions on the Web.
To locate information on the Web, one can look at index sites such as Yahoo (http://www.yahoo.com) or keyword search engines such as Lycos (http://www.lycos.com). A good place to start looking for OR-related resources is Michael Trick's home page at http://mat.gsia.cmu.edu.
Data Mining. In the course of its operation, a modern enterprise can generate a large volume of data, typically in the form of transaction records. While these data are suitable for accounting and auditing purposes, they are often not in a form usable for other sorts of analyses, such as market research, production and inventory planning. The tools and methods used to transform, archive and analyze data are collectively known as data mining (DM) or knowledge discovery.
Effective data mining is both I/O and compute-intensive, and is typically not done directly on production systems. Transforming and distilling the data can improve the efficiency of the analysis, and running the analysis off-line avoids affecting the performance of the production systems. The designer of the off-line database (or data warehouse) must exercise care, as a poorly designed database can actually hinder the analysis. The difficulty is that it is not always known in advance what is the right analysis to perform, hence, what is the best structure for the data warehouse.
"Top-down" analysis, in which the user states specific queries, is the most familiar form of data mining, but DM tools also support a "bottom-up" approach, in which data is analyzed for general indications of patterns and trends which are then brought to the analyst's attention. DM tools can be grouped into the following classes:
Programming Languages and Methods
OBJECT-ORIENTED PROGRAMMING. One of the most important trends in programming methodology is object-oriented programming (OOP). Although the definition of this term (like many in this article) is rather fluid, the core ideas are solid. The key concepts are encapsulation and inheritance. Encapsulation refers to the idea that the data elements and operations on a particular data structure should be grouped together, and that access to information in the data elements should be controlled by the defined operations, so that programmers using the structure cannot see the actual representation of data. Inheritance refers to the derivation of specialized or extended data types from more general types, sharing the properties and operations that the parent and child types have in common, but allowing the child type to add or modify properties and operations to support the specialization. Both of these concepts are designed to promote code reuse and reduce the need to develop code from scratch for every application.
Although one can program in an object-oriented style in any programming language with less or greater difficulty, doing so in a language without built-in OO constructs requires enormous self-discipline on the part of the programmer, and often forces a stilted and unnatural style. Object-oriented languages naturally enforce the discipline and allow natural expression of the inheritance relations.
By far the most widely used OO language is C++, a derivative of C with extensions to support encapsulation and inheritance. C++ is a hybrid of traditional and OO language designs and owes much of its popularity to its C origins. It also does not have some features that are useful when programming in an OO style, such as garbage collection (automatic reuse of memory) and run-time binding (determination of an object's type). (C++ is in the process of being standardized, so its feature list is currently in flux.) There are more "pure" OO languages, such as Smalltalk, but they are not as widely used. The latest Fortran standard, Fortran 90, includes several new features designed to support encapsulation (but not inheritance), array and subarray manipulation, and memory management. Compilers for Fortran 90 are appearing, but are not yet widespread.
OOP is not a panacea for programming problems. If anything, it requires more careful design up front to make sure that the objects and relationships among them are right for the job at hand and for reusability. In addition, the hierarchical relationships among data types imposed by the inheritance paradigm may not adequately express the true relationships among the objects being modeled.
SYMBOLIC COMPUTATION AND ALGEBRAIC MODELING TOOLS. A number of programming systems have appeared in recent years that support combined numerical and symbolic manipulation of mathematical objects such as functions, matrices, equations, etc. These tools (the best known are Maple, Mathematica, and Matlab) can express algorithms and equations in a compact format similar to mathematical notation; find symbolic derivatives, integrals and solutions; draw and manipulate two- and three-dimensional graphs; and perform numerical function evaluation and equation solution as well. These packages are useful tools for performing algebraic manipulation of equations and formulas in derivations, for prototyping algorithms, and even for solving numerical problems (if they are not too large).
A related idea, useful in the context of nonlinear optimization, is automatic differentiation. AD programs can analyze a subroutine written in, say, Fortran or C, that describes a function, and produce a program in the same language that describes the function's derivative, by applying the chain rule to the elementary operations. Their major advantage over symbolic differentiation is that they can be applied to programs that involve complicated control structures. They are also accurate to machine precision, as opposed to numerical techniques such as forward or symmetric differences, and the cost of evaluating the derivative is on the order of the cost of evaluating the function itself. The packages can be used to provide exact gradients and Hessians to numerical equation solvers and optimizers.
A variety of tools are available for expressing systems of equations or mathematical programs in algebraic form, and for separating the actual numerical coefficients of the models from their algebraic structure. Many of these packages were surveyed in a recent issue of OR/MS Today, so they are not discussed in detail here. Spreadsheet tools can also achieve this purpose, although some users have reported that the built-in spreadsheet optimizers are not as robust as some state-of-the-art packages.
Number Crunching
The last decade has seen remarkable advances in our ability to solve computational OR problems. Although new hardware technology has certainly contributed to these advances, by far the most important developments have been algorithmic. Where problems are very large or difficult to formulate as mathematical programs or systems of equations, techniques from Artificial Intelligence have been applied successfully as well. Here are brief descriptions of some of the major computational ideas currently under development.
MATHEMATICAL PROGRAMMING. The catalyst for many of the recent advances in mathematical programming was almost certainly Narendra Karmarkar's announcement in 1984 of a computationally competitive interior point algorithm for linear programming. Advances have occurred since then not only in interior point algorithms for linear and nonlinear programs, but in simplex implementations as well. One key to efficient implementations of both simplex and interior point algorithms has been efficient implementation of linear algebra subroutines for solving sparse and specially structured linear systems. Some other major advances are reviewed briefly here:
A different set of developments has fueled advances in integer programming. IP algorithms typically solve a sequence of relaxations of the original problem, often obtained by eliminating the integrality constraints to yield a linear program. The major thrust of recent computational IP efforts has been to develop tighter relaxations, either by the addition of "deep" cutting planes or by other means, and to exploit them in IP algorithms.
POLYHEDRAL CUTS. Much of the theoretical development in integer programming in the 1980s was the derivation of facets (theoretically deepest cuts, based on the geometric structure of the feasible set) for specially structured problems. Though this work continues now, general-purpose IP and mixed-integer codes make use of generic polyhedral cuts based on identifiable substructures of the general problems.
BRANCH AND CUT. Current advanced IP codes generate cuts not only at the start, but also when solving subproblems. The subproblem cuts are generally constructed in a way that keeps them valid for the original problem, so they can be applied at all subsequent subproblems to tighten the LP relaxations and reduce the number of subproblems solved.
BRANCH AND PRICE. A dual concept to branch-and-cut can be applied to integer programs with a large number of variables. The idea is to solve an LP relaxation with a number of columns left out of the relaxation. Columns are then added to the problem based on the solution to a pricing problem, which generates variables that violate the LP optimality conditions. Branching occurs when the relaxation solution is fractional and no columns are added. The pricing step can be applied to subproblems as well as at the start.
SEMIDEFINITE PROGRAMMING. For some combinatorial optimization problems, a tight relaxation can be formulated as the problem of finding a linear combination of matrices that is positive semidefinite (i.e., for which xT Ax ≥ 0 for all vectors x). The development of interior point methods for semidefinite programming allows these relaxations to be used in the solution of such integer programs in place of the LP relaxation, where appropriate. This formulation also applies to other important optimization problems in nonlinear programming, control theory and other areas.
Metaheuristics and Artificial Intelligence Techniques
A contribution to optimization from the Artificial Intelligence field is the development of heuristic strategies or metaheuristics for solving problems that are large or otherwise difficult to formulate or solve as mathematical programs (such as many scheduling problems). These strategies are often analogs of physical or biological processes (though they should not be mistaken for models of the actual processes). Some of these and other AI techniques are described here.
Conclusion
Predicting the future of computing continues to be a wildly speculative activity, which is why I have concentrated here on the current state of the art. The advent of Java, in particular, has futurists buzzing about the "demise of the personal computer." Some (including IBM's Louis Gerstner) talk of small, cheap devices that are driven by their connections to the Internet, retrieving software and data as needed from central repositories. Critics of this view (including Microsoft's Bill Gates) point out that the end-user devices would still require much of the power of current desktop computers to make use of the services they access, and that network connections with much higher bandwidth than is currently common would be required.
Nevertheless, a trend toward more reliance on globally distributed data and services is certain to accelerate. One example of interest to operations researchers is the Optimization Technology Center's Network-Enabled Optimization System (NEOS) at http://www.mcs.anl.gov/home/otc. The NEOS Server is a repository of optimization software, but instead of retrieving the software to run on one's own computer, a user can submit an optimization problems to NEOS, where it will be solved on their computers and the results returned via E-mail or directly on the Web.
I have touched here on only a few of the trends and active areas of development in computation that are relevant to OR. Watch future issues of OR/MS Today for more in-depth surveys of some of these topics. Useful references are also available on the World Wide Web, and are accessible through the index and search sites listed above.