SCRO / Journées de l'optimisation
HEC Montréal, 2931 mai 2023
CORSJOPT2023
HEC Montréal, 29 — 31 mai 2023
MOLS Modelling and Optimization of Large Systems
30 mai 2023 10h30 – 12h10
Salle: Transat (jaune)
Présidée par Pierre Mordant
4 présentations

10h30  10h55
A Conic Integer Programming Approach to Bandwidth Packing Problem with Queuing Delays
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 (BPPQDC) 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 Mixedinteger SecondOrder Cone Programming equivalent reformulations for the BPPQDC. The proposed conic reformulations are strengthened with McCormick and polymatroid inequalities to improve computational performance. Computational experiments on synthetic instances and reallife telecommunication networks demonstrate that the bestproposed 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.

10h55  11h20
AIdriven Analysis of Thematic Convergence of User Conversations on the Reddit platform
We study largescale user collectives to gain insight into the complex structural organization of online consumer conversations. Specifically, we combine topic modeling, JensenShannon divergence and kmeans 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 largescale dataset and visualize thematic convergence trends in Reddit.

11h20  11h45
Decremental statespace relaxation for dynamic programs of pseudopolynomial complexity
We present an iterative method for the resolution of dynamic programming problems of pseudopolynomial 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 subsetsum 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.

11h45  12h10
New modeling approach for the rolling stock scheduling problem
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.