Author Archives: benkoczi

Title: Local Search Algorithms for Data Placement Problem
Speaker: Anamay Sarkar, NIT Rourkela, MITACS Globalink Fellow in the Optimization Research Group

Abstract: I will talk about Local Search based Approximation Algorithms for the data placement problem. One of the local search operators is based on the assignment problem and the second one is based on the operators for the Un-capacitated facility location problem. I will report some experimental results on the data set obtained from the OR library. This work was done as part of Mitacs Globalink internship.

Bio: Anamay Sarkar is pursuing B. Tech in Computer Science and Engineering and is currently in his final year at NIT Rourkela. His past internship was at “IIT Delhi” in the area of Approximation Algorithms under Prof Naveen Garg. He is currently the branch topper after 3rd year.

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).

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.

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.

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.

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.

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.

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.