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 |