CIM PROGRAMS AND ACTIVITIES

Fields Industrial Optimization Seminar
2007-08

Amy Cohn, University of Michigan
"Optimized" Airline Plans and Operational Realities

This talk will investigate the role of Operations Research in airline planning and, in particular, investigate the link between an airline plan and its operational robustness. I will provide a brief review of the airline schedule planning process, discuss the relationship between a planned airline schedule and its operational performance, highlight sources of delay propagation, and describe methods for improving robustness in the planning process and for recovering from disruptions during day-of-operations.

and

Timothy Jacobs, American Airlines (Past-President of AGIFORS, the Airline Group of IFORS)
Integrating O&D Passenger Effects into the Airline Scheduling Process

This paper presents an overview of the fleet assignment, schedule development and revenue management processes airlines typically use to develop, fleet and manage the seat inventory of their schedule. In addition, this paper presents a methodology for incorporating O&D network and pricing effects into the fleet assignment process. To illustrate the O&D fleeting concept and its benefits, we apply this concept to a typical schedule planning scenario at American Airlines and a Demand Driven Dispatch (D3) scenario where near-term fleeting changes improve the match between O&D passenger demand and available aircraft capacity close to the day of departure for American Eagle Airlines.

C.T. Kelly, North Carolina State University
Optimal Design of Municipal Water Supply Portfolios with Implicit Filtering

In this talk we describe an optimal design problem for a portfolio of water rights, leases, and options in the Southwestern Unites States. The design is based on a Monte Carlo model of rainfall and demand. The design parameters encode the government's response to demand and expected supply. The stochastic model implies that the objective function, the cost of a city's water supply for a year, is a discontinuous function of the design parameters. Constraints on reliability and conditional value at risk can only be tested when the simulation is complete and are not given by explicit formulae. We show how the implicit filtering method can solve the problem and exploit our knowledge of the size of the noise.

and

Amr El-Bakry, EXXON
Optimization in the Oil and Gas Industry: the Models and the Challenges

Although optimization has been used extensively in refineries since the 1950's, its use in other areas of the oil and gas industry such as exploration, development, drilling, and production has been relatively limited. Recent developments in optimization technology and the increasing complexity in the above-mentioned activities led to a renewed interest in optimization as an analysis and decision-support tool.

In this talk I will give an overview of the challenging optimization problems facing the current and the future oil and gas exploration and production activities. The resulting models cover almost all areas of optimization technology, from continuous to combinatorial, from linear to nonlinear and from deterministic to stochastic. I will conclude the talk with few comments for those who are aspiring to pursue careers as industrial mathematicians.

Bartosz Protas, McMaster University
Adjoint-Based Optimization in Fluid Mechanics: Theory, Computations and Industrial Applications

In this presentation we review solution methods for a class of equality constrained optimization problems in fluid dynamics governed by partial differential equations such as the Navier-Stokes equation and other conservation equations. We show how such PDE-constrained optimization problems can be efficiently solved using a gradient-based approach. Since the control variable in such problems is usually continuous, the main challenge consists in determining the gradient of the cost functional with respect to such infinite-dimensional control, and we demonstrate that this can be done conveniently by solving a suitably-defined adjoint PDE system. We emphasize, in particular, problems described by PDEs defined on variable domains, whose treatment necessitates the use of specialized techniques, such as the shape-differential calculus. Application of the presented approach to a number of classical problems in fluid mechanics and thermodynamics will be discussed, including optimal control for drag reduction, optimal state estimation and optimization of interfacial phenomena (the Stefan problem). We will conclude by presenting some industrial applications concerning optimization of advanced welding techniques in automotive industry.

and

Saroja Polavarapu, Environment Canada
Four-dimensional variational assimilation in the context of weather prediction

Data assimilation involves combining observations with computer model output to obtain a consistent, evolving 3-dimensional picture of the atmosphere. This process is used at operational weather forecasting centres to produce initial conditions for launching weather forecasts.

The mathematics of data assimilation is from estimation theory, but in practice, there are many unique challenges and constraints to contend with. Weather forecasting models simulate an ever increasing number of nonlinear atmospheric processes, and are very large-- with state space of dimension 10 to 100 million. Such models require the fastest and largest supercomputers in order to produce timely forecasts. At the same time, while millions of observations are collected and distributed globally, this is an order of magnitude smaller than the state vector.

Therefore, there are also too few observations to compute the forecast error statistics needed for data assimilation. Approximations are
thus necessary, and where possible, knowledge of atmospheric dynamics provides guidance. This talk will provide an overview of the
atmospheric data assimilation problem in the context of global numerical weather prediction and will focus on the four-dimensional variational assimilation technique which is operational at Environment Canada.

Jan Modersitzki, McMaster University
Numerical Methods for Image Registration

Image registration is one of the most challenging tasks within digital imaging. Given two images R and T, one is looking for a transformation y such that a deformed version T(y(x)) of T is similar to R. The problem arises, for example, when images taken from different objects, perspectives, times, or devices need to be compared or fused.
Image registration, and in particular medical image registration, has been subject to extensive studies in the past years. Its versatile and important applications have attracted researchers from various branches. In this talk, we not only give an overview on some new
and exiting approaches but also point out some of the computational challenges associated with these approaches. Moreover, we explain why variational based methods to image registration naturally lead to large scaled and challenging optimization problems. We
present various instructive examples and real life applications.

and

Vladimir Pekar, Philips Research North America
Image Registration in Radiation Therapy Planning

The changes in a patient’s anatomy during the course of fractionated radiotherapy lead to uncertainties in radiation delivery. This limits the treatment efficacy and can cause severe side effects. The aim of adaptive image-guided radiation therapy (IGRT) is to minimize these uncertainties through the use of additional imaging studies (including multi-modal imaging), which allows for highly individualized radiation treatment plans. In doing so, deviations from the treatment plan can be detected at an early stage to correctively adjust the plan parameters. Image registration is the key technological component for successful implementation of IGRT.
In this talk, we will review and discuss several classes of image registration methods and their applications in radiation therapy planning. A comparative presentation of voxel-based, model-based, and feature-based registration methods will be given. Illustrative examples using real clinical data will also be presented.

John W. Chinneck, Carleton University
The Maximum Feasible Subsystem Problem and Applications

Given an infeasible set of linear constraints, the Maximum Feasible Subsystem Problem (MaxFS) consists of finding the largest cardinality feasible subset of the constraints. A wide variety of algorithms for the solution of this problem have been proposed in recent years. These solution algorithms will be summarized, and applications in areas as diverse as machine learning, statistics, computational biology, digital video broadcasting, etc. will be described.

and

Mauricio G. C. Resende, Lead Member of Technical Staff, Algorithms & Optimization Research Department
AT&T Labs Research
Some combinatorial optimization problems arising in telecommunications

Combinatorial optimization problems are abundant in the telecommunications industry and the successful solution of these problems has played an important role in telecommunications and its widespread use. Optimization arises in problems as varied as planning and design of optical and wireless networks, routing, restoration, network survivability, e-commerce, and search engine design. In this talk, we report on five problems that we have recently come across while working at an industrial research center of a large communications services company. The focus of our research is on developing heuristics to find good-quality solutions for these problems.

Telephone migration occurs when an organization upgrades to a newer phone switch (PBX) and needs to move all the phones using the old switch to the new one. PBX switches implement many features in which groups of phones can interact. One example is the "multi-line hunt group" where up to 100 phones are placed in a cycle and any call coming into any phone in the group will cycle through the group until it is answered. Another example is "call pickup" where any phone in the group can answer any call made to other phones in the group. Given a number of periods in which to migrate the phones and a maximum number of phones that can be moved per period, we want to complete the migration process in the time horizon while minimizing the disruption to the features provided by the switches.

Traffic migration occurs when traffic is to be moved from an outdated network to a new one. At each time period, a node in the old network is decommissioned and deloaded. i.e. all traffic coming into it or going out of it is moved to a given node in the new network. After a few nodes have been decommissioned, there will be some traffic in the old network, some traffic in the new network, and some traffic between the two networks for which temporary capacity will have to be provided. The objective is to minimize this capacity by determining the order in which the old nodes are decommissioned.

The Internet is divided into many routing domains, called autonomous systems. An autonomous system, or simply AS, is a network that consists of routers and links connecting the routers. These ASes interact to control and deliver Internet Protocol (IP) traffic. They typically fall under the administration of a single institution, such as a company, a university, or a service provider. Intra-domain traffic engineering aims to make more efficient use of network resources within an AS. Interior Gateway Protocols such as OSPF (Open Shortest Path First) are commonly used to select the paths along which traffic is routed within an AS. These routing protocols direct traffic based on link weights assigned by the network operator. Each router in the AS computes shortest paths and creates destination tables used to direct each packet to the next router on the path to its final destination. Given a set of traffic demands between origin-destination pairs, the "OSPF weight setting problem" consists in determining weights to be assigned to the links so as to optimize a cost function, typically associated with a network congestion measure.

It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as arc or router failures. In such situations, IP traffic is re-routed through the shortest paths not of one or more "pipes", where pipes can have different capacities and costs. We consider a survivable IP network design problem, where we need to assign OSPF weights and select a subset of pipes to assign to each arc, aiming to produce efficient OSPF-routed networks with minimum total "pipe" cost needed to route
the required demand and handle any single arc or router failure.

In the optimal node placement problem for path disjoint network monitoring we wish to carry out end-to-end network performance measurements between each of a given set of target nodes and pairs of measurement nodes, under the constraint that the pair of paths from each measurement node to the corresponding target node are node disjoint. Arbitrary routes are disallowed and we are constrained to obey standard network routing policies, such as OSPF. The objective is to find the smallest cardinality set of measurement nodes.

Peter Sturdza, Desktop Aeronautics, Palo Alto, CA
Design Optimization of a Supersonic Natural Laminar Flow Business Jet
Few aircraft are specifically designed to emphasize passive laminar flow at the preliminary design stage. The Aerion natural laminar flow supersonic business jet concept requires just that. This paper discusses some details of the unique technology developed for the design of Aerion’s revolutionary jet. An overview of the laminar flow features of the configuration are presented, along with a summary of the design-oriented transition prediction methodology used for aerodynamic design of the airplane. Results from aerodynamic shape optimizations of the business jet and of a new high Reynolds number supersonic laminar flow experiment are also presented.

and

Sivakumaran Nadarajah, Department of Mechanical Engineering, McGill University
Pushing the Limits of Optimum Shape Design for Unsteady FlowsIn the past decade, aerodynamic shape optimization has been the focus of attention due largely to advanced algorithms that have allowed researchers to calculate gradients cheaply and efficiently. The majority of work in aerodynamic shape optimization has focused on the design of aerospace vehicles in a steady flow environment. Investigators have applied these advanced design algorithms, particularly the adjoint method, to numerous problems, ranging from the design of two-dimensional airfoils to full aircraft configurations to decrease drag, increase range, and reduce sonic boom. Researchers have tackled these problems using many different numerical schemes on both structured and unstructured grids.

Unlike fixed wing aircraft, helicopter rotors and turbomachinery blades operate in an unsteady flow and are constantly subjected to unsteady loads. The flight envelope of a helicopter rotor is set by the compressibility effects experienced by the advancing rotor blade and by the dynamic stall of the retreating blade. As the helicopter forward flight speed increases, local supersonic zones that terminate at a shock wave develop on the advancing side, while at the retreating phase, the blade's velocity relative to the air decreases and the blade approaches the stall angle. This causes significant flow separation to occur on the upper surface of the blade, which in turn produces a loss in lift. All these issues have to be carefully taken into consideration to fully appreciate the performance of helicopter rotor blades.

Despite the recent efforts in ameliorating existing steady flow aerodynamic shape optimization algorithms, there is a considerable need to develop innovative and cost-effective optimal control techniques as well as new schemes for the design of aerodynamic surfaces subjected to unsteady loads. The goal is to push the limits on both the development of new schemes for the solution of unsteady flows as well as new algorithms for the design of aerodynamic shapes subject to unsteady loads.

Valuation of financial derivatives and financial planning are two different directions in mathematical finance. Both use optimization methods and we present a few recent models and methodologies in both directions. Dynamic programming problems are formulated for the valuation of the Bermudan and American put and call, dividend paying options under the Black-Scholes-Merton model for the asset price process. The models are solved by formulas that are numerically evaluated. Under more general conditions, the problem to approximate the price of a derivative, by the use of lower and upper bounds, is formulated as a special case of the classical moment problem. The probability distribution of the asset price is unknown but moment information is assumed to be available. Formulas, as well as specially designed algorithms provide us with the approximating values. Finally, we present recent results on the use of VaR, CVaR and CVAR risk measures in optimal portfolio composition problems.

and

Reha Tutuncu, Goldman Sachs
Optimization and Quantitative Portfolio Management

Optimization models and methods are central elements of quantitative equity portfolio management platforms. They serve as sophisticated tools for transfering the excess return ideas generated through research and testing into portfolios that best represent these ideas. In addition to the standard mean-variance optimization models that are adjusted for trading costs, we will discuss topics such as multi-portfolio optimization (optimizing multiple portfolios simultaneously while minimizing the joint market impact costs) and multi-period portfolio selection.

Eva K. Lee, Director
Center for Operations Research in Medicine and HealthCare
School of Industrial and Systems Engineering, Georgia Institute of Technology
and
Department of Radiation Oncology
School of Medicine
Emory University

Robust Optimization to Accommodate Effects of Systematic Treatment Uncertainties

Efficient and reliable IMRT treatment planning is challenging even when using only a single frozen-in-time CT scan of anatomic structures. The challenge is intensified in 4-D treatment planning, which is based on highly expanded imaging datasets that provide views of structure shape and position shifts over time. Incorporating these expanded datasets into the treatment planning process has the potential to yield better treatment plans, but at the same time results in models and optimization problems that are several magnitudes larger than those associated with traditional single-time-period planning. And along with the increase in problem size, there are additional sources of uncertainty and error (e.g., uncertainties in breathing trajectories, errors in organ contour outlining related to the increased number of images). Treatment planning methods must therefore be developed that can accommodate the increased problem size, and at the same time compensate for the errors and uncertainties.

In this talk, we describe various mathematical models for such robust and large-scale planning methods. Their mathematical complexity will be analyzed, and theoretical results will be described. We will demonstrate that our methods allow a reduction in mean dose to normal tissue, and in some cases, higher dose to tumor volume.

and

Timothy Craig, Princess Margaret Hospital
Accuracy in Radiation Therapy: Current Achievements, Future Solutions

Recent technical innovations in radiation therapy such as intensity modulated radiation therapy (IMRT) and image-guided radiation therapy (IGRT) provide the ability to deliver a high dose of radiation that conforms to the shape of a tumour while also avoiding healthy tissue. To ensure that the high radiation dose is localized on the tumour, great accuracy is required for treatment delivery. In addition, treatment must be designed to be robust to residual uncertainties in the treatment process.

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.