Operations Research Seminar

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

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

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

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

Abstract:

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

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

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

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

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

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

and

IRMACS 10901

Introduction to multiple objective programming and simplex method for solving bi-objective 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 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

and

IRMACS 10900

Recent progress in the application of semidefinite programming to discrete optimization

Miguel Anjos, University of Waterloo

Abstract:

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

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

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

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

Modified: September 6th, 2010.