Optimization

Fall Quarter (September - December, 2002)

Supply Chain and Logistics Optimization

Organizers: William R. Pulleyblank, George Nemhauser, Tom Magnanti, Brenda Dietrich, Ellis L. Johnson, David Simchi-Levi, Cindy Barnhart

The term 'supply chain' is used to refer to the design, planning, procurement, production, and delivery of materials and other resources used in delivering products and services to customers. Supply chain management applications provide significant benefits to a business such as reduced costs, improved quality and inventory management. Supply chain management uses advanced information management and mathematical models to plan and control resources in order to better produce and deliver products and services.

Supply chain management is the logical progression of developments in logistics management. Physical distribution management, begun in the 1960's, integrated warehousing and transportation of goods, providing inventory-reduction benefits from the use of faster, more frequent, and, more reliable transportation. Faster warehouse handling and transportation shortened the demand-forecast horizon, and increased the accuracy of forecasts. By considering transportation and warehousing costs together companies could optimize warehouse locations for better service and lower total cost. Physical distribution management was enabled by two related factors, improved data communications and more complex analyses.

The 'logistics' phase in SCM's development, the late 1970's through the mid 1990's, encompassed manufacturing, procurement, and order management functions. This expansion of scope was made possible by electronic data interchange, worldwide communications, and the growing availability of computers to store data and perform complex analyses. The current stage, "integrated supply chain management", which includes supplier and customers, relies on electronic data, electronic funds transfer, high bandwidth communications, and computerized decision-support systems for planning and for execution.

In next few years, the scope will be further expanded to incorporate functions such as product development, marketing, and customer service. This expansion will be enabled by even more advanced communications, and by better and more user-friendly computerized decision support systems. This progress is being propelled by advances in computer technology and communications technology, which make it possible to have more information, more accurately, more frequently, from more sources, from all over the globe. Advances in computer technology, and in mathematical models and algorithms will make it possible to digest, to understand, and to act on this information using sophisticated analysis, optimization and decision-support capabilities.

As the scope of supply chain management is extended, the underlying optimization problems grow dramatically in size. We expect that many of these 'mega models' will create the need for hybrid optimization models, wherein the results of one problem become the input for another. These problems are of great importance to the many small software companies beginning to create supply chain management products, as well as to the many large corporations who wish to incorporate these techniques. The ability to manage the complete supply chain, often across several companies and to optimize decisions is increasingly being recognized as a crucial competitive factor. The automotive industry is very advanced in this area, and heavy industries, such as steel and paper manufacturing, are taking this up. Adoption of these techniques in travel and transportation are being led by airlines and by trucking companies.

The availability of real-time status information is creating a need for 're-optimization' models and methods that can quickly repair a plan in response to changes in input data. This is particularly important for operational problems, where the solution to the optimization problem specifies a short-term assignment or schedule of resource use. When a disruption occurs, for example, due to weather or supply difficulties, the short-term plan may become infeasible and must be adjusted immediately. For this recovery problem, even the desired optimality criteria are not well understood. Just as risk measurement and management are becoming recognized as fundamental subjects in financial mathematics, so too should "robustness" become a fundamental notion in the supply chain and logistics domain. Important issues must be addressed. How should robustness be defined? Can robustness be calculated? approximated? optimized?

Clearly any notion of robustness must be closely linked to methods for dealing with uncertainty. Stochastic models may be used to build robustness into a plan, or to determine how to hedge against future situations.

Problems arising in supply chain and logistics optimization are being studied in departments of operations research and management science, as well as by mathematicians and computer scientists. Some of the underlying mathematical issues involve development of fast algorithms to approximate the solutions to very large-scale problems, as well as methods for combining models of different types to form hybrid models. The basic methods include linear programming, integer programming and dynamic programming, however new methods which exploit the special structure in these problems must be developed. In addition, specialized heuristics often play an important role, particularly as the problems become increasingly large. The issue of real-time updates to solutions has been addressed for a few specific applications, but no underlying theory has been developed.

This segment of the special year should have a substantial computational component, including `optimization engines' or `solvers' that work on classical problems such as linear and integer programs, as well as `middleware' that facilitates development of models and linkage of solvers. Dealing with real-world uncertainties makes stochastic optimization an essential component.

Several major societies should also be interested in participating in this program. INFORMS (the union of ORSA and TIMS) is heavily involved with some of these topics, and the Mathematical Programming Society focuses on much of the underlying methodology.

By holding a semester on this topic we will be able to bring an unprecedented degree of focus to industrial scale problems of this sort. We expect that it will lead both to the incorporation of advanced techniques in commercial products and to the driving of increased activity in the academic community dealing with the fundamental mathematical problems underlying these important problems. By having several workshops focused on specific application domains, we will be able to accelerate interactions between the mathematicians, computer scientists and the appropriate practitioners. 

Winter Quarter (January - March, 2003)

New Optimization Paradigms and Approaches

Organizers: Andrew Conn, Omar Ghattas, Donald Goldfarb (chair), Jorge Nocedal, Michael J. Todd, Michael Overton

Recently several new optimization paradigms and approaches have been proposed which not only have generated a large body of extremely important algorithmic research but have also given birth to new and widely diverse areas to which mathematical optimization is now being and can be applied. Perhaps the most exciting of these new paradigms is semidefinite programming. Semidefinite programming (SDP) is itself subsumed under what is known as cone programming and includes as special cases linear programming, quadratic programming, quadratically constrained quadratic programming and second order cone programming. SDP problems are convex optimization problems that have a particular structure that makes their solution computationally tractable by interior point methods.

Because of this and the fact that an extremely broad array of problems can be modeled as SDP's, research in this area is very exciting. This situation is similar to what happened fifty years ago when the simplex method was proposed for solving linear programming problems. As in that case, optimization problems that had not previously been tackled were now possible to solve. In the case of SDP, this has created interest in the optimization community in such areas as robust optimization (optimization when the problem data is subject to certain types of uncertainty), eigenvalue optimization, robust control and stochastic control. Specific application areas range from structural design to signal processing to finance. SDP formulations have also led to new ways to solve hard combinatorial optimization problems and generate approximate solutions to these problems.

What makes SDP a particularly attractive topic for IMA involvement is that, in addition to SDP's broad impact on industrial problems, its underlying theory and algorithmic development introduces into the field of optimization fundamental mathematical results from areas such as Jordan and associate algebras and symmetric cones.

Computational differentiation (CD) has been a very active area of research in the past few years with the production of numerous workshops, books, and software tools. Obviously there is an intimate connection with optimization, and applied optimization problems, through the calculation of gradients, Jacobians, and Hessians. Indeed, since the dominant cost in the solution of many optimization problems is often the calculation of derivatives, CD is of enormous importance to practical optimization. However, despite the often-used name 'automatic differentiation', effective use of these new CD tools often requires exploitation of problem structure and clever integration with optimization approaches. Application areas span the full spectrum but are particularly interesting (challenging) in the areas of (multidisciplinary) design and inverse optimization (where there is an underlying PDE structure).

Another exciting new development in optimization has been the recent interest in simulation based optimization, and as a consequence of this, the renewed interest in derivative-free optimization. This is an area of tremendous importance because many problems in industry cannot be modeled analytically due to their complexity. Rather, one can only simulate them by computer programs. Exposing the types of problems and simulation outputs of interest to industry to the developers of optimization algorithms and introducing derivative free optimization algorithms that have already been developed to those who wish to optimize some simulation model should have a major impact on this area.

Finally, the availability of optimization software, and supporting computational tools, has increased dramatically over the past few years. In addition to new software packages, both free and commercial, there are internet/web tools, supercomputer/parallel codes, and automatic differentiation codes. A number of questions can be addressed: how do the different packages compare, what is covered and what is missing, is there scalability, how do the codes behave on degenerate problems, how convenient/flexible are the interfaces? Moreover, in many application settings the optimization software is still homegrown - why is this the case? What improvements are required and what is coming down the line?

Spring Quarter (April - June, 2003)

Information Technology and Optimization

The semester can bring together mathematicians, software developers, and Internet business personnel to focus attention on the optimization needs of information users, and to explore the applicability of a wide variety of mathematical tools.

It is difficult to overestimate the importance of the role mathematical optimization will play in the design, management, and use of future information networks and IT devices. Firms deploying network elements will depend on specialized linear and integer programming to utilize their resources efficiently; routing algorithms for the transmission of data will be based on discrete optimization methods; users of information networks will employ graph, eigenvalue and other innovative mathematical techniques to sift through vast amounts of data over global networks.

The IMA can have a major impact in this area. The timing of the proposed year on optimization is ideal for a focus semester on information technology. The semester would be the center of activity for the design and use of information networks at a time when a large portion of the global economy will be making the transition from building basic network structures to utilizing network information to impact all aspects of decision making. Industrial partners in the semester should include the major telecommunications laboratories, firms in the computer industry, and internet-based firms.

There are a wide variety of optimization problems that need to be solved. New technologies offer a wide range of opportunities to realize the future "information superhighway'', but they also present extremely complex design challenges. Demands on the network designer range from choosing the appropriate equipment configurations, down to providing the means to recover from the failure of a fiber-cable link or switching node. The mathematical models of these design problems necessarily involve discrete variables, due to the inherently discrete nature of the logical network and the choices of the equipment to realize it.

Models arising in this area are amongst the most difficult integer programming problems studied to date, and solution methodologies are currently an active area of research in universities and in industrial laboratories. The size and difficulty of these problems make them impossible to solve with traditional optimization methods, and require the development of specialized combinatorial optimization techniques.

The area of network design has received a large amount of attention. This semester of the optimization year would enable the bringing together of the theoretical and computational researchers with the constraints produced by the real devices.

In addition to design issues, there is the great challenge of how to harness the potential of the information that will be stored on future networks. This area involves searching, data mining, text mining, and data fitting. The origin of these methods lies in statistics and data analysis, but they are rapidly being adapted to include supervised learning, clustering, and more general data modeling. The general objective is to optimize the parameters expressing the observed data by means of a particular model, and in so doing optimize the microeconomic business objectives of the enterprise. Market segmentation- a classical objective of data mining and mass customization - has given rise to a new breed of optimization problems on large data sets.

New algorithms and computational methods are sorely needed here. There is particular interest in text mining - the problems of automatically extracting meaning from text and of identifying similar documents. With the sequencing of the human genome scheduled to be completed in the next three years, there is considerable impetus to develop methods for discovering the relationships between the genomic sequences and the physical characteristics. These problems are all within the area of combinatorial optimization.

The techniques used are evolving too rapidly to be able to project what the most important optimization tools will be at the time of the proposed year at the IMA, but current advanced methods center around graph algorithms (Kleinberg's HITS algorithm and the CLEVER project at IBM), eigenvector techniques (latent semantic indexing), and randomized methods (Frieze, Kannan, and Vempala). At present, approximation algorithms are a major field of study in theoretical computer science. Some of the new techniques being developed are likely to be of relevance here. We include descriptions of two proposed workshops, a third will be added during the preparation for this semester.