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`
`Abstract:`
`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  `
`Abstract:`
`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  `
`Abstract:`
`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`
`Abstract:`
`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`
`Abstract:`
`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`
`Abstract:`
`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`
`Abstract:`
`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`
`Abstract:`
`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`
`Abstract: `
`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`
`provided.`

December 4

`Optimization algorithms for dynamic SPECT image reconstruction`
`Germain Tanoh, SFU Burnaby`
`Abstract: `
`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`
`Abstract: `
`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`
`Abstract: `
`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`
`Abstract: `
`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
Series:
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