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.