Date	Speaker	Title and Abstract
July 6th *3:00-4:30* *SUR 2710*	Jingbo Tian M.Sc. thesis defense Senior Supervisor: A. Punnen	The Multiplicative Assignment Problem Abstract: The quadratic assignment problem (QAP) is an extensively studied combinatorial optimization problem. The special case of QAP where the cost matrix is of rank one is called the multiplicative assignment problem (MAP). MAP is not well studied in literature, particularly in terms of experimental analysis of algorithms. In this thesis we present some mixed integer linear programming formulations and compare their selective strength using experimental analysis. We also present exact and heuristic algorithms to solve MAP. Our heuristic algorithms include improvements in existing FPTAs, as well as local search and tabu search enhancements. Results of extensive experimental analyses are also reported.
May 22nd-25th	No seminar	The 2017 SIAM Conference on Optimization takes place in Vancouver.
May 11th via COCANA (Kelowna) *3:00*	Frank Maurer Computer Science University of Calgary	Immersive Analytics Further details available from the COCANA Website.
Apr. 7th *Friday* *2:30-4:00* *SUR 2980*	Olga Zasenko M.Sc. thesis defense Senior Supervisor: T. Stephen	Algorithms for Colourful Simplicial Depth and Median in the Plane Abstract: The colourful simplicial depth (CSD) of a point x in R2 relative to a configuration P=(P1, P2, ..., Pk) of n points in k colour classes is exactly the number of closed simplices (triangles) with vertices from 3 different colour classes that contain x in their convex hull. We consider the problems of efficiently computing the colourful simplicial depth of a point x, and of finding a point in R2, called a median, that maximizes colourful simplicial depth. For computing the colourful simplicial depth of x, our algorithm runs in time O(n log(n) + kn) in general, and O(kn) if the points are sorted around x. For finding the colourful median, we get a time of O(n4). For comparison, the running times of the best known algorithm for the monochrome version of these problems are O(n log(n)) in general, improving to O(n) if the points are sorted around x for monochrome depth, and O(n4) for finding a monochrome median.
Apr. 6th *11:30* *SUR 2980*	R. Jiang, W. Lu, L.T.S. Siu, T. Tong and D. Yin Simon Fraser University	Math 402W Operations Research Clinic project presentation School Infrastructure Planning and Catchment Rezoning: Alleviating Surrey Enrollment Pressure for 2020-2024
Feb. 2nd via COCANA (Kelowna)	Majid Jaberipour UBC Okanagan	Derivative-Free methods for Solving Unconstrained and Constrained Optimization Problems Further details available from the COCANA Website.
Jan. 26th	Songzi Du Department of Economics Simon Fraser University	Robust Mechanisms Under Common Valuation Abstract: We study robust mechanisms to sell a common-value good. We assume that the mechanism designer knows the prior distribution of the buyers’ common value but is unsure of the buyers’ information structure about the common value. We use linear programming duality to derive mechanisms that guarantee a good expected revenue for all information structures and all equilibria. Our mechanism maximizes the revenue guarantee when there is one buyer. As the number of buyers tends to infinity, the revenue guarantee of our mechanism converges to the full surplus. We numerically demonstrate that the revenue guarantees of our mechanisms are generally close to optimal when there are two buyers.
Jan. 12th via COCANA (Kelowna)	Honglin Luo Chongqing Normal University	SDP relaxation and rank-1 decomposition for maximin 1-dispersion problems Further details available from the COCANA Website.
Dec. 14th *12:00* *SUR 2710*	Pooja Pandey Ph.D. thesis proposal presentation Senior Supervisor: A. Punnen	The quadratic set covering problems and its variations Abstract: The set covering problem is a well studied combinatorial problem with numerous applications. In this thesis we primarily consider set covering problems with quadratic objective function (QSCP). QSCP has many applications such as the location of access points in a wireless network, the facility layout problem, or line planning in public transports. QSCP is known to be NP-hard and there are not many studies on this interesting problem. Some of the previous studies include: the polynomial approximation properties of the QSCP and approximation hardness results, and cutting-plane algorithm. In this thesis we plan to study various linearization techniques integrating the ideas from classical linearization techniques, McCormick envelopes, binary and decimal expansion of integers etc. We also plan to perform the theoretical analysis of the strengths of their LP relaxations. For the computational experiments we will use general purpose mixed integer programming solver (CPLEX) and do the experimental comparison of these formulations. Since not many benchmark problems are available for QSCP, for computational task we will develop benchmark test problems. Another direction of investigation is on efficient heuristic algorithms and systematic experimentation comparing various strategies using our benchmark problems. We will compare our heuristics with existing heuristics for QSCP from literature. We also plan to develop exact algorithms based on branch- and-cut strategies using valid inequalities and effective branching strategies. The exact algorithms we develop will be compared with general purpose commercial codes. Finally, several variations and special cases will be examined from theoretical as well as experimental point of view. These include the generalized vertex cover problem, the quadratic vertex cover problem, and the bottleneck quadratic set cover problem.
Dec. 14th *10:30* *SUR 2710*	Brad Woods Ph.D. thesis proposal presentation Senior Supervisor: A. Punnen	The quadratic travelling salesman problem: complexity, approximations, and exponential neighbourhoods Abstract: The (linear) travelling salesman problem (TSP) is to find a least cost Hamilton cycle in an edge weighted graph. It is one of the most widely studied hard combinatorial optimization problems, and has been used to model a wide variety of applications. In this thesis, a proper generalization of TSP, referred to as the quadratic travelling salesman problem (QTSP), is considered. Here, costs are incurred for every pair of edges belonging to a tour. A special case has been studied by various authors recently, which only considers pairs of adjacent edges (QTSP(A)). Since QTSP contains TSP as a special case, it is clearly NP-hard. For any NP-hard problem it is natural to investigate the conditions under which one can solve the problem in polynomial time, examine the approximability, and also to identify exponential neighbourhoods which can be searched efficiently. We begin by considering the polynomially solvable special cases for the linear TSP. QTSP is found to be sufficiently complex to remain intractable, and this motivates restrictions on the QTSP objective function. In addition to the general QTSP, we will consider two restrictions, QTSP(A) and the rank p QTSP (QTSP(p)), which restricts the rank of the quadratic cost matrix to some fixed number p. We will discuss the computational complexity of these problems, develop pseudopolynomial algorithms and develop fully polynomial time approximation schemes wherever appropriate. This includes specially structured graphs and special classes of tours. The behaviour of special cases of QTSP(A) and QTSP(p) are different, depending on their structural properties. Our work will focus on exploiting these structure in algorithm development. We will also consider the QTSP linearization problem, which extends the work of Kabadi and Punnen on the QAP linearization problem. We will give necessary and sufficient conditions for identifying when an instance of QTSP is linearizable.
Dec. 8th *SUR 2746* via COCANA (Kelowna)	Jonathan Eckstein Management Science & Information Systems Rutgers University	Asynchronous Projective Splitting for Convex Optimization and Monotone Inclusion Problems Further details available from the COCANA Website.
Nov. 24th	Steffen Borgwardt University of Colorado, Denver	Operations Research in Land Exchange Abstract: With geometric modeling techniques, one can represent the feasible solutions of problems in operations research as objects in high-dimensional space. The properties of these objects reveal information about the underlying problems and lead to algorithms. We model an application in land exchange as a clustering problem where the clusters have to adhere to prescribed cluster sizes. In this approach, we connect least-squares assignments, cell complexes, and the studies of polyhedra. Further, we report on how these results were implemented in practice. The devised methods lead to various tools for more general questions on big data.
Nov. 17th	Zirui Zhou Simon Fraser University	A Unified Approach to Error Bounds for Structured Convex Optimization Problems Abstract: Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.
Nov. 3rd	Stefan Lendl Institute of Discrete Mathematics Graz University of Technology	Time-Expanded Combinatorial Optimization Problems Abstract: For some combinatorial optimization problems their temporal dimension has been widely studied. Network flow problems and scheduling problems are major examples, where lots of such results are known. For other types of combinatorial optimization problems there are hardly any or no results at all about their temporal extension. First we introduce different models and variants of time-expanded combinatorial optimization problems. We present complexity and algorithmic results for some problem variants. This is joint work with Bettina Klinz.
Oct. 27th via COCANA (Kelowna)	John Chinneck Systems and Computer Engineering Carleton University	MILP Insights and Algorithms Further details available from the COCANA Website.
Oct. 13th	Mahsa Faizrahnemoon Simon Fraser University	Scheduling of a Production Line at SKF via Integer Programming Abstract: We describe a project to find the required sizes of the buffers in one of the future roller production channels in SKFs factory in Gothenburg. An integer linear programming model for finding the best schedule for the channel is developed. The model minimizes the sum of the lead times for the batches of rollers in the channel. Thereby, the total time that the rollers are kept in the buffers is minimized, which in turn minimizes the average demand for the volumes of the buffers. Since the model is time-indexed, it represents an approximation of the real scheduling problem. Therefore, post-processing is used to improve the solution obtained. We study a case from the channel at SKF and present results in the form of optimal production schedules and number of pallets of rollers in the buffers during the planning period. A comparison is made between optimal schedules obtained from the time-indexed model with different time step intervals.
Oct. 6th *no seminar*	PIMS Afternoon on the Mathematics of Data and Information	There will be no O.R. Seminar on October 6th, but PIMS is hosting two interesting talks for their Afternoon on the Mathematics of Data and Information, featuring Robert Calderbank and Ingrid Daubechies. These events are located at IRMACS on the Burnaby campus, from 2 p.m. to 4:30 p.m.
Oct. 1st *8:30-4:00*	WCOM Hosted by UBC	Details of the Fall 2016 West Coast Optimization Meeting here.
Sept. 29th *SUR 2990*	Timothy Yusun Ph.D. thesis proposal presentation Senior Supervisor: T. Stephen	Circuit Diameters of Polyhedra and Related Conjectures Abstract: The study of polytope diameters has flourished in recent years due to the insight it provides to the performance of the simplex method for linear programming. In this thesis we consider a variant of the combinatorial diameter of polyhedra called the circuit diameter, where we allow vertex-vertex walks to enter the interior of the polyhedron, using its circuit directions. Klee and Walkup in 1967 show the equivalence of a family of conjectures about the combinatorial diameter - the Hirsch conjecture, the d-step conjecture, and the nonrevisiting conjecture. They disprove these conjectures for unbounded polyhedra in the same article, by constructing a 4-dimensional polyhedron U4 with 8 facets and diameter 5. The conjectures remained open for bounded polytopes until 2010 when a counterexample was discovered by Santos (in 43 dimensions). We will show that U4 is no longer a counterexample for the circuit version of Hirsch - that is, it has a circuit diameter of at most 4, independent of its realization. We aim to explore whether the other known counterexamples satisfy Hirsch as well. It is currently an open question whether the circuit diameter satisfies the Hirsch bound. We also propose to study a reformulation in the circuit setting of this family of conjectures. However, a more nuanced version of simplicity is needed to transfer these claims to circuit diameter. Then we explore empirical studies of simplex-like algorithms that employ circuit diameter.
Sept. 22nd via COCANA (Kelowna)	Yves Lucet UBC Okanagan	Approximate Subdifferential Computation in Computational Convex Analysis Further details available from the COCANA Website.
Sept. 15th	Richard Hoshino Quest University	Solving Quadratic Optimization Problems using the Cauchy-Schwarz Inequality Abstract: Quadratic Programming (QP) is an example of a non-linear programming problem, where the goal is to optimize a quadratic function on $n$ variables, subject to linear constraints on those variables. In this talk, we provide an alternative way of solving one special type of QP problem, via the Cauchy-Schwarz Inequality. We apply the technique to determine the optimal fare prices for a train network that charges its commuters by total travel distance; this will inform the work of a well-known provincial transportation organization that is in the process of conducting a comprehensive review of transit fare policy for the first time in its history.
Sept. 8th via COCANA (Kelowna)	Warren Hare UBC Okanagan	Algorithmic Construction of the Subdifferential from Directional Derivatives Further details available from the COCANA Website.