2016-2017 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 3040, SFU Surrey.
Please contact Tamon Stephen if you would like to speak.

Date Speaker Title and Abstract
July 6th


*SUR 2710*
Jingbo Tian

M.Sc. thesis defense

Senior Supervisor: A. Punnen
The Multiplicative Assignment Problem

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)

Frank Maurer

Computer Science

University of Calgary
Immersive Analytics

Further details available from the COCANA Website.
Apr. 7th



*SUR 2980*
Olga Zasenko

M.Sc. thesis defense

Senior Supervisor: T. Stephen
Algorithms for Colourful Simplicial Depth and Median in the Plane

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


*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

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


*SUR 2710*
Pooja Pandey

Ph.D. thesis proposal presentation

Senior Supervisor: A. Punnen
The quadratic set covering problems and its variations

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


*SUR 2710*
Brad Woods

Ph.D. thesis proposal presentation

Senior Supervisor: A. Punnen
The quadratic travelling salesman problem: complexity, approximations, and exponential neighbourhoods

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

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

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

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

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


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

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

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.

Archives of the 2006-07, 2007-08, 2008-09, 2009-10 2010-11 2011-12 2013-14 2014-15 and 2015-16 SFU Operations Research Seminars.

Last modified April 5th, 2016.