This
page is an archive of the 200910 Simon Fraser
University Operations Research seminar. Information on the
current seminar is available here.
Summer
2010


August 18 *Wednesday* 
Analysis of bandwidth allocation with elastic demand on networks
under budget
constraints
Hsing Paul Luh, National
Chengchi University
Abstract: This paper considers the problem of bandwidth allocation on endtoend communication networks with multiclass traffic, where bandwidth is determined optimally under the budget and network constraints. We derive the blocking probabilities with respect to bandwidth, traffic demand and the available number of endtoend paths based on Erlang loss formula for all service classes. Depending upon the blocking probability, the paper presents different performance metrics, such as budget ratio, utilization level and bandwidth elasticity of blocking. Monotonicity and convexity of blocking probabilities with different parameters, such as allocated bandwidth, traffic demand and the number of endtoend paths are also discussed.
This is joint work with ChiaHung Wang. 
Spring
2010


April 22 *SUR 15300* 
Phylogenybased Analysis of Gene Clusters
Roland
Wittler, Simon
Fraser University and University
of Bielefeld
Abstract: The order of genes in genomes provides extensive information. In comparative genomics, differences or similarities of gene orders are determined to predict functional relations of genes or phylogenetic relations of genomes. For this purpose, various combinatorial models can be used to identify gene clusters – groups of genes that are colocated in a set of genomified approach to model gene clusters and define the problem of labeling the inner nodes of a given phylogenetic tree with sets of gene clusters. Our optimization criterion in this context combines two properties: (1) Parsimony, i.e. the number of gains and losses of gene clusters has to be minimal. This aim can be approached using well known methods, like Fitch Hartigan. (2) Consistency, i.e. for each ancestral node, there must exist at least one potential gene order that contains all the reconstructed clusters. Verifying this property is far from being trivial. We give an overview of already known and our new results for solving the "consistency problem" for different gene cluster models. Our findings range from a simple and efficient solution for adjacencies to NPcompleteness for other models. We developed an oracle based algorithm to reconstruct optimal labeling and finally show results on both simulated and real data. 
April 15 
The Quickest Flow Problem
Alex Goussiatiner, Simon
Fraser University and Modern Port
Technologies
Abstract: We discuss the paper of Burkard, Dlaska and Klinz on the quickest flow problem. 
March 25 
DataDriven Inventory Management
Woonghee Tim Huh, University
of British Columbia
Abstract: We consider inventory planning problems where the distribution of demand distribution is not available a priori, and lost sales are not observable. We take a nonparametric approach, and propose adaptive algorithms that generate a sequence of ordering decisions over time, where the decision in each period depends only on historical sales data. We show that our adaptive algorithms converge to the optimal solution, and establish the convergence rate. Our results are based on recent developments in online convex optimization. 
March 18 SUR 14400 and IRMACS 10908 
Sparse topology selection in graphical models of time series
Lieven Vandenberghe, University
of California at Los Angeles
Abstract: Graphical models give a graph representation of conditional independence relations between random variables. Estimating the model from observed data therefore generally includes the selection of the graph topology as well as the parameters in the model. In a Gaussian graphical model, the topology of the graph specifies the sparsity pattern of the inverse covariance matrix, and several topology selection methods based on convex optimization and 1norm regularization have been proposed recently. In this talk we consider an extension to graphical models of autoregressive Gaussian time series. We discuss the problem of maximum likelihood estimation of autoregressive models with conditional independence constraints, and convex techniques for topology selection via nonsmooth regularization. 
March 9 **Tuesday** 
On Methods for Solving Nonlinear Semidefinite Optimization Problems Jie Sun, National
University of Singapore
Abstract: The nonlinear semidefinite optimization problem arises from applications in system control, structural design, financial management, and other fields. However, much work is yet to be done to effectively solve this problem. We introduce some new theoretical and algorithmic development in this field. In particular, we discuss first and secondorder algorithms that appear to be promising, which include the alternating direction method, the augmented Lagrangian method, and the smoothing Newton method. Convergence theorems are presented and preliminary numerical results are reported. 
January 8 **Friday, 12:30** 
The Bottleneck Traveling Salesman Problem and Some Variations
John LaRusic, Simon Fraser
University
M.Sc. Thesis defense (senior supervisor: Abraham Punnen) 
Fall
2009


December 3 **Thursday, 11:30** 
FirstOrder Methods for Nuclear Norm Minimization and its
Applications
Hua Zheng, Simon Fraser
University
M.Sc. Thesis defense (senior supervisor: Zhaosong Lu) 
November 16 SUR 14400 and IRMACS 10901 
Gene trees and species trees: parsimony problems
Cedric Chauve,
Simon Fraser University
Abstract: A gene family is a set of genes, present in the genomes of several genomes, possibly in multiple occurrences in some genomes, that all originates from a single ancestral gene. A gene tree is a binary tree that describes evolutionary relationships between the genes of a same family, in terms of three kinds of events: speciations, duplications and losses. Phylogenomics aims at inferring, from a set of gene trees, a species tree. Here we consider the following NPcomplete optimization problem: infer the species tree that minimizes the number of gene duplications. I will present two results:  a description of tractable sets of gene trees (work with J.P. Doyon and N. ElMabrouk, Universite de Montreal)  approximation algorithms for computing a parsimonious first speciation, based on edgecut problems in graphs and hypergraphs (work with A. Ouangraoua and K. Swenson, Universite du Quebec a Montreal) 
November 2 SUR 14400 and IRMACS 10901 
Introduction to multiple objective programming and simplex method for
solving biobjective programming
Sara Taghipour, Simon Fraser
University
Abstract: In this seminar, main definitions and theorems of multiple objective programming (a linear programming consisting of several objective functions) will be mentioned. Also, solving biobjective programming will be discussed by extending simplex method for solving these problems. (We assume familiarity with simplex method.) 
October 26 SUR 14400 and IRMACS 10900 
Recent progress in the application of semidefinite
programming to discrete optimization
Miguel Anjos, University of Waterloo
Abstract: The maxcut algorithm of Goemans and Williamson is 15 years old in 2009, and its impact in the area of semidefinite programming has been remarkable. In this talk, I will survey some of the main modelling and algorithmic developments since 1994 in the application of semidefinite programming to discrete optimization problems. I will also highlight promising directions for research in this area. 
October 5 
Design in Inverse Problems
Eldad Haber,
University of British Columbia
Abstract: While there was much attention given to solving inverse problems there is a gap in the question of design, that is, the design of experiments for illposed problems and the design of regularization functionals.
In this talk we will present a framework to attack this problem. We show that it leads to a stochastic bilevel optimization problem and suggest algorithms for its solution. 
September 16 *Wednesday* **3:30** 
Necessary optimality conditions for bilevel
programming problems
Jane Ye, University of Victoria
Abstract: A bilevel programming problem is a sequence of two optimization problems where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. Bilevel programming problems can be used to model many problems in operations research and are also known as the Stackelberg games in economics. In this talk we discuss difficulties of deriving necessary optimality conditions for bilevel programming problems, in particular when the lower level problem is nonconvex. We provide a new necessary optimality condition which is valid under very weak constraint qualifications. 
Archives of 20056, 20067, 20078 and
20089
Seminars.
Organizer: Tamon Stephen, email: tamon
at sfu ca.
Modified: September 6th, 2010.