Browsing by Author "Mateus, Geraldo Robson"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    Conflict graphs in mixed-integer linear programming : preprocessing, heuristics and cutting planes.
    (2020) Brito, Samuel Souza; Santos, Haroldo Gambini; Santos, Haroldo Gambini; Fonseca, George Henrique Godim da; Mateus, Geraldo Robson; Aragão, Marcus Vinicius Soledade Poggi de; Toffolo, Túlio Ângelo Machado
    This thesis addresses the development of con ict graph-based algorithms for MixedInteger Linear Programming, including: (i) an e cient infrastructure for the construction and manipulation of con ict graphs; (ii) a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19.65% stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities; (v) two diving heuristics capable of generating integer feasible solutions in restricted execution times. Additionally, we generated a new version of the COIN-OR Branch-and-Cut (CBC) solver by including our con ict graph infrastructure, preprocessing routine and cut separators. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23.53%.
  • No Thumbnail Available
    Item
    Modeling and analysis of different reconfiguration strategies for virtual network function placement and chaining with service classes identification.
    (2023) Araújo, Samuel Moreira Abreu; Souza, Fernanda Sumika Hojo de; Mateus, Geraldo Robson
    The Virtual Network Function Placement and Chaining problem (VNF-PC) is an important part of the Network Functions Virtualization (NFV) based-technologies implementation. VNF-PC problem focuses on the allocation of customer demands on the Substrate Network. Aiming to evaluate the impact of diverse modeling, various reconfiguration strategies based on implicit steps in solving the VNF-PC are proposed: resizing virtual network instances, re-routing chaining, and repositioning Network Functions (NF) instances on different servers. In addition, this work analyzes, compares, and discusses the advantages and disadvantages of each proposed reconfiguration strategy in an online scenario. Traditionally, VNF-PC solutions from literature process requests generated at random and do not take into account real-world demands. Complementing the analyses of reconfiguration strategies, works from the literature are surveyed to identify commonly used Network Services (NS). Following that, these NS are classified into service classes, and used to generate realistic requests to be mapped in the experimental stage of the reconfiguration approaches. The experiments are conducted using realistic requests and a real-world network topology. An Integer Linear Programming model is used to process the requests. Simulations show that repositioning NF instances can generate up to ≈ 25% more profit than reconfiguring only the VNF instances, but the processing time increases by up to 99.99%. On the other hand, resizing virtual network instances and rerouting the chaining had no significant impact on runtime.
  • No Thumbnail Available
    Item
    On a vector space representation in genetic algorithms for sensor scheduling in wireless sensor networks.
    (2014) Martins, Flávio Vinícius Cruzeiro; Carrano, Eduardo Gontijo; Wanner, Elizabeth Fialho; Takahashi, Ricardo Hiroshi Caldeira; Mateus, Geraldo Robson; Nakamura, Fabiola Guerra
    Recent works raised the hypothesis that the assignment of a geometry to the decision variable space of a combinatorial problem could be useful both for providingmeaningful descriptions of the fitness landscape and for supporting the systematic construction of evolutionary operators (the geometric operators) that make a consistent usage of the space geometric properties in the search for problem optima. This paper introduces some new geometric operators that constitute the realization of searches along the combinatorial space versions of the geometric entities descent directions and subspaces. The new geometric operators are stated in the specific context of the wireless sensor network dynamic coverage and connectivity problem (WSN-DCCP). A genetic algorithm (GA) is developed for the WSN-DCCP using the proposed operators, being compared with a formulation based on integer linear programming (ILP) which is solved with exact methods. That ILP formulation adopts a proxy objective function based on the minimization of energy consumption in the network, in order to approximate the objective of network lifetime maximization, and a greedy approach for dealing with the system’s dynamics. To the authors’ knowledge, the proposed GA is the first algorithm to outperform the lifetime of networks as synthesized by the ILP formulation, also running in much smaller computational times for large instances.