2022 Optimization Days
HEC Montréal, Québec, Canada, 16 — 18 May 2022
MB10 - Networks
May 16, 2022 03:30 PM – 05:10 PM
Location: Banque Scotia (blue)
Chaired by Hugo Tremblay
4 Presentations
-
03:30 PM - 03:55 PM
Tactical Wireless Network Design for Challenging Environments
Designing and optimizing a tactical wireless network for maximal throughput is a very complex problem. A full network design includes a hybrid topology with a global tree structure and the possibility of containing mesh clusters. It also includes the selection of a master hub node which acts as the root of the tree, a valid assignment of waveforms and signal frequencies to all of its connections as well as the alignment and configuration of the multi-beam antennas. Compared to previous work, we formulate this combinatorial optimization problem in its full form with very few approximations. Because of its complexity and non-linearity, we solve this problem in multiple phases with a variety of sub-strategies ranging from exact methods to meta-heuristics and machine learning.
-
03:55 PM - 04:20 PM
Mathematical Formulations for Multi-Period Network Design with Modular Capacity Adjustments
Network design refers to combinatorial problems concerned with selecting a subset of typically capacitated arcs such that commodities can be routed from their origin to their destination nodes at minimal costs. Multi-period models aim at preparing the network for varying demand along time, which may imply adjusting arc capacities along time to better respond to demand changes. Some works therefore proposed models that allow for the expansion of arc capacities along the planning horizon. However, even though it may be a viable and cost-beneficial option in several application contexts, the reduction of existing capacity has mostly been ignored. This work proposes a new multi-period network design problem variant, in which modular capacities can be added or reduced along the planning horizon. The problem further allows to represent economies of scales in function of the total arc capacity, a detail that has typically been overlooked in the literature. We propose three different mixed-integer programming formulations and analyze further modeling alternatives. We theoretically compare the strength of all formulations and evaluate their computational performance in extensive experiments. The results suggest that a recent modeling technique using more precise decision variables yields the strongest formulation, which also results in significantly faster solution times.
-
04:20 PM - 04:45 PM
Heuristic to obtain lower bounds for the discrete ordered p-median problem
We propose a heuristic method to obtain lower bounds for the discrete ordered p-median problem (DOMP). In the DOMP, we have a set of nodes, which represent clients as well as potential facility locations. With each pair (facility, client) we associate an assignment cost. A fixed number p of facilities must be located to service all clients, each of which is allocated to its nearest facility in terms of cost. Given a set of p open facilities, we define a minimal assignment cost of clients to a facility. Also, we have a vector of weights for the objective function of the DOMP. The objective then consists of minimizing the total ordered weighted average allocation costs according to the weight vector. The heuristic we design consists in solving a series a covering problems that provide an optimal solution for a DOMP with an elementary weight vector. We combine those solutions to derive a lower bound on the original DOMP. Numerical results indicate that our heuristic is able to provide lower bounds of good quality for several classes of classical instances for the DOMP.
-
04:45 PM - 05:10 PM
Minimizing the number of robots required for a Robotic Process Automation problem
Robotic Process Automation (RPA) consists of virtual robots programmed for executing various automated actions on a graphical user interface (GUI), thus eliminating the need for human user interactions. Its usage in various fields of human activity has led for faster and more secure processes through a reduction in the risks or errors but also an increase in the productivity rates. The increase of its use and importance calls for evermore efficient solution methods for this problem. In this work, RPA is addressed in the context of a financial institution where the organization handles a large volume of transactions daily, some of which are short and repetitive. When processing the latter type of transaction, humans would typically get bored and lose focus rather fast. Thus, using software robots instead seems like a more effective solution as their processing times and productivity are not affected by contingencies such as exhaustion and boredom. The RPA problem presented in this work consists in determining the minimum number of robots required in order to complete several concurrent financial transactions. Each transaction type is constrained by market operation hours and a clearance date. It also has a volume (i.e. number) of transactions to be completed, each of which require a given processing time. The solution to the problem provides a schedule for the robots that minimizes the maximal number of active robots at a given period for different transactions combinations.
The content of the presentation is as follows: First, four heuristics are used to compute an upper bound on the number of required software robots. Then, this bound is given as a parameter to an integer linear program, which is used to assign the transactions to the different robots. The quality of the solutions is assessed by an extensive experimental study on a set of 39,000 instances. The results show that two heuristics outperform the others and allow for a faster resolution by the integer linear program which in turn finds the optimal solution for most of the instances within a timeout of 60 seconds.