 |
Fields Industrial Optimization Seminar
2006-07
|
Supported by
|
|
|
|
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
The Spring seminars will include seminars on:
- Financial Optimization
- Optimization of Energy Systems
- Chemical Process Optimization
- Convex Optimization in Electrical Engineering
June 5, 2007
Christine A. Shoemaker, Cornell University
Optimization, Calibration, and Uncertainty Analysis of
Multi-modal, Computationally Expensive Models with Environmental
Applications
Many important problems in engineering and science require optimization
of computationally expensive (costly) functions. These applications
include calibration of simulation model parameters to data and
optimizing a design or operational plan to meet an economic objective.
With costly functions (like nonlinear systems of PDEs, partial
differential equations), this optimization is made difficult by
the limited number of model simulations that can be done because
each simulation takes a long time (e.g. an hour or more). The
optimization problem is even more difficult if it has multiple
local optima, thereby requiring a global optimization algorithm.
Our new algorithms use function approximation methods and experimental
design to approximate the objective function based on previous
costly function evaluations. In our optimization algorithm, function
approximation is combined with metrics of locations of previous
costly function evaluations to select iteratively the next costly
function evaluation. We have different algorithms for unimodal
and multimodal functions, both of which have theorem for convergence
to the global minimum will be described.
Numerical algorithm comparisons will be presented for test functions
and for an environmentally based partial differential equation
model that requires 1.5 hours to run for each simulation. This
nonlinear model (based on fluid mechanics and chemical reactions)
describes the fate and transport of water and pollutants in a
groundwater aquifer. The optimization is used for calibration
of the model by selecting the parameter values (decision variables)
that best fit measured data from a military field site in Florida.
The parameter surface is multi-modal so this is a global optimization
problem. The results indicate that a Regis and Shoemaker (2006a)
method generally gives better results for global optimization
test problems and the environmental model than alternative methods
when the number of model simulations is limited. It is especially
effective at dimensions higher than 6. Related parallel algorithms
will also be briefly discussed (Regis and Shoemaker, 2006b).
Working with David Ruppert's statistics group, we have also expanded
the use of function approximation to Bayesian analysis of uncertainty
for costly functions. In this NSF project, we are combining optimization
for calibration with an assessment of the uncertainty in calibrated
parameter estimates and in calibrated model output based on input
data. Numerical results for an environmental PDE problem based
on a hypothetical chemical spill demonstrated good accuracy and
a 60-fold reduction in costly simulations over that required for
conventional MCMC analysis for Bayesian uncertainty analysis.
---
All this research has been done jointly with Rommel Regis and
was funded by NSF. Parts of the seminar will discuss research
also done with Dr. Pradeep Mugunthan, Prof. David Ruppert, and
Nikolai Blizniouk.
References
Mugunthan, P., C.A. Shoemaker, R. G. Regis "Comparison of
Function Approximation, Heuristic and Derivative-based Methods
for Automatic Calibration of Computationally Expensive Groundwater
Bioremediation Models," Water Resources Research Vol. 41,
W11427,doi:10.1029/2005WR004134, Dec. 2005.
Regis, R.G., C.A. Shoemaker, "A Stochastic Radial Basis
Function Method for the Global Optimization of Expensive Functions",
INFORMS Journal of Computing, in press 2006a.
Regis, R.G. and C. A. Shoemaker, "Parallel Radial Basis
Function Methods for the Global Optimization of Expensive Functions,"
European Journal of Operations Research, in press 2006b.
Blizniouk, N., D. Ruppert, C.A. Shoemaker, R. G. Regis, S. Wild,
P. Mugunthan, "Bayesian Calibration of Computationally Expensive
Models Using Optimization and Radial Basis Function Approximation."
Computational and Graphical Statistics, requested revision submitted
2007.
and
Ron Dembo, Zerofootprint
The World Needs Optimization NOW!
Climate crisis is now a fact of life whereas only a few years
ago it was an abstract concept. We are clearly faced with a massive
problem in planning for the future. How do we adapt to a world
of finite resources and a surplus of carbon dioxide in the atmosphere?
How do we continue to bring the world out of poverty and not destroy
it in the process? How do we supply the future energy needs of
the world?
If ever there was a time where Optimization techniques and principles
were needed it is now. We will have to minimize the use of fossil
fuel, maximize carbon sequestration, optimize our use of energy.
It is a long list. This talk will address these subjects and pose
more problems than solutions. It is an amazing time for the field
but it will require strong leadership and vision for Optimization
to achieve the prominence it deserves.
PAST SEMINARS
May 1, 2007 (audio
of talks)
Michael C. Ferris, University of Wisconsin
Optimization of Gamma Knife Radiosurgery and Beyond
The Gamma Knife is a highly specialized treatment unit that provides
an advanced stereotactic approach to the treatment of tumors,
vascular malformations, and pain disorders within the head. Inside
a shielded treatment unit, beams from 201 radioactive sources
are focused so that they intersect at the same location in space,
resulting in a spherical region of high dose referred to as a
shot of radiation. The location and width of the shots can be
adjusted using focussing helmets. By properly combining a set
of shots, larger treatment volumes can be successfully treated
with the Gamma Knife.
The goal of this project is to automate the treatment planning
process. For each patient, an optimization seeks to produce a
homogeneous dose distribution that conforms closely to the treatment
volume, while avoiding overdosing nearby sensitive structures.
The variables in the optimization can include the number of shots
of radiation along with the size, the location, and the weight
assigned to each. Formulation of such problems using a variety
of mathematical programming models is described, and the solution
of several test and real-patient examples is demonstrated.
If time allows, we will describe commonalities of this approach
with other treatment devices and outline some of the challenges
for the future.
and
Doug Moseley, Department of Radiation Oncology, University
of Toronto
The Data Tsunami in Radiation Therapy
Recent technical innovations in radiation therapy such as intensity
modulated radiation therapy (IMRT) and image-guided radiation
therapy (IGRT) have given clinicians the ability to exquisitely
sculpt and deliver the therapeutic dose of ionizing radiation
to the patient. This revolution in radiotherapy is generating
vast amounts of patient specific information in the form of volumetric
computed tomography (CT) images. Analyzing and responding to these
images presents an onerous task.
This talk will briefly introduce the basics of radiation therapy
and highlight some of the recent developments and technical challenges
in patient care taking place at Princess Margaret Hospital.
April 3, 2007
Theme: Energy Markets: Hydroelectric Dispatch
Rick Adams, Operating Manager, Niagara Plant Group, Ontario
Power Generation.
Niagara, from Water to Wire
This presentation provides the basics of how the fuel for
(water) and the product from (electricity) hydroelectric generators
are managed in the Niagara Peninsula.
and
Hans J.H. Tuenter, Senior Model Developer, Planning &
Analysis, Ontario Power Generation
Hydroelectric dispatch from a system perspective.
This talk places the hydroelectric dispatch problem within
the setting of optimally dispatching a fleet of generators, and
discusses what type of optimization problems this gives rise to.
and
Ranendra Ponrajah, Senior Market Risk Analyst, Corporate
Finance, Ontario Power Generation
Optimal unit commitment at hydroelectric facilities.
The presentation will focus on the unit commitment problem as
it applies to hydroelectric facilities. Topics discussed will
include the unit performance relations, characteristics of hydroelectric
units, the input parameters and operating constraints. Typical
benefits of unit commitment will be discussed followed by schematics
outlining how one can implement unit commitment in an operational
environment. In the latter part of the presentation the theory
on Lagrangian Relaxation as implemented in the unit commitment
algorithm will be presented. This implementation was co-developed
with assistance from McGill University. The presentation will
conclude with a demonstration of the unit commitment solution.
March 6, 2007
Revenue management optimization
Gilles Savard, Ecole Polytechnic Montreal
Pricing a segmented market subject to congestion*
Price optimization fits naturally the framework of bilevel programming,
where a leader integrates within its decision process the reaction
of rational customers. In this presentation we address the problem
of setting profit-maximizing tolls on a congested transportation
network involving several user classes. At the upper level, the
firm (leader) sets tolls on a subset of arcs and strives to maximize
its revenue. At the lower level, each user minimizes its generalized
travel cost, expressed as a linear combination of travel time
and out-of-pocket travel cost. We assume the existence of a probability
density function that describes the repartition of the value of
time (VOT) parameter throughout the population. The resulting
non-convex infinite-dimensional problem is solved by a hybrid
algorithm that alternates between global (combinatorial) and local
(descent) phases. We will briefly present real life applications
in airline and rail industries.
*This is a joint work with M. Fortin, P. Marcotte and A. Schoeb.
and
Jean-François Pagé, Air Canada
Revenue management in the airline industry: where do we come
from and where do we go
All experts agree to recognize the benefits of revenue management
in the airline industry (between 5% to 10% more revenue). First
we will define revenue management in the airline industry from
its three major components (scheduling, pricing and seat allocation).
We will then revise quickly the classical approach to solve the
seat allocation problem and discuss the current issues faced by
the industry. We will conclude by presenting the application of
the model proposed by Gilles Savard in the context of Air Canada.
February 6, 2007
Audio of talks
Virginia Torczon, Department of Computer Science, College
of William & Mary
Generating Set Search Methods for Nonlinear Optimization
The nonlinear optimization problems encountered in industrial
settings often have features that can foil gradient-based nonlinear
optimization methods. These features include a lack of reliable
derivative/adjoint information, discretization errors introduced
by the computational simulations that define the optimization
problem, discontinuities that either are inherent to the optimization
problem or are introduced by discretization, and the need for
global, versus local, minimizers.
Generating set search (GSS) methods are derivative-free optimization
techniques that, under ideal circumstances, deliver convergence
guarantees comparable to those for gradient-based optimization
techniques. This talk will focus on how the analysis for GSS methods
accommodates heuristics, such as the use of response surface models,
to tackle the less than ideal circumstances often encountered
when attempting to solve industrial optimization problems.
Don Jones, General Motors
A Taxonomy of Global Optimization Methods Based on Response
Surfaces
This paper presents a taxonomy of existing approaches for
using response surfaces for global optimization. Each method is
illustrated with a simple numerical example that brings out its
advantages and disadvantages. The central theme is that methods
that seem quite reasonable often have non-obvious failure modes.
Understanding these failure modes is essential for the development
of practical algorithms that fulfill the intuitive promise of
the response surface approach.
December 5, 2006
Nicholas G. Hall, The Ohio State University
The Coordination of Pricing and Production Decisions
This talk has two purposes. First, it provides an overview
of current and future research on the coordination of pricing
and production decisions. Second, it considers a specific new
model for the coordination of pricing and scheduling
decisions. In this model, we assume knowledge of a deterministic
demand function which is nonincreasing in price. We consider
three standardmeasures of scheduling cost: total weighted completion
time of jobs, total weight of jobs delivered late to customers,
and overall schedule length, respectively. The objective is
to maximize the total net profit, i.e. revenue less scheduling
cost, resulting from the pricing and scheduling decisions. We
developcomputationally efficient optimal algorithms for solving
the three coordinated pricing and scheduling problems. We show
that much faster algorithms are not possible. We also develop
a fast approximation method for each problem. Managerial insights
are obtained from a detailed computational study which compares
solutions obtained by using various levels of coordination.
Our results estimate the value of coordination between pricing
and scheduling decisions, and provide tools with which such
coordination can easily be achieved.
and
Eddie Hsu, Sr. Developer (Optimization), Workbrain Inc.
Vinh Quan (Formerly) Sr. Solutions Engineer, Workbrain
Inc.
Optimization in Practice: A Retail Labor Scheduling Example
Retail labour scheduling can be described as the process of
producing optimized timetables for employees. The challenges
faced by store managers is to ensure that there is an optimal
staffing level in place to accommodate fluctuating sales volumes
and customer traffic, subject to various constraints that involve
employee availability and qualifications, compliance with labour
laws and regulation, as well as payroll costs and budgetary
considerations. The problem can be formulated as a mixed integer
programming model and solved using Dash Optimization's solver
suite.
This seminar will discuss in detail the different constraint
requirements for the retail labour scheduling problem and how
one can reduce the time for solving such problems in practice.
These include (a) Optimizing the use of the modeling language
itself (b) Alternative model formulations and (c) Employing
a dynamic termination scheme.
October 31, 2006
Optimization in the Airline Industry
Diego Klabjan, University of Illinois at Urbana-Champaign
Recent Advances in the Crew Pairing Optimization
The first breakthrough in airline crew pairing optimization
occurred approximately ten years ago. Since then several solution
methodologies have been developed. The most important driving
force is the step from a local view to the global view in how
a solution is constructed. Many of these techniques are now
successfully used by commercial software vendors. In the talk
modern solution methodologies for crew pairing will be presented.
We will also discuss the implications of being able to quickly
solve relatively large crew pairing problems to problems in
related domains, such as robustness and integration with other
problems.
Dr. Barry Smith, Sabre Holdings, Inc
Revenue Management in the Airline Industry: A Review of Development
and Some Bumps along the Way
We'll review the development of revenue management and its
impact on the airline industry, describing how changes in the
airline business environment have driven the evolution of revenue
management through multiple generations of approaches and applications.
We'll consider how the current airline environment is likely
to shape future revenue management theory and applications.
October 3, 2006
R. Baker Kearfott, University of Louisiana at Lafayette
A Current Assessment of Interval Techniques in Global Optimization
Interval techniques have been used for several decades in
global optimization, for
- computing bounds on ranges in branch and bound processes,
and
- providing mathematical rigor (to encompass roundoff error
and algorithmic approximations), leading to mathematically rigorous
bounds on the optimum and guarantees that all optimizers have
been bounded.
"Classical" interval global optimization methods include
bounding the range of the objective with interval arithmetic,
various types of constraint propagation, and use of interval
Newton methods both to narrow sub-regions and to prove existence
and uniqueness of critical points within tight bounds. These
methods, effective for some problems, had not been able to tackle
a number of important practical problems for which alternate
techniques have made
inroads.
However, exciting developments have occurred during the past
decade. For example, while foregoing mathematical rigor, some
global optimization algorithm developers have used interval
arithmetic effectively in selected places, resulting in highly
competitive codes. Other theoretical developments, such as the
Neumaier / Shcherbina technique for supplying a rigorous lower
bound, given an approximate solution to a linear program, allow
non-rigorous techniques to become rigorous, thus narrowing the
gap between codes without guarantees and codes with guarantees.
Refinement of implementation details, particularly in constraint
propagation, has also led to advances, in both rigorous and
non-rigorous codes. These classical and emerging techniques
will be briefly surveyed. The talk will also include some speculation
about advances based on literature that seems to have been overlooked
to date.
and
Janos D. Pinter, Pinter Consulting Services, Inc.
Adjunct Professor, Dalhousie University
Global Optimization: Software Development and Advanced Applications
Global optimization (GO) is aimed at finding the “absolutely
best” solution in nonlinear decision models that frequently
may have an unknown number of local optima. Finding such solutions
numerically requires non-traditional, global scope search algorithms
and software.
For over two decades, we have been developing GO algorithms
followed by software implementations for (C and FORTRAN) compilers,
optimization modeling environments (AIMMS, Excel, GAMS, MPL),
and the scientific-technical computing platforms Maple, Mathematica,
and MATLAB.
In this presentation we review the key technical background,
followed by software implementation examples and a glimpse at
various scientific and engineering applications.
|
|
