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


 Spring 2007

April 16

The capacitated max k-cut problem
Ramesh Krishnamurti, School of Computing Science, SFU
We consider a capacitated max k-cut problem in which a set of vertices
is partitioned into k subsets. Each edge has a non-negative weight, and
each subset has a possibly different capacity that imposes an upper bound
on its size. The objective is to find a partition that maximizes the sum
of edge weights across all pairs of vertices that lie in different
subsets. We describe a local-search algorithm that obtains a solution with
value no smaller that  1-1/k  of the optimal solution value. This improves
a previous bound of 1/2 for the max k-cut problem with fixed, though
possibly different, sizes of subsets.

April 2

Robust discrete optimization and network flows,
Annie Ruonan Zhang, SFU Surrey  
In this talk we will discuss the paper Robust discrete optimization
and network flows, by Bertimas and Sim. The authors proposed an approach
to address data uncertainty for discrete optimization and network flow
problems that allows controlling the degree of conservatism of the solution,
and is computationally tractable. In particular, when uncertain data
appears in both the cost coefficients and the the constraints of an
integer programming problem, the robust counterpart will result in a
solution with probabilistic bounds on constraint violation; when only the
cost coefficients are subject to uncertainty and the problem is a 0-1
discrete optimization problem on n variables, then the robust counterpart
will be solved by solving at most n+1 instances of the original problem.
Polynomially solvable cases and approximations will be analyzed. Finally,
the paper proposed an algorithm for robust network flows that solves the
robust counterpart by solving a polynomial number of nominal minimum cost
flow problems in a modified network.

March 26

Polynomial Time Approximation Schemes for Euclidean
Traveling Salesman and Other Geometric Problems
Arman Kaveh, SFU Surrey  
For every fixed c > 1 and any given n nodes in the plane, we can find a
(1 + 1/c) approximation to the optimum TSP tour in O(n (log n)^O(c))
time. The previous best approximation algorithm (due to Christofides)
achieves a 3/2 approximation in polynomial time. The problem of whether
a polynomial time approximation scheme for Euclidean TSP exists was
open prior to the Arora's paper. We will present this TSP polynomial
approximation scheme and we will also give similar polynomial
approximation schemes for a few other NP-hard Euclidean problems
such as Minimum Steiner Tree, k-TSP and k-MST.

March 19

On Goemans's and Williamson's MAXCUT algorithm
Karel Casteel, SFU Surrey
This will be an expository talk on the seminal work of Goemans and 
Williamson towards using semidefinite programming to develop improved
approximation algorithms for combinatorial optimization problems,
particularly MAX CUT and 2SAT.
I will introduce/review semidefinite programming and then outline how this
can be used to give a polynomial time randomized algorithm which finds a
maximum cut with expected value at least 0.87856 times the optimal weight.
Previous to this work, the best known approximation guarantee was
only 0.5 + o(n).
We will then examine a similar algorithm for 2SAT.

March 12

Constructing Incremental Sequences in Graphs
Joseph Peters, SFU, School of Computing Science
Given a weighted graph G=(V,E,w), we investigate the problem of
constructing a sequence of n=|V| subsets of vertices M_1,...,M_n
(called groups) with small diameters, where the diameter of a group
is calculated using distances in G.  The constraint on these n groups
is that they must be incremental: M_1 is a subset of M_2 ... is a subset
of M_n=V.  The cost of a sequence is the maximum ratio between the
diameter of each group M_i and the diameter of a group N_i with i
vertices and minimum diameter.  This quantity captures the impact of
the incremental constraint on the diameters of the groups in a sequence.
We give general bounds on the value of this ratio and we prove that
the problem of constructing an optimal incremental sequence cannot be
solved approximately in polynomial time with an approximation ratio
less than 2 unless P = NP.  Surprisingly, the related eccentricity problem
is in P.  We develop an optimal eccentricity algorithm and use it as the
basis of a 4-approximation algorithm for the diameter problem.  We show
that the analysis of our algorithm is tight.
Joint work with Ralf Klasing, Christian Laforest, and Nicolas Thibault

March 5

 Improving solution times in VLSI optimization problems
Warren Hare, IRMACS, SFU
Advances in technology for the manufacturing of integrated
circuits have resulted in extremely large, and time consuming, problems on
how to lay out components for optimal circuit performance.  The problem of
wire layout (or routing) in VLSI design can be written as a large scale
integer linear program with upper bound constraints.  Due to the size of
these programs, optimization by use of classical methods can be extremely
time consuming.  In this talk we will discuss some of the recent
techniques and ideas which have been emerging on how to improve the time
required to solve these highly structured linear programs.  The majority
of the talk will focus on applying novel preprocessing techniques to
simplify the problem.  However, if time permits, we will also discuss
recent ideas in parameter tuning, and various methods of embedding the
upper bound constraints into the constraint matrix in order to make better
use of interior point algorithms.

February 19

VLSN search: empirical analysis and theoretical reasoning
Abraham P. Punnen, SFU Surrey
In this talk, we introduced VLSN search algorithms for solving discrete
optimization problems. VLSN algorithms are precisely local search 
schemes using neighborhoods of very large size. We discuss theoretical 
analysis of algorithms in terms of associated neighborhood size or 
dominated solutions. Special neighborhoods are introduced that can be 
searched using matching problems or simpler integer programs. Results of 
extensive experimental analysis are discussed using the generalized 
assignment problem and its variations.

February 12

A New Cone Programming Approach for Robust Portfolio Selection
Zhaosong Lu, SFU Surrey
The robust portfolio selection problems have recently been studied by
several researchers. In their work, the ``separable'' uncertainty sets
of the problem parameters (e.g.,  mean and covariance of the random 
asset returns) were considered. These uncertainty sets share two common 
drawbacks: i) the actual confidence level of the uncertainty set is
unknown, and it can be much higher than the desired one; and ii) the
uncertainty set is fully or partially box-type. The consequence of these 
drawbacks is that the resulting robust portfolio can be too conservative and 
moreover, it is usually highly non-diversified as observed in computational 
experiments. To combat these drawbacks, we consider a factor model for the 
random asset returns. For this model, we introduce a ``joint'' ellipsoidal 
uncertainty set for the model parameters and show that it can be constructed as 
a confidence region associated with a statistical procedure applied to estimate 
the model parameters for any desired confidence level. We further show that 
the robust maximum risk-adjusted return problem with this uncertainty set can 
be reformulated and solved as a cone programming problem. Some 
computational experiments are performed to compare the performances of the 
robust portfolios corresponding to our ``joint'' uncertainty set and Goldfarb and 
Iyengar's ``separable'' uncertainty set. We observe that our robust portfolio has 
much better performance than Goldfarb and Iyengar's in terms of wealth growth 
rate and transaction cost, and moreover, our robust portfolio is fairly diversified, 
but Goldfarb and Iyengar's is highly non-diversified.

February 5

Introduction to robust optimization
Annie Ruonan Zhang, SFU Surrey

Fall 2006


December 11

Dynamic SPECT reconstruction using Kalman algorithm 
Joseph Qranfal, SFU Burnaby
Single photon emission computed tomography (SPECT) is a nuclear medicine
imaging technique that is extensively used for clinical diagnosis. Classical
SPECT reconstruction algorithms assume that the activity does not vary in
time. This is not always true in practice. For instance, when we study
Teboroxime cardiac images, the activity changes in time. Thus arises the
need of exploring dynamic SPECT. In this talk, I will explore a Kalman
reconstruction approach to estimate the time varying activity. While other
methods assume a priori knowledge about the activity behavior, Kalman
assumes little. We formulate a state-space model of the problem which we
solve using the optimal Kalman filter and smoother. Numerical results are

December 4

Optimization algorithms for dynamic SPECT image reconstruction
Germain Tanoh, SFU Burnaby
Nuclear medicine is a medical specialty that aids diagnosis as
well as treatment planning and monitoring by producing noninvasive,
diagnostic images using radiopharmaceutical. In dynamic SPECT we
study the dynamics of physiological processes and biochemical
functions of living organism. One of the problems we face is the
reconstruction of time activity curve. Because the emitted
activities are time dependent, classical Expectation Maximization
method fails to reconstruct a dynamic image. In this talk, I will
present new reconstruction algorithms which preserve the shape of
the time activity curve for each voxel. The proposed methods take
into account information about the dynamic of the activity as a
linear inequality constraints.  We consider two classes of
reconstruction method. The first class is a interior gradient
iterative algorithm based on Bregman generalized projection. The
second is a Newton based method and uses a line search to ensure
global convergence. Numerical experiments verify the effectiveness
of the algorithms.

November 27 

Allocating Resources to Control Infectious Diseases
by Margaret L. Bandeau
Karel Casteels, SFU Surrey

November 20 

Colourful linear programming
Tamon Stephen, SFU Surrey
We study a colourful generalization of the linear programming feasibility 
problem, comparing the algorithms introduced by Barany and Onn with new 
methods. We perform benchmarking on generic and ill-conditioned problems, 
as well as recently introduced highly structured problems. We
show that some algorithms can lead to cycling or slow convergence, but we 
provide extensive numerical experiments which show that others perform much 
better than predicted by complexity arguments. We conclude that an effective 
method in practice is a proposed multi-update algorithm.

November 13 

Seminar cancelled – due to Remembrance Day 

November 6

Models for Kidney Allocation
by Stefanos A. Zenois
Randall Pyke, SFU Surrey

November 1 

Optimization and Highly Informative Graph Invariants
Distinguished speaker: Dragos Cvetkovic, University of Belgrade, Serbia
It is known that graph invariants, which contain a great quantity of information on 
graph structure (for example, spectral invariants), are obtained by solving some 
extremal problems on graphs. Recently, such highly informative graph invariants 
are applied in solving optimization problems on graphs (e.g., the travelling 
salesman problem (TSP)). Using these paradigms, several relations, 
interconnections and interactions between graph theory and mathematical 
programming are described. A model of TSP based on semidefinite 
programming and algebraic connectivity of graphs is described. A class of 
relaxations of this TSP model is defined and some solution techniques based 
on this class are proposed. Several examples of graph invariants defined by 
some kind of optimization tasks are also presented. Using several spectrally 
based graph invariants we treat the graph isomorphism problem. 

October 23 

A primal-dual first-order method for cone programs
Zhaosong Lu, SFU Surrey
In this talk, we first review Nesterov's optimal methods for a class of 
smooth/non-smooth convex programs. A variant of his methods will be 
proposed. Based on these methods, we propose some primal-dual first-order 
methods for cone programs. Some preliminary computational results of our 
methods for randomly generated large-scale linear program and semidefinite 
program problems are then presented. We finally conclude that our methods 
are very promising for solving large-scale (dense) cone programs.
Joint work with G. Lan and R. Monteiro, Georgia Tech.

October 16 

Supply Chain Management of Blood Banks
by W.P. Pierskalla
Ron Ferguson, IRMACS, SFU

October 2 

The proximal average
Heinz Bauschke, University of British Columbia, Okanagan
Joint works with Yves Lucet (UBC Okanagan) and Mike Trienis (UBC Okanagan)

September 25 

Location of health care facilities
by Mark S. Daskin and Latoya K. Dean 
Arman Kaveh, SFU Surrey

September 18 

Benchmarking using DEA: The case of mental health organizations
by Y.A Ozcan, E. Merwin, K. Lee and J.P. Morrissey
Annie Ruonan Zhang, SFU Surrey

September 11 

Capacity planning and management in hospitals
by Linda V. Green 
Dan Benvenuti, SFU Surrey



Some of this year’s seminars discussed topics from the following book:


Operations Research and Health Care

A Handbook of Methods and Applications
International Series in Operations Research & Management Science , Vol. 70, 2004
Brandeau, Margaret L., Sainfort, Francois and Pierskalla, William P. (Eds.)  2004


Organizer: Snezana Mitrovic-Minic, e-mail: snezanam at sfu ca.

Modified: September 5th, 2007