4 présentations

• 
  10h30 - 10h55

  New algebraic graph contraction applied to the network pricing problem

  • Julien Hébert-Doutreloux, prés., Université de Montréal
  • Margarida Carvalho, Université de Montréal
  • Emma Frejinger, Université de Montréal

  The graph is one of the simplest mathematical structures with a remarkably wide range of applications in research. From a colouring problem to the modelling of a gene regulation network, from transportation network optimization to the multi-commodity network pricing problem (NPP), the use of graphs is central. However, frequently, the exact methodologies to solve these problems do not scale well, making solving real-world problems hardly approachable. Therefore, heuristics are often used in an attempt to obtain good quality solutions, but having guarantees on their results remains difficult. Our research focuses specifically on the problem of scalability by algebraically reducing the size of the graph itself and then solving the original problem on the newer reduced graph. To validate our framework, this new graph contraction is applied on the network pricing problem.

• 
  10h55 - 11h20

  Minimum Spanning Tree interdiction and extensions

  • Noah Weninger, University of Waterloo
  • Ricardo Fukasawa, prés., University of Waterloo

  Interdiction problems have many applications in economics, military, marketing, security, etc. In these problems there are two decision makers: a leader and a follower. The follower wants to solve their own optimization problem and the leader wants to interdict access to some decisions of the follower. We study the minimum spanning tree interdiction problem, where the follower wants to compute a minimum spanning tree in a graph (connect the graph at minimum cost). The objective of the leader is to "interdict" or make certain edges in the graph unavailable to the follower in order to maximize the cost of the follower. However, the leader has to respect a certain budget (knapsack) constraint.
  We devise a combinatorial branch-and-bound algorithm for the problem which improves the state-of-the-art for the problem by orders of magnitude. Our algorithm makes use of a problem-specific bound and enumeration scheme. We also extend our results to more general matroid interdiction problems.

• 
  11h20 - 11h45

  Handling ambiguity in Stochastic Humanitarian Supply Chain Network Design

  • Mohammad Daneshvar, prés., ESG-UQAM
  • Sanjay Dominik Jena, Université du Québec à Montréal
  • Walter Rei, Université de Montréal

  After natural disasters, humanitarian organizations face complex challenges in the design and operation of Humanitarian Supply Chain Networks (HSCN). The design of an HSCN relies on various data sources (e.g., surveys and satellite imagery) involved in the demand and damage assessment in affected areas to estimate uncertain components of the problem. However, the provided estimations by data sources may be inconsistence, resulting in ambiguity in the HSCN design problem. We propose four mathematical models to handle ambiguity with different degrees of conservatism. These models are evaluated using real-world data from the 2018 Indonesia earthquake, considering different ambiguity patterns and confidence levels in data sources. Results show the advantages of minimizing the worst-case expected opportunity loss model when the ambiguity pattern is unknown and confidence levels in data sources are equal.

• 
  11h45 - 12h10

  Application placement simulations over HEAVEN platform

  • Antoine Bernard, prés., Polytechnique Montréal
  • Antoine Legrain, Polytechnique Montréal

  In recent years, deploying distributed applications efficiently over cloud platforms has been extensively studied. Various algorithms were developed to solve this optimization problem, such as virtual network embedding algorithms.

  The HEAVEN platform is an embedded wireless datacenter solution that provides resilient and flexible internet coverage. This solution is an efficient way to provide emergency connectivity through to its mesh network. The next logical step after establishing connectivity is to provide processing power to the users. Exploiting drones' processing power can be a method for offloading computations, providing essential offline emergency services. With limited connectivity between devices, link allocation becomes a key component of the problem.

  This talk presents a comprehensive analysis of the capabilities such platform could offer, by presenting a simulation based on individual device capability and connectivity. The simulation framework incorporates models for device capability, connectivity, and application requirements, enabling the evaluation of efficient application deployment strategies over HEAVEN. Optimizing application placement in real-time and in a distributed way would expand the network resiliency to its applications.

  Additionally, this talk presents preliminary results on implementing greedy placement to the simulation framework as a first step to solve the virtual application placement problem under heavy network and resource constraints.