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.