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 v_{j} > 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 ksplittable flows in singlesource networks
Abstract: Given a network with a single source and several sinks with associated demands, we study flow problems with restrictions on the flowcarrying paths. In the unsplittable flow problem, the demand of each sink has to be satisfied along a single sourcesink path. The ksplittable flow problem allows to split each demand into at most k packets such that each packet is sent along a single sourcesink path. We discuss recent results and algorithms for turning an arbitrary flow into an unsplittable or ksplittable 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 firstorder algorithms for largescale 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:004: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 clusterrestricted maximum weight clique problem (CRCP), a variation of the wellknown 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:305: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 NPhard 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, semigreedy algorithm and multistart 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:0011: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 l_{0} 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 l_{1}norm relaxation problems of other sparse approximation applications. Finally, we propose penalty decomposition methods for solving the original l_{0} minimization problems in which a sequence of penalty subproblems are solved by a block coordinate descent method. 
Apr. 8th
*12:302: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:

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 DouglasRachford 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 hugescale 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 closedform 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 ForwardBackward 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 FourierMotzkin 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 sumofsquare relaxation. Various theorybased 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 VUtheory
Further details available from the COCANA Website. 
Nov. 14th
*1:30 p.m.* 
Dachuan Xu
Department of Applied Mathematics Beijing University of Technology 
Primaldual approximation algorithm for the twolevel facility location
problem via a dual quasigreedy approach
Abstract: The main contribution of this work is to propose a primaldual combinatorial 3(1+epsilon)approximation algorithm for the twolevel facility location problem (2LFLP) by exploring the approximation oracle concept. This result improves the previous primaldual 6approximation algorithm for the multilevel facility location problem, and also matches the previous primaldual approximation ratio for the singlelevel facility location problem. One of the major merits of primaldual type algorithms is their easy adaption to other variants of the facility location problems. As a demonstration, our primaldual approximation algorithm can be easily adapted to several variants of the 2LFLP, 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 NonConvex 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 momentbased approach for DVHguided 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* 
ILin 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. 