CIM PROGRAMS AND ACTIVITIES

March 19, 2024

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.