The inaugural meeting of the Fields Industrial Optimization Seminar
took place on November 2, 2004.. This series will meet once a month,
on the first Tuesday, in the early evening. Each meeting will comprise
two related lectures on a topic in optimization; typically, one speaker
will be a university-based research and the other from the private or
government sector.We welcome the participation of everyone in the academic
or industrial community with an interest in optimization -- theory or
practice, expert or student.
Please subscribe to the Fields mail list to
be informed of upcoming seminars.
=================================================
UPCOMING SEMINARS,
Seminars start at 5:00 pm at the Fields Institute, 222 College Street,
Room 230
May 2, 2006 --Energy Markets: Theory and Practice.
Speakers:
Peter J. Vincent, Manager Quantitative Analysis, Risk Services,
Ontario Power Generation
Introduction to Energy Markets
This talk gives an overview of the basic principles that govern energy
markets, and discuss the characteristics and interaction of load,
transmission and generation.
Hans J.H. Tuenter, Senior Model Developer, Planning & Analysis,
Ontario Power Generation
Mathematical models in Energy Markets.
This talk gives an overview of the different mathematical models and
techniques that are being used in energy markets.
Matt Davison, Associate professor of Applied Mathematics and
Faculty of Science Scholar at the University of Western Ontario.
Valuation and Optimal Control of Energy Assets.
This talk represents joint work with Matt Thompson and Henning Rasmussen.
I will discuss the ways in which real options theory can be used both
to value and to determine optimal control strategies for real energy
generation assets. After motivating the analysis and developing a
general framework for analyzing such assets, we will look at the particular
challenges of optimizing three particular assets -- a thermal (coal
fired) power plant, a pump storage hydroelectric unit, and a natural
gas storage facility. I will close by discussing current work on extending
these ideas to other energy assets.
PAST SEMINARS
April 4, 2006
Workshop on IMRT Radiation Therapy Treatment Planning:
Target Uncertainties, Computational Challenges and Beyond
Eva Lee (Georgia Tech)
Large-Scale Optimization Strategies for Optimal Cancer Treatment
Design
and
Joseph Deasy (Washington University)
Computational challenges in radiation oncology
March 7, 2006
Daniel E. Rivera, Department of Chemical and Materials Engineering,
Arizona State University
"Plant-Friendly" System Identification: A Challenge for
the Process Industries
Dynamic modeling is a critical task to many problems in the areas
of simulation, prediction, and control of process systems. Most industrial
plants are either too complex, or the underlying processes too poorly
understood, to be adequately modeled using first principles. A sensible
approach, then, is to estimate dynamical models from data generated
through well-designed experiments; this is the problem of system identification.
Certain industries, such as petrochemicals and refining, rely almost
exclusively on system identification as the principal means for obtaining
the dynamic models necessary to design advanced control systems.
The term "plant-friendly" system identification has been
used within the chemical process control community in reference to
the broad-based goal of accomplishing informative identification testing
while meeting the demands of industrial practice. In the formulation
developed in this talk, a priori knowledge available to the engineer
is used to specify a frequency spectrum for a multisine input signal.
An optimization problem is then solved which seeks to find the optimal
phases of the multisine signal (and additionally, the Fourier coefficients
in frequency bands not specified by the user) that directly minimize
friendliness criteria such as crest factor. The optimization problem
is solved in the presence of explicit time-domain constraints on upper/lower
limits and rate of change in either (or both) input and output signals.
Such a constrained time-domain formulation is appealing to process
control engineers, who tend to think more in terms of maintaining
high/low limits, move size constraints, and test duration during identification
testing, and less in terms of norm criteria that are typically used
in the classical optimal experimental design formulations.
The optimization-based framework developed in this talk is illustrated
with an application to a high-purity distillation column, a demanding
nonlinear and multivariable process system. The paper concludes with
a discussion of identification test monitoring as an important novel
paradigm for accomplishing plant-friendly identification.
and
Hans D. Mittelmann, Department of Mathematics and Statistics,
Arizona State University
State-of-the-Art in the Solution of Control-Related Nonlinear Optimization
Problems
We start by giving an overview of some of our activities related
to the computational solution of a range of optimization problems,
including a leading web-based guide to software and its performance
and a major installation of free web-based solvers.
Then we sketch two classes of problems from our recent research,
PDE constrained optimization as it arises in the control of PDEs and
system identification problems. The first class gives rise to very
large and sparse nonlinear optimization problems that still challenge
state-of-the art algorithms including commercial products.
The second class of problems are system identification problems
including those suitable for data-centric estimation and control.
At first we will address the solution of the crest-factor optimization
problems described in the previous lecture, then we will introduce
a novel optimization formulation which has facilitated the application
of MoD (Model-on-Demand) type of control for process systems. For
all problems considered formulations in the modeling language AMPL
are utilized and we sketch some exemplarily.
February 7, 2006
Jorge Nocedal, McCormick School of Engineering and Applied
Science, Northwestern University
New Developments in Nonlinear Optimization
In the last 5 years, the field of nonlinear optimization has grown
and evolved at a rapid pace. We now have a much better understanding
of constrained optimization at both the algorithmic and theoretical
levels. This talk reviews these recent developments.
Nonlinear optimization is also expanding in new directions, guided
by applications in financial engineering, integrated circuit design,
and wireless communications. In all these areas it is important to
solve optimization problems with complementarity constraints. These
problems pose challenging theoretical and algorithmic challenges,
which will be discussed in this talk. Some recent successful applications
will be presented.
and
Kankar Bhattacharya, University of Waterloo
New NLP problems for Power System Analysis and Operation in Competitive
Electricity Markets
This presentation discusses in detail several novel applications
of NLP to the analysis and operation of power grids in the context
of competitive electricity markets. In particular, various new NLP
models designed and developed for dispatch and clearing of power networks
and their associated markets are presented, emphasizing their unique
characteristics, such as the introduction and handling of implicit
constraints and the use of heuristics to transform the optimization
problem into an NLP problem, which exploit the particular characteristics
of these optimization problems so that they can be solved more efficiently.
These optimization problems are compared with respect to more classical
models currently being used by industry to highlight their unique
characteristics and challenges.
December 6, 2005
John Birge, University of Chicago
Research Challenges and Opportunities for Optimization in the Energy
Sector
The energy sector presents multiple opportunities for optimization
applications while also presenting numerous challenges. This talk
will focus on these issues for electricity markets with an emphasis
on common characteristics in other energy markets: high volatility,
dynamic and distributed decision making, estimation difficulties,
limited storage capacity, and significant fixed costs.
The talk will consider the impact of these factors on optimization
models, current methods to address these issues, and directions for
further research.
and
Samer Takriti, IBM
Stochastic Programming Applications in Deregulated Energy Markets
Until the early 1990s, the US electric power utilities were fully
regulated with captive customers and controlled tariffs. However,
the deregulation of the energy market, which began in 1992 with the
Energy Policy Act, changed market dynamics by opening the transmission
system and creating hubs for trading energy. As a result, most utilities
were faced with increased competition and opportunities. In this talk,
we discuss energy markets and associated uncertainties from the point
view of a power producer. We then discuss two problems, namely the
unit commitment problem and the problem of selecting bids in the next-day
energy market, which we model as mixed-integer stochastic programs.
We present numerical results for work with two energy clients.
November 1, 2005
Natalia Alexandrov, NASA Langley Lab.
Managing models in simulation based design optimization
Advances in numerical modeling and computational power enable increasingly
accurate simulation of physical and engineering phenomena. However,
the enormous cost of repeated high-fidelity simulations, such as the
Navier-Stokes equations or those based on fine computational meshes,
makes the use of high-fidelity models impractical in the context of
single-discipline or multidisciplinary design optimization.
Approximation and model management optimization (AMMO) combines the
use of general variable-fidelity models with analytically substantiated
algorithms to improve tractability of design with high-fidelity, expensive
models while preserving provable convergence properties. While in
demonstrations to-date AMMO has produced significant savings as compared
to algorithms that use a single-fidelity model, these savings are
highly dependent on the non-local properties of the lower-fidelity
models. In this talk, we discuss the attempts to detect these properties
and use them to speed up algorithms where the model quality is uncertain.
--
David Zingg, University of Toronto
Topics in Aerodynamic Shape Optimization
This presentation will focus on two important topics in aerodynamic
shape optimization. First, a comparison of a gradient-based and a
gradient-free strategy will be presented for several single-point,
multi-point, and multi-objective aerodynamic optimization problems.
The gradient is computed using the discrete-adjoint approach. The
two algorithms use the same geometry parameterization and produce
identical flow solutions for a given parameterization; consequently
the two design spaces are identical. The objective is to assess the
dependence of the relative cost of the two approaches on the nature
of the problem, the number of design variables, and the degree of
convergence required. The results indicate that the genetic algorithm
is better suited to preliminary design, while the gradient-based algorithm
is more appropriate for detailed design.
The second portion of the presentation will focus on airfoil optimization
under variable operating conditions. Examples will be shown to demonstrate
that it is difficult to pose a multi-point optimization problem a
priori and that the feedback from the optimization can lead to better
problem specification. A technique will be presented to automatically
select sampling points and their weights in order to achieve desired
performance over a range of operating conditions, in this case constant
drag over a range of Mach numbers. The results provide insight both
in formulating and in solving multi-point aerodynamic optimization
problems.
October 4, 2005
Ellis Johnson, Georgia Institute of Technology, Atlanta GA
Imposing Station Purity using Station Decomposition
Fleet assignment models are used by many airlines to assign aircraft
to flights in a schedule to maximize profit [Abara 1986, Hane et al
1995]. A major airline reported that the use of the fleet assignment
model increased annual profits by more than $100 million [www.informs.org,
2002] a year over three years. The results of fleet assignment models
affect subsequent planning, marketing and operational processes within
the airline. Anticipating these processes and developing solutions
favorable to them can further increase the benefits of fleet assignment
models. We develop fleet assignment solutions that increase planning
flexibility and reduce cost by imposing station purity, limiting the
number of fleet types allowed to serve each airport in the schedule
[Smith and Johnson 2005]. Imposing station purity on the fleet assignment
model can limit aircraft dispersion in the network and make solutions
more robust relative to crew planning, maintenance planning and operations.
Because imposition of station purity constraints can significantly
increase computational difficulty, we develop a solution approach,
station decomposition, which takes advantage of airline network structure.
Station decomposition is an instance of Dantzig-Wolfe decomposition
and uses a column generation approach to solving the fleet assignment
problem. We further improve the performance of station decomposition
by developing a primal-dual method that increases solution quality
and reduces running times. This method can be applied generally within
the Dantzig-Wolfe decomposition framework to speed convergence. It
avoids "instability of the duals" and minimizes the "tailing"
effect.
Station decomposition solutions can be highly fractional causing
excessive running times in the branch-and-bound phase. We develop
a "fix, price, and unfix" heuristic to efficiently find
integer solutions to the fleet assignment problem.
Station purity can provide benefits to airlines by reducing planned
crew costs, maintenance costs, and the impact of operational disruptions.
We show that purity can provide compelling benefits (up to $29 million
per year) to airlines based on reduced maintenance costs alone. Benefits
associated with reduced crew costs are estimated at $100 million per
year, giving $129 million per year increased profit. We would expect
additional savings in operations.
References:
Abara, J. (1989), "Applying Integer Linear Programming to the
Fleet Assignment Problem" Interfaces 19 pp. 20-28.
Hane, C. A., C. Barnhart, E. L. Johnson, R. E. Marsten, G. L. Nemhauser,
G. Sigismondi (1995), "The Fleet Assignment Problem: Solving
a Large-scale Integer Program" Mathematical Programming 70 pp.
211-232.
http://www.informs.org/Press/EDELMAN02.html
Smith, B. C., E. L. Johnson (2005), "Robust Airline Fleet Assignment:
Imposing Station Purity using Station Decomposition", submitted
and
Stefan Karisch, Carmen Systems, Montreal QC
Applying Optimization in the Airline Industry
What does it take to successfully apply optimization in the airline
industry and build a company around it? I will try to answer this
and related questions in my presentation and use Carmen Systems as
an example. Carmen develops and implements resource management and
optimization solutions for demanding transportation operations.
Clients include five of the ten largest airlines in the world, namely
Air France, British Airways, Delta Air Lines, Lufthansa, Northwest
Airlines, and Deutsche Bahn (German Railways), one of the largest
passenger transportation companies in the world.
Back to top
