A sampling-based multi-objective iterative robust optimization method for Bandwidth Packing Problem. (1st October 2022)

• Record Type: Journal Article
• Authors: Butkeraites, Renan Brito Cano; de Salles Neto, Luiz Leduino; Gendreau, Michel
• Is Part Of: Expert systems with applications. Volume 203(2022)
• Publication Date: 2022-10-01
• Subjects: Optimization -- Robustness and sensitivity analysis -- Monte Carlo simulation -- Bandwidth Packing Problem; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2022.117337
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: This paper proposes a new paradigm for solving robust optimization problems using sampling within a multi-objective framework to solve the Bandwidth Packing Problem, the Sampling-based Robust Optimization Method (SIROM). The key feature of this new approach is that it performs robust optimization without having to specify a priori an uncertainty budget. The new method thus provides the decision-maker a Pareto frontier composed by the best solutions (objective function value versus uncertainty protection) found by exploring the topology of the uncertain parameter set. A general framework based on unsupervised learning is built for the method, which can be used to find solutions for linear, non-linear, and integer programming problems under parametric uncertainty. The general idea is to sample possible realizations of a given uncertain parameter vector and solve each problem associated with all those parameters. After that, we cluster the realizations based on optimal constraint and objective function values. All "similar" cases are grouped together to form problem sets with few "representative" realizations that we can solve and, in analyzing the quality of the optimal solution, use to compose a Pareto frontier. The framework is applied to solve the Bandwidth Packing Problem under uncertain demand and we compare results to a methodology based on Bertsimas and Sim robust optimization approach. The results demonstrate that the proposed method performs better than previously existing ones. The code and instances used to perform the computational experiment are available in https://github.com/butkeraites/sirom_bpp . Highlights: New multi-objective paradigm for solving Robust Optimization problems. Does not require continuity, nor convexity from the objective function. Find solutions associated with different robustness levels automatically. A method that can be applied to NLPs.