Date  Speaker  Title and Abstract 
August 9th

Zhipeng Lü
Department of Computer Science Huazhong University of Science and Technology 
Advanced Metaheuristics for CurriculumBased Course Timetabling
Abstract: In operational research, computer science and artificial intelligence, there exist a large number of large scale combinatorial optimization problems that have been proven to be NPhard. For these problems, exact algorithms can only be scalable to problems of very limited size. However, metaheuristic algorithms can solve large scale NPhard problems effectively within a reasonable computational time. In designing a powerful metaheuristic algorithm, the essential point is to obtain a good tradeoff between intensification and diversification and consider the specific problem structure in designing search operators. One case study on the university course timetabling problem is presented to show how to design an effective metaheuristic algorithm for NPhard problems. I will present an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculumbased course timetabling. The proposed algorithm follows a general framework composed of three phases: initialization, intensification and diversification. The initialization phase constructs a feasible initial timetable using a fast greedy heuristic. Then an adaptively combined intensification and diversification phase is used to reduce the number of soft constraint violations while maintaining the satisfaction of hard constraints. The proposed ATS algorithm integrates several distinguished features such as an original double Kempe chains neighborhood structure, a penaltyguided perturbation operator and an adaptive search mechanism. Computational results show the high effectiveness of the proposed ATS algorithm, compared with five reference algorithms as well as the current best known results. This paper also shows an analysis to explain which are the essential ingredients of the ATS algorithm. 
July 19th

Paul Hsing
Luh
Department of Mathematical Sciences National Chengchi University 
Estimating the loss probability under heavy traffic conditions
Abstract: This talk presents a multipleserver queueing model under the assumptions of renewal arrival processes and limited buffer size. An approximation for the loss probability and the asymptotic behavior are studied under the heavy traffic conditions. We present an asymptotic analysis of the loss probability when both the arrival rate and number of servers approach infinity. In illustrative examples, the loss probabilities are estimated with heavy traffic under three common distributions of interarrival times: exponential, deterministic and Erlangr distributions, respectively. 
June 21st
*SUR 2990* 
Chen Xu
Department of Statistics University of British Columbia 
The Sparse MLE for Variable Screening in UltraHigh Dimensional Feature
Space
Abstract: Feature selection is fundamental for modeling the high dimensional data, where the number of features can be huge or even larger than the sample size. Reducing the dimension of feature space is essential in such analysis. Motivated from the seminal theory of sure independence screening (SIS; Fan and Lv (2008)), we investigate another screening method via the sparsityrestricted maximum likelihood estimator to remove most irrelevant features before the formal selection. Compared with the SIS, which screens features based on the marginal correlations, the new method accounts for more joint effects between the covariates and thus can be more reliable in applications. We establish the consistency of proposed method in the context of (ultra) high dimensional generalized linear models and further illustrate its decent performances through numerical examples. 
June 4th
3:30 
Bruce Shepherd
Department of Mathematics and Statistics McGill University 
On combinatorial optimization problems with side constraints
Abstract: We describe several network flow and network design problems where recent changes in technology required strengthening the notion of "feasibility". In each case, we try to assess the impact or "cost" of adding the new constraint. Some models we consider include resilient, unsplittable and confluent flows. 
June 4th
**10:30** 
Bin Dong
Department of Mathematics University of Arizona 
Sparse Approximation by Wavelet Frames and Applications
Abstract: Wavelet frames are known to be able to sparsely approximate piecewise smooth functions, which has recently been used for solving illposed linear inverse problems such as image restoration and computed tomography. In the first half of this talk, I will start with a brief review of wavelet frame based models and their connections to variational models. Then I will present a model (as well as some fast algorithms) that penalizes the l_{0}norm of the frame coefficients, instead of the commonly used l_{1}norm. Numerical experiments show that using the l_{0}norm has advantages for some specific type of images. The second half of the talk is focused on the applications of wavelet frame based models to xray based CT image reconstruction. 
March 29th

Yuriy Zinchenko
Department of Mathematics and Statistics University of Calgary 
Polytopes and Arrangements: Diameter and Curvature
Abstract: We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature, and a continuous analogue of a dstep equivalence result for the diameter of a polytope. Potential extensions of this work will be highlighted. Based in part on joint work with Antoine Deza (McMaster) and Tamas Terlaky (Lehigh). 
February 23rd

Roger Yu
Department of Mathematics and Statistics Thompson Rivers University 
Scheduling Pilot Training Problem
Abstract: In this talk, we will report on an Engage Grant Project "Scheduling Pilot Training Problem" conducted with three TRU students. This is joint project with Pelesys Learning System Inc., a Richmond company. The project is to build a system to assist in the scheduling of training/recertificating for airline pilots. After building multiple mathematical models for this purpose, we created Recurrent Training Model 5, a model that is capable of assigning pilots, instructors, rooms, and time slots to the courses involved in the training. This model has been implemented in the optimization software called AIMMS, and in addition to simply providing a schedule for training also allows data to be imported from a database for ease of data entry and utilizes search heuristic (e.g., tabu) to assist in generating a good schedule, with all its features easily accessible from a userfriendly GUI. 
February 9th

Daniel Karapetyan
Department of Mathematics Simon Fraser University 
Efficient Local Search Algorithms for Known and New
Neighborhoods for the Generalized Traveling Salesman Problem
Abstract: The Generalized Traveling Salesman Problem (GTSP) is a wellknown combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into socalled clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically. This is joint work with Gregory Gutin. 
January 26th

Joe Qranfal
Department of Mathematics Simon Fraser University 
A Fast Computational Algorithm for Segmentation of Noisy Medical Images
Abstract: We show here that the implementation a Markov random fields image segmentation algorithm works well for the purpose of denoising and segmenting medical images. One of the main contributions here is the ability for a user to manipulate online the image so as to achieve clear delineation of objects of interest in the image. This is made possible by the efficiency of the implementation. Results are presented for images that are generated by Single Photon Emission Computed Tomography and Magnetic Resonance Imaging. The results show that the method presented is effective at denoising medical images as well as segmenting tissue types, organs, lesions, and other features within medical images. We advocate that this method should be considered as part of the medical imaging toolbox. 
January 20th
*Friday, 2:30 p.m.* *SUR 3120* 
Michael Monagan
Department of Mathematics Simon Fraser University 
Computing Tutte polynomials
Abstract: The Tutte polynomial from graph theory is the most general graph invariant that can be computed by edge deletion and contraction. Because it includes the Chromatic polyomial as a special case, it is NPhard to compute, and a straightforward implementation of the edge deletion and contraction algorithm, like the one in Mathematica, takes O( 1.6^(n+m) ) time where n=V and m=E. In recent work, Haggard, Pearce and Royle studied edge selection heuristics and used the graph normal form in Brendan McKay's "nauty" package to speed up the edge deletion contraction algorithm. They succeeded in computing the Tutte polyomial of the truncated icosahedron graph, a graph with 32 vertices and 90 edges, in one week on 150 computers. [ See here. ] In this talk we will present a new edge selection heuristic which we have implemented in vanilla Maple. It dramatically improves the computation time and surprisingly, computes the Tutte polynomial of some generalized Petersen graphs in polynomial time. We will present also the connection of the Tutte polynomial with the reliability polynomial from network theory which is what motivated us to consider computing Tutte polynomials and we comment about what facilities in Maple aided the implementation. Our examples are presented using Maple's GraphTheory package which a group of students and faculty at SFU developed. No prior knowledge of Tutte polynomials is assumed. 
December 6th
*1:30 p.m.* 
Timothy Yusun
Department of Mathematics Simon Fraser University 
Dedekind Numbers and Related Sequences
M.Sc. thesis defence Abstract: This thesis considers Dedekind numbers, where the nth Dedekind number D(n) is defined as the number of monotone Boolean functions (MBFs) on n variables, and R(n), which counts nonequivalent MBFs. The values of D(n) and R(n) are known for up to n = 8 and n = 6, respectively; in this thesis we propose a strategy to compute R(7) by considering profile vectors of monotone Boolean functions. The profile of an MBF is a vector that encodes the number of minimal terms it has with 1;2; : : : ;n elements. The computation is accomplished by first generating all profile vectors of 7variable MBFs, and then counting the functions that satisfy each one by building up from scratch and taking disjunctions one by one. As a consequence of this result, we will be able to extend some sequences on the Online Encyclopedia of Integer Sequences, notably R(n) up to n = 7, using only modest computational resources. 
December 6th
*11:00 a.m.* 
Sara Taghipour
Department of Mathematics Simon Fraser University 
Quadratic Balanced Optimization Problems
M.Sc. thesis defence Abstract: We introduce the Quadratic Balanced Optimization Problem (QBOP) and study its complexity. QBOP is NPhard even for very special cases such as Quadratic Balanced Knapsack Problem (QBKP) and Quadratic Balanced Assignment Problem (QBAP). Several general purpose algorithms are proposed and tested on the special cases of QBKP and QBAP. Polynomial solvable special cases are also identified. 
November 24th
*12:30 p.m.* 
Mehrnoush Malekesmaeili
Department of Mathematics Simon Fraser University 
On Certificates that a Matrix does not have the Consecutive
Ones Property
M.Sc. thesis defence Abstract: A binary matrix has the consecutive ones property (C1P) if there exists a permutation of its columns which makes the 1s consecutive in every row. The C1P has many applications which range from computational biology to optimization. We give an overview of the C1P and its connections to other related problems. The main contribution of this thesis is about certificates of nonC1Pness. The notion of incompatibility graph of a binary matrix was introduced in [McConnell, SODA 2004] where it is shown that odd cycles of this graph provide a certificate for a nonC1P matrix. A bound of k+2 was claimed for the smallest odd cycle of a nonC1P matrix with k columns. We show that this result can be obtained directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. Furthermore we empirically study the minimal conflicting set certificate on synthetic data. 
November 3rd

Piyashat Sripratak
Department of Mathematics Simon Fraser University 
Facets of the Boolean Quadric Polytope
Abstract: In this talk, we introduce a linearization of the unconstrained quadratic zeroone program in n variables. We denote the convex hull of solutions the Boolean quadratic polytope. Based on Manfred Padberg's work; The Boolean Quadric Polytope: some Characteristics, Facets and Relatives, we show all trivial facets and three families of facets of the polytope. There are O(3^{n}) facets in these four types. At the end of the talk, we give some special cases and a generalization that are polynomially solvable or all facets are describable. 
October 20th
*1:30 p.m.* 
Annie Zhang
Department of Mathematics Simon Fraser University 
Quadratic Bottleneck Problems: Algorithms, Complexity and Related Topics
Ph.D. thesis defence Abstract: In this thesis we study the quadratic bottleneck combinatorial optimization problem (QBCOP) which generalizes the wellknown class of bottleneck problems. The solvability of QBCOP is linked to that of the linear combinatorial optimization problems with conflict constraints. Various properties and algorithms for these classes of problems are developed and special cases of spanning trees, knapsack type problems, and assignment variations are explored. These problems are shown to be strongly NPhard even on very special graphs. We then identify polynomially solvable special cases and also develop heuristics algorithms. Experimental results are reported for all the heuristics we developed. As a byproduct our work, we have an approximation algorithm for the maximum edge clique partitioning problem, improving the best known performance ratio for the problem. 