SFU
Operations Research Seminar
Welcome to the Web pages of the SFU
Operations Research Seminar Series.
We are associated with:
Our aim is to meet and discuss Operations Research topics.
Regular Meeting time: Thursdays, 3:30pm to
4:30pm
Meeting place:
Room 2746, Podium 2, SFU Surrey.
If you are interested in giving a talk, please contact Tamon Stephen,
tamon at sfu
ca.
Summer
2011


July 14 **SUR 3010** 
Application
of computational geometry to network location problems
Binay
Bhattacharya, Computing Science, SFU
Abstract: One of the objectives of this talk is to show that the tools from computational geometry can be effectively applied to solve location problems in networks. In particular we show that the pcenter problem in general networks can be transformed to a geometric problem known as Klee's measure problem (KMP). When the underlying network is a partial ktree (kfixed), we showed that the pcenter problem could be efficiently solved by transforming the problem to a range search problem. 
June 24 **Friday** 
The
Generalized Quadratic Assignment Problem (GQAP)
Farzana Sultana, SFU
Abstract: The Generalized Quadratic Assignment Problem (GQAP) covers a broad class of problems that involve the minimization of a total pairwise interaction cost among M equipments, tasks or other entities and where placement of these entities into N possible destinations is dependent upon existing resource capacities. These problems arise naturally in yard management, where containers are to be located in the storage areas with limited capacity, and in distributed computing where processing tasks are to be assigned to processors with limited computing resources. This problem generalizes the wellknown quadratic assignment problem (QAP), one of the most difficult problems in the combinatorial optimization field. Previous studies on the GQAP are relatively limited. The GQAP is NPhard, and it is NPhard to approximate. 
June 6 **Monday, 2 p.m., SUR 3290** 
Hybrid Heuristics for Routing of Barge
Container Ships
Tatjana Davidović, Serbian Academy of Sciences
and Arts
Abstract: The optimization of inland transport routes of barge container ships with the objective to maximize the profit of a shipping company is investigated. This problem consists of determining the upstream and downstream calling sequence and the number of loaded and empty containers transported between any two ports. Combinatorial and MIP formulations will be presented. The problem is initially approached by improved variants of existing MIP heuristics: Local Branching, Variable Neighborhood Branching, and Variable Neighborhood Decomposition Search. A new heuristic is then presented. The heuristic is based on the combination of the two formulations and aims to generate better quality solutions of the considered problem. The proposed mixedformulation Local Search (LS) represents a good basis for the implementation of LSbased meta Heuristic methods and a Multistart Local Search within this framework will be presented. The comparison of the proposed approach with the stateoftheart MIPbased heuristics will be reported.
This research has been done with V. Maraš, J. Lazić and N. Mladenović. 
Spring
2011


April 21 
A Certifying Algorithm for the Consecutive
Ones Property
Mehrnoush Malekesmaeili, SFU
Abstract: This is a presentation of the results in R. McConnell’s paper on “A Certifying Algorithm for the Consecutive Ones Property” (proceedings of SODA 2004). 
March 31 
Schur ComplementBased Preconditioners
for SaddlePoint Linear Systems
Chen Greif, Computer Science, UBC
Abstract: Block preconditioners play a prominent role in the numerical solution of saddle point linear systems arising from discretization of partial differential equations and largescale constrained optimization problems. In this talk I will provide an overview of preconditioning approaches based on primal and dual Schur complements. A key for their efficiency is the ability to characterize the spectra of the underlying continuous operators. A challenge of particular interest is how to deal with situations in which the (1,1) block of the saddlepoint matrix is nearly singular. We show that in such situations, the primal Schur complement related to the augmented Lagrangian methodology can be quite effective. The analytical results are complemented by numerical examples. 
February 24 
Santos' counterexamples to the Hirsch
conjecture and prismatoids
Tamon
Stephen, SFU
Abstract: In this talk we describe Santos' recent construction of counterexamples to the famous conjecture of Hirsch (1957): that a ddimensional polytope with n facets has diameter at most nd. The construction highlights a particular 5dimensional "prismatoid" polytope. In joint work with Hugh Thomas, we give a simple proof that there is no analogous 4dimensional prismatoid. 
February 10 
Practical Methods for Computing Sparse or
LowRank Solutions
Zhaosong
Lu, SFU
Abstract: Nowadays there are numerous emerging applications in science and engineering concerning about sparse or lowrank solution such as compressed sensing, image recovery and dimension reduction. In this talk, we propose some practical methods for computing sparse or lowrank solutions. In particular, we study a novel firstorder augmented Lagrangian (AL) method for solving a class of nonsmooth constrained optimization problems which include l_{1}norm and nuclearnorm regularized problems as special cases. The global convergence of this method is established. We also develop two firstorder methods for solving the associated AL subproblems and establish their global and local convergence. In addition, we propose penalty decomposition methods for solving l_{0}norm and rank minimization problems. Under some suitable assumptions, we show that each accumulation point is a stationary point of an equivalent smooth optimization problem. Finally, we demonstrate the computational performance of these methods by applying them to sparse principal component analysis and sparse logistic regression. 
January 20 
Travelling Salesman Problems with Time Windows and Applications
Sara Taghipour, SFU
Abstract: The traveling salesman problem with time windows(TSPTW) is an instance of TSP with an extra constraint of visiting each city in a certain time interval. A special case of this problem will be discussed. Small instances are solved with Cplex, while a Heuristic method is proposed for larger instances. 
Fall
2010


December 3 **Friday, 3 p.m.** 
Generalized Travelling Salesman Problems on Halin
Graphs
Brad
Woods, SFU
M.Sc. thesis defence (senior supervisor: Abraham Punnen). 
December 3 **Friday, 1 p.m.** 
Algorithms and Theoretical Topics on Selected Combinatorial
Optimization
Problems
Arman Kaveh, SFU
M.Sc. thesis defence (senior supervisor: Abraham Punnen). 
November 25 
A quadratic kernel for kVertexDeletion rregular Subgraph
Flavio Guińez, Sauder School of Business, UBC
Abstract: One way of thinking a vertex cover of a graph, is as a set of vertices which removal leaves an stable set. Also, any stable set can be viewed as a 0regular graph, and then a natural generalization of Vertex Cover is to ask for a subset of at most k vertices which deletion leaves an rregular subgraph, where r is some fixed integer. This problem was introduced in by Moser and Thilikos, and as it is expected, it is NPhard for each fixed r.
A parameterized problem is said to be Fixed Parameter Tractable (FPT) if there exists a function f and an algorithm that solves the problem in O(f(k)n^q) running time, where k is the parameter, n is the size of the input and q is a constant. There are several techniques to show that a parameterized problem is FPT, being kernelization one of the most applied. In the case of Vertex Cover, using a classical result of Nemhauser and Trotter we can deduce the existence of a kernel of size 2k, which is the best possible so far. Motivated by this, Moser and Thilikos found an algorithm for the general problem that produces a kernel that is cubic in k for each r>1, but that turns out quadratic in k for r=1. In this talk, we review this technique and see how to construct a kernel that is quadratic in k for each r>0.
This is based on a joint work with Stephan Thomasse. 
November 18 
No O.R. Seminars: Computational
Biology Seminar in Burnaby.

November 4 
SOS and SDP relaxations of sensor network localization
Ting Kei Pong, University of Washington
Abstract: The sensor network localization problem has received much attention in recent years. This problem is NPhard and thus various convex relaxation techniques have been applied to approximate it. In this talk, we compare the strength of SDP, ESDP and sparseSOS relaxations. Like the SDP and ESDP relaxations, we show that zero individual trace for sparseSOS relaxation also certifies accuracy of sensor position when distance measurements are exact. We show by a counterexample that this condition is no longer sufficient in the presence of distance measurement noise, for all three relaxations.
This is based on joint work with Joao Gouveia and Paul Tseng. 
October 21 
Parametric Stochastic Programming Models for CallCenter Workforce
Scheduling
YongPin Zhou, ISOM,
University of Washington
Abstract: We develop and test an integrated forecasting and stochastic programming approach to workforce management in call centers. We first demonstrate that parametric forecasts can be used to drive stochastic programs whose results are stable with relatively small numbers of scenarios. We then extend our approach to include forecast updates and twostage stochastic programs with recourse. We use experiments with two large sets of callcenter data to explore the importance of the use of scenarios and the use of recourse actions.
This is joint work with N. Gans, H. Shen, N. Korolev, A. McCord, and H. Ristock. 
October
7 
Recognizing Graph Properties Through
Polynomial Ideals
Mohamed Omar, University of California  Davis
Abstract: In the work of M. Laurent, J. Lasserre; P. Parrilo, Y.Nesterov, and others, optimization problems which are modeled by zerodimensional radical ideals have been shown to have a finite sequence of semidefinite programs that converge to an optimal solution. This has important implications for combinatorial optimization as it allows for a paradigm to solve many problems in polynomial time. An example is integer optimization over the assignment polytope.
In this talk I will give an overview of this theory and show applications to the study of special subsets of the assignment polytope. As a nice application I will discuss consequences for the wellknown automorphism and isomorphism problem for graphs.
This is joint work with Jesus De Loera, Christopher Hillar, and Peter N. Malkin. 
September 23 and 30 
No O.R. Seminars: Computational
Biology Seminars in Burnaby.

Archives of 20056, 20067, 20078, 20089 and 200910
Seminars.
Organizer: Tamon Stephen, email: tamon
at sfu ca.
Modified:
September 16th, 2010.