Operations Research Seminars

Warren Hare,

UBC-Okanagan

Title & Abstract: TBA

Postponed due to COVID-19 pandemic.

Title & Abstract: TBA

Postponed due to COVID-19 pandemic.

Linearized Robust Counterparts of Two-stage Robust Optimization Problem

In many decision-making problems, some decisions must be made here-and-now before the realization of actual data. However, other decisions are of a wait-and-see type, i.e., they can wait until uncertain data is revealed. It is a computationally challenging task to make wait-and-see decisions fully adaptable while the problem remains computationally tractable. We propose a new tractable method that can be applied to a class of two-stage optimization problems under uncertainty. The method mainly relies on a linearization scheme employed in bilinear optimization problems, therefore it gives rise to the “linearized robust counterpart” models. We identify a close relation between this linearized robust counterpart model and the popular affinely adjustable robust counterpart model. We also describe methods of modifying both types of models to make these approximations less conservative. These methods are heavily inspired by the use of valid linear and conic inequality in the linearization process for bilinear models. We finally demonstrate the potential of our method in operations management applications.

13 February

Special room:

ASB 10940

CCA 2D: a computational convex analysis library for bivariate functions

Critical to any optimization problem, duality can be expressed using Fenchel's duality Theorem, which is formulated using the convex conjugate. Computing such a conjugate and other fundamental convex transforms is the goal of computational convex analysis (CCA). In this talk, we will look at the upcoming public release of CCA 2D, a numerical library for computing with bivariate piecewise linear-quadratic functions. We will present optimal data structures for convexity checking, conjugacy, and addition. How best to convert between the different function representations will also be explained. The talk will finish with remaining challenges and open problems.

Game Theoretic Models of Clear Versus Plain Speech

Clear speech is a vocal style used when a speaker wishes to improve comprehension, usually due to the presence of external noise, less-than-optimal listening conditions, or when they are simply instructed to speak clearly. Clear speech has many distinguishing features, including increased duration, pitch, and amplitude, as well as the exaggeration of articulatory movement.  We use game theory to model the phenomenon of clear speech, and make predictions of how it changes under different circumstances. We view the behaviours of speakers and hearers when communicating as optimal strategies in communication games. When comprehension becomes more difficult, the
optimal strategies of the games shift so that speakers exert more energy to improve the likelihood of accurate communication. We discuss how our models correspond to experimental observations and see what predictions are made for future experiments. This is joint work with Jie Jian, Keith Leung, and Yue Wang, Allard Jongman, and Joan Sereno.

Optimization of expected returns per unit risk

Portfolio optimization is the process of choosing the best portfolio (optimal investment decision across a set of financial instruments or assets) out of the possible set of portfolios. The optimal portfolio should maximize the expected return and/or minimize the financial risk. Investors want to maximize their returns, but higher expected
return usually means taking on more risk. So, investors are faced with a trade-off between risk and expected return. Researchers have considered this problem from two perspectives, one is to maximize a portfolio's expected return for any given amount of risk and other is to minimize a portfolio's risk for a given return. So, one out of return or risk has to keep fixed while optimizing the other. We introduce a fractional model with returns over risk ratio that keeps the expected return and risk flexible simultaneously. The expected risk is measured by using the widely used risk measure conditional value at risk (CVaR). The introduced model provides us with the optimal investment portfolio for which the expected returns for per unit of risk will be maximum.

Large-Scale Optimization: Algorithms and Applications

This talk presents my recent work on algorithms and software implementations to solve nonlinear stochastic programming problems to local and global optimality. Our algorithms exploit emerging high-performance computing hardware (e.g., multi-core CPUs, GPUs, and computing clusters) to achieve computational scalability. We are currently using our capabilities to address engineering and scientific questions that arise in diverse application domains including control of wind turbines, power management in large networks, and parameter inference in microbial community models. The problems that we are addressing are of unprecedented complexity and defy the state-of-the-art. For example, the problem of designing a control system for wind turbines is a nonlinear programming problem (NLP) with 7.5 million variables that takes days to solve with existing solvers.
We have solved this problem in less than 1.3 hours using our parallel solvers.

Random Tessellation Forests

Space partitioning methods such as random forests and the Mondrian process are powerful machine learning methods for multi-dimensional and relational data, and are based on recursively cutting a domain. The flexibility of these methods is often limited by the requirement that the cuts be axis aligned. The Ostomachion process and the self-consistent binary space partitioning-tree process were recently introduced as generalizations of the Mondrian process for space partitioning with non-axis aligned cuts in the two dimensional plane. Motivated by the need for a multi-dimensional partitioning tree with non-axis aligned cuts, we propose the Random Tessellation Process (RTP), a framework that includes the Mondrian process and the binary space partitioning-tree process as special cases. We derive a sequential Monte Carlo algorithm for inference, and provide random forest methods. Our process is self-consistent and can relax axis-aligned constraints, allowing complex inter-dimensional dependence to be captured. We present a simulation study, and analyse gene expression data of brain tissue, showing improved accuracies over other methods.

Mathematical Foundation of Blockchain Technology

Blockchain technology has recently received much attention. In addition to serving as a digital platform for Bitcoin and other cryptocurrencies, it has the potential to transform various industries including finance, healthcare, logistics, and public administration. Despite its great potential, blockchain technology is still in an early stage and is sometimes misunderstood by the general public. In this talk, we will explain some mathematical foundation of this emerging technology, with a particular focus on the mathematical modelling and analysis of Bitcoin. This talk is self-contained and no background in Bitcoin and blockchains will be assumed.
This seminar will be streamed from UBC-O

Bayes-Adaptive Treatment Plans: The Case of Chronic Kidney Disease

We consider the problem of designing ongoing treatment plans for a population with heterogeneity in disease progression and response to medical interventions. We create a model that partially learns the patient type by monitoring the patient health over time and updates a patient's treatment plan accordingly. We formulate the problem as a multivariate state-space, partially observable Markov decision process (POMDP) and provide structural properties of the value function, as well as the optimal policy. We extend this modeling framework to a general class of treatment initiation problems where there is a stochastic lead-time before a treatment becomes available or effective. As a case study, we develop a data-driven, decision-analytic model to study the optimal timing of vascular access surgery for patients with progressive chronic kidney disease, and we establish policies that consider a patient's rate of disease progression in addition to the kidney health state. To circumvent the curse of dimensionality of the POMDP, we develop several approximate policies and evaluate them against a lower bound. Through a numerical study and several sensitivity analyses, we establish that our model-based recommendations perform well, and we provide further policy insights that sharpen existing guidelines.

On the gap between theory and practice in deep learning

Deep learning (DL) is transforming whole industries as complicated decision-making processes are being automated by neural networks trained on real-world data. Yet as these tools are increasingly being applied to critical problems in medicine, science, and engineering, many important questions about their stability, reliability, and approximation capabilities remain. Such questions include: how many data points are sufficient to train a neural network on simple approximation tasks and how robust are these trained architectures to unknown sources of noise? Numerous studies have demonstrated that neural network models trained on image classification tasks are vulnerable to misclassification when provided images corrupted by so-called adversarial perturbations of the data, a special form of additive noise designed by exploiting the trained model s own weights. These observations point to an inherent instability, either in the training process or the architectures themselves. In this work we seek to quantify the approximation capabilities of deep neural networks (DNNs), the core architectures driving much of the recent successes of DL. Recently published theoretical results on approximation with DNNs show that these architectures allow for the same convergence rates as best-in-class schemes, including h,p-adaptive finite element approximations, in norms relevant to PDE problems. Indeed, our own analysis confirms that DNNs afford the same sample complexity estimates as compressed sensing (CS) on sparse polynomial approximation problems. To explore the approximation capabilities of DNNs, we present numerical experiments on a series of simple tests in high-dimensional function approximation, with comparisons to results achieved with CS on the same problems. In contrast to the theory, our numerical experiments show that current methods of training often yield DNNs which fail to achieve the theoretical error estimates, exposing a critical disconnect between the generalization potential of DNNs predicted by the theory and real-world performance of trained DNNs.

August 2nd *Friday*
*1:30*
*Lib 2020* 
(Burnaby)

Michelle Spencer
M.Sc. thesis defence
Senior Supervisor: T. Stephen

Formulating Quadratic Traveling Salesman Problems for Computation 

Abstract:  The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem. Adding costs associated with pairs of edges included in a tour gives the Quadratic Traveling Salesman Problem (QTSP). This increases modeling power by allowing, for example, the inclusion of transfer costs between edges. We consider a general version of this problem, where costs are attached to all pairs of edges.
We give a brief history of computational solvers, especially in relation to the TSP. For the QTSP, we consider modifying the structure of the quadratic cost input and linearizing the quadratic objective function, with detail on how to generate the modifications and linearizations. We study the impact of these structures on computational efficiency for randomly generated instances, using the Gurobi solver. We find that by making the quadratic cost matrix negative semidefinite, we improve solve times, and that solving the problem as a quadratic minimization problem outperforms linearization approaches.

Math 402W Operations Research Clinic project presentation 

Coordinating Primary Care Operating Hours to Reduce Acute Care Visits 

• Selecting Optimal Tolling Levels
• Location and Routing of Community Mailboxes
• Optimal Locations of Telecommunication Equipment

July 14

**SUR 3010**

Application of computational geometry to network location problems
Binay Bhattacharya, Computing Science, SFU

Abstract:   One of the objectives of this talk is to show that the tools from computational geometry can be effectively applied to solve location problems in networks.  In particular we show that the p-center problem in general networks can be transformed to a geometric problem known as Klee's measure problem (KMP).  When the underlying network is a partial k-tree (k-fixed), we showed that the p-center problem could be efficiently solved by transforming the problem to a range search problem.

June 24

**Friday**

The Generalized Quadratic Assignment Problem (GQAP)
Farzana Sultana, SFU

Abstract:  The Generalized Quadratic Assignment Problem (GQAP) covers a broad class of problems that involve the minimization of a total pair-wise interaction cost among M equipments, tasks or other entities and where placement of these entities into N possible destinations is dependent upon existing resourc capacities. These problems arise naturally in yard management, where containers are to be located in the storage areas with limited capacity, and in distributed computing where processing tasks are to be assigned to processors with limited computing resources. This problem generalizes the well-known quadratic assignment problem (QAP), one of the most difficult problems in the combinatorial optimization field. Previous studies on the GQAP are relatively limited. The GQAP is NP-hard, and it is NP-hard to approximate.

June 6

**Monday, @ 2 p.m.

SUR 3290**

Hybrid Heuristics for Routing of Barge Container Ships
Tatjana Davidović, Serbian Academy of Sciences and Arts

Abstract:  The optimization of inland transport routes of barge container ships with the objective to maximize the profit of a  shipping company is investigated. This problem consists of determining the upstream and downstream calling sequence and the number of loaded and empty containers transported between any two ports. Combinatorial and MIP formulations will be presented. The problem is initially approached by improved variants of existing MIP heuristics: Local Branching, Variable Neighborhood Branching, and Variable Neighborhood Decomposition Search. A new heuristic is then presented. The heuristic is based on the combination of the two formulations and aims to generate better quality solutions of the considered problem. The proposed mixed-formulation Local Search (LS) represents a good basis for the implementation of LS-based meta-Heuristic methods and a Multi-start Local Search within this framework will be presented. The comparison of the proposed approach with the state-of-the-art MIP-based heuristics will be reported.  

This research has been done with V. Maras, J. Lazić and N. Mladenović.

April 21

A Certifying Algorithm for the Consecutive Ones Property
Mehrnoush Malekesmaeili, SFU

Abstract: This is a presentation of the results in R. McConnell's paper on "A Certifying Algorithm for the Consecutive Ones Property" (proceedings of SODA 2004).

March 31

Schur Complement-Based Preconditioners for Saddle-Point Linear Systems
Chen Greif, Computer Science, UBC

Abstract:  Block preconditioners play a prominent role in the numerical solution of saddle-point linear systems arising from discretization of partial differential equations and large-scale constrained optimization problems. In this talk I will provide an overview of preconditioning approaches based on primal and dual Schur complements. A key for their efficiency is the ability to characterize the spectra of the underlying continuous operators. A challenge of particular interest is how to deal with situations in which the (1,1) block of the saddle-point matrix is nearly singular. We show that in such situations, the primal Schur  complement related to the augmented Lagrangian methodology can be quite effective. The analytical results are complemented by numerical examples.

February 24

Santos' counterexamples to the Hirsch conjecture and prismatoids
Tamon Stephen, SFU

Abstract:  In this talk we describe Santos' recent construction of counterexamples to the famous conjecture of Hirsch (1957): that a d-dimensional polytope with n facets has diameter at most n-d.� The construction highlights a particular 5-dimensional "prismatoid" polytope. In joint work with Hugh Thomas, we give a simple proof that there is no analogous 4-dimensional  prismatoid.

February 10

Practical Methods for Computing Sparse or Low-Rank Solutions
Zhaosong Lu, SFU

Abstract:  Nowadays there are numerous emerging applications in science and engineering concerning about sparse or low-rank solution such as compressed sensing, image recovery and dimension reduction. In this talk, we propose some practical methods for computing sparse or low-rank solutions. In particular, we study a novel first-order augmented Lagrangian (AL) method for  solving a class of nonsmooth constrained optimization problems which include l₁-norm and nuclear-norm regularized problems as special cases. The global convergence of this method is established. We also develop two first-order methods for solving the associated AL subproblems and establish their global and local convergence.

In addition, we propose penalty decomposition methods for solving l₀-norm and rank minimization problems. Under some  suitable assumptions, we show that each accumulation point is a stationary point of an equivalent smooth optimization problem. Finally, we demonstrate the computational performance of these methods by applying them to sparse principal component analysis and sparse logistic regression.

January 20

Travelling Salesman Problems with Time Windows and Applications
Sara Taghipour, SFU

Abstract:  The traveling salesman problem with time windows(TSPTW) is an instance of TSP with an extra constraint of visiting each city in a certain time interval.�

A special case of this problem will be discussed.�� Small instances are solved with Cplex, while a Heuristic method is proposed for larger instances.

December 3

**Friday, 3 p.m.**

Generalized Travelling Salesman Problems on Halin Graphs
Brad Woods, SFU

M.Sc. thesis defence (senior supervisor: Abraham Punnen).

December 3

**Friday, 1 p.m.**

Algorithms and Theoretical Topics on Selected Combinatorial Optimization Problems
Arman Kaveh, SFU

M.Sc. thesis defence (senior supervisor: Abraham Punnen).

November 25

A quadratic kernel for k-Vertex-Deletion r-regular Subgraph
Flavio Guinez, Sauder School of Business, UBC

Abstract:  One way of thinking a vertex cover of a graph, is as a set of vertices which removal leaves an stable set. Also, any stable set can be viewed as a 0-regular graph, and then a natural generalization of Vertex Cover is to ask for a subset of at most k vertices which deletion leaves an r-regular subgraph, where r is some fixed integer. This problem was introduced in by Moser and  Thilikos, and as it is expected, it is NP-hard for each fixed r.

A parameterized problem is said to be Fixed Parameter Tractable (FPT) if there exists a function f and an algorithm that solves the problem in O(f(k)n^q) running time, where k is the parameter, n is the size of the input and q is a constant.  There are several techniques to show that a parameterized problem is FPT, being kernelization one of the most applied. In the case of Vertex Cover, using a classical result of Nemhauser and Trotter we can deduce the existence of a kernel of size 2k, which is the best possible so far. Motivated by this, Moser and Thilikos found an algorithm for the general problem that produces a kernel that is cubic in k for each r>1, but that turns out quadratic in k for r=1. In this talk, we review this technique and see how to construct a kernel that is quadratic in k for each r>0.

This is based on a joint work with Stephan Thomasse.

November 18

No O.R. Seminars: Computational Biology Seminar in Burnaby.

November 4

SOS and SDP relaxations of sensor network localization
Ting Kei Pong, University of Washington

Abstract:  The sensor network localization problem has received much attention in recent years. This problem is NP-hard and  thus various convex relaxation techniques have been applied to approximate it. In this talk, we compare the strength of SDP, ESDP and sparse-SOS relaxations. Like the SDP and ESDP relaxations, we show that zero individual trace for sparse-SOS relaxation also certifies accuracy of sensor position when distance measurements are exact. We show by a counterexample that this condition is no longer sufficient in the presence of distance measurement noise, for all three relaxations.

This is based on joint work with Joao Gouveia and Paul Tseng.

October 21

Parametric Stochastic Programming Models for Call-Center Workforce Scheduling
Yong-Pin Zhou, ISOM, University of Washington

Abstract:  We develop and test an integrated forecasting and stochastic programming approach to workforce management in call centers. We first demonstrate that parametric forecasts can be used to drive stochastic programs whose results are stable with relatively small numbers of scenarios. We then extend our approach to include forecast updates and two-stage stochastic programs with recourse. We use experiments with two large sets of call-center data to explore the importance of the use of scenarios and the use of recourse actions.

This is joint work with N. Gans, H. Shen, N. Korolev, A. McCord, and H. Ristock.

October 7

Recognizing Graph Properties Through Polynomial Ideals
Mohamed Omar, University of California - Davis

Abstract:  In the work of M. Laurent, J. Lasserre; P. Parrilo, Y.Nesterov, and others, optimization problems which are modeled by zero-dimensional radical ideals have been shown to have a finite sequence of semidefinite programs that converge to an optimal solution. This has important implications for combinatorial optimization as it allows for a paradigm to solve many problems in polynomial time.  An example is integer optimization over the assignment polytope.

In this talk I will give an overview of this theory and show applications to the study of special subsets of the assignment polytope. As a nice application I will discuss consequences for the well-known automorphism and isomorphism problem for graphs.

This is joint work with Jesus De Loera, Christopher Hillar, and Peter N. Malkin.

September 23 and 30

No O.R. Seminars: Computational Biology Seminars in Burnaby.

August 18

*Wednesday*

Analysis of bandwidth allocation with elastic demand on networks under budget constraints
Hsing Paul Luh, National Chengchi University

Abstract:  This paper considers the problem of bandwidth allocation on end-to-end communication networks with multi-class traffic, where bandwidth is determined optimally under the budget and network constraints. We derive the blocking probabilities with respect to bandwidth, traffic demand and the available number of end-to-end paths based on Erlang loss formula for all service classes.  

Depending upon the blocking probability, the paper presents different performance metrics, such as budget ratio, utilization level and bandwidth elasticity of blocking. Monotonicity and convexity of blocking probabilities with different parameters, such as allocated bandwidth, traffic demand and the number of end-to-end paths are also discussed.

This is joint work with Chia-Hung Wang.

April 22

*SUR 15-300*

Phylogeny-based Analysis of Gene Clusters
Roland Wittler, Simon Fraser University and University of Bielefeld

Abstract:  The order of genes in genomes provides extensive information. In comparative genomics, differences or similarities of gene orders are determined to predict functional relations of genes or phylogenetic relations of genomes. For this purpose, various combinatorial models can be used to identify gene clusters � groups of genes that are co-located in a set of genomified approach to model gene clusters and define the problem of labeling the inner nodes of a given phylogenetic tree with sets of gene clusters. Our optimization criterion in this context combines two properties:

(1) Parsimony, i.e. the number of gains and losses of gene clusters has to be minimal. This aim can be approached using well known methods, like Fitch-Hartigan.

(2) Consistency, i.e. for each ancestral node, there must exist at least one potential gene order that contains all the reconstructed clusters.

Verifying this property is far from being trivial. We give an overview of already known and our new results for solving the "consistency problem" for different gene cluster models. Our findings range from a simple and efficient solution for adjacencies to NP-completeness for other models.� We developed an oracle-based algorithm to reconstruct optimal labeling and finally show results on both simulated and real data.

April 15

The Quickest Flow Problem
Alex Goussiatiner, Simon Fraser University and Modern Port Technologies

Abstract:  We discuss the paper of Burkard, Dlaska and Klinz on the quickest flow problem.

March 25

Data-Driven Inventory Management
Woonghee Tim Huh, University of British Columbia

Abstract:  We consider inventory planning problems where the distribution of demand distribution is not available a priori, and lost sales are not observable.  We take a non-parametric approach, and propose adaptive algorithms that generate a sequence of ordering decisions over time, where the decision in each period depends only on historical sales data.� We show that our adaptive algorithms converge to the optimal solution, and establish the convergence rate.�  Our results are based on recent developments in on-line convex optimization.

March 18

Sparse topology selection in graphical models of time series
Lieven Vandenberghe, University of California at Los Angeles

Abstract:  Graphical models give a graph representation of conditional independence relations between random variables.� Estimating the model from observed data therefore generally includes the selection of the graph topology as well as the parameters in the model.  In a Gaussian graphical model, the topology of the graph specifies the sparsity pattern of the inverse covariance matrix, and several topology selection methods based on convex optimization and 1-norm regularization have been proposed recently.  In this talk we consider an extension to graphical models of autoregressive Gaussian time series.� We discuss the problem of maximum likelihood estimation of autoregressive models with conditional independence constraints, and convex techniques for topology selection via nonsmooth regularization.

March 9

**Tuesday**

On Methods for Solving Nonlinear Semidefinite Optimization Problems
Jie Sun, National University of Singapore

Abstract:  The nonlinear semidefinite optimization problem arises from applications in system control, structural design,  financial management, and other fields.  However, much work is yet to be done to effectively solve this problem. We introduce some new theoretical and algorithmic development in this field. In particular, we discuss first and second-order algorithms that appear to be promising, which include the alternating direction method, the augmented Lagrangian method, and the smoothing Newton method.� Convergence theorems are presented and preliminary numerical results are reported.

January 8

**Friday, 12:30**

The Bottleneck Traveling Salesman Problem and Some Variations
John LaRusic, Simon Fraser University

M.Sc. Thesis defense (senior supervisor: Abraham Punnen)

December 3

**Thursday, 11:30**

First-Order Methods for Nuclear Norm Minimization and its Applications
Hua Zheng, Simon Fraser University

M.Sc. Thesis defense (senior supervisor: Zhaosong Lu)

November 16

SUR 14-400
and
IRMACS 10901

Gene trees and species trees: parsimony problems
Cedric Chauve, Simon Fraser University

Abstract:  A gene family is a set of genes, present in the genomes of several genomes, possibly in multiple occurrences in some genomes, that all originates from a single ancestral gene. A gene tree is a binary tree that describes evolutionary relationships between the genes of a same family, in terms of three kinds of events: speciations, duplications and losses.� Phylogenomics aims at inferring, from a set of gene trees, a species tree.� Here we consider the following NP-complete optimization problem: infer the species tree that minimizes the number of gene duplications. I will present two results:

- a description of tractable sets of gene trees (work with J.-P. Doyon and � N. El-Mabrouk, Universite de Montreal)
- approximation algorithms for computing a parsimonious first speciation, � based on edge-cut problems in graphs and hypergraphs (work with � A. Ouangraoua and K. Swenson, Universite du Quebec a Montreal)

November 2

SUR 14-400
and
IRMACS 10901

Introduction to multiple objective programming and simplex method for solving bi-objective programming
Sara Taghipour, Simon Fraser University

Abstract:  In this seminar, main definitions and theorems of multiple objective programming (a linear programming consisting of several objective functions) will be mentioned. Also, solving bi-objective programming will be discussed by extending simplex method for solving these problems. (We assume familiarity with simplex method.)

October 26

SUR 14-400
and
IRMACS 10900

Recent progress in the application of semidefinite programming to discrete optimization
Miguel Anjos, University of Waterloo

Abstract:  The max-cut algorithm of Goemans and Williamson is 15 years old in 2009, and its impact in the area of semidefinite programming has been remarkable. In this talk, I will survey some of the main modelling and algorithmic developments since 1994 in the application of semidefinite programming to discrete optimization problems. I will also highlight promising directions for research in this area.�

October 5

Design in Inverse Problems
Eldad Haber, University of British Columbia

Abstract:  While there was much attention given to solving inverse problems there is a gap in the question of design, that is, the design of experiments for ill-posed problems and the design of regularization functionals.

In this talk we will present a framework to attack this problem. We show that it leads to a stochastic bilevel optimization problem and suggest algorithms for its solution.�

September 16

*Wednesday*

**3:30**

July 27

**2:30**

*14-400*

Combinatorial optimization problems for genome rearrangement phylogeny
Eric Tannier, LBBE, Universit� Claude Bernard Lyon 1

Abstract: TBA

April 6

Extending Lovasz's Theta Body of a Graph to all Real Varieties
Rekha Thomas, Department of Mathematics, University of Washington

Abstract:  The theta body of a graph, constructed by Lovasz about 30 years ago, is one of the first examples of SDP approximation in discrete optimization. This body has a not-so-well-known definition in terms of sums of squares polynomials that appears in papers by Lovasz in the 1990s. Using this definition and a question he raises, we define a hierarchy of theta bodies for any real algebraic variety (real solutions to a polynomial system over the reals). We prove that these theta bodies are SDP relaxations of the convex hull of real varieties and are in fact a version of Lasserre's relaxations. For the max cut problem this hierarchy appears to be new. When the real variety is finite (as is usual in combinatorial optimization), we give a complete characterization of when the first theta body in the hierarchy equals the convex hull of the variety.

Joint work with Joao Gouveia and Pablo Parrilo.

April 2

 *Thursday*

On the Implementation of a Primal-Dual Interior Point Method
Arman Kaveh, SFU

Abstract:  We discuss Mehrotra�s predictor-corrector technique in interior point methods.

March 30

Presolving in Linear Programming
Sareh Nabi-Abdolyousefi, SFU

Abstract:  We discuss Andersen and Andersen�s paper on presolving in linear programming.

March 23

Improving Patient Flow and Resource Utilization in an Ambulatory Clinic Through Simulation Modelling
Vincent Chow, CIHR Team in Operations Research for Improved Cancer Care, B.C. Cancer Agency

Abstract:  In this talk we consider an ambulatory care unit (ACU) in a large cancer centre, where operational and resource utilization challenges led to overcrowding, excessive delays, and concerns regarding safety of critical patient care duties.  We use simulation to analyze the simultaneous impact of operations, scheduling, and resource allocation on patient wait time, clinic overtime, and resource utilization.  The impact of these factors has been studied before, but usually in isolation.  Further, our model considers multiple clinics operating concurrently, and includes the extra burden of training residents and medical students during patient consults.  Through scenario analyses we found that the best outcomes were obtained when not one but multiple changes were implemented simultaneously.  We developed configurations that achieve a reduction of up to 70% in patient wait times and 25% in physical space requirements, with the same appointment volume.  We will present and discuss the key findings of this study and potential extensions to other outpatient services.

March 16

**SUR 4040**

A Redistributed Proximal Bundle Method for Nonconvex Optimization
Warren Hare, IRMACS, SFU

Abstract:  Proximal bundle methods have been shown to be highly successful optimization methods for nonsmooth convex optimization. This naturally leads to the question of whether bundle methods can be extended to work for nonconvex problems. In this talk we review some past (convex) results for proximal bundle methods, and demonstrate a method for extending classic bundle methods to a nonconvex setting.

The method is based on generating cutting planes model not of the objective function (as most bundle methods do) but of a local convexification of the objective function. The convexification parameter is calculated  on the fly,� which allows for both strong convergence results and the ability to inform the user as to what proximal parameters are sufficiently large to ensure a unique proximal point of the model functions. This novel approach is sound from both the primal and dual perspective, which will make it possible to create workable nonconvex algorithms based on nonconvex VU theory.

March 12

**Thursday**

A Newton-CG Augmented Lagrangian Method for Large Scale SDPs
Defeng Sun, Department of Mathematics, National University of Singapore

Abstract:  We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods.  In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems.

Numerical experiments on a variety of large scale SDPs with the matrix dimension n up to 4,110 and the number of equality constraints m up to 2,156,544 show that the proposed method is very efficient.   We are also able to solve the SDP problem fap36 (with n=4,110 and m=1,154,467) in the 7th DIMACS Implementation Challenge much more accurately than in previous attempts.

[This is a joint work with Xin-Yuan Zhao and Kim Chuan Toh at the National University of Singapore]

March 12

**Thursday**

4:30 p.m.

Large-scale convex optimization over matrices for multi-task learning
Paul Tseng, Department of Mathematics, University of Washington

Abstract:  A recently proposed approach to multi-task learning entails minimizing a function of the form:  f(Q,W) = trace(W'Q^-1W) + trace(Q) + ||AW-B||² where Q is an n by n real matrix constrained to be positive definite, and W is an n by m real matrix.  Here A is a p by n real matrix whose columns correspond to biological images, B is a p by m real matrix of measured data, p is the number of data points, m is the number of tasks.  Q^-1 is a (unknown) covariance matrix.��

In an application to Drosophila gene expression pattern analysis, m, n, p can be up to 100, 2000, 3000, so the number of variables is about 2 million.  Worse, the minimum is typically not attained.

We show that this problem can be reduced to a semidefinite program (SDP) that always has an optimal solution.  The SDP is still too large to be solved by general SDP solvers.  By considering the dual, we show that the dual problem reduces to a convex quadratic optimization problem over n by m real matrices and subject to a matrix version of ball constraint.

Moreover, projection onto the "ball" can be done efficiently using singular value decomposition.  An implementation of Nesterov's accelerated gradient projection method finds a sufficiently accurate solution of the original problem in a matter of minutes on most instances.

This is joint work with Ting Kei Pong (Univ. Washington) and Jieping Ye (Arizona State Univ.)

February 23

Metamodel-based Design Optimization (MBDO) in Support of Modern Engineering Design
Gary Wang, School of Engineering Science, SFU

Abstract:  Modern engineering design features computation-intensive analyses and Simulations. Tools such as finite element analysis (FEA), computational fluid dynamics (CFD), are widely used in engineering design applications. 

How to integrate these various computation-intensive tools to support design synthesis and optimization has been a challenging task. This talk will start with an introduction of such a challenge, after which the inadequacy of classic gradient-based optimization methods will be analyzed from the perspective of design support. To tackle the challenge, a promising approach, metamodel- based design optimization (MBDO), will be introduced. Metamodel, literally meaning "model of model," is a simple surrogate of the computation-intensive function, on which further analysis and optimization is performed. One MBDO approach for multi-objective optimization, the Pareto Set Pursuing (PSP) method, will be described in detail. PSP overcomes common difficulties of MBDO approaches, demonstrates high efficiency for multi-objective optimization, and represents an innovative interpretation of optimization. Testing and application of PSP will also be given. Future research topics on MBDO will be highlighted at the end. This talk should be of interests to researchers in complex system identification, sampling, modeling, simulation-based design, and optimization.

February 2

Energy and Quality Optimization in Mobile TV Broadcast Networks
Mohamed Hefeeda, School of Computer Science, SFU

Abstract:  Mobile TV networks enable users to watch their favorite TV shows on small hand-held devices while traveling. Market research forecasts that mobile TV will grow to be a multi-billion dollar industry with several hundred million subscribers in the next few years. In this talk, we will first give a brief overview of mobile TV networks highlighting some of the main research issues in them.   

Then, we will focus on the problem of minimizing the energy consumption of mobile devices while maximizing the visual quality of different TV channels. More specifically, in mobile TV broadcast networks, the base station broadcasts TV channels in bursts such that mobile devices can receive a burst of traffic and then turn off their radio frequency circuits till the next burst in order to save energy. The base station must carefully construct the burst transmission schedule for all TV channels. This is called the burst scheduling problem. We prove that the burst scheduling problem for TV channels with arbitrary bit rates is NP-complete. We then propose a practical simplification of the general problem, which allows TV channels to be classified into multiple classes with bit rates that have power of two increments, e.g., 100, 200, and 400 kbps. Using this practical simplification, we propose an optimal and efficient burst scheduling algorithm. In addition, we propose a near-optimal approximation algorithm to solve the general scheduling problem. We present theoretical analysis, simulation, and actual implementation in a mobile TV testbed to demonstrate the optimality, practicality, and efficiency of the proposed algorithms.

January 26

Transversal structures on triangulations: a combinatorial study and algorithmic applications
Eric Fusy, SFU and UBC

Abstract:  We study the combinatorial properties and algorithmics of planar maps (planar graphs embedded in the plane). The techniques are illustrated on a particular family, namely plane triangulations with no separating triangle (called irreducible).

These triangulations can be endowed with specific edge bicolorations, called transversal structures, which makes it possible to count the triangulations bijectively, generate them at random, encode them and draw them on a grid.  

Simulations indicate that the grid used by the drawing has with high probability a size close to 11n/27 * 11n/27, where n is the number of vertices. As we will see, this can be proved rigorously using tools from bijective combinatorics as well as analytic combinatorics.

January 19

**SUR 4040**

Gr�bner bases of lattices, corner polyhedra, and integer programming
Simon Lo, SFU

Abstract:  We discuss the paper of Sturmfels, Weismantel and Ziegler describing Connections between Gr�bner bases, corner polyhedra and integer progamming.

November 26

Expressing the TSP and Matching Polytopes by Symmetric Linear Programs
John LaRusic, SFU

Abstract:  We discuss Mihalis Yannakakis' famous result that the TSP and matching polytopes cannot be expressed by symmetric LPs of polynomial size.

November 21

**4:30 Friday**

SUR 15-300 & IRMACS 10908

Some analogies between simplex and interior point methods
Antoine Deza, Computing and Software, McMaster University

Abstract:  Linear optimization consists of maximizing, or minimizing, a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms.  While the simplex methods follow an edge path, the interior point methods follow the central path. In this talk we highlight links between the edge and central paths, and between the diameter of a polytope and the largest possible total curvature of the associated central path. We prove continuous analogues of two results of Holt-Klee, and Klee-Walkup. We construct a family of polytopes which attain the conjectured order of the largest total curvature, and we prove that the special case where the number of inequalities is twice the dimension is equivalent to the general case.

This talk is based on joint-works with Tamas Terlaky, Lehigh University and Yuriy Zinchenko, University of Calgary.

November 19

Linear Satisfiability Algorithm for 3CNF Formulas of Certain Signaling Networks
Utz-Uwe Haus, Institute for Math. Optimization, University of Magdeburg

Abstract:  A simple model of signal transduction networks in molecular biology consists of CNF formulas with two and three literals per clause. A necessary condition for correctness of the network model is satisfiability of the formulas. Deciding satisfiability turns out to be NP-complete. However, for a subclass that still is of practical interest, a linear satisfiability algorithm and related characterization of unsatisfiability can be established. The subclass is a special case of so-called closed sums of CNF formulas.  Computational Results on an extensive curated Human T-Cell Model are included.

Joint work with Kathrin Niermann, Klaus Truemper and Robert Weismantel

November 13

**Thursday**

Comparing Two Systems: Beyond Common Random Numbers
Shane Henderson, ORIE, Cornell University

Abstract:  Suppose one is comparing two closely related stochastic systems via simulation.  Common-random numbers (CRN) involves using the same streams of uniform random variables on both systems to sharpen the comparison.  One can view CRN as a special choice of copula that gives the joint distribution on the inputs to both systems. We discuss the possibility of using more general copulae, including simple examples that show how this can outperform CRN.

Joint work with Sam Ehrlichman

November 12

Appointment Scheduling with Discrete Random Durations and Applications
Mehmet Begen, Sauder School School of Business, UBC

Abstract:  We present two papers and give an overview of the existing work.  

In the first paper*, we determine optimal appointment times for a given sequence of jobs (medical procedures) on a single processor (operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random duration given by its discrete probability distribution. A simple condition on the cost rates implies that the objective function is submodular and L-convex. Then there exists an optimal appointment schedule that is integer and can be found in polynomial time. 

The second paper** is also concerned with the same appointment scheduling problem but without assuming the knowledge of the job duration distributions. Instead, information on the duration distributions may be obtained by random sampling. We show that the objective function is convex under a simple condition and characterize its subdifferential, and determine the number of independent samples required to obtain a provably near-optimal solution with high probability.

There are many other challenging and important real-life applications for appointment scheduling including healthcare diagnostic operations (such as CAT scan, MRI) and physician appointments, as well as project scheduling, container vessel and terminal operations, gate and runway scheduling of aircrafts in an airport.

*, ** Joint work with Maurice Queyranne (Sauder School of Business, UBC)
** Joint work with Retsef Levi (Sloan School of Management, MIT)

October 3

**Friday**

Irmacs 10908 & SUR 14-400

Kirchberger's theorem, coloured and multiplied
Imre B�r�ny, R�nyi Institute of the Hungarian Academy of Sciences

September 24

Rational Generating Functions and Integer Programming Games
Chris Ryan, Sauder School School of Business, UBC

Abstract:  We explore the computational complexity of computing pure Nash equilibria for a new class of strategic games called integer programming games with difference of piecewise linear convex payoffs.  Integer programming games are games where players' action sets are integer points inside of polytopes. Using recent results from the study of short rational generating functions for encoding sets of integer points pioneered by Alexander Barvinok, we present efficient algorithms for enumerating all pure Nash equilibria, and other computations of interest, such as the pure price of anarchy, and pure threat point, when the dimension and number of  convex" linear pieces in the payoff functions are fixed. Sequential games where a leader is followed by competing followers (a Stackelberg--Nash setting) are also considered.

(Joint work with Matthias Koeppe and Maurice Queyranne.)

September 3

A robust approach to handle risk constraints in mid and long-term energy planning of hydro-thermal systems
Claudia Sagastiz�bal, Centro de Pesquisas de Energia El�trica, Brazil

Abstract:  We consider the optimal management of a hydro-thermal power system in the mid and long-term.  This is a large-scale multistage stochastic linear program, often solved by combining sampling with dynamic programming, for example by stochastic dual dynamic programming techniques. However, such methodologies are no longer applicable, at least not in a straightforward manner, when the model is set in a risk-averse formulation.  We propose to take into account risk by using a chance-constrained formulation of the energy-planning problem. In particular, for a given confidence level, and having critical minimum reservoirs levels at each time stage, reservoirs can be kept above the critical volume in a probabilistic manner. When the uncertainty in the problem-typically, the natural inflows- is represented by a periodic autoregressive stochastic process, the corresponding  probabilistic constraints can be expressed as Conditional Value-at-Risk constraints and the chance-constrained problem is a linear program. Such linear program can be thought of as a robustified deterministic variant of the original stochastic  programming problem. Several robust adaptive management strategies are then proposed and the methodology is applied to the Brazilian system.

This is joint work with Vincent Guigues.

April 16

*1:30*

Computational Convex Analysis and Applications
Yves Lucet, University of British Columbia, Okanagan

Abstract:  Computational Convex Analysis focuses on the practical computation of fundamental transforms arising in Convex Analysis. Currently two main frameworks exist for such Computer-Aided investigation: fast algorithms based on discretization enhanced with computational geometry algorithms, and the Piecewise Linear-Quadratic framework based on quadratic spline approximation. After recalling the current state of the art, we will illustrate where these algorithms appear in a wide variety of fields: thermodynamics, robot navigation, medical imaging, image processing, and network communications.

April 3

*Thurs. 4:30*

*15-300*

Value, Trading Strategies, Technology, and Financial Investment of Natural Gas Storage Assets
Youyi Feng, SEEM, Chinese University of Hong Kong

Abstract:  By valuing a natural gas storage facility as a portfolio of real options, we study the value, trading strategies, technology, and financial investment of the storage for a risk neutral natural gas marketer to trade gas in an energy commodity exchange (spot market). The storage facility under consideration can either represent a highly deliverable peak load storages or a lowly deliverable base load storages. Its operational flexibilities could be valued by the expected maximum profit earned from seasonal and daily trading. The primary focus is to optimize trading strategy to extract the embedded options value and assess the financial value of a storage contract to gain the whole or partial control of the facility over years.  We show that the optimal trading policy will refill (withdraw) gas only when the market price exceeds (is exceeded by) the convenience yield, an amount of the value to keep gas underground, less (plus) the marginal operating cost. Moreover, we explore the contingency of the optimal gas trading policy on the prediction of the spot prices by characterizing when it is optimal to sell low and buy high and when, on the other hand, it is optimal to buy high and sell higher. Finally, we demonstrate that the analysis can be deployed to value firm storage contract, and related technological deployment and financial investment.

April 2

A Faster and Simpler Approximation for Maximum Multicommodity Flow
John LaRusic, SFU

Abstract:  We discuss the maximum multicommodity flow approximation algorithm Garg and Könemann describe in their paper, "Faster and Simpler Algorithms for Multicommodity Flows and other Fractional Packing Problems" (SIAM J.  Comput. 37 [2007], no. 2).  Their approach is to substitute shortest path computations for min-cost flow computations, which they apply to other related multicommodity flow problems.

March 12

Normal Cones and Nonconvex Optimization
Warren Hare, IRMACS, SFU

Abstract:  In constrained optimization, the normal cone is to the constraint set what derivatives are to the objective function. That is, normal cones provide first order information describing in a limiting sense how the constraint set behaves near the point of interest. Thus normal cones allow researchers to extend the notions and algorithms of unconstrained optimization (min{f (x)}) into a constrained setting (min{f (x) : x in S}). In this talk we discuss the basic definition of a normal cone both for convex and nonconvex constraint sets. We provide illustrative examples, and demonstrate how normal cones provide the tools necessary to develop constraint identification theory for nonconvex optimization problems.

February 27

Recent developments on LQP-based numerical algorithm
Xiaoming Yuan, UBC-Okanagan and Shanghai Jiao Tong University

Abstract:  The talk focuses on the computational aspects of the so-called Logarithmic-quadratics proximal (LQP) method, which was originally proposed by A. Auslender, et al. Some efficient LPQ-based numerical algorithms are presented for solving  nonlinear complementarity problems and structured variational inequalities. These new algorithms are applied to solve some traffic equilibrium problems.

February 13

*Room 15-300*

Primal-dual gradient methods for linear cone programming and applications
Zhaosong Lu, SFU

Abstract:  In this talk, we consider linear cone programming (LCP) problem, and propose general primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss a class of gradient methods suitable for solving these reformulations including Nesterov's smooth method, Nesterov's smooth approximation scheme, and Nemirovski's prox-method. The iteration-complexity bounds of these methods applied to the aforementioned reformulations are derived. We also propose a variant of Nesterov's smooth (VNS) method that has clear advantages over Nesterov's smooth one. We then discuss the VNS method for solving three natural primal-dual convex smooth minimization reformulations of LCP problem. The associated iteration complexity bounds and overall arithmetic operation cost are estimated and compared. Finally, we apply the VNS method to solve MAXCUT, Lovász capacity, and several important large-scale problems arising in compressed sensing that are challenging to simplex and/or interior point methods.

January 23

*Room 15-300*

Fraser Health uses Mathematical Programming to Plan its Inpatient Hospital Network
Pablo Santibanez, B.C. Cancer Agency

Abstract:  Fraser Health (FH), the largest and fastest growing health region in British Columbia, launched in 2005 the Acute Care Capacity Initiative (ACCI) to look forward into the future and identify the major challenges for the region in terms of capacity, from an evidence-based analytical approach.

The ACCI focus was on projecting the population’s need for clinical services over the next 15 years, developing clinical service plans to address that need, and creating service mix/siting configurations for the hospitals in its network of care.

This talk is focused on the clinical service mix/siting phase of the ACCI, with emphasis on the mathematical programming model used in the planning process to develop configuration scenarios for FH’s network of hospitals.

November 28

Local Search with Constraint Propagation and Conflict-Based Heuristics
Arman Kaveh, SFU

Abstract:  We will introduce a class of algorithms referred to as Hybrid Search Methods for solving Constraint Satisfaction problems. There are two major classes of algorithms used in CSP: constructive search and local search. Hybrid search algorithms combine the two methods in an effort to utilize their advantages.

The proposed algorithm is experimented with using the Open Shop Problem and some numerical results are presented.

November 21

November 14

Online Scheduling with Stochastic Methods
John LaRusic, SFU

Abstract:  Online scheduling problems differ from their offline counterparts in that the problem data is not completely available from the beginning but rather revealed during execution.  Generally, this involves new jobs/activities/requests unexpectedly arriving during execution that must now be considered.  In addition to having to make scheduling decisions based upon future uncertainty, time constraints often leave one with little time to make a new decision.  We discuss the stochastic methods proposed by Chang, Givan and Chong (2000) and Bent and Van Hentenryck (2004) for dealing with these issues.

November 8

*Thurs. 4pm*

Advances in portfolio decision analysis
Ahti Salo group, Helsinki University of Technology

Abstract: This seminar includes three presentations on the following subtopics:

- Robust Portfolio Modelling (Juuso Liesiö, Pekka Mild, Ahti Salo)
- Contingent Portfolio Programming (Janne Kettunen, Ahti Salo)
- Rank-Oriented Data Envelopment Analysis (Ahti Salo, Antti Punkka)  

November 1

*Thurs. 4pm*

New Classification Methods for Cancer Diagnosis and Biomarker Discovery
Nabil Belacel, NRC Institute for Information Technology, Moncton, NB

Abstract:  Though many methods already exist for determination of markers and tumor diagnosis using micro-array data, more precise and accurate methods for feature analysis and selection as well as tumor classification are still needed. This talk will present an overview on the application of new approach based on data mining and machine learning tools for tumor classification and for the selection of marker genes.  

October 31

Minimal generating families of parametric discrete and polyhedral sets with applications to survivable network design
Matthias Köppe, Inst. for Mathematical Optimization, University of Magdeburg

Abstract:  We consider the capacitated network design problem under arc-survivability constraints.  We present a new method based on the study of the family of sets of feasible routings for fixed capacities and demands.  It turns out that Minkowski sums play an important role in this setting and arc-survivability is easily modelled using non-linear, Minkowski-additive arc-survivability functionals.  The crucial feature of this framework is that the non-linear survivability constraints can be exactly linearized whenever a finite integral generating set (with respect to Minkowski sums) is known.

We present new algorithms to compute minimal integral generating sets (with respect to Minkowski sums) of families of discrete sets (for use with the model of integral flows) and parameterized polyhedra (for the model of fractional flows).

October 24

Complexity of the simplex method for linear fractional assignment problem
Abraham Punnen, SFU

Abstract:  In this talk we show that the complexity of simplex method for the linear fractional assignment problem (LFAP) is strongly polynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton's method or binary search, no polynomial time bound for the simplex method for LFAP was known.

October 17

Semidefinite liftings for stable set and matching
Tamon Stephen, SFU

Abstract:  This is a survey of the "lift and project" approach to solving integer programs.  We focus on the semi-definite matrix relaxations proposed by Lovász and Schrijver and the examples of finding maximum stable sets and matchings in a graph.

October 10

Packing T-joins
Matt DeVos, SFU

Abstract:  T-joins are a common generalization of st-paths and perfect matchings, and have proved to be an important structure in combinatorial optimization. Numerous classic results in graph theory, for instance Menger's theorem and Konig's theorem, may be viewed as giving optimal packings of T-joins in certain special cases.  Here we present a couple of theorems (joint with Paul Seymour) which give fairly good packings of T-joins in general circumstances.

October 3

Improved bounds for the symmetric rendezvous value on the line
Qiaoming Han, School of Eng. & Management, Nanjing University, visiting SFU

Abstract:  A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best known result (3.9546, 4.3931).  To achieve the improved bounds, we call upon results from absorbing Markov chain theory and mathematical programming theory - particularly fractional quadratic programming and semidefinite programming.  Moreover, we also establish some important properties of this problem, which may be of independent interest and useful for resolving this problem completely. Finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations.

September 19

Modeling and optimization of loan portfolios
Fadil Santosa, IMA, University of Minnesota, visiting SFU

Abstract:  This presentation is a very elementary introduction to credit risk modeling.  We will describe how such a model can be calibrated against data, and how it can then be used to assess risk.  We will also show how to formulate Markowitz type portfolio optimization which minimizes risk for a fixed expected loss.

Spring 2007

April 16

The capacitated max k-cut problem
Ramesh Krishnamurti, School of Computing Science, SFU

Abstract:  We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller that  1-1/k  of the optimal solution value. This improves a previous bound of 1/2 for the max k-cut problem with fixed, though possibly different, sizes of subsets.

April 2

Robust discrete optimization and network flows
Annie Ruonan Zhang, SFU Surrey

Abstract:  In this talk we will discuss the paper Robust discrete optimization and network flows, by Bertimas and Sim. The authors proposed an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable. In particular, when uncertain data appears in both the cost coefficients and the the constraints of an integer programming problem, the robust counterpart will result in a solution with probabilistic bounds on constraint violation; when only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then the robust counterpart will be solved by solving at most n+1 instances of the original problem.  Polynomially solvable cases and approximations will be analyzed. Finally, the paper proposed an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network.

March 26

Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems
Arman Kaveh, SFU Surrey

Abstract:  For every fixed c > 1 and any given n nodes in the plane, we can find a (1 + 1/c) approximation to the optimum TSP tour in O(n (log n)^O(c)) time. The previous best approximation algorithm (due to Christofides) achieves a 3/2 approximation in polynomial time. The problem of whether a polynomial time approximation scheme for Euclidean TSP exists was open prior to the Arora's paper. We will present this TSP polynomial approximation scheme and we will also give similar polynomial approximation schemes for a few other NP-hard Euclidean problems such as Minimum Steiner Tree, k-TSP and k-MST.

March 19

On Goemans's and Williamson's MAXCUT algorithm
Karel Casteel, SFU Surrey

Abstract:  This will be an expository talk on the seminal work of Goemans and Williamson towards using semidefinite programming to develop improved approximation algorithms for combinatorial optimization problems, particularly MAX CUT and 2SAT.  I will introduce/review semidefinite programming and then outline how this can be used to give a polynomial time randomized algorithm which finds a maximum cut with expected value at least 0.87856 times the optimal weight.  Previous to this work, the best known approximation guarantee was only 0.5 + o(n).  We will then examine a similar algorithm for 2SAT.

March 12

Constructing Incremental Sequences in Graphs
Joseph Peters, SFU, School of Computing Science

Abstract:  Given a weighted graph G=(V,E,w), we investigate the problem of constructing a sequence of n=|V| subsets of vertices M_1,...,M_n (called groups) with small diameters, where the diameter of a group is calculated using distances in G.  The constraint on these n groups is that they must be incremental: M_1 is a subset of M_2 ... is a subset of M_n=V.  The cost of a sequence is the maximum ratio between the diameter of each group M_i and the diameter of a group N_i with i vertices and minimum diameter.  This quantity captures the impact of the incremental constraint on the diameters of the groups in a sequence.  We give general bounds on the value of this ratio and we prove that the problem of constructing an optimal incremental sequence cannot be solved approximately in polynomial time with an approximation ratio less than 2 unless P = NP.  Surprisingly, the related eccentricity problem is in P.  We develop an optimal eccentricity algorithm and use it as the basis of a 4-approximation algorithm for the diameter problem.  We show that the analysis of our algorithm is tight.  Joint work with Ralf Klasing, Christian Laforest, and Nicolas Thibault

March 5

Improving solution times in VLSI optimization problems
Warren Hare, IRMACS, SFU

Abstract:  Advances in technology for the manufacturing of integrated circuits have resulted in extremely large, and time consuming, problems on how to lay out components for optimal circuit performance.  The problem of wire layout (or routing) in VLSI design can be written as a large scale integer linear program with upper bound constraints.  Due to the size of these programs, optimization by use of classical methods can be extremely time consuming.  In this talk we will discuss some of the recent techniques and ideas which have been emerging on how to improve the time required to solve these highly structured linear programs.  The majority of the talk will focus on applying novel preprocessing techniques to simplify the problem.  However, if time permits, we will also discuss recent ideas in parameter tuning, and various methods of embedding the upper bound constraints into the constraint matrix in order to make better use of interior point algorithms.

February 19

VLSN search: empirical analysis and theoretical reasoning
Abraham P. Punnen, SFU Surrey

Abstract:  In this talk, we introduced VLSN search algorithms for solving discrete optimization problems. VLSN algorithms are precisely local search schemes using neighborhoods of very large size. We discuss theoretical analysis of algorithms in terms of associated neighborhood size or dominated solutions. Special neighborhoods are introduced that can be searched using matching problems or simpler integer programs. Results of extensive experimental analysis are discussed using the generalized assignment problem and its variations.

February 12

A New Cone Programming Approach for Robust Portfolio Selection
Zhaosong Lu, SFU Surrey

Abstract:  The robust portfolio selection problems have recently been studied by several researchers. In their work, the  ``separable'' uncertainty sets of the problem parameters (e.g.,  mean and covariance of the random asset returns) were considered. These uncertainty sets share two common drawbacks: i) the actual confidence level of the uncertainty set is unknown, and it can be much higher than the desired one; and ii) the uncertainty set is fully or partially box-type. The consequence of these drawbacks is that the resulting robust portfolio can be too conservative and moreover, it is usually highly non-diversified as observed in computational experiments. To combat these drawbacks, we consider a factor model for the random asset returns. For this model, we introduce a ``joint'' ellipsoidal uncertainty set for the model parameters and show that it can be constructed as a confidence region associated with a statistical procedure applied to estimate the model parameters for any desired confidence level. We further show that the robust maximum risk-adjusted return problem with this uncertainty set can be reformulated and solved as a cone programming problem. Some computational experiments are performed to compare the performances of the robust portfolios corresponding to our ``joint'' uncertainty set and Goldfarb and Iyengar's ``separable'' uncertainty set. We observe that our robust portfolio has much better performance than Goldfarb and Iyengar's in terms of  wealth growth rate and transaction cost, and moreover, our robust portfolio is fairly diversified, but Goldfarb and Iyengar's is highly non-diversified.

February 5

Introduction to robust optimization
Annie Ruonan Zhang, SFU Surrey

Fall 2006

December 11

Dynamic SPECT reconstruction using Kalman algorithm
Joseph Qranfal, SFU Burnaby

Abstract:  Single photon emission computed tomography (SPECT) is a nuclear medicine imaging technique that is extensively used for clinical diagnosis. Classical SPECT reconstruction algorithms assume that the activity does not vary in time. This is not always true in practice. For instance, when we study Teboroxime cardiac images, the activity changes in time. Thus arises the need of exploring dynamic SPECT. In this talk, I will explore a Kalman reconstruction approach to estimate the time varying activity. While other methods assume a priori knowledge about the activity behavior, Kalman assumes little. We formulate a state-space model of the problem which we solve using the optimal Kalman filter and smoother. Numerical results are provided.

December 4

Optimization algorithms for dynamic SPECT image reconstruction
Germain Tanoh, SFU Burnaby

Abstract:  Nuclear medicine is a medical specialty that aids diagnosis as well as treatment planning and monitoring by producing noninvasive, diagnostic images using radiopharmaceutical. In dynamic SPECT we study the dynamics of physiological processes and biochemical functions of living organism. One of the problems we face is the reconstruction of time activity curve. Because the emitted activities are time dependent, classical Expectation Maximization method fails to reconstruct a dynamic image. In this talk, I will present new reconstruction algorithms which preserve the shape of the time activity curve for each voxel. The proposed methods take into account information about the dynamic of the activity as a linear inequality constraints.  We consider two classes of reconstruction method. The first class is a interior gradient iterative algorithm based on Bregman generalized projection. The second is a Newton based method and uses a line search to ensure global convergence. Numerical experiments verify the effectiveness of the algorithms.

November 27

Allocating Resources to Control Infectious Diseases  by Margaret L. Bandeau

Karel Casteels, SFU Surrey

November 20

Colourful linear programming
Tamon Stephen, SFU Surrey

Abstract:  We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Barany and Onn with new methods. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence, but we provide extensive numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that an effective method in practice is a proposed multi-update algorithm.

November 13

Seminar cancelled – due to Remembrance Day

November 6

Models for Kidney Allocation  by Stefanos A. Zenois

Randall Pyke, SFU Surrey

November 1 

Optimization and Highly Informative Graph Invariants
Distinguished speaker: Dragos Cvetkovic, University of Belgrade, Serbia

Abstract:  It is known that graph invariants, which contain a great quantity of information on graph structure (for example, spectral invariants), are obtained by solving some extremal problems on graphs. Recently, such highly informative graph invariants are applied in solving optimization problems on graphs (e.g., the travelling salesman problem (TSP)). Using these paradigms, several relations, interconnections and interactions between graph theory and mathematical programming are described. A model of TSP based on semidefinite programming and algebraic connectivity of graphs is described. A class of relaxations of this TSP model is defined and some solution techniques based on this class are proposed. Several examples of graph invariants defined by some kind of optimization tasks are also presented. Using several spectrally based graph invariants we treat the graph isomorphism problem.

October 23

A primal-dual first-order method for cone programs
Zhaosong Lu, SFU Surrey

Abstract:  In this talk, we first review Nesterov's optimal methods for a class of smooth/non-smooth convex programs. A variant of his methods will be proposed. Based on these methods, we propose some primal-dual first-order methods for cone programs. Some preliminary computational results of our methods for randomly generated large-scale linear program and semidefinite program problems are then presented. We finally conclude that our methods are very promising for solving large-scale (dense) cone programs.  Joint work with G. Lan and R. Monteiro, Georgia Tech.

October 16

Supply Chain Management of Blood Banks  by W.P. Pierskalla

Ron Ferguson, IRMACS, SFU

October 2 

The proximal average
Heinz Bauschke, University of British Columbia, Okanagan

Joint works with Yves Lucet (UBC Okanagan) and Mike Trienis (UBC Okanagan)

September 25

Location of health care facilities  by Mark S. Daskin and Latoya K. Dean

Arman Kaveh, SFU Surrey

September 18

Benchmarking using DEA: The case of mental health organizations  by Y.A Ozcan, E. Merwin, K. Lee and J.P. Morrissey

Annie Ruonan Zhang, SFU Surrey

September 11

Capacity planning and management in hospitals  by Linda V. Green

Dan Benvenuti, SFU Surrey

Summer 2006

August 10

Health care delivery: current problems and future challenges

Snezana Mitrovic-Minic, SFU Surrey

August 3

Applying systematic local search to job shop scheduling problems

Lei Duan, School of Computing Science, SFU

July 18

A new approach to interrelated two way clustering of gene expression data

Distinguished Speaker: Prof. B. Chandra, Head

Department of Mathematics, Indian Institute of Technology, Delhi

July 13 

Neighborhood search heuristics

Abraham P. Punnen, SFU Surrey

July 6

An efficient variable neighborhood search for the generalized assignment problem

Snezana Mitrovic-Minic, SFU Surrey

June 29

Using group theory to construct and characterize metaheuristic search neighborhoods by Bruce W. Colleti and J. Wesley Barnes

Sandy Rutherford, IRMACS , SFU

June 8

Controlled pool maintenance for metaheuristics by Peter Greistorfer and Stefan Vos

Lei Duan, School of Computing Science, SFU

June 1 

Logistics management: An opportunity for metaheuristics by Helena R. Lourenco

Arman Kaveh, SFU Surrey

May 25

On the integration of metaheuristic strategies in constrained programming by Mauro Dell’Amico and Andrea Lodi

Annie Ruonan Zhang, SFU Surrey

May 15

Lessons from applying and experimenting with scatter search by Manuel Laguna and Vinicius A. Armentano

Dan Benvenuti, SFU Surrey

May 8

Scatter Search vs. Genetic Algorithms by Rafael Marti, Manuel Laguna and Vicente Campos

Ron Ferguson, IRMACS, SFU

Spring 2006

April 3

Second level local optimization approach to employee timetabling by D. Bokal, G. Fijavz, D. Vodopivec, and S. Pintar

Drago Bokal, University of Ljubljana, Slovenia

March 27

A Very Fast Tabu Search Algorithm for Job Shop Problem – Part 2  by Józef Grabowski and Mieczyslaw Wodecki

Sandy Rutherford, IRMACS, SFU

March 20

Some New Ideas in Tabu Search for Job Shop Scheduling  by Eugeniusz Nowicki and Czeslaw Smutnicki

Lei Duan, School of Computing Science, SFU

March 13

A Tabu Heuristic for the Uncapacitated Facility Location Problem by Minghe Sun

Randall Pyke, SFU Surrey

March 6

Review session

February 27

Tabu Search Heuristics for the Vehicle Routing Problem by Jean-François Cordeau and Gilbert Laporte

Snezana Mitrovic-Minic, SFU Surrey

February 20

Cancelled due to the University Reading Break

February 13

A Very Fast Tabu Search Algorithm for Job Shop Problem by Józef Grabowski and Mieczyslaw Wodecki

Sandy Rutherford, IRMACS, SFU

February 6

Scatter Search Methods for the Covering Tour Problem by Roberto Baldacci, Marco A. Boschetti, Vittorio Maniezzo and Marco Zamboni

Annie Ruonan Zhang, SFU Surrey

January 27

A Multistart Scatter Search Heuristic for Smooth NLP and MINLP Problems by Zsolt Ugray, Leon Lasdon, John C. Plummer, Fred Glover, Jim Kelly and Rafael Martí

Dan Benvenuti, SFU Surrey

January 23

A Scatter Search Tutorial for Graph-Based Permutation Problems by César Rego and Pedro Leão

Snezana Mitrovic-Minic, SFU Surrey