2013-2014 Operations Research Seminar

Welcome to the Web page of the SFU Operations Research Seminar Series. We are associated with:
CORDS (Centre for Operations Research and Decision Sciences), and
The Department of Mathematics, Simon Fraser University.
Our aim is to meet and discuss Operations Research topics.

Unless noted the talks will be at 2:30 on Thursday in Room 5380, SFU Surrey.
Please contact Tamon Stephen if you would like to speak.

Date Speaker Title and Abstract
May 29th

via COCANA (Kelowna)

Jeffrey Pang Chin How

National University of Singapore
Set Intersection Problems with Supporting Halfspaces and Quadratic Programming: More Observations

Further details available from the COCANA Website.
May 15th

Arash Rafiey

Department of Computing Science

Simon Fraser University
PTAS for Some Instances of Fair Allocation Problem

Abstract:
We consider the problem of fair allocation of indivisible goods where we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that the minimum utility (sum of the resources) received by each of the customers is as high as possible.

We are interested in instances of the problem that admit a PTAS (polynomial time approximation scheme) As an example, we demonstrate a PTAS when there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources. Other variation of the resource allocation problem will be discussed.

Based on joint works with R. Krishnamurti, K. Khodamoradi, and G. Stamulis.
May 8th

Martin Skutella

Department of Mathematics

TU Berlin
Unsplittable and k-splittable flows in single-source networks

Abstract:
Given a network with a single source and several sinks with associated demands, we study flow problems with restrictions on the flow-carrying paths. In the unsplittable flow problem, the demand of each sink has to be satisfied along a single source-sink path. The k-splittable flow problem allows to split each demand into at most k packets such that each packet is sent along a single source-sink path. We discuss recent results and algorithms for turning an arbitrary flow into an unsplittable or k-splittable flow with bounded increase of flow values along arcs.
Apr. 17th

Wotao Yin

Department of Mathematics

UCLA
Distributed Optimization over Network

Abstract:
There has been considerable recent interest in solving optimization problems with data stored over a network. For these problems we need techniques that process data locally yet converge rapidly to an (approximate) solution across the entire network. This talk reviews primarily first-order algorithms for large-scale optimization of the distributed or decentralized types. We emphasize on recognizing separable structures in a large set of signal processing and statistical learning problems and demonstrate that, through skillful uses of gradient, proximal, duality, and splitting techniques, massively parallel algorithms can be developed. Numerical results are presented to demonstrate the scalability of the parallel codes on typical Unix clusters and Amazon EC2.
Apr. 15th

*3:00-4:30*

*SUR 4010*
Krishna Teja Malladi

M.Sc. thesis defense

Senior Supervisor: A. Punnen
Cluster Restricted Maximum Weight Clique Problem and linkages with Satellite Image Acquisition Scheduling

Abstract:
We consider the cluster-restricted maximum weight clique problem (CRCP), a variation of the well-known maximum weight clique problem. While CRCP itself is a mathematically interesting, our motivation to study the problem primarily comes from its application in the area of Satellite Image Acquisition Scheduling.

Earth observing satellites revolve around the earth in specific orbits and takes images of prescribed areas requested by the clients. Not every region can be fully acquired in a single satellite pass. This necessitates the division of the region into multiple strips. There might be several image acquisition opportunities for each strip as the satellites have agility in their rolling angles. Then the Satellite Image Acquisition Scheduling Problem (SIASP) is to select the opportunities to acquire as many images as possible, without repetition, within a planning horizon while considering the image priorities and energy constraints. SIASP has a piecewise linear objective function to favor the completion of an image acquisition request and try to avoid partial acquisition of many requests. Extensive experimental study is provided on randomly generated instances based on the predicted statistics given by MDA Corporation, Richmond, Canada. These experiments are intended as a preliminary investigation on image acquisition scheduling for the Canadian RADARSAT Constellation Mission (RCM), a constellation of three satellites, which is planned to be launched in 2018.

SIASP can be modeled as a CRCP with piecewise linear objective function. We provide integer programming (IP) formulations for CRCP with linear and piecewise linear objective function. We also suggest heuristic (metaheuristic) algorithms that exploit the power of modern IP solvers such as CPLEX. Experimental results using the heuristic algorithms on DIMACS and BOSHLIB benchmark instances for the clique problem and reported. Finally, an exact algorithm for CRCP along with some theoretical analysis is presented.
Apr. 10th

*3:30-5:00*

*SUR 5320*
Xueying (Sylvia) Shen

M.Sc. thesis defense

Senior Supervisor: A. Punnen
Path Selection Problem in Network Design

Abstract:
In this thesis we study several models for the Path Selection Problem associated with the construction of fiber optic networks. Four different variations of the Greedy Path Selection Problem (GPSP), Benevolent Path Selection Problem (BPSP), Discounted Path Selection Problem (DPSP) and Path Selection with capacity expansion. All the variations are NP-hard and polynomially solvable special cases are identified for GPSP and BPfied. We also present detailed complexity analysis and integer programming formulations for these problems. Heuristic algorithms including greedy algorithm, semi-greedy algorithm and multi-start local search algorithm are developed for each problem. Extensive computational results are provided with the algorithm performance analysis. We also present some future directions for research.
Apr. 10th

*10:00-11:00*

*SUR 4010*
Yong Zhang

Ph.D. thesis proposal presentation

Senior Supervisor: Z. Lu
Optimization Methods for Sparse Approximation

Abstract:
Recently, there are numerous applications in which sparse solutions are concerned. Mathematically, all these applications can be formulated into the l0 minimization problems. In this proposal, we first briefly introduce some interesting applications of the sparse approximation problems and discuss their formulations. We then look into one important application, that is, sparse Principal Component Analysis (PCA) which is a popular tool for data processing and dimension reduction. We discuss some drawbacks of the existing formulations for sparse PCA and propose a new formulation for it by taking into account the three nice properties of the standard PCA, that is, maximal total explained variance, uncorrelation of principal components, and orthogonality of loading vectors. We then propose a novel augmented Lagrangian method to solve this formulation. Additionally, we propose two nonmonotone gradient methods for solving the augmented Lagrangian subproblems. The augmented Lagrangian method and the nonmontone gradient methods can also be adapted to solve the l1-norm relaxation problems of other sparse approximation applications. Finally, we propose penalty decomposition methods for solving the original l0 minimization problems in which a sequence of penalty subproblems are solved by a block coordinate descent method.
Apr. 8th

*12:30-2:20*

*SUR 2740*
Operation Research Clinic project presentations Please join us as our undergraduates from Math 402W Operations Research Clinic present their projects. Each project is an analysis of an applied problem using operations research techniques. The topics, selected by the students, are:
  • Selecting Optimal Tolling Levels
  • Location and Routing of Community Mailboxes
  • Optimal Locations of Telecommunication Equipment
Apr. 3rd

via COCANA (Kelowna)

Samir Adly

Université de Limoges
Modern Nonsmooth Analysis and its Applications in Electrical Engineering

Further details available from the COCANA Website.
Mar. 27th

via COCANA (Kelowna)

Hung Phan

University of British Columbia, Okanagan
Linear convergence of the Douglas-Rachford method for two closed sets

Further details available from the COCANA Website.
Feb. 27th

Zhaosong Lu

Department of Mathematics

SFU
Randomized Block Coordinate Gradient Methods for a Class of Structured Nonlinear Programming

Abstract:
Nowadays a class of huge-scale structured optimization problems arise in some emerging areas such as machine learning. They can be reformulated as minimizing the sum of a smooth and block separable nonsmooth functions. For these problems, it is prohibitive to evaluate the full gradient of the smooth component of the objective function due to huge dimensionality and hence the usual gradient methods cannot be efficiently applied. Nevertheless, its partial gradients can often be computed much more cheaply. In this talk we study a randomized block coordinate gradient (RBCG) method for solving this class of problems. At each iteration this method randomly picks a block, and solves a proximal gradient subproblem over the subspace defined by the block that only uses a partial gradient and usually has a closed-form solution. We present new iteration complexity results for this method when applied to convex problems. We also propose a nonmonotone RBCG method for solving a class of nonconvex problems with the above structure, and establish their global convergence and iteration complexity. In addition, we present new complexity results for the accelerated RBCG method proposed by Nesterov for solving unconstrained convex optimization problems. Finally, we discuss the application of these methods for solving some support vector machine problems and report some computational results.

This is a joint work with Lin Xiao at Microsoft Research, Redmond.
Feb. 13th

via COCANA (Kelowna)

Yunier Bello Cruz

Universidade Federal de Goiás
On Forward-Backward Splitting Methods

Further details available from the COCANA Website.
Jan. 30th

via COCANA (Kelowna)

Chris Ryan

The University of Chicago, Booth School of Business
Duality theory via Fourier-Motzkin Elimination

Further details available from the COCANA Website.
Jan. 14th

(Tuesday, 2:30 p.m.)

*SUR 3010*
Ray Kawai

School of Mathematics and Statistics

University of Sydney
Mathematical Programming Gives Hard Bounds of the Dirichlet Problem for Partial Differential Equations

Abstract:
Differential equations, either deterministic or stochastic, play an indispensable role in modeling virtually every dynamics in physical and social sciences and devising efficient computational methods for differential equations is thus of paramount importance out of sheer necessity. The existing methods, such as finite difference, finite element and spectral methods, are designed to provide a good approximation of the solution, while approximation results do not provide any direct information about where and how far the true value is. We propose a novel numerical method based on mathematical programming for the Dirichlet problem for elliptic and parabolic partial differential equations without discretization. Our method is designed to provide hard upper and lower bounds of the solution by mathematical programming. The availability of hard bounds is of paramount significance as those hard bounds form a 100%-confidence interval in the context of probabilistic Monte Carlo methods. An optimization problem is formulated based upon the probabilistic representation of the solution and can be solved by semidefinite programming with the help of sum-of-square relaxation. Various theory-based techniques are developed to cope with difficult situations, such as finding a bounding polynomial function over the entire domain through a single implementation of the optimization problem. Numerical results are presented to support our theoretical developments and to illustrate the effectiveness of our methodology and techniques.
Nov. 28th

via COCANA (Kelowna)

Nghia Tran

University of British Columbia, Okanagan
Metric Regularity of the Subdifferential

Further details available from the COCANA Website.
Nov. 14th

via COCANA (Kelowna)

Warren Hare

University of British Columbia, Okanagan
Numerical Variational Analysis for VU-theory

Further details available from the COCANA Website.
Nov. 14th

*1:30 p.m.*

Dachuan Xu

Department of Applied Mathematics

Beijing University of Technology
Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach

Abstract:
The main contribution of this work is to propose a primal-dual combinatorial 3(1+epsilon)-approximation algorithm for the two-level facility location problem (2-LFLP) by exploring the approximation oracle concept. This result improves the previous primal-dual 6-approximation algorithm for the multilevel facility location problem, and also matches the previous primal-dual approximation ratio for the single-level facility location problem. One of the major merits of primal-dual type algorithms is their easy adaption to other variants of the facility location problems. As a demonstration, our primal-dual approximation algorithm can be easily adapted to several variants of the 2-LFLP, including models with stochastic scenario, dynamically arrived demands, and linear facility cost, respectively.

(Joint work with Chenchen Wu and Donglei Du.)
Oct. 29th

*10:00 a.m.*

*SUR 2980*
Xiaorui Li

Department of Mathematics

Simon Fraser University
Sparse Inverse Covariance Selection with Non-Convex Regularizations

M.Sc. thesis defence
Oct. 17th

via COCANA (Kelowna)

Liangjin Yao

Carma, University of Newcastle
Sum theorems for maximally monotone operators of type (FPV)

Further details available from the COCANA Website.
Oct. 3rd

via COCANA (Kelowna)

Hristo Sendov

Statistics and Actuarial Science, University of Western Ontario
Loci of Complex Polynomials

Further details available from the COCANA Website.
Sept. 19th

via COCANA (Kelowna)

Pooyan Shirvani Ghomi

Mathematics, University of Calgary
A moment-based approach for DVH-guided radiotherapy treatment plan optimization

Further details available from the COCANA Website.
Sept. 5th

via COCANA (Kelowna)

Bastien Talgorn

GERAD
Constrained Blackbox Optimization for Engineering Design

Further details available from the COCANA Website.
July 18th

* 1 p.m. *

*SUR 2995*
I-Lin Wang

Department of Industrial and Information Management

National Cheng Kung University
Operations Research and Logistics Issues raised in Bike Sharing Systems

Abstract:
Bike sharing systems (BSS) have been popular in several modern metropolitan areas. A bike is taken from a rental site and returned in another to help deal with the first and last mile problem for connecting passengers to public transit systems. The success of BSS relies on effective logistics management in its bikes. In particular, bikes need to be moved between rental sites to satisfy more demands in taking and returning bikes. In this talk, the speaker will explain how BSS works, how to model the network design problem that seeks the best locations for rental sites, how to balance the imbalanced bike flows caused by the rental demands, and how to solve these problems by efficient heuristics.


Archives of the 2006-07, 2007-08, 2008-09, 2009-10 2010-11 and 2011-12 SFU Operations Research Seminars.

Last modified July 6th, 2013.