tag:www.gerad.ca,2005:/fr/papersCahiers du GERAD2023-12-06T14:39:44-05:0020tag:www.gerad.ca,2005:Paper/30442023-12-04T15:00:41-05:002023-12-06T14:39:44-05:00G-2023-50 : Network design with vulnerability constraints and probabilistic edge reliabilityOkan Arslan, Gilbert Laporte
<p>The Network Design Problem with Vulnerability Constraints and Probabilistic Edge Reliability (NDPVC-PER) is an extension of the NDPVC obtained by additionally considering edge reliability. We consider the design of a telecommunication network in which every origin-destination pair is connected by a hop-constrained primal path, and by a hop-constrained backup path when certain edges in the network fail. The edge failures occur with respect to their reliability, and the network is designed by considering a minimum reliability level. Therefore, an hop-constrained backup path must be built by considering all simultaneous edge failures that have a certain probability of realization. While there exist models to solve the NDPVC without enumerating all edge subsets, edge reliability cannot be dealt with by applying the techniques applied to the NDPVC. Therefore, we develop models based on a new concept of <em>resilient length-bounded cuts</em>, and solve the NDPVC-PER without edge set enumerations. We perform extensive testing of the model to determine the best performing settings, and demonstrate the computational efficiency of the developed model. Our findings on these instances show that, in the dataset considered in this study, increasing the reliability level from 90% to 95% increases the average cost only by 12.4%, while increasing it from 95% to 99% level yields a cost increase of 93.9%. </p>
2023-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30432023-11-30T13:39:18-05:002023-11-30T13:39:18-05:00G-2023-49 : Incentivizing healthy food choices using add-on bundling: A field experimentNymisha Bandi, Maxime Cohen, Saibal Ray
<p>How can retailers incentivize customers to make healthier food choices? Price, convenience, and taste are known to be among the main drivers behind such choices. Unfortunately, healthier food options are often expensive and infrequently promoted. Recent efforts in deploying healthy nudges to incentivize customers toward healthier food choices have been observed. In this paper, we conducted a field experiment with a global convenience store chain to better understand how different add-on bundle promotions influence healthy food choices. We considered three types of add-on bundles: (i) an unhealthy bundle (when customers purchased a coffee, they could add a pastry for $1), (ii) a healthy bundle (offering a healthy snack as an add-on), and (iii) choice bundle (offering either a pastry or a healthy snack). In addition to our field experiment, we conducted an online lab study to strengthen the validity of our results. We found that offering healthy snacks as part of an add-on bundle significantly increased healthy purchases (and decreased unhealthy purchases). Surprisingly, this finding continued to hold for the choice bundle, that is, even when unhealthy snacks were concurrently on promotion. Unfortunately, we did not observe a long-term stickiness effect, meaning that customers returned to their original (unhealthy) purchase patterns once the healthy or choice bundle was discontinued. Finally, we show that offering an add-on choice bundle is also beneficial for retailers, who can earn higher revenue and profit.</p>
2023-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30402023-11-14T14:25:45-05:002023-11-14T14:25:45-05:00G-2023-53 : An history of relevance in unsupervised summarizationFlorian Carichon, Gilles Caporossi
<p>Le résumé automatique de document a pour but de créer une version réduite d’un ensemble de textes pour aider des utilisateurs à mieux assimiler l’information pertinente contenue dans ces derniers. Les méthodes non supervisées sont parmi les méthodes les plus appropriées pour effectuer cette tâche puisqu’elles ne nécessitent pas d’étiquetage humain a priori pour condenser l’information. Cet article propose une revue de littérature détaillée de ces approches appliquées au résumé de document, octroyant alors une meilleure compréhension de leurs mécanismes et des principes fondamentaux sous-jacents. Cette analyse traite donc de plusieurs aspects importants. Tout d’abord elle offre une vue globale du domaine permettant d’expliquer certains contextes d’application, l’évaluation et l’évolution des approches non supervisées. Elle fournit une nouvelle typologie de classification des méthodes, clarifiant ainsi le lien entre la tâche du résumé de document et certains facteurs contextuels tels que l’intention et l’audience. Cela met particulièrement en avant comment ces facteurs influencent la notion de pertinence et la manière dont l’information est sélectionnée par un algorithme pour non seulement former le résumé, mais aussi mesurer sa performance. Résultant de ce travail, une discussion sur les ressemblances profondes entre les différentes méthodes et les limites qui leur sont reliées nous permet de proposer différentes recommandations et des pistes de recherche future afin d’intégrer les observations que nous avons réalisées. </p>
2023-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30392023-11-14T10:39:18-05:002023-11-14T11:39:48-05:00G-2023-52 : An optimization model for the energy management of the network of tanks in a water distribution systemFranklin Djeumou Fomeni, Ali Montaz
<p>"L'eau c'est la vie" is a well known french expression for "Water is life", which reflects the fact that water is undoubtedly the most vital resource in the world. The main mission for water utility companies is to convey and distribute water that is of acceptable quality to satisfy the demand of the population at any time of the day. In the recent years, achieving this mission has become very challenging for these companies. Indeed, the rapid growth of the population and of the expansion of urbanization have significantly increased the demand for water on the one hand. While on the other hand, natural phenomenon such as drought as well as the impact of climate changes are making it almost impossible for water distribution companies to be able to convey the right amount of water where and when it is needed. The presence of water storage tanks in a water distribution network is aimed at alleviating this pressure by storing water and distributing it later in response of the variability of the demand across the network. The management of the tanks of the network is done based on the assignment of three level set-points which allows to meet the outflow demand of water from each tank, while maintaining the adequate flow rate of through the network. The set-points define the level at which the valves that enable inflow and outflow of water to the tank have to be switched on or off. However, operating the valves during different periods of the day in order to meet the water demand, may yield extremely high operational cost, since opening some of the of the valves will induce the running of pumps to maintain an adequate flow rate of water in the network. We present a network optimization model for managing the network of storage tanks in a water distribution system while minimizing the total cost of electricity involved. Computational experiments have been conducted to show that the proposed optimization model can be used to reduce the operational cost of managing the network of storage tanks for a water distribution system, while still being able to maintain the right amount of water in the tanks.</p>
2023-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30412023-11-14T15:54:36-05:002023-11-14T15:54:36-05:00G-2023-48 : Price-based strategies for mitigating electric vehicle-induced overloads on distribution systemsFeng Li, Ilhan Kocar, Antoine Lesage-Landry
<p>This paper first introduces a computationally efficient approach for conducting a time-series impact analysis of electric vehicle (EV) charging on the loading levels of power system equipment. This study incorporates the stochastic nature of EV owners' charging behaviours by modelling various charging profiles as probability distributions. This work then develops new mitigation strategies to temporally shift EV charging from periods of equipment overloading to alternative time periods to improve power system equipment lifetime. A reward program and a time-of-use (TOU) tariff are proposed to incentivize EV owners to participate to the mitigation effort. A search algorithm integrating a convex optimization problem is developed to determine optimal incentive levels and quantify resulting changes in EV owner charging behaviours. The proposed mitigation strategies are numerically evaluated on a modified version of the large-scale IEEE-8500 test feeder with a high EV penetration to mitigate the overloading of the substation transformer.</p>
2023-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30382023-10-27T17:01:19-04:002023-10-27T17:01:19-04:00G-2023-47 : Dynamic rebalancing optimization for bike-sharing systems: A modeling framework and empirical comparisonJiaqi Liang, Sanjay Dominik Jena, Andrea Lodi
<p>Station-based Bike-sharing systems have been implemented in multiple major cities, offering a low-cost and environmentally friendly transportation alternative. As a remedy to unbalanced stations, operators typically rebalance bikes by trucks. The resulting dynamic planning has received significant attention from the Operations Research community. Due to its modeling flexibility, mixed-integer programming remains a popular choice. However, the complex planning problem requires significant simplifications to obtain a computationally tractable model. As a result, existing models have used a large variety of modeling assumptions and techniques regarding decision variables and constraints. Unfortunately, the impact of such assumptions on the solutions’ performance in practice remains generally unexplored.</p>
<p>In this paper, we first systematically survey the literature on rebalancing problems and their modeling assumptions. We then propose a general mixed-integer programming model for multi-period rebalancing problems that can be easily adapted to different assumptions, including trip modeling, time discretization, trip distribution, and event sequences. We develop an instance generator to synthesize realistic station networks and customer trips, as well as a realistic fine-grained simulator to evaluate the operational performance of rebalancing strategies. Finally, extensive numerical experiments are carried out, both on the synthetic and on real-world data, to analyze the effectiveness of various modeling assumptions and techniques. Based on our results, we identify the assumptions that empirically provide the most effective rebalancing strategies in practice. Specifically, a set of specific trip distribution constraints and event sequences ignored in the previous literature seem to provide particularly good results.</p>
2023-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30372023-10-25T15:58:51-04:002023-10-25T15:58:58-04:00G-2023-46 : Risk averse constrained blackbox optimization under mixed aleatory/epistemic uncertaintiesCharles Audet, Jean Bigeon, Romain Couderc, Michael Kokkolaras
<p>This paper addresses risk averse constrained optimization problems where the objective and constraint functions can only be computed by a blackbox subject to unknown uncertainties. To handle mixed aleatory/epistemic uncertainties, the problem is transformed into a conditional value-at-risk (CVaR) constrained optimization problem. General inequality constraints are managed through Lagrangian relaxation. A convolution between a truncated Gaussian density and the Lagrangian function is used to smooth the problem. A gradient estimator of the smooth Lagrangian function is derived, possessing attractive properties: it estimates the gradient with only two outputs of the blackbox, regardless of dimension, and evaluates the blackbox only within the bound constraints. This gradient estimator is then utilized in a multi-timescale stochastic approximation algorithm to solve the smooth problem. Under mild assumptions, this algorithm almost surely converges to a feasible point of the CVaR-constrained problem whose objective function value is arbitrarily close to that of a local solution. Finally, numerical experiments are conducted to serve three purposes. Firstly, they provide insights on how to set the hyperparameter values of the algorithm. Secondly, they demonstrate the effectiveness of the algorithm when a truncated Gaussian gradient estimator is used. Lastly, they show its ability to handle mixed aleatory/epistemic uncertainties in practical applications.</p>
2023-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30362023-10-25T11:32:15-04:002023-10-25T11:32:16-04:00G-2023-45 : Home health care delivery with consistency consideration in a stochastic environmentSaeede Hosseini, Yossiri Adulyasak, Louis-Martin Rousseau
<p>We study the integration of multi-period assignment, routing, and scheduling of care workers for home health care services. In such a context, it is important to ensure service consistency, where a designated care worker must visit each patient at a specific time and in a consistent manner based on an established route and schedule. The challenge in maintaining service consistency and quality lies in the fact that a care agency must determine consistent and efficient schedules of visits to patient locations for multiple care workers despite uncertainty in travel and service times. To this end, we extend the home health care routing and scheduling problem (HHCRSP) presented in the literature and introduce a stochastic optimization model to incorporate service level constraints under stochastic travel and service times. We propose the solution framework based on two representations: a discrete scenario set and an extreme value theory-based (EVT-based) approximation. To tackle instances of practical size, we employ branch-and-check (B&Ch), a variant of the logic-based Benders decomposition (LBBD) method, where the subproblem is efficiently solved using constraint programming (CP). The results show that the stochastic approaches, especially with the EVT-based approximation model, can efficiently handle practical benchmark instances while producing schedules with significantly higher service levels than the deterministic approach. We also demonstrate the effectiveness of scenario-based and EVT-based models under different types of uncertainty.</p>
2023-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30342023-10-20T15:03:32-04:002023-10-20T15:03:32-04:00G-2023-44 : Evolution of high throughput satellite systems: Vision, requirements, and key technologiesOlfa Ben Yahia, Zineb Garroussi, Olivier Bélanger, Brunilde Sansò, Jean-François Frigon, Stéphane Martel, Antoine Lesage-Landry, Gunes Karabulut-Kurt
<p>High throughput satellites (HTS), with their digital payload technology, are expected to play a key role as enablers of the upcoming 6G networks. HTS are mainly designed to provide higher data rates and capacities. Fueled by technological advancements including beamforming, advanced modulation techniques, reconfigurable phased array technologies, and electronically steerable antennas, HTS have emerged as a fundamental component for future network generation. This paper offers a comprehensive state-of-the-art of HTS systems, with a focus on standardization, patents, channel multiple access techniques, routing, load balancing, and the role of software-defined networking (SDN). In addition, we provide a vision for next-satellite systems that we named as extremely-HTS (EHTS) toward autonomous satellites supported by the main requirements and key technologies expected for these systems. The EHTS system will be designed such that it maximizes spectrum reuse and data rates, and flexibly steers the capacity to satisfy user demand. We introduce a novel architecture for future regenerative payloads while summarizing the challenges imposed by this architecture.</p>
2023-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/28172020-11-13T15:04:22-05:002023-11-27T10:47:47-05:00G-2020-54 : Unified branch-and-Benders-cut for two-stage stochastic mixed-integer programsArthur Maheo, Simon Belieres, Yossiri Adulyasak, Jean-François Cordeau
<p>Two-stage stochastic programs are a class of stochastic problems where uncertainty is discretized into scenarios, making them amenable to solution approaches such as Benders decomposition. However, classic Benders decomposition is not applicable to general two-stage stochastic mixed-integer programs due to the restriction that the second-stage variables should be continuous. We propose a novel Benders decomposition-based framework that accommodates mixed-integer variables in both stages as well as uncertainty in all of the recourse parameters. The proposed approach is a unified branch-and-Benders algorithm, where we use a heuristic to maintain a global upper bound and a post-processing phase to determine an optimal solution. This new approach is flexible, allowing practitioners to integrate acceleration techniques such as partial decomposition or convexification schemes. We demonstrate the efficiency of our approach versus classic ones on the stochastic server location problem; and, its generality on a new, complex stochastic problem where the second stage is a traveling salesman problem.</p>
2020-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30332023-10-19T16:12:51-04:002023-11-27T13:46:14-05:00G-2023-43 : Evaluation of counterparty credit risk under netting agreementsMichèle Breton, Ahmadreza Tavasoli
<p>Cet article étudie le risque de crédit de contrepartie et l’ajustement réglementaire correspondant (CVA) pour des portefeuilles de produits dérivés avec possibilité d’exercice anticipé, lorsque les parties ont signé un accord de compensation (netting).
Nous montrons que le risque de contrepartie et le netting ont un impact significatif sur la façon dont les portefeuilles sont gérés (c’est-à-dire sur les stratégies d’exercice des options) et, par conséquent, sur la valeur du portefeuille et sur le prix du risque de contrepartie.
Nous obtenons la valeur du portefeuille à partir de la solution d’un jeu dynamique stochastique à somme nulle sur horizon fini. Nous montrons que cette interprétation de l’interaction entre les parties peut être utilisée pour déterminer la valeur des exigences réglementaires requises des institutions financières pour couvrir le risque de contrepartie et nous proposons une approche numérique.
Nos expériences numériques montrent que les approches actuellement utilisées en pratique peuvent entraîner des erreurs importantes dans l’estimation du CVA. </p>
2023-09-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30322023-10-19T14:28:10-04:002023-11-27T13:44:31-05:00G-2023-42 : Modeling and solving the traveling salesman problem with speed optimization for a plug-in hybrid electric vehicleFuliang Wu, Yossiri Adulyasak, Jean-François Cordeau
<p>This paper investigates a variant of the traveling salesman problem (TSP) with speed optimization for a plug-in hybrid electric vehicle (PHEV), simultaneously optimizing the average speed and operation mode for each road segment in the route. Two mixed-integer nonlinear programming models are proposed for the problem: one with continuous speed decision variables and one with discretized variables. Since the models are non-linear, we propose reformulation schemes and introduce valid inequalities to strengthen them. We also describe a branch-and-cut algorithm to solve these reformulations. Extensive numerical experiments are performed to demonstrate the algorithm's performance in terms of computing time and energy consumption costs. Specifically, the proposed solution method can efficiently solve instances with a realistic number of customers and outperforms the benchmark approaches from the literature. Integrating speed optimization into the TSP of a PHEV can lead to significant energy savings compared to the fixed-speed TSP. In addition, the proposed model is extended to investigate the impact of the presence of charging stations, which makes the problem harder to solve but has the potential to further reduce energy consumption costs.</p>
2023-09-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30312023-10-12T11:56:39-04:002023-11-27T13:43:05-05:00G-2023-41 : PLSR1: A limited-memory partitioned quasi-Newton optimizer for partially-separable loss functionsPaul Raynaud, Dominique Orban, Jean Bigeon
<p>Improving neural network optimizer convergence speed is a long-standing priority.
Recently, there has been a focus on quasi-Newton optimization methods, which have fewer hyperparameters compared to gradient-based methods and show improved convergence results in deterministic optimization.
We introduce PLSR1, a limited-memory partitioned quasi-Newton optimizer designed for optimizing a partially separable loss function, which is a sum of element loss functions of smaller dimensions.
PLSR1 aggregates limited-memory quasi-Newton approximations of individual element loss Hessians to better approximate the overall loss Hessian.<br>
To keep storage affordable, element function dimensions must be small compared to the total dimension.
Thus, we adapt standard neural network architectures by incorporating separable layers, creating a partitioned architecture (PSNet).
The numerical results compare the performance of several optimizers training the same partially-separable loss function on LeNet and PSNet architectures of similar sizes and effectiveness.
The graphs exhibit the optimizer accuracies over epochs, on both the MNIST and CIFAR10 datasets.
PLSR1 and an adaptative Nesterov variant show a training convergence comparable to Adam and outperforms LBFGS and SGD. </p>
2023-09-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30422023-11-15T16:19:54-05:002023-11-27T11:41:35-05:00G-2023-27 : The primal Benders decompositionEl Mehdi Er Raqabi, Issmail El Hallaoui, François Soumis
<p>Benders decomposition has been applied significantly to tackle large-scale optimization problems with complicating variables, which, when temporarily fixed, yield problems significantly easier to solve. Still, in its standard form, Benders decomposition, also known as the L-shaped method within the stochastic optimization community, shows several shortcomings. Leveraging the view of Benders decomposition as the dual of Dantzig-Wolfe decomposition, we propose the primal Benders decomposition. This method, a paradigm shift, is based on considering a reduced pool of complicating variables and inserting dynamically promising ones. We show that this method: (i) converges theoretically to optimality, (ii) requires only optimality cuts, referred to as Primal Benders cuts, to reach the optimal solution, (iii) benefits from the integrality of the subproblem, always viewed as a hindrance, and (iv) has an accelerated version with decreasing steps, and for which the number of iterations is, at most, the size of the complicating variables pool. We report promising computational results on the deterministic and stochastic facility location problems for which the proposed method reaches strictly optimal solutions.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30352023-10-25T10:01:26-04:002023-11-27T12:17:35-05:00G-2023-36 : Partially-separable loss to parallellize partitioned neural network trainingPaul Raynaud, Dominique Orban, Jean Bigeon
<p>Historically, the training of deep artificial neural networks has relied on parallel computing to achieve practical effectiveness.
However, with the increasing size of neural networks, they may no longer fit into the memory of a single computational unit.
To address this issue, researchers are exploring techniques to distribute the training process on powerful computational grids or less capable edge devices.
In computer vision, multiclass classification neural networks commonly use loss functions depending non-linearly on all class raw scores, making it impossible to compute independently partial derivatives of weight subsets during training.
In this work, we propose a novel approach for distributing neural network training computations using a <em>master(s)-workers</em> setup and a partially-separable loss function, which is a sum of <em>element</em> loss functions.
Each element loss only depends on a specific subset of variables, corresponding to a subpart of the neural network, whose derivatives can be computed independently.
It makes it possible to distribute every element loss and its corresponding neural network subpart across multiple workers, coordinated by one or several masters.
The master(s) will then aggregate worker contributions and will perform the optimization procedure before updating the workers.
To ensure that each element loss is parameterized by a small fraction of the neural network's weights, the architecture must be adapted, which is why we propose <em>separable layers</em>.
Numerical results show the viability of partitioned neural networks considering a partially-separable loss function using state-of-the-art optimizers.
Finally, we discuss the flexibility of a <em>partitioned</em> neural network architecture and how other deep learning techniques may reflect on it.
In particular, in a federated learning context, it can preserve worker privacy, as each worker possesses only a fragment of the network, and reduce communication.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30302023-10-03T15:28:39-04:002023-11-27T12:23:58-05:00G-2023-40 : MINARES: An iterative solver for symmetric linear systems Alexis Montoison, Dominique Orban, Michael A. Saunders
<p>We introduce an iterative solver named MINARES for symmetric linear systems <code>\(Ax \approx b\)</code>, where <code>\(A\)</code> is possibly singular.
MINARES is based on the symmetric Lanczos process, like MINRES and MINRES-QLP, but it minimizes <code>\(\|Ar_k\|\)</code> in each Krylov subspace rather than <code>\(\|r_k\|\)</code>, where <code>\(r_k\)</code> is the current residual vector.
When <code>\(A\)</code> is symmetric, MINARES minimizes the same quantity <code>\(\|Ar_k\|\)</code> as LSMR, but in more relevant Krylov subspaces, and it requires only one matrix-vector product <code>\(Av\)</code> per iteration, whereas LSMR would need two.
Our numerical experiments with MINRES-QLP and LSMR show that MINARES is a pertinent alternative on consistent symmetric systems and the most suitable Krylov method for inconsistent symmetric systems.
We derive properties of MINARES from an equivalent solver named CAR that is to MINARES as CR is to MINARES, is not based on the Lanczos process, and minimizes <code>\(\|Ar_k\|\)</code> in the same Krylov subspace as MINARES.
We establish that MINARES and CAR generate monotonic <code>\(\|x_k - x^{\star}\|\)</code>, <code>\(\|x_k - x^{\star}\|_A\)</code> and <code>\(\|r_k\|\)</code> when <code>\(A\)</code> is positive definite.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30292023-09-29T15:32:12-04:002023-11-27T12:02:50-05:00G-2023-29 : OCP optimizes its supply chain for AfricaEl Mehdi Er Raqabi, Ahmed Beljadid, Mohammed Ali Bennouna, Rania Bennouna, Latifa Boussaadi, Nizar El Hachemi, Issmail El Hallaoui, Michel Fender, Anouar Jamali, Nabil Si Hammou, François Soumis
<p>Operations research specialists at the OCP Group, the Mohammed VI Polytechnic University, and the Polytechnique Montreal operationalized a system optimizing OCP's supply chain downstream activities. The system simultaneously schedules production, inventory, and vessels while ensuring the highest demand fulfillment. Therefore, it has become central to the OCP planning process, fundamentally transforming the supply chain and operations management within the group. Planners now use the optimizer's solutions and insights to improve plans. The system was initially a bottleneck curbing the use of other supply chain management tools. However, after its operationalization, OCP management credits the system with providing operational benefits, contributing to over a $240 million increase in annual turnover.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30282023-09-26T15:37:35-04:002023-11-27T12:22:34-05:00G-2023-39 : Revisiting column-generation-based matheuristic for learning classification treesKrunal Kishor Patel, Guy Desaulniers, Andrea Lodi
<p>Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal trees in terms of accuracy. Other discrete optimization models in the literature address the optimality problem but only work well on relatively small datasets. Firat et al.(2020) proposed a column-generation-based heuristic approach for learning decision trees. This approach improves scalability and can work with large datasets. In this paper, we describe improvements to this column generation approach. First, we modify the subproblem model to significantly reduce the number of subproblems in multiclass classification instances. Next, we show that the data-dependent constraints in the master problem are implied, and use them as cutting planes. Furthermore, we describe a separation model to generate data points for which the linear programming relaxation solution violates their corresponding constraints. We conclude by presenting computational results that show that these modifications result in better scalability.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30272023-09-25T14:43:00-04:002023-11-27T12:19:04-05:00G-2023-37 : The indefinite proximal gradient methodGeoffroy Leconte, Dominique Orban
<p>We introduce a variant of the proximal gradient method in which the quadratic term is diagonal but may be indefinite, and is safeguarded by a trust region.
Our method is a special case of the proximal quasi-Newton trust-region method of Aravkin et al. (2022).
We provide closed-form solution of the step computation in certain cases where the nonsmooth term is separable and the trust region is defined in the infinity norm, so that no iterative subproblem solver is required.
Our analysis expands upon that of Aravkin et al. (2022) by generalizing the trust-region approach to problems with bound constraints.
We provide an efficient open-source implementation of our method, named TRDH, in the Julia language in which Hessians approximations are given by diagonal quasi-Newton updates.
TRDH evaluates one standard proximal operator and one indefinite proximal operator per iteration.
We also analyze and implement a variant named iTRDH that performs a single indefinite proximal operator evaluation per iteration.
We establish that iTRDH enjoys the same asymptotic worst-case iteration complexity as TRDH.
We report numerical experience on unconstrained and bound-constrained problems, where TRDH and iTRDH are used both as standalone and subproblem solvers.
Our results illustrate that, as standalone solvers, TRDH and iTRDH improve upon the quadratic regularization method R2 of Aravkin et al. (2022) but also sometimes upon their quasi-Newton trust-region method, referred to here as TR-R2, in terms of smooth objective value and gradient evaluations.
On challenging nonnegative matrix factorization, binary classification and data fitting problems, TRDH and iTRDH used as subproblem solvers inside TR improve upon TR-R2 for at least one choice of diagonal approximation.</p>
2023-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/30262023-09-22T16:20:47-04:002023-11-27T12:14:35-05:00G-2023-34 : Tactical wireless network design with multi-beam antennasVincent Perreault, Alain Hertz, Andrea Lodi
<p>Tactical wireless networks are used in cases where standard telecommunication networks are unavailable or unusable, e.g. disaster relief operations. We fully model the design of these tactical networks as a nested optimization problem with a physically-modeled signal and three elementary data traffic scenarios. Specifically, we consider the problem for tree networks with two channels, four possible frequencies and multi-beam antennas of 24 beams. We propose a multi-level algorithm that uses 1) a Tabu Beam Search for the topology design, 2) a simple geometrical heuristic for the antenna configuration and 3) exact methods, heuristics, meta-heuristics and bounding procedures for the network configuration. Synthetic experiments suggest that our method finds very good networks and that it significantly outperforms a previous algorithm.</p>
2023-08-01GERADinfo@gerad.ca