Category Archives: news

Optimization Seminar Series – Wed Sep 16 @ noon in B543

Title: Combinatorial Optimizations of Some Graph  Problems using Evolutionary Algorithms
Speaker: Dr. Mozammel H. A. Khan, Visiting Researcher
Location & time: B543, Wed. Sept. 16, 2015, 12:00pm – 12:50pm

Many classical graph problems such as maximum clique problem (MCP), graph coloring problem (GCP), and degree-constrained minimum spanning tree (d-MST) are NP-hard problems and combinatorial in nature. Meta-heuristic algorithms such as evolutionary algorithms (EA) are found to be very effective in global optimization of combinatorial problems in general. We have solved MCP using quantum-inspired evolutionary algorithm (QEA), GCP using both memetic algorithm and QEA, and d-MST using QEA. In all the cases, the experimental results establish that our methods outperform the previous methods.
The talk is based on the published papers of Professor Khan with his students. The talk is intended for senior undergraduate students, graduate students, and faculty members interested in collaborating in solving combinatorial graph problems and other combinatorial problems using EA.

Biography:
Dr. Khan is a Professor in the Department of Computer Science and Engineering at East West University, Dhaka, Bangladesh and currently a Visiting Researcher in the Department of Mathematics and Computer Science at University of Lethbridge, AB, Canada. Prof. Khan is a Senior Member of the Institution of Electrical and Electronics Engineers (IEEE). He has obtained B. Sc. Engg. degree in Electrical and Electronic Engineering, M. Sc. Engg. degree in Computer Engineering, and Ph. D. degree in Computer Science and Engineering form  Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh in 1984, 1986, and 1998, respectively. He has served as Head of the Department of Computer Science and Engineering, Head of the Department of Electronics and Communications Engineering, and Dean of the School of Science, Engineering and Technology at Khulna University, Khulna, Bangladesh. He has also served as Chairperson of the Department of Computer Science and Engineering, Chairperson of the Department of Electrical and Electronic Engineering, and Dean of the Faculty of Science and Engineering at East West University, Dhaka, Bangladesh. Prof. Khan’s research interests include Logic Synthesis, Quantum Computing, Evolutionary Algorithms, and Nano-Electronics. He has published 88 papers in journals, book chapters, and conferences. More about him can be found at www.ewubd.edu/~mhakhan

Optimization Seminar Series – Fri. Sept. 11, 2015 in B543

Title: Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line
(extended version of Mark’s upcoming talk at ALGOSENSORS in Patras, Greece)
Speaker: Mark Thom, PhD student, Optimization Research Group
Location & time: B543, Fri. Sept. 11, 2015, 12:00pm – 12:50pm

Abstract: Barrier coverage is a cost effective approach to intruder detection
applications. It consists of monitoring the perimeter, or barrier, of
an area by placing sensors at appropriate locations on the barrier. In
this talk, we consider a restricted version of the barrier coverage
problem in which the area of coverage is a line segment and the
sensors are points with varying detection ranges that lie in initial
positions disjoint to the line segment. Sensors are moved along the
line containing the line segment to their final positions in the
coverage, and the distances moved by each sensor are summed,
determining the cost of the coverage. The objective is to find the
coverage of least cost.  We sketch a proof of the NP-hardness of the
restricted problem and outline a polynomial-time approximation scheme
that produces barrier coverages of cost arbitrarily close to that of
an optimal solution. Everyone is welcome, no prior knowledge of
approximation algorithms or NP-hardness is assumed.

Optimization Seminar Series – Feb 18, 2015 (Cancelled)

Due to an emergency, the following talk has been cancelled.
Title: Multi-Hop Wireless Networking: Issues and Opportunities
Speaker: Dr. Yuanzhu Chen, Associate Professor, Department of Computer Science, Memorial University.
Abstract:
A multi-hop wireless network is a wireless communication network, where nodes that are not within direct transmission range of each other will require other nodes to forward data. It can operate without existing infrastructure, supports mobile users, and sometimes take the form of mobile ad hoc networks, wireless sensor networks, delay-tolerant networks, and so forth. Such a networking paradigm originated from the needs in battlefield communications, emergence operations, search and rescue, and disaster relief operations. Later, it found civilian applications such as community networks. Compared to the TCP/IP based Internet, such a networking paradigm has a number of salient features, such as broadcast medium, fast network topology change, and frequent and extended disruption. In this talk, I will present some of our research projects to address the issues inherent to this networking technology in an effort to advance the state of the art of the area.
Bio:
Yuanzhu Chen is an Associate Professor and Deputy Head of Undergraduate Studies in the Department of Computer Science, Memorial University of Newfoundland, St. John’s, Newfoundland. He received his Ph.D. from Simon Fraser University in 2004 and B.Sc. from Peking University in 1999, both in Computer Science. He was a Visiting Professor to Dartmouth College in 2011-2012. Between 2004 and 2005, he was a post-doctoral researcher at Simon Fraser University. His research interests include wireless networking, mobile computing, optimization of graph problems, and information retrieval.

Optimization Seminar Series – Feb 17, 2015 (Cancelled)

Due to an emergency, the following talk has been cancelled.
Title: Robustness and Evolvability in Evolutionary Computation
Speaker: Dr. Ting Hu, Assistant Professor, Department of Computer Science, Memorial University.
Abstract:
Robustness, the maintenance of a phenotypic character in the presence of genotypic changes, is the result of a redundant mapping between genotype and phenotype, where many mutational variants of a genotype produce an identical phenotype. Such robustness, at first glance, seems to hinder the capability of innovating, i.e. evolvability. However, empirical evidences have been reported on living organisms that robustness can facilitate evolvability since it allows genetic variants to expand in neutral spaces that provide a staging ground for future adaptive innovations. Redundant genotype to phenotype mapping is common in Evolutionary Computation. We use genotype networks to characterize the mutational connectivity of an Evolutionary Computation system, and to further quantify robustness and evolvability at the genotype, phenotype, and fitness levels. We show that robustness and evolvability correlate very differently at these three levels, and their interplay crucially depends on how the mutational connections are distributed among phenotypes.
Bio:
Dr. Ting Hu is an Assistant Professor at the Department of Computer Science, Memorial University of Newfoundland. She was a postdoctoral researcher at Computational Genetics Laboratory, Dartmouth College. She obtained her PhD in Computer Science from Memorial University, MSc in Computer Science and BSc in Applied Mathematics from Wuhan University. Dr. Hu’s research interests include bio-inspired computing and bioinformatics.

Optimization Seminar Series – Wednesday Jan 28, 9 am D511

Title: Cumulative Vehicle Routing Problem: A Column Generation Approach
Speaker: Rishi Ranjan Singh, Department of Computer Sc. and Engg., Indian Institute of Technology Ropar (IIT – Ropar), India.
Time & location: Wednesday Jan 28, 2015, 9 am in D511. This talk is presented by video conference.

Abstract:
In this talk, aimed at senior undergraduate and graduate students, we describe a computational approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation. This work, to appear in the proceedings of CALDAM 2015, is jointly with D. Gaur.

Bio: Mr. Singh is a PhD Scholar in the Department of Computer Science and Engineering at IIT Ropar. He received his B. Tech (Hons.) in Computer Science and Engineering from UPTU Lucknow, India in 2011. He is interested in approximation algorithms for vehicle routing problems, social and complex network, network analysis and operations research.

Optimization SeminarSeries – Monday Nov 10, 2014 @ 2pm

Regret-Bounded Vehicle Routing
Professor Zachary Friggstad, Canada Research Chair Tier-II in Combinatorial Optimization, Department of Computing Science, University of Alberta.
Room: C674, University Hall

A typical vehicle routing problem involves deploying a fleet of vehicles to serve some clients. Many well-studied models are concerned mostly with the distance travelled by the vehicles. However, this objective does not differentiate between clients that are located at different distances from the depot. For example, a client closer to the depot may incur a larger delay than a client that is further away in a minimum-length TSP tour. This can be a source of client dissatisfaction.
This leads us to consider the notion of regret of a client: the time a client waits to be served in excess of its shortest-path distance from the depot. I will discuss old and new approximation algorithms for client-centric vehicle routing models and their applications to more classical models. In particular, I will present the first constant-factor approximation for the problem of deploying the fewest vehicles to ensure each client is served with regret at most some given bound B.
Students are encouraged to attend.

Professor Friggstad’s main research interests lie in designing approximation algorithms and, more specifically, in investigating the effectiveness of mathematical programming based techniques in the design of such algorithms. His research has been applied to problems in vehicle routing, facility location, resource allocation, network design, and lift-and-project techniques. Professor Friggstad is a University of Lethbridge alumnis (2005) and, as a student, he has competed twice in the ACM Programming Contest World Finals obtaining one Bronze Medal in 2006.

Optimization Seminar Series – Friday Oct 24, 2014 @ 11 am

The Impact of Social Network Influences on the Cost of Capacity Reservation
Professor Mozart Menezes, Haskayne School of Business, University of Calgary
Room: D634, University Hall

In a connected world where information moves fast and has long reach, mostly through social networks, the disclosure of personal preferences influences consumer behaviour and affects probability distribution of demand in ways that seem hard to predict. Going beyond just taking into account the intrinsic individuals’ preferences, in this paper we attempt to model for the first time the impact that social inner-circles and product market share have on (forecasted) probability distribution of demand. We find that both inner-circles’ influence and market share information may substantially increase demand variability of a product with a consequent substantial impact on costs for matching supply and demand.

Optimization Seminar: The weighted colouring problem on path graphs

18 Sept 2013 @ 1:00 – 1:50 pm
Room: E575
Presenter: Ram Dahal

Abstract: We present a generalization of the classical vertex colouring problem, weighted colouring, that has applications in the management of wireless networks. We focus on the simplest network topology, the path graph. Time permitting, we conclude with several open problems.

Bio: Ram Dahal is a PhD candidate in Computer Science at The University of Lethbridge. He is a member of the Optimization Research Group since September 2012.

Optimization Seminar – Thr. Apr. 11, 2013

Thursday April 11, from 12:15-13:05
Room E-575
Speaker: Daya Gaur.
Abstract:
Given a fleet of vehicles and a set of customers, the objective in capaciated vehicle routing problems is to minimize the total distance traveled and serve the customers subject to vehicle capacity constraints. We will examine existing approximation algorithms for deterministic and stochastic versions of capaciated vehicle routing problems.
This talk is open to everyone. Graduate students are encouraged to attend. Light refreshments will be served.

Optimization Seminar – Thr. Mar 21, 2013

Thursday Mar 21 from 12:15-13:05
Room E-575

Speaker: Ram Dahal
Ram will talk about the weighted colouring problem in a graph and its connection to routing and scheduling in wireless networks.
Everyone is welcome. All graduate students are encouraged to attend. Light refreshments will be served.