Date	Speaker	Title and Abstract
July 12th *Thursday* *2:00-4:30* *SUR 2980*	Pooja Pandey Ph.D. thesis defence Senior Supervisor: A. Punnen	Topics in Quadratic Binary Optimization Problems Abstract: In this dissertation, we consider the quadratic combinatorial optimization problem (QCOP) and its variations: the generalized vertex cover problem (GVC), the quadratic unconstrained binary optimization problem (QUBO), and the quadratic set covering problem (QSCP). We study these problems as discussed below. For QCOP, we analyze equivalent representations of the pair (Q, c), where Q is a quadratic cost matrix and c is a linear cost vector. We present various procedures to obtain equivalent representations, and study the effect of equivalent representations on the computation time to obtain an optimal solution, on the quality of the lower bound values obtained by various lower bounding schemes, and on the quality of the heuristic solution. The first variation of QCOP is GVC, and we show that GVC is equivalent to QUBO and also equivalent to some other variations of GVC. Some solvable cases are identified and approximation algorithms are suggested for special cases. We also study GVC on bipartite graphs. QUBO is the second variation of QCOP. For QUBO, we analyze several heuristic algorithms using domination analysis. We show that for QUBO, if any algorithm that guarantees a solution no worse than the average, has a domination ratio of at least 1/40. We extend this result to the maximum and minimum cut problems; maximum and minimum uncut problems; and GVC. We also study the QUBO when Q is: 1) (2d + 1)-diagonal matrix, 2) (2d + 1)-reverse-diagonal matrix, and 3) (2d+1)-cross diagonal matrix, and show that these cases are solvable in polynomial time when d is fixed or is of O(log n). The last variation of QCOP is QSCP. For QSCP, we identify various inaccuracies in the paper by R. R. Saxena and S. R. Arora, A linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. We also present the mixed integer linear programming formulations (MILP) for QSCP. We compare the lower bounds obtained by the linear programming relaxations of MILPs, and study the effect of equivalent representations of QSCP on these MILPs.
July 12th *Thursday* *10:00-12:30* *SUR 2710*	Brad Woods Ph.D. thesis defence Senior Supervisor: A. Punnen	The Quadratic Travelling Salesman Problem: Complexity and Approximation Abstract: In this thesis we study the Quadratic Travelling Salesman Problem (QTSP) which generalizes the well-studied Traveling Salesman Problem and several of its variations. QTSP is to find a least cost Hamiltonian cycle in an edge-weighted graph, where costs are defined for all pairs of edges contained in the Hamilton cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. When c = 0, it is referred to as the homogenous rank p QTSP. We study QTSP by examining the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP and the adjacent quadratic TSP.
May 10th *2:30* via COCANA (Kelowna)	Björn Rüffer University of Newcastle (Australia)	Lyapunov Functions and Optimization Further details available from the COCANA Website.
May 5th *Saturday, 8:30-4:00* *Seattle*	WCOM	Details of the Spring 2018 West Coast Optimization Meeting held at UW Seattle are here.
Apr. 20th *Friday* *4:30-5:30* *SUR 2710*	Jingxin Guo M.Sc. project presentation Senior Supervisor: A. Punnen	The Unrestricted Linear Fractional Assignment Problem Abstract: The linear fractional assignment problem (LFAP) is a well-studied combinatorial optimization problem with various applications. It attempts to minimize ratio of two linear functions subject to standard assignment constraints. When the denominator of the objective function is positive, LFAP is solvable in polynomial time. However, when the denominator of the objective function is allowed to take positive and negative values, LFAP is known to be NP-hard. In this thesis, we present two 0-1 programming formulations of LFAP and compare their relative merits using experimental analysis. We also show that LFAP can be solved as a polynomial bounded sequence of constrained assignment problems. Experimental results using this methodology are also given. Finally, some local search heuristics are developed and analyzed their efficiency using systematic experimental analysis. Our algorithms are able to solve reasonably large size problems within acceptable computational time.
Apr. 10th *11:30* *SUR 2980*	Negin Bolkhanian and Matthew Reyers Simon Fraser University	Math 402W Operations Research Clinic project presentation The Walking School Bus Routing Problem
Apr. 10th *10:30* *SUR 2980*	Alan Bi, Trevor Dallow and Samantha Zimmerman Simon Fraser University	Math 402W Operations Research Clinic project presentation Scheduling of Nurses at Raven Song Community Health Care Centre
Apr. 5th via COCANA (Kelowna)	Yves Lucet UBC Okanagan	On the convexity of piecewise-defined functions Further details available from the COCANA Website.
Mar. 15th	Sandy Rutherford Complex Systems Modelling Group Simon Fraser University	Control of an HIV Epidemic among Injection Drug Users: Simulation Modeling on Complex Networks Abstract: HIV remains a serious public health problem in many marginalized communities. We develop a network model of the HIV epidemic affecting injection drug users and female sex workers in the Downtown Eastside neighborhood of Vancouver, Canada, calibrated using data from public health surveillance and cohort studies. Many HIV positive individuals are unaware of their status and strategies for testing are an important part of HIV response programs. Upon diagnosis, HIV patients enter a continuum of care, involving both engagement and retention in treatment. We explored potential epidemic control strategies through simulation: reduced syringe sharing during injection drug use, reduced time to diagnosis, reduced time to initiation of treatment following diagnosis, and improved retention in treatment. We find that syringe sharing, HIV testing, and retention in treatment significantly impact HIV prevalence. Close connections between syringe sharing and sexual networks deserve attention as important avenues for rapid HIV transmission.
Mar. 8th via COCANA (Kelowna)	Tim Hoheisel McGill University	Epi-convergent Smoothing with Applications to Convex-Composite Functions Further details available from the COCANA Website.
Mar. 1st SUR 3040	Winfried Grassmann Computer Science University of Saskatchewan	Discrete Event Systems as Basis of Discrete-time Queues, Including Multiserver Queues and Tandem Queues Abstract: A number of papers have appeared describing how to calculate the distribution of the number of elements in a discrete-time GI/G/1 queue in a statistical equilibrium. Essentially, the process is converted to a discrete-time Markov chain and solved as such. It turns out that this method also works for discrete-time discrete event systems in a statistical equilibrium. They, too, can be converted into discrete time Markov chains, and solved. The problem is that due to the curse of dimensionality, the number of states is huge, and to solve the equilibrium equations, iterative methods should be used, such as Gauss-Seidel. Still, every effort must be made to reduce the dimensionality of the problem as much as possible. One way to do this is to embed the process at the points in time where events occur. Using this method, we could solve systems of reasonable size on our laptop, including GI/G/c queues and tandem queues. For some models, further reductions in the dimensionality are possible. One example is the applications of the distributional Little’s law to the GI/G/1 queue. Possible extensions of this method are discussed.
Feb. 22nd *SUR 3040*	David Stanford Statistics and Actuarial Science Western (Ontario) University	The Affine Accumulating Priority Queue: a model which prioritises based upon acuity and waiting time Abstract: Previous accumulating priority queues (APQ) in the literature have assumed that all arriving customers accumulate priority credits over time starting from an initial value of 0. The affine APQ model introduces a new element in terms of an initial class-dependent credit level, from which the accumulated priority grows linearly over time. In this presentation, we consider a two-class APQ, for which class-1 customers receive a positive initial credit upon arrival. (Without loss of generality the class-2 customers continue to have an initial credit of 0.) We assess the impact of the initial priority score upon the waiting time distribution for the lower class of customers, and insights regarding the higher priority class waiting time distribution as well. Numerical examples will be presented to illustrate the trends we observe. This is joint work with Maryam Mojalal, Richard Caron, Peter Taylor and Ilze Ziedins.
Jan. 25th via COCANA (Kelowna) *SUR 2746*	Paulo J. S. Silva Unicamp	Using the Spectral Proximal Gradient Method to Decompose a Matrix as the Sum of a Sparse Plus a Low-rank Term Further details available from the COCANA Website.
Dec. 11th *Monday* *9:00-10:30* *SUR 2710*	Bolong He M.Sc. project presentation Senior Supervisor: T. Stephen	Analysis of Firefighter Absences and Hiring Schedule Optimization at the Surrey Fire Department Abstract: We study staffing issues at the Surrey Fire Department with a view to understanding and optimizing the annual hiring cycle for full-time firefighters. This project begins with a discussion of a previous model used by the Fire Department which predicts absences based on seasonally adjusted historical data and then optimizes the hiring cycle based on a simulation. We extend the analysis of the data to include the age cohort as a variable and compare short-term and long-term absences. We then use time series to predict future absences and use these predictions along with additional constraints to optimize the hiring schedule.
Dec. 4th *Monday* *10:30-1:00* *SUR 3040*	Timothy Yusun Ph.D. thesis defence Senior Supervisor: T. Stephen	On the Circuit Diameters of Polyhedra Abstract: We develop a framework to study the circuit diameters of polyhedra. The circuit diameter is a generalization of the combinatorial (edge) diameter, where walks are permitted to enter the interior of the polyhedron as long as steps are parallel to its circuit directions. Because the circuit diameter is dependent on the specific realization of the polyhedron, many of the techniques used in the edge case do not transfer easily. We reformulate circuit analogues of the Hirsch conjecture, the d-step conjecture, and the nonrevisiting conjecture, recovering the edge case equivalences in the circuit case. To do this we adapt the notion of simplicity to work with circuit diameter, and so we define C-simplicity and wedge-simplicity. Then, we prove the circuit 4-step conjecture, including for unbounded polyhedra, by showing that the original counterexample U4 to the combinatorial analogue satisfies the Hirsch bound in the circuit case, independent of its realization. This was the first known counterexample to Hirsch, and several families of counterexamples are constructed from U4. In particular, the unbounded Hirsch conjecture could still hold in the circuit case. We also use computational methods to study Q4, the bounded counterpart to U4, and give two realizations with different circuit diameters. It remains open whether Q4 is circuit Hirsch-sharp; however, we are able to lower the distance bound for at least one direction between the two far vertices of Q4. Finally, we present some auxiliary results involving representations of polyhedra and circuit calculations.
Oct. 26th via COCANA (Kelowna)	Hamid Afshari University of Manitoba and UBC Okanagan	Improving the Resilience of Energy Flow Exchanges in Eco-Industrial Parks: Optimization Under Uncertainty Further details available from the COCANA Website.
Sept. 28th via COCANA (Kelowna)	Gord Lovegrove UBC Okanagan	Models of Bicycle Rider Perceptions Related to Safety and Comfort Further details available from the COCANA Website.
Sept. 16th *Saturday, 8:30-4:00* *2740*	WCOM	Details of the Fall 2017 West Coast Optimization Meeting here.
Sept. 14th via COCANA (Kelowna)	Scott Lindstrom University of Newcastle (Australia)	Douglas-Rachford Method for Non-Convex Feasibility Problems Further details available from the COCANA Website.