A branch-and-cut algorithm for the hub location and routing problem

We study the hub location and routing problem where we decide on the location of hubs, the allocation of nodes to hubs, and the routing among the nodes allocated to the same hubs, with the aim of minimizing the total transportation cost. Each hub has one vehicle that visits all the nodes assigned to it on a cycle. We propose a mixed integer programming formulation for this problem and strengthen it with valid inequalities. We devise separation routines for these inequalities and develop a branch-and-cut algorithm which is tested on CAB and AP instances from the literature. The results show that the formulation is strong and the branch-and-cut algorithm is able to solve instances with up to 50 nodes.     

On the hop-constrained survivable network design problem with reliable edges

In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge costs and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum cost set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. In addition, we consider here a subset of reliable edges that are not subject to failure. We study two variants: a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost. We adapt for the two variants an extended formulation proposed in Botton, Fortz, Gouveia, Poss (2011) [1] for the case without reliable edges. As before, we use Benders decomposition to accelerate the solving process. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network.     

Multi-period design of survivable wireless access networks under capacity constraints

Design of survivable wireless access networks plays a key role in the overall design of a wireless network. In this research, the multi-period design of a wireless access network under capacity and survivability constraints is considered. Given the location of the cells and hubs, the cost of interconnection, and the demands generated by the cells, the goal of the designer is to find the best interconnection between cells and hubs so that the overall connection cost is minimized and the capacity and the survivability constraints are met. Integer programming formulations for this problem are proposed and the problems are solved using heuristic methods. Using different combination of network sizes, demand patterns and various time periods, a number of numerical experiments are conducted and all of them are found to yield high quality solutions.     

A branch-and-cut algorithm for quadratic assignment problems based on linearizations

The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed for instances of size larger than 15 have been generally unsuccessful even though successful implementations have been reported on some test problems from the QAPLIB up to size 36. In this study, we focus on the Koopmans–Beckmann formulation and exploit the structure of the flow and distance matrices based on a flow-based linearization technique that we propose. We present two new IP formulations based on the flow-based linearization technique that require fewer variables and yield stronger lower bounds than existing formulations. We strengthen the formulations with valid inequalities and report computational experience with a branch-and-cut algorithm. The proposed method performs quite well on QAPLIB instances for which certain metrics (indices) that we proposed that are related to the degree of difficulty of solving the problem are relatively high (?0.3$?0.3$). Many of the well-known instances up to size 25 from the QAPLIB (e.g. nug24, chr25a) are in this class and solved in a matter of days on a single PC using the proposed algorithm.     

A branch-and-cut algorithm for the partitioning-hub location-routing problem

We introduce the Partitioning-Hub-Location-Routing Problem (PHLRP), a hub location problem involving graph partitioning and routing features. The PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. This problem finds applications in deployment of an Internet Routing Protocol called Intermediate System–Intermediate System (ISIS), and strategic planning of LTL ground freight distribution systems. We present an Integer Programming (IP) model for solving exactly the PHLRP and explore possible valid inequalities to strengthen it. Computational experiments prove the effectiveness of our model which is able to tackle instances of PHLRP containing up to 20 vertices.     

A column generation and branch-and-cut algorithm for the channel assignment problem

We present an exact algorithm for solving the channel assignment problem in cellular telephony networks. This problem consists of assigning sets of channels to the network cells in such a way that the channel demand is satisfied, while avoiding co-channel interference and adjacent channel interference and respecting the channel spacing constraint for each antenna. In a previous article [Jaumard B, Marcotte O, Meyer C, Vovor T. Comparison of column generation models for channel assignment in cellular networks. Discrete Applied Mathematics 2002; 118:299–322], we formulated this problem as a covering problem in two different ways and compared these two formulations and another formulation both from a theoretical and computational point of view (by solving their linear relaxations). In the present article we focus on the best set covering formulation, where the subsets are sets of cells that can be assigned the same channel, and we actually solve two versions of the integer program. In the first version, we seek to minimize the unmet demand, while in the second, we seek to minimize the overall interference while assigning the required number of channels to each cell. In either version, the integer program is solved by an algorithm combining the column generation technique and a branch-and-cut scheme. Finally, we present the solutions produced by these algorithms for some instances of European networks and real-life instances supplied by the Bell Mobilité company.     

A parallel algorithm with enhancements via partial objective value cuts for cluster-based wireless sensor network design

In this paper, we develop a parallel algorithm for the solution of an integrated topology control and routing problem in Wireless Sensor Networks (WSNs). After presenting a mixed-integer linear optimization formulation for the problem, for its solution, we develop an effective parallel algorithm in a Master–Worker model that incorporates three parallelization strategies, namely low-level parallelism, domain decomposition, and multiple search (both cooperative and independent) in a single Master–Worker framework.     

A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB.     

The generalized fixed-charge network design problem

In this paper we present the generalized fixed-charge network design (GFCND) problem. The GFCND problem is an instance of the so-called generalized network design problems. In such problems, clusters instead of nodes have to be interconnected by a network. The network interconnecting the clusters is a fixed-charge network, and thus the GFCND problem generalizes the fixed-charge network design problem. The GFCND problem is related to the more general problem of designing hierarchical telecommunication networks.     

Bicriteria network design using a spanning tree-based genetic algorithm

The optimization problems in communication networks have received the attention of many researchers in such related fields as network designer, network analysis, and network administration. The use of computer communication networks has been increasing rapidly in order to share expensive hardware/software resources and provide access to main systems from distant locations. These network problems have many applications in telecommunications, computer networking, and related domains in electric, gas, and sewer networks. In computer networking, LANs (local area networks) are commonly used as the communication infrastructure that meets the demands of users in the local environment. These networks typically consist of several LAN segments connected together via bridges. The use of these transparent bridges requires.loop-free paths between LAN segments. Therefore, only spanning tree topologies can be used as active LAN configurations. Recently, genetic algorithms have greatly advanced in related research fields such as network optimization problems, combinatorial optimization, multiobjective optimization, and so on. Genetic algorithms have also received a great deal of attention because of their ability as optimization techniques for many real-world problems. In this paper, we attempt to solve the LAN topology design problem with bicriteria which minimize the cost and average message delay using genetic algorithms, and propose a method of searching the Pareto solutions. We also employ the Prüfer number in order to represent the chromosomes, because the interconnection between the network service centers must yield spanning tree configurations. Finally, we conduct experiments to certify the quality of the networks designs obtained by using genetic algorithms. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

Availability guarantee in survivable WDM mesh networks: A time perspective

Since availability is an important quality-of-service (QoS) factor in mesh networks, different service provision with availability guarantee have been discussed by many researchers in the literature. However, with the increasing demand for mesh networks to support both data and real-time multimedia traffic, multiple availability requirements may be made during one connection’s holding time. The traffic of different availability requirements has to be routed by special wavelengths. In this paper we discuss availability guarantee in mesh networks from the perspective of time and propose a new scheme called Time Aware Availability Guarantee (TAAG). The routing paths of each connection are adjusted according to the different availability requirements in different time spans. Simulation results show that the proposed scheme outperforms the previous schemes such as Time Unaware Availability Guarantee (TUAG) in terms of resource utilization, blocking probability and traffic throughput.     

An optimization algorithm for the inventory routing problem with continuous moves

The typical inventory routing problem deals with the repeated distribution of a single product from a single facility with an unlimited supply to a set of customers that can all be reached with out-and-back trips. Unfortunately, this is not always the reality. We focus on the inventory routing problem with continuous moves, which incorporates two important real-life complexities: limited product availabilities at facilities and customers that cannot be served using out-and-back tours. We need to design delivery tours spanning several days, covering huge geographic areas, and involving product pickups at different facilities. We develop an integer programming based optimization algorithm capable of solving small to medium size instances. This optimization algorithm is embedded in local search procedure to improve solutions produced by a randomized greedy heuristic. We demonstrate the effectiveness of this approach in an extensive computational study.     

A surrogate-based optimization algorithm for network design problems

Network design problems (NDPs) have long been regarded as one of the most challenging problems in the field of transportation planning due to the intrinsic non-convexity of their bi-level programming form. Furthermore, a mixture of continuous/discrete decision variables makes the mixed network design problem (MNDP) more complicated and difficult to solve. We adopt a surrogate-based optimization (SBO) framework to solve three featured categories of NDPs (continuous, discrete, and mixed-integer). We prove that the method is asymptotically completely convergent when solving continuous NDPs, guaranteeing a global optimum with probability one through an indefinitely long run. To demonstrate the practical performance of the proposed framework, numerical examples are provided to compare SBO with some existing solving algorithms and other heuristics in the literature for NDP. The results show that SBO is one of the best algorithms in terms of both accuracy and efficiency, and it is efficient for solving large-scale problems with more than 20 decision variables. The SBO approach presented in this paper is a general algorithm of solving other optimization problems in the transportation field.     

An efficient link allocation algorithm for survivable ATM-based personal communication networks

The integration of the issue of survivability of wireless networks in the design process of the backbone network is addressed in this paper. The effectiveness of this integration plays a critical role in the success of the wireless network and the satisfaction of its mobile users. In this paper, we consider the design problem of allocating the backbone links in ATM-based personal communication networks (PCNs) that are survivable under single backbone link failures. Survivability is achieved by selecting two link-disjoint routes in the backbone network between every pair of ATM switches. We also take the novel approach of not only minimizing the diameter of the network as a primary objective but also minimizing the total length of the network as a secondary objective. We propose a new heuristic algorithm to optimize the design of the network based on both objectives. We report the results of an extensive simulation study that show that our algorithm generates backbone networks that can withstand single link failures, have shorter average diameters and smaller total lengths and achieve a higher percentage of admitted calls under a mobile environment.     

Lower bounds for large traveling umpire instances: New valid inequalities and a branch-and-cut algorithm

Given a double round-robin tournament, the Traveling Umpire Problem (TUP) seeks to assign umpires to the games of the tournament while minimizing the total distance traveled by the umpires. The assignment must satisfy constraints that prevent umpires from seeing teams and venues too often, while making sure all games have umpires in every round, and all umpires visit all venues. We propose a new integer programming model for the TUP that generalizes the two best existing models, introduce new families of strong valid inequalities, and implement a branch-and-cut algorithm to solve instances from the TUP benchmark. When compared against published state-of-the-art methods, our algorithm significantly improves all best known lower bounds for large TUP instances (with 20 or more teams).     

Capacitated closed-loop supply chain network design under uncertainty

This study optimizes the design of a closed-loop supply chain network, which contains forward and reverse directions and is subject to uncertainty in demands for new & returned products. To address uncertainty in decision-making, we formulate a two-stage stochastic mixed-integer non-linear programming model to determine the distribution center locations and their corresponding capacity, and new & returned product flows in the supply chain network to minimize total design and expected operating costs. We convert our model to a conic quadratic programming model given the complexity of our problem. Then, the conic model is added with certain valid inequalities, such as polymatroid inequalities, and extended with respect to its cover cuts so as to improve computational efficiency. Furthermore, a tabu search algorithm is developed for large-scale problem instances. We also study the impact of inventory weight, transportation weight, and marginal value of time of returned products by the sensitivity analysis. Several computational experiments are conducted to validate the effectiveness of the proposed model and valid inequalities.     

A multi-objective approach for solving the survivable network design problem with simultaneous unicast and anycast flows

In this paper, we consider the survivable network design problem for simultaneous unicast and anycast flow requests. We assume that the network is modeled by a connected and undirected graph. This problem aims at finding a set of connections with a minimized network cost in order to protect the network against any single failure. The cost is computed using the all capacities modular cost (ACMC) model and a set of flow demands. We name it as ACMC-based survivable network design problem (A-SNDP). It is proved that the problem is NP-hard. We introduce a multi-objective approach to solve A-SNDP. The objectives are to minimize the network cost (NCost) and the network failure (NFail). Extensive simulation results on instances of Polska, Germany and Atlanta networks showed the efficiency of the multi-objective approach for solving A-SNDP.     

A graph theoretic-based heuristic algorithm for responsive supply chain network design with direct and indirect shipment

The configuration of the supply chain network has a strong influence on the overall performance of the supply chain. A well designed supply chain network provides a proper platform for efficient and effective supply chain management. The supply chain network should be designed in the way that could meet the customer needs with an efficient cost. This paper studies the responsive, multi-stage supply chain network design (SCND) problem under two conditions: (1) when direct shipment is allowed and (2) when direct shipment is prohibited. First, two mixed integer programming models are proposed for multi-stage, responsive SCND problem under two abovementioned conditions. Then, to escape from the complexity of mixed integer mathematical programming models, graph theoretic approach is used to study the structure of the SCND problems and it is proven that both of SCND problems considered in this paper could be modeled by a bipartite graph. Finally, since such network design problems belong to the class of NP-hard problems, a novel heuristic solution method is developed based on a new solution representation method derived from graph theoretic view to the structure of the studied problem. To assess the performance of the proposed heuristic solution method, the associated results are compared to the exact solutions obtained by a commercial.     

A GRASP with path-relinking heuristic for the survivable IP/MPLS-over-WSON multi-layer network optimization problem

In this paper we deal with the survivable internet protocol (IP)/multi-protocol label switching (MPLS)-over-wavelength switched optical network (WSON) multi-layer network optimization problem (SIMNO). This problem entails planning an IP/MPLS network layer over a photonic mesh infrastructure whilst, at the same time, ensuring the highest availability of services and minimizing the capital expenditures (CAPEX) investments. Such a problem is currently identified as an open issue among network operators, and hence, its solution is of great interest. To tackle SIMNO, we first provide an integer linear programming (ILP) formulation which provides an insight into the complexity of its managing. Then, a greedy randomized adaptive search procedure (GRASP) with path-relinking (PR) together with a biased random-key genetic algorithm (BRKGA) are specifically developed to help solve the problem. The performance of both heuristics is exhaustively tested and compared making use of various network and traffic instances. Numerical experiments show the benefits of using GRASP instead of BRKGA when dealing with highly complex network scenarios. Moreover, we verified that the use of GRASP with PR remarkably improves the basic GRASP algorithm, particularly in real-sized, complex scenarios such as those proposed in this paper.