Date	Speaker	Title and Abstract
August 9th	Zhipeng Lü Department of Computer Science Huazhong University of Science and Technology	Advanced Metaheuristics for Curriculum-Based 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 NP-hard. For these problems, exact algorithms can only be scalable to problems of very limited size. However, metaheuristic algorithms can solve large scale NP-hard 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 NP-hard problems. I will present an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculum-based 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 penalty-guided 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 multiple-server 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 inter-arrival times: exponential, deterministic and Erlang-r distributions, respectively.
June 21st *SUR 2990*	Chen Xu Department of Statistics University of British Columbia	The Sparse MLE for Variable Screening in Ultra-High 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 sparsity-restricted 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 ill-posed 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 l0-norm of the frame coefficients, instead of the commonly used l1-norm. Numerical experiments show that using the l0-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 x-ray 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 d-step 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/re-certificating 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 user-friendly 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 well-known 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 so-called 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 NP-hard to compute, and a straight-forward 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 non-equivalent 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 7-variable 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 NP-hard 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 non-C1Pness. 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 non-C1P matrix. A bound of k+2 was claimed for the smallest odd cycle of a non-C1P 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 zero-one 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(3n) 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 well-known 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 NP-hard 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 by-product our work, we have an approximation algorithm for the maximum edge clique partitioning problem, improving the best known performance ratio for the problem.