In this paper, we study the k-labeled spanning forest problem (kLSF). The input for this problem is an undirected graph with labeled edges and a positive integer k. The goal is to find a spanning forest of the graph with at most$k$different labels associated with the edges, minimizing the number of components. kLSF finds practical applications in different scenarios related to networks design and telecommunications. Solving it may help to reduce the negative impact of electromagnetic fields exposure on the population health or to increase profits of internet management companies, among others. The interest in kLSF is not only practical but also theoretical since the problem generalizes the best-known NP-hard minimum labeling spanning tree problem (MLST). To approach kLSF, we propose a fix-and-optimize matheuristic that was tested over several instances, achieving high-quality solutions in reasonable computational time. When compared to the best-known algorithms in the literature, our matheuristic outperformed the other proposals in most cases, finding better solutions in less computational time for the most challenging instances.

We employ a state-of-the-art Mixed-Integer Linear Programming (MILP) formulation of the literature, and our enhanced version of it, to solve a classical instance dataset for the Guillotine 2D variants of both the Knapsack Problem (G2KP) and the Bin Packing Problem (G2BPP). The results with the G2KP allow us to establish our reimplementation as fair to the original implementation (not available). As far as we know, before this work the considered instances have never been optimally solved for the considered variant of the G2BPP, i.e., the unlimited stages variant, only for the simpler two-staged variant. We also believe this work is the first to gather empirical results of a pure MILP formulation for the G2BPP, even considering the possibility of adaptation was previously known. As we focus on pure and adaptable formulations, we do not employ pricing frameworks or problem-specific heuristics in this short paper. We examine the differences in the running times caused by the change of problems, formulations, number of threads, and, for a subset of the runs, the solver random seed. Some of our findings follow: except for a few G2BPP instances, our enhanced formulation has better timings; 8 of the 30 considered instances have better solutions for unlimited stages G2BPP than for the two-staged G2BPP; the speed-up with 12 threads is smaller than expected and, for the G2BPP, the solver random seed may have a larger effect than the number of threads.

Maritime Inventory Routing Problem (MIRP) is a challenging combinatorial problem in which decision solutions evolve vessels route and schedule, besides the inventory management at the ports along a limited planning horizon. Common solution approaches for solving MIRPs use matheuristics combining heuristic elements and mathematical programming for obtaining high-quality solutions in relatively short processing time. The performance of such approaches can be compromised if the problem size grows considerably. To provide an alternative approach for solving larger MIRPs, we propose a multi-start metaheuristic capable of producing several solutions for the problem in short processing time. Additionally, we developed a large neighborhood search for improving a subset of the generated solutions, which are then used to build a reduced mixed-integer problem which is solved by a mathematical solver. Computational results demonstrated that our algorithm can obtain solutions in short processing time, compared to the current solutions methods, and it can solve larger problem instances, in which no solutions were known.

Scheduling the activities for a group of physicians in a hospital is a recurring activity that impacts both the health-related costs and the quality of services provided by these professionals. Mismanagement of scheduling could lead to the use of excessive overtime to achieve health demands, increasing the costs. Moreover, physicians assigned to a stressful task over long periods may result in a reduction in their performance and cause a sense of injustice towards other physicians. The use of algorithms makes scheduling more agile and with better results when compared to the manual execution. This work addresses a physician rostering problem applied to the Hospital de Clínicas de Porto Alegre (HCPA), in Brazil. Instances were generated based on data provided by the hospital and approached employing the Coin-OR (CBC) solver and a VNS heuristic. Both strategies were selected to evaluate the performance of an exact integer programming and a heuristic in different instances, classified by demand and availability of physicians.

We applied a Biased Random Key Genetic Algorithm (BRKGA) to solve the Vehicle Routing Problem with Time Windows and Synchronization Constraints. Additionally, both vehicles and clients are skilled, and each client can require up to two distinct skills to be serviced. On double-skilled clients, the operations of each skill should be performed by different vehicles, either simultaneously or respecting a precedence order. Those requirements introduce nonlinearities on the problem, in the sense that a small change on a single route potentially impacts all the other routes of the solution, making it hard to define an effective local search procedure. To circumvent this difficulty, we approached the problem using a genetic algorithm that evolves the sequence in which the services are inserted into the routes. We assessed the performance of our solution method using instances from the literature of the home health care problem. The genetic algorithm outperformed the previous best-known solutions found by a fix-and-optimize matheuristic by up to 25%, using less than half of computational times reported previously. The BRKGA demonstrated to be able to perform well both in exploration and exploitation in the solution space of the problem.

Network virtualization is a growing trend in the implementation of Internet infrastructures. The Virtual Network Embedding problem is one of the challenges in the virtualization of physical networks. This work shows that finding a feasible solution to this problem is NP‐Hard. However, in practice, it can be solved to optimality by exploiting the problem structure. We propose a new branch‐and‐price algorithm applied to a flow‐based formulation of the problem, and present an extensive computational study performed for instances of distinct topologies and sizes. The results presented attest the efficiency of the branch‐and‐price algorithm in solving the problem.

Cloud computing has recently emerged as a new technology for hosting and supplying services over the Internet. This technology has brought many benefits, such as eliminating the need for maintaining expensive computing hardware and allowing business owners to start from small and increase resources only when there is a rise in service demand. With an increasing demand for cloud computing, providing performance guarantees for applications that run over cloud become important. Applications can be abstracted into a set of virtual machines with certain guarantees depicting the quality of service of the application. In this paper, we consider the placement of these virtual machines across multiple data centers, meeting the quality of service requirements while minimizing the bandwidth cost of the data centers. This problem is a generalization of the NP-hard Generalized Quadratic Assignment Problem (GQAP). We formalize the problem and propose a novel algorithm based on a biased random-key genetic algorithm (BRKGA) to find near-optimal solutions for the problem. The experimental results show that the proposed algorithm is effective in quickly finding feasible solutions and it produces better results than a baseline aproach provided by a commercial solver and a multi-start algorithm.

Network Function Virtualization (NFV) is a promising network architecture concept, in which virtualization technologies are employed to manage networking functions via software as opposed to having to rely on hardware to handle these functions. By shifting dedicated, hardware-based network function processing to software running on commoditized hardware, NFV has the potential to make the provisioning of network functions more flexible and cost-effective, to mention just a few anticipated benefits. Despite consistent initial efforts to make NFV a reality, little has been done towards efficiently placing virtual network functions and deploying service function chains (SFC). With respect to this particular research problem, it is important to make sure resource allocation is carefully performed and orchestrated, preventing over- or under-provisioning of resources and keeping end-to-end delays comparable to those observed in traditional middlebox-based networks. In this paper, we formalize the network function placement and chaining problem and propose an Integer Linear Programming (ILP) model to solve it. Additionally, in order to cope with large infrastructures, we propose a heuristic procedure for efficiently guiding the ILP solver towards feasible, near-optimal solutions. Results show that the proposed model leads to a reduction of up to 25% in end-to-end delays (in comparison to chainings observed in traditional infrastructures) and an acceptable resource over-provisioning limited to 4%. Further, we demonstrate that our heuristic approach is able to find solutions that are very close to optimality while delivering results in a timely manner.

Network virtualization has become increasingly popular in recent years. It has the potential to allow timely handling of network infrastructure requests and, after instantiated, their lifecycle. In addition, it enables improved physical resource utilization. However, the use of network virtualization in large-scale, real environments depends on the ability to adequately map virtual routers and links to physical resources, as well as to protect virtual networks against security threats. With respect to security, confidentiality and privacy mechanisms have become essential in light of recent discoveries related to pervasive electronic surveillance. In this paper we propose a heuristic method for virtual network embedding with security support. The method features precise modeling of overhead costs of security mechanisms and handles incoming requests in an online manner. Additionally, we present a detailed performance comparison between the proposed heuristic and an optimization model based on the same problem. The obtained results demonstrate that the heuristic method is able to find feasible mappings in the order of seconds even when dealing with large network infrastructures, while the optimization model is limited to smaller networks.

Three-dimensional (3-D) protein structure determination has become an important area of research in structural bioinformatics. Proteins are responsible for the execution of different functions in the cell. Understanding the 3-D structure provides important information about the protein function. Many computational methodologies for the protein structure prediction were developed along the last 20 years, but the problem still challenges researchers because the complexity and high dimensionality of its large search space. In this article we present a strategy for reducing the search space explored by heuristic methods for solving the problem taken into consideration previous occurrences of amino acid residues in a well known protein database (PDB). We propose a genetic algorithm that takes advantages of this kind of information, reducing considerable the search space, allowing the algorithm to save time with less promising solutions. A simple Local Search operator helps the GA to intensify the search of the 3-D protein conformational space. We demonstrate the effectiveness of the strategy with a set of experimental results.

Network virtualization is a mechanism that allows the coexistence of multiple virtual networks on top of a single physical substrate. One of the research challenges addressed recently in the literature is the efficient mapping of virtual resources on physical infrastructures. Although this challenge has received considerable attention, state-of-the-art approaches present, in general, a high rejection rate, i.e., the ratio between the number of denied virtual network requests and the total amount of requests is considerably high. In this work, we investigate the relationship between the quality of virtual network mappings and the topological structures of the underlying substrates. Exact solutions of an online embedding model are evaluated under different classes of network topologies. The obtained results demonstrate that the employment of physical topologies that contain regions with high connectivity significantly contributes to the reduction of rejection rates and, therefore, to improved resource usage.

Although network virtualization can improve security by isolating traffic from different networks, routers and links are still vulnerable to attacks on the underlying network. High capacity physical links, in particular, constitute good targets since they may be important for a large number of virtual networks. Previous work protects virtual networks by setting aside backup resources. Although effective, this solution increases the cost to infrastructure providers. In this paper, we present a virtual network embedding approach which enables resilience to attacks and efficiency in resource utilization. Our approach is two-folded: while a preventive strategy embeds virtual links into multiple substrate paths, a reactive strategy attempts to reallocate any capacity affected by an underlying DoS attack. Since the embedding problem is NP-Hard, we devise a Simulated Annealing meta-heuristic to solve it efficiently. Results show our solution can provide resilience to attacks at a lower cost.

Pattern databases have been successfully applied to several problems. Their use assumes that the goal state is known, and once the pattern database is built, commonly it can be used by all instances. However, in Sokoban, before solving the puzzle, the goal position of each stone is unknown. Moreover, each Sokoban instance has its own state space search. In this paper we apply pattern databases to Sokoban. The proposed approach uses an instance decomposition, that allows multiple possible goal states to be abstracted into a single state. Thus, an instance dependent pattern database is employed. Experiments with the standard set of instances show that the proposed approach overcomes the current best lower bounds in initial states for several instances. Furthermore, three of these new best lower bounds match exactly with the optimal solution length. Finally, we run experiments of 5 million explored states for each instance. Nine instances were solved with optimality guarantees, while only four instances were solved under the same conditions by previous methods.

We study the effect of perturbations on the Price of Anarchy for the Traffic Assignment Problem. Adopting the smoothed analysis approach, we randomly perturb the latency functions of the given network and estimate the expected Price of Anarchy on the perturbed instances. We provide both theoretical and experimental results that show that the Smoothed Price of Anarchy is of the same order of magnitude as the original one.

One of the main research problems in Structural Bioinformatics is related to the prediction of three-dimensional structures (3-D) of polypeptides or proteins. The rate at which amino acid sequences are identified is increasing faster than the 3-D protein structure determination by experimental methods. Computational prediction methods have been developed during the last years, but the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. In this article we present a hybrid genetic algorithm for the Protein Structure Prediction (PSP) Problem. A genetic algorithm is combined with a structured population, and it is hybridized with a path-relinking procedure that helps the algorithm to scape from local minima. We perform a set of experiments and show that the proposed hybrid genetic algorithm is effective in finding good quality solutions for the PSP Problem.

Cellular automata models for traffic movement assume that vehicles are particles without routes. However, if one is interested in analysing microscopic properties, it is necessary to assign a route to each trip. This paper discusses the latest developments in the ITSUMO traffic simulator. These developments aim at modeling more sophisticated drivers’ behaviors such as en-route decision-making. They were tested in two scenarios, one being a real-world traffic network. We extensively discuss the effects of the use of various routing algorithms, as well as ration demand/capacity, control measures, network topologies, and re-planning strategies.

One of the main research problems in Structural Bioinformatics is the analysis and prediction of three-dimensional structures (3-D) of polypeptides or proteins. The 1990's Genome projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures has not followed the same trend. The determination of protein structure is experimentally expensive and time consuming. This makes scientists largely dependent on computational methods that can predict correct 3-D protein structures only from extended and full amino acid sequences. Several computational methodologies and algorithms have been proposed as a solution to the Protein Structure Prediction (PSP) problem. We briefly describe the AI techniques we have been used to tackle this problem.

Dynamic shortest-path algorithms update the shortest paths taking into account a change in an arc weight. This paper describes a new generic technique that allows the reduction of heap sizes used by several dynamic single-destination shortest-path algorithms. For unit weight changes, the updates can be done without heaps. These reductions almost always reduce the computational times for these algorithms. In computational testing, several dynamic shortest-path algorithms with and without the heap-reduction technique are compared. Speedups of up to a factor of 1.8 were observed using the heap-reduction technique on random weight changes and of over a factor of five on unit weight changes. We compare as well with Dijkstra's algorithm, which recomputes the paths from scratch. With respect to Dijkstra's algorithm, speedups of up to five orders of magnitude are observed.

A wireless sensor network (WSN) is energy constrained, and the extension of its lifetime is one of the most important issues in its design. Usually, a WSN collects a large amount of data from the environment. In contrast to the conventional remote sensing - based on satellites that collect large images, sound files, or specific scientific data - sensor networks tend to generate a large amount of sequential small and tuple- oriented data from several nodes, which constitutes data streams. In this work, we propose and evaluate two algorithms based on data stream, which use sampling and sketch techniques, to reduce data traffic in a WSN and, consequently, decrease the delay and energy consumption. Specifically, the sampling solution, provides a sample of only log n items to represent the original data of n elements. Despite of the reduction, the sampling solution keeps a good data quality. Simulation results reveal the efficiency of the proposed methods by extending the network lifetime and reducing the delay without loosing data representativeness. Such a technique can be very useful to design energy-efficient and time-constrained sensor networks if the application is not so dependent on the data precision or the network operates in an exception situation (e.g., there are few resources remaining or there is an urgent situation).

This work presents a sampling data stream algorithm for wireless sensor networks (WSNs). The proposed algorithm is based on sampling techniques applied to data histograms created from original data streams acquired by sensor nodes. As a result, the algorithm provides a sample of only log n items to represent the original data of n elements. We show that by using our algorithm, we can save energy and reduce delay in WSN applications in different scenarios while keeping a good data quality.

Abstract Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path‐based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing links on shortest paths to a given destination, it splits traffic evenly over these links. It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as arc or router failures. In such situations, IP traffic is rerouted through the shortest paths not traversing the affected part of the network. This article addresses the issue of assigning OSPF weights and multiplicities to each arc, aiming to design efficient OSPF‐routed networks with minimum total weighted multiplicity (multiplicity multiplied by the arc length) needed to route the required demand and handle any single arc or router failure. The multiplicities are limited to a discrete set of values, and we assume that the topology is given. We propose an evolutionary algorithm for this problem, and present results applying it to several real‐world problem instances. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 51–64 2007

We present two space bounded random sampling algorithms that compute an approximation of the number of triangles in an undirected graph given as a stream of edges. Our first algorithm does not make any assumptions on the order of edges in the stream. It uses space that is inversely related to the ratio between the number of triangles and the number of triples with at least one edge in the induced subgraph, and constant expected update time per edge. Our second algorithm is designed for incidence streams (all edges incident to the same vertex appear consecutively). It uses space that is inversely related to the ratio between the number of triangles and length 2 paths in the graph and expected update time O(log |V |·(1+s ·|V |/|E|)), where s is the space requirement of the algorithm. These results significantly improve over previous work [20, 8]. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size and so they provide a basic tool to analyze the structure of large graphs. They have many applications, for example, in the discovery of Web communities, the computation of clustering and transitivity coefficient, and discovery of frequent patterns in large graphs. We have implemented both algorithms and evaluated their performance on networks from different application domains. The sizes of the considered graphs varied from about 8, 000 nodes and 40, 000 edges to 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with parameter s = 1, 000, 10, 000, 100, 000, 1, 000, 000 to evaluate running time and approximation guarantee. Both algorithms appear to be time efficient for these sample sizes. The approximation quality of the first algorithm was varying significantly and even for s = 1, 000, 000 we had more than 10% deviation for more than half of the instances. The second algorithm performed much better and even for s = 10, 000 we had an average deviation of less than 6% (taken over all but the largest instance for which we could not compute the number of triangles exactly). Copyright 2006 ACM.

Wikipedia is an online encyclopedia, available in more than 100 languages and comprising over 1 million articles in its English version. If we consider each Wikipedia article as a node and each hyperlink between articles as an arc we have a "Wikigraph", a graph that represents the link structure of Wikipedia. The Wikigraph differs from other Web graphs studied in the literature by the fact that there are explicit timestamps associated with each node's events. This allows us to do a detailed analysis of the Wikipedia evolution over time. In the first part of this study we characterize this evolution in terms of users, editions and articles; in the second part, we depict the temporal evolution of several topological properties of the Wikigraph. The insights obtained from the Wikigraphs can be applied to large Web graphs from which the temporal data is usually not available.

Abstract Intradomain traffic engineering aims to make more efficient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS‐IS (Intermediate System‐Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link weights assigned by the network operator. Each router in the autonomous system computes shortest paths and creates destination tables used to direct each packet to the next router on the path to its final destination. Given a set of traffic demands between origin‐destination pairs, the OSPF weight setting problem consists of determining weights to be assigned to the links so as to optimize a cost function, typically associated with a network congestion measure. In this article, we propose a genetic algorithm with a local improvement procedure for the OSPF weight‐setting problem. The local improvement procedure makes use of an efficient dynamic shortest path algorithm to recompute shortest paths after the modification of link weights. We test the algorithm on a set of real and synthetic test problems, and show that it produces near‐optimal solutions. We compare the hybrid algorithm with other algorithms for this problem illustrating its efficiency and robustness. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(1), 36–56 2005