This page is an archive of the 2009-10 Simon Fraser University Operations Research seminar.  Information on the current seminar is available here.


Summer 2010

August 18


Analysis of bandwidth allocation with elastic demand on networks under budget


Hsing Paul Luh, National Chengchi University

This paper considers the problem of bandwidth allocation on end-to-end 
communication networks with multi-class 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 end-to-end 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 end-to-end paths are also discussed.
This is joint work with Chia-Hung Wang.



Spring 2010

April 22

*SUR 15-300*

Phylogeny-based Analysis of Gene Clusters

Roland Wittler, Simon Fraser University and University of Bielefeld

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 co-located 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-
(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 NP-completeness 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

We discuss the paper of Burkard, Dlaska and Klinz on the quickest flow problem.

March 25

Data-Driven Inventory Management

Woonghee Tim Huh, University of British Columbia

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 non-parametric 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 on-line convex optimization.

March 18


SUR 14-400


IRMACS 10908

Sparse topology selection in graphical models of time series

Lieven Vandenberghe, University of California at Los Angeles

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 1-norm 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

March 9


On Methods for Solving Nonlinear Semidefinite Optimization Problems

Jie Sun, National University of Singapore

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 second-order 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**

First-Order Methods for Nuclear Norm Minimization and its Applications

Hua Zheng, Simon Fraser University

M.Sc. Thesis defense (senior supervisor: Zhaosong Lu)

November 16


SUR 14-400


IRMACS 10901

Gene trees and species trees: parsimony problems

Cedric Chauve, Simon Fraser University

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 
NP-complete 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. El-Mabrouk, Universite de Montreal)
- approximation algorithms for computing a parsimonious first speciation,
 based on edge-cut problems in graphs and hypergraphs (work with
 A. Ouangraoua and K. Swenson, Universite du Quebec a Montreal)

November 2


SUR 14-400


IRMACS 10901

Introduction to multiple objective programming and simplex method for solving bi-objective programming

Sara Taghipour, Simon Fraser University

In this seminar, main definitions and theorems of multiple objective programming 
(a linear programming consisting of several objective functions) will be 
mentioned. Also, solving bi-objective programming will be discussed by 
extending simplex method for solving these problems.
(We assume familiarity with simplex method.)

October 26


SUR 14-400


IRMACS 10900

Recent progress in the application of semidefinite programming to discrete optimization

Miguel Anjos, University of Waterloo

The max-cut 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

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 ill-posed 
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 

September 16



Necessary optimality conditions for bilevel programming problems

Jane Ye, University of Victoria

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 2005-6, 2006-7, 2007-8 and 2008-9 Seminars.


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

Modified:  September 6th, 2010.