Optimization Seminar Series – Wed Mar 23, 1Pm in D633

Title: A Comparison of Rotation Parameterisations for Bundle Adjustment.
Speaker: Nurgul Aimati, MSc candidate, UofL Optimization Research Group.
Time & Location: Wednesday, March 23, 2016 in room D633

Bundle Adjustment is an iterative process where 3D information is estimated from 2D image measurements. Typically, the position of object points are estimated simultaneously with the position and orientation of the cameras. While the object points and camera positions have a straightforward “natural” parameterisation, several possibilities exist for the rotation. In this thesis, seven parameterisation of the rotation were investigated; Euler angles (two variants), the Rodriguez representation, the axis-and-angle representation, unit quaternions, and two variants of the direction cosine matrix (DCM).

Optimization Seminar Series – Mon Mar 7 at 1 pm – B756

Title: Cellular Automaton Based Algorithms in Wireless Communication
Speaker: Dr. Salimur Choudhury, Mathematics and Computer Science, Algoma University, Sault Ste. Marie, ON
Location and time: 1 pm, Room B756

Abstract: The cellular automaton is a bioinspired model used to model different physical systems including wireless communication. One of the main advantages of using cellular automaton based algorithms is that they need very little local information to compute a solution. In this talk, several optimization problems in wireless sensor networks and RFID (radio frequency identification) networks along with the corresponding cellular automaton based algorithms will be presented. The problems include sleep-awake scheduling of sensors, mobile sensors dispersion, and elimination of redundant readers in RFID system.

Bio: Dr. Salimur Choudhury is an assistant professor in the department of Mathematics and Computer Science at Algoma University, Sault Ste. Marie, ON. He is also an adjunct assistant professor in the school of computing at Queen’s University, Kingston, ON. His research interests include designing algorithms for wireless communication systems including sensor networks, RFID networks, device to device communication systems, etc. Dr. Choudhury completed PhD from School of Computing, Queen’s University in 2012 and Masters from the Department of Mathematics and Computer Science, University of Lethbridge in 2008. He has experience teaching at several other universities in USA and Bangladesh. He also worked at IBM Canada Software Lab in Markham, ON.

Optimization Seminar Series – Fri Feb 12 at 9 am

Title: Approximation Algorithms for Cumulative VRP with Stochastic Demands
Speaker: Rishi Ranjan Singh, Department of Information Technology, Indian Institute of Information Technology Allahabad (IIT – Allahabad), India.
Location and time: B716, Friday Feb 12, 9 am

Abstract: In this talk we describe randomized approximation algorithms for metric stochastic cumulative VRP for split and unsplit deliveries. The approximation ratios are \(2(1 + \alpha)\) and 7 respectively, where \(\alpha\) is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. We use and extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].
This work, to appear in the proceedings of CALDAM 2016, is jointly with D.R. Gaur and A. Mudgal.

Bio: Mr. Singh is a Visiting Faculty in the Department of Information Technology at IIIT Allahabd, India. He submitted his PhD in the Department of Computer Science and Engineering at IIT Ropar, India in 2015. 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 analysis, discrete optimization.

CPSC 4625: Design and analysis of advanced algorithms

Course outline.

Optimization Seminar Series – Wed Dec 9 at 12:30

Title: Evolutionary Algorithmic Deployment of Radio Beacons for Indoor Positioning
Speaker: Dr. Peter Chen, Memorial University of Newfoundland by video-conference.
Location and time: B716, Wednesday Dec 9, 12:30pm – 13:30pm.

In mobile computing, the location awareness of a mobile device or its user enables numerous personalized and social services such as recommendation of products and sharing current locations on social networks. Extending positioning services to indoor environments augments the value of the mobile communication market vastly. Due to serious signal attenuation, navigation satellite are incapable, and a common approach is to use or deploy small-scale radio frequency transmitters. When deploying these radio beacons, it is crucial to use a small number of them to provide high-quality positioning service. As this turns out a difficult optimization problem, the system administrators would benefit from have a spectrum of solutions with different tradeoffs between cost and quality. This talk provides an Evolutionary Algorithm (EA) framework to fulfill this need. Using a cost-quality adjustment parameter, he EA framework is able to provide a set of solution options to meet varying requirements balancing cost and quality. This property is resulted by the parallel population-based search of EAs, and can be very useful in real-world engineering applications.

Bio: Yuanzhu Chen is an Associate Professor 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 – Wed Oct 28 noon

Title: The Robust Weighted Vertex Coloring Problem with Uncertain Data
Speaker: Ram Dahal, PhD candidate, Optimization Research Group
Location and time: B543, Wednesday Oct 28, 12:00pm – 12:50pm.

The vertex coloring problem (VCP) is a classical problem of assigning a color to each vertex of a graph such that no two adjacent vertices have the same color. In the weighted version of classical VCP, the vertices of the graph are assigned a positive weight and the objective is to minimize the sum of the costs of the colors from a feasible coloring. The cost of a color equals the maximum vertex weight among all vertices assigned to the color. WVCP is strongly NP-hard since it generalize the classical VCP. WVCP has several applications in scheduling, timetabling, register allocation, train platforming. In addition, the problem captures the essence of scheduling data transmissions in a time division multiple access (TDMA) wireless network. In our work we consider a much more difficult setting for WVCP called robust WVCP (RWVCP). In the robust problem, the vertex weights are uncertain and only known to lie between given lower and upper bounds. Any particular assignment of values to the uncertain parameters in the allowed ranges is called a scenario. The goal is to find a solution robust to the uncertainty that is, a solution X for which the difference between the cost of X under the worst possible scenario and the cost of the optimal solution for that scenario is minimized. RWVCP is completely open at present. In this talk, we investigate the strength of linear and integer programming techniques in solving robust WVCP. In our apporach, we use Benders decomposition to generate the scenarios of interest but our master problem is a linear program with an exponential number of variables
and it is solved by column generation.

Optimization Seminar Series – Wed Sep 30 @ 1 pm

Title: Design Structure Matrix : Models, Applications and Data Exchange Format
Speaker: Rumana Quashem, MSc candidate, Optimization Research Group
Location and time: B660, Wednesday Sept 30, 1 pm

Abstract: A Design Structure Matrix(DSM) is much more than an adjacency matrix representation of a network. The design and analysis of complex engineered systems can be greatly aided by tools that can capture, organize and represent interactions among systems’ elements. It is a tool that can be used to represent a system’s design structure in a visually appealing manner. The DSM research over the last 3 decades have produced important analysis techniques that have been applied to a variety of projects. Many real world examples of DSM matrices remain scattered in the literature. Recently, the book by Eppinger and Browning has compiled 44 DSM examples from diverse areas; and we have discovered that most of these examples are not in easily retrievable digital form.
Thus, we proposed a new exchange format “Design Structure Matrix Data Exchange(DSMDE)” as a common file format to promote reliable and efficient exchange of Design Structure Model (DSM) and MDM (Multi-domain Model) data. It is an extension of the widely used “Matrix Market(MM)” file format (for the exchange of sparse and dense matrices data). At present there does not exist a common standard for sharing DSM/MDM data. We believe that a standardized exchange format will greatly facilitate research and development of DSM modelling techniques by making data widely available than currently possible. Thus, the DSMDE is expected to be a standard way to share DSM/MDM data among researchers, practitioners, and on different computing environments. 

Everyone is welcome. Graduate students are encouraged to attend.

Optimization Seminar Series – Mon Sep 28 @ 1 pm

Title: Ranking Components of Scientific Software using Spectral Methods
Speaker: Soma Khan, MSc candidate, Optimization Research Group.
Location and time: D630, Monday Sept 28, 1 pm.

Abstract: Our main objective is to determine the importance or centrality of the components of a scientific software which will be helpful in understanding the design architecture of the scientific software. We explore the centrality rankings of functions in call graphs of scientific software using spectral methods. We employ a set of quantitative measures to identify important design elements in scientific software by analyzing the interactions between them. The notion of centrality of software components extended beyond nodal degree. Hub and authority scores are computed using the HITS algorithm and Benzi’s method. The results will be compared to see the accuracy.
Everyone is welcome. Graduate students are encouraged to attend.

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.

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

CPSC 3780: Data Communications and Networking

The course materials are available on moodle to registered students.
Course outline

  • Main text: Computer Networking, Principles, Protocols and Practice 2nd Ed, by Bonaventure, available online here.
  • Supplementary texts: Computer Networks 5th Ed, by Tanenbaum and Wetherall; Computer Networking: A Top-Down Approach (7th Edition) by Kurose and Ross.