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 p-center 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 k-tree (k-fixed), we showed that the 
p-center 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 pair-wise 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 well-known
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 NP-hard, and it is NP-hard 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 mixed-formulation Local 
Search (LS) represents a good basis for the implementation of LS-based meta-
Heuristic methods and a Multi-start Local Search within this framework will be
presented. The comparison of the proposed approach with the state-of-the-art 
MIP-based 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 Complement-Based Preconditioners for Saddle-Point 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 large-scale 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 saddle-point 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 d-dimensional polytope with n facets 
has diameter at most n-d.  The construction highlights a particular 5-dimensional 
"prismatoid" polytope. In joint work with Hugh Thomas, we give a simple proof 
that there is no analogous 4-dimensional prismatoid.

February 10

Practical Methods for Computing Sparse or Low-Rank Solutions

Zhaosong Lu, SFU

Abstract: 
Nowadays there are numerous emerging applications in science and engineering 
concerning about sparse or low-rank solution such as compressed sensing, 
image recovery and dimension reduction. In this talk, we propose some practical 
methods for computing sparse or low-rank solutions. In particular, we study a 
novel first-order augmented Lagrangian (AL) method for solving a class of 
nonsmooth constrained optimization problems which include l1-norm and 
nuclear-norm regularized problems as special cases. The global convergence of 
this method is established. We also develop two first-order methods for solving 
the associated AL subproblems and establish their global and local convergence. 
In addition, we propose penalty decomposition methods for solving l0-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 k-Vertex-Deletion r-regular 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 0-regular 
graph, and then a natural generalization of Vertex Cover is to ask for a subset of 
at most k vertices which deletion leaves an r-regular subgraph, where r is some 
fixed integer. This problem was introduced in by Moser and Thilikos, and as it is 
expected, it is NP-hard 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 NP-hard and thus various convex relaxation techniques 
have been applied to approximate it. In this talk, we compare the strength of 
SDP, ESDP and sparse-SOS relaxations. Like the SDP and ESDP relaxations, 
we show that zero individual trace for sparse-SOS 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 Call-Center Workforce Scheduling

Yong-Pin 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
two-stage stochastic programs with recourse. We use experiments with two
large sets of call-center 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 zero-dimensional 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 well-known 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 2005-6, 2006-7, 2007-8, 2008-9 and 2009-10 Seminars.

  

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

Modified:  September 16th, 2010.