This page is an archive of the 2007-8 Simon Fraser University Operations Research Seminar.  The current seminar Web page is here. 

 

 

Spring 2008
 
 
April 16

*1:30*

 
Computational Convex Analysis and Applications
Yves Lucet, University of British Columbia, Okanagan
Abstract: 
Computational Convex Analysis focuses on the practical computation of 
fundamental transforms arising in Convex Analysis. Currently two main 
frameworks exist for such Computer-Aided investigation: fast algorithms 
based on discretization enhanced with computational geometry algorithms, 
and the Piecewise Linear-Quadratic framework based on quadratic spline
approximation. After recalling the current state of the art, we will illustrate where 
these algorithms appear in a wide variety of fields: thermodynamics, robot 
navigation, medical imaging, image processing, and network communications.
April 3

*Thurs. 4:30*

*15-300*

 
Value, Trading Strategies, Technology, and Financial Investment of Natural 
Gas Storage Assets 
Youyi Feng, SEEM, Chinese University of Hong Kong
Abstract: 
By valuing a natural gas storage facility as a portfolio of real options, we study
the value, trading strategies, technology, and financial investment of the storage
for a risk neutral natural gas marketer to trade gas in an energy commodity 
exchange (spot market). The storage facility under consideration can either 
represent a highly deliverable peak load storages or a lowly deliverable base
load storages. Its operational flexibilities could be valued by the expected
maximum profit earned from seasonal and daily trading. The primary focus is to 
optimize trading strategy to extract the embedded options value and assess the 
financial value of a storage contract to gain the whole or partial control of the 
facility over years.  We show that the optimal trading policy will refill (withdraw) 
gas only when the market price exceeds (is exceeded by) the convenience 
yield, an amount of the value to keep gas underground, less (plus) the marginal 
operating cost. Moreover, we explore the contingency of the optimal gas trading 
policy on the prediction of the spot prices by characterizing when it is optimal to 
sell low and buy high and when, on the other hand, it is optimal to buy high and 
sell higher. Finally, we demonstrate that the analysis can be deployed to value 
firm storage contract, and related technological deployment and financial 
investment.
April 2
 
A Faster and Simpler Approximation for Maximum Multicommodity Flow
John LaRusic, SFU
Abstract: 
We discuss the maximum multicommodity flow approximation algorithm Garg
and Könemann describe in their paper, "Faster and Simpler Algorithms for
Multicommodity Flows and other Fractional Packing Problems" (SIAM J.
Comput. 37 [2007], no. 2).  Their approach is to substitute shortest path
computations for min-cost flow computations, which they apply to other related
multicommodity flow problems.
March 12
 
Normal Cones and Nonconvex Optimization
Warren Hare, IRMACS, SFU 
Abstract:
In constrained optimization, the normal cone is to the constraint set what
derivatives are to the objective function. That is, normal cones provide first 
order information describing in a limiting sense how the constraint set behaves 
near the point of interest. Thus normal cones allow researchers to extend the 
notions and algorithms of unconstrained optimization (min{f (x)}) into a 
constrained setting (min{f (x) : x in S}). In this talk we discuss the basic definition 
of a normal cone both for convex and nonconvex constraint sets. We provide
illustrative examples, and demonstrate how normal cones provide the tools 
necessary to develop constraint identification theory for nonconvex optimization 
problems.
February 27
 
Recent developments on LQP-based numerical algorithm
Xiaoming Yuan, UBC-Okanagan and Shanghai Jiao Tong University
Abstract:
The talk focuses on the computational aspects of the so-called Logarithmic-
quadratics proximal (LQP) method, which was originally proposed by 
A. Auslender, et al. Some efficient LPQ-based numerical algorithms are
presented for solving nonlinear complementarity problems and structured 
variational inequalities. These new algorithms are applied to solve some traffic 
equilibrium problems.
February 13

*Room 15-300*

 
Primal-dual gradient methods for linear cone programming and applications
Zhaosong Lu, SFU 
Abstract:
In this talk, we consider linear cone programming (LCP) problem, and propose 
general primal-dual convex (smooth and/or nonsmooth) minimization
reformulations for it. We then discuss a class of gradient methods suitable for
solving these reformulations including Nesterov's smooth method, Nesterov's
smooth approximation scheme, and Nemirovski's prox-method. The iteration-
complexity bounds of these methods applied to the aforementioned
reformulations are derived. We also propose a variant of Nesterov's smooth 
(VNS) method that has clear advantages over Nesterov's smooth one. We then 
discuss the VNS method for solving three natural primal-dual convex smooth
minimization reformulations of LCP problem. The associated iteration
complexity bounds and overall arithmetic operation cost are estimated and 
compared. Finally, we apply the VNS method to solve MAXCUT, Lovász 
capacity, and several important large-scale problems arising in compressed
sensing that are challenging to simplex and/or interior point methods.
January 23

*Room 15-300*

 
Fraser Health uses Mathematical Programming to Plan its Inpatient Hospital Network
Pablo Santibanez, B.C. Cancer Agency 
Abstract:

Fraser Health (FH), the largest and fastest growing health region in British

Columbia, launched in 2005 the Acute Care Capacity Initiative (ACCI) to look

forward into the future and identify the major challenges for the region in terms

of capacity, from an evidence-based analytical approach.

 

The ACCI focus was on projecting the population’s need for clinical services

over the next 15 years, developing clinical service plans to address that need,

and creating service mix/siting configurations for the hospitals in its network of

care.

 

This talk is focused on the clinical service mix/siting phase of the ACCI, with

emphasis on the mathematical programming model used in the planning

process to develop configuration scenarios for FH’s network of hospitals.

 

Fall 2007
 
 
November 28
 
Local Search with Constraint Propagation and Conflict-Based Heuristics
Arman Kaveh, SFU 
Abstract: 
We will introduce a class of algorithms referred to as Hybrid Search Methods
for solving Constraint Satisfaction problems. There are two major classes of
algorithms used in CSP: constructive search and local search. Hybrid search
algorithms combine the two methods in an effort to utilize their advantages.
The proposed algorithm is experimented with using the Open Shop Problem
and some numerical results are presented.
November 21
 
Unified Canonical Duality Theory for Solving a Class of Nonconvex
Problems with Applications in Integer Programming
David Yang Gao, Virginia Tech
November 14
 
Online Scheduling with Stochastic Methods
John LaRusic, SFU
Abstract: 
Online scheduling problems differ from their offline counterparts in that the 
problem data is not completely available from the beginning but rather revealed 
during execution.  Generally, this involves new jobs/activities/requests 
unexpectedly arriving during execution that must now be considered.  In 
addition to having to make scheduling decisions based upon future uncertainty, 
time constraints often leave one with little time to make a new decision.  We 
discuss the stochastic methods proposed by Chang, Givan and Chong (2000) 
and Bent and Van Hentenryck (2004) for dealing with these issues.
November 8

*Thurs. 4pm*

 
Advances in portfolio decision analysis
Ahti Salo group, Helsinki University of Technology
Abstract:
This seminar includes three presentations on the following subtopics:
- Robust Portfolio Modelling (Juuso Liesiö, Pekka Mild, Ahti Salo)
- Contingent Portfolio Programming (Janne Kettunen, Ahti Salo)
- Rank-Oriented Data Envelopment Analysis (Ahti Salo, Antti Punkka)  
November 1

*Thurs. 4pm*

 
New Classification Methods for Cancer Diagnosis and Biomarker Discovery
Nabil Belacel, NRC Institute for Information Technology, Moncton, NB
Abstract:
Though many methods already exist for determination of markers and tumor
diagnosis using micro-array data, more precise and accurate methods for
feature analysis and selection as well as tumor classification are still
needed. This talk will present an overview on the application of new
approach based on data mining and machine learning tools for tumor
classification and for the selection of marker genes.  
October 31
 
Minimal generating families of parametric discrete and polyhedral sets with
 applications to survivable network design
Matthias Köppe, Inst. for Mathematical Optimization, University of Magdeburg 
Abstract: 
We consider the capacitated network design problem under arc-survivability
constraints.  We present a new method based on the study of the family of 
sets of feasible routings for fixed capacities and demands.  It turns out that
Minkowski sums play an important role in this setting and arc-survivability is 
easily modelled using non-linear, Minkowski-additive arc-survivability 
functionals.  The crucial feature of this framework is that the non-linear 
survivability constraints can be exactly linearized whenever a finite integral
generating set (with respect to Minkowski sums) is known.
 
We present new algorithms to compute minimal integral generating sets
(with respect to Minkowski sums) of families of discrete sets (for use with 
the model of integral flows) and parameterized polyhedra (for the model of
fractional flows).
October 24
 
Complexity of the simplex method for linear fractional assignment problem
Abraham Punnen, SFU 
Abstract: 
In this talk we show that the complexity of simplex method for the linear
fractional assignment problem (LFAP) is strongly polynomial. Although LFAP
can be solved in polynomial time using various algorithms such as Newton's
method or binary search, no polynomial time bound for the simplex method for
LFAP was known.
October 17
 
Semidefinite liftings for stable set and matching
Tamon Stephen, SFU
Abstract: 
This is a survey of the "lift and project" approach to solving integer programs.
We focus on the semi-definite matrix relaxations proposed by Lovász and
Schrijver and the examples of finding maximum stable sets and matchings in
a graph.
October 10
 
Packing T-joins
Matt DeVos, SFU
Abstract: 
T-joins are a common generalization of st-paths and perfect matchings, and
have proved to be an important structure in combinatorial optimization. 
Numerous classic results in graph theory, for instance Menger's theorem and
Konig's theorem, may be viewed as giving optimal packings of T-joins in
certain special cases.  Here we present a couple of theorems (joint with
Paul Seymour) which give fairly good packings of T-joins in general
circumstances.
October 3
 
Improved bounds for the symmetric rendezvous value on the line
Qiaoming Han, School of Eng. & Management, Nanjing University, visiting SFU
Abstract: 
A notorious open problem in the field of rendezvous search is to decide the
rendezvous value of the symmetric rendezvous search problem on the line,
when the initial distance apart between the two players is 2. We show that the
symmetric rendezvous value is within the interval (4.1520, 4.2574), which
considerably improves the previous best known result (3.9546, 4.3931). 
To achieve the improved bounds, we call upon results from absorbing Markov
chain theory and mathematical programming theory - particularly fractional
quadratic programming and semidefinite programming.  Moreover, we also
establish some important properties of this problem, which may be of
independent interest and useful for resolving this problem completely. 
Finally, we conjecture that the symmetric rendezvous value is asymptotically
equal to 4.25 based on our numerical calculations.
September 19
 
Modeling and optimization of loan portfolios
Fadil Santosa, IMA, University of Minnesota, visiting SFU
Abstract: 
This presentation is a very elementary introduction to credit risk modeling.  We
will describe how such a model can be calibrated against data, and how it can 
then be used to assess risk.  We will also show how to formulate Markowitz 
type portfolio optimization which minimizes risk for a fixed expected loss.

   

Organizer: Tamon Stephen, e-mail: tamon at sfu ca.

Modified: September, 2008.