4 Presentations

• 
  10:30 AM - 10:55 AM

  A Conic Integer Programming Approach to Bandwidth Packing Problem with Queuing Delays

  • Masoud Amel Monirian, presenter, Ph.D. Candidate of Industrial Engineering, Concordia University
  • Onur Kuzgunkaya, Associate Professor, Concordia University
  • Navneet Vidyarthi, Concordia University

  We study a variant of the Bandwidth Packing Problem (BPP) that arises in telecommunication networks. Given a set of calls, and their associated potential revenues and bandwidth requirements, arising at an instant on a telecommunication network with limited bandwidth on its links, the BPP decides which of these calls to accept, and assigns a single path to route each selected call, such that the total revenue is maximized. Excessive delays due to congestion in the network may arise if certain links are utilized close to their bandwidth capacities. We focus on a variant of BPP that accounts for queuing delay costs (BPP-QDC) in the network. The problem is formulated as a binary integer nonlinear problem which has been solved in literature by exact methods of finite linearization and cutting plane algorithm (CPA). We present several Mixed-integer Second-Order Cone Programming equivalent reformulations for the BPP-QDC. The proposed conic reformulations are strengthened with McCormick and polymatroid inequalities to improve computational performance. Computational experiments on synthetic instances and real-life telecommunication networks demonstrate that the best-proposed reformulation performs on average 2.78 times faster than CPA. The addition of the proposed polymatroid and McCormick inequalities further reduces the computation time by 24% and 27%, respectively.
• 
  10:55 AM - 11:20 AM

  AI-driven Analysis of Thematic Convergence of User Conversations on the Reddit platform

  • Ivan Belik, presenter, Associate Professor in Business Analytics

  We study large-scale user collectives to gain insight into the complex structural organization of online consumer conversations. Specifically, we combine topic modeling, Jensen-Shannon divergence and k-means clustering to analyze changes over time in thematic foci in conversations on the popular social media platform Reddit. Based on the developed approach, we identify several categories of online discussions with distinct overarching structural organizations. We found that user conversations on Reddit often have little thematic cohesion and so may have limited value to researchers or platform holders that, for example, look to use online platforms to disperse information among customers. This finding calls into question the validity of the implicit assumption of immutability of information that is passed through a network of individuals – an assumption that goes into much of the research of the phenomenon of social influence. We test our approach on a large-scale dataset and visualize thematic convergence trends in Reddit.
• 
  11:20 AM - 11:45 AM

  Decremental state-space relaxation for dynamic programs of pseudo-polynomial complexity

  • Claudio Contardo, presenter, Concordia University
  • José L. Walteros, University at Buffalo

  We present an iterative method for the resolution of dynamic programming problems of pseudo-polynomial complexity. The method integrates the iterative alternation between an aggregation mechanism that reduces the dimension of the problem --but that may provide infeasible solutions-- with a repair mechanism that detects those infeasibilities and prevents them in subsequent iterations. We illustrate the performance of the proposed method on three problems: the ranged subset-sum problem, the shortest path problem with time windows and linear waiting costs, and the weighted tree partitioning problem. The proposed method is especially useful when involving parameters of large magnitudes, offering speed ups of orders of magnitude with respect to a classical DP.
• 
  11:45 AM - 12:10 PM

  New modeling approach for the rolling stock scheduling problem

  • Pierre Mordant, presenter, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montreal & CIRRELT
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  We consider the problem of assigning rail units to scheduled train trips over a single day. This assignment must respect a number of constraints, including the availability of the different types of units, the daily periodicity of parking in the depots, and the coupling and uncoupling constraints of the units according to predefined rules. This problem can be solved efficiently by splitting the problem into two distinct parts (computation of optimal train compositions while ignoring certain constraints and then assignment of train units to these compositions). However, when this heuristic approach is used, it is impossible to determine the gap with respect to the optimal value of the problem. We therefore seek to model this problem in a single phase, as a multicommodity network flow problem with additional constraints, where each commodity follows a set of paths in an acyclic network, each path describing a sequence of trips covered by a single unit. This linear model is solved by column generation, before using a MIP solver to derive an integer solution on the subset of generated columns. To reduce the computational time for the largest instances, heuristic techniques are further applied.