A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

LP extreme points and cuts for the fixed-charge network design problem

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem. The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions. We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known properties of the plant location problem. Supported in part by grant number ECS-831-6224 of the National Science Foundation.     

A branch-and-price approach to the feeder network design problem

In this paper we consider the problem of designing a container liner shipping feeder network. The designer has to choose which port to serve during many rotations that start and end at a central hub. Many operational characteristics are considered, such as variable leg-by-leg speeds and cargo transit times. Realistic instances are generated from the LinerLib benchmark suite. The problem is solved with a branch-and-price algorithm, which can solve most instances to optimality within one hour. The results also provide insights on the cost structure and desirable features of optimal routes. These insights were obtained by means of an analysis where scenarios are generated varying internal and external conditions, such as fuel costs and port demands.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

0-1 reformulations of the multicommodity capacitated network design problem

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.     

A partial dual algorithm for the capacitated warehouse location problem

The Capacitated Warehouse Location Problem (CWLP) consists of the ordinary transportation problem with the additional feature of a fixed cost associated with each supplier. A supplier can be used towards meeting the demands of the customers only if the corresponding fixed cost is incurred. The problem is to determine which suppliers to use and how the customer demands should be met, so that total cost is minimised.Most of the recently published algorithms for CWLP use branch and bound based on a Lagrangian relaxation of demand constraints. Here, a partial dual of a tight LP formulation is used in order to take advantage of the properties of transportation problems. Computational results are given which show good overall performance of the algorithm, with the size of the tree search being reduced compared with previous published results.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

A combined facility location and network design problem with multi-type of capacitated links

This article presents a mixed-integer model to optimize the location of facilities and the underlying transportation network at the same time to minimize the total transportation and operating costs. In this problem, it is assumed that for connecting two nodes, there are several types of links in which their capacity, transportation and construction costs are different. The developed model has various applications in telecommunication, emergency, regional planning, pipeline network, energy management, distribution, to just name a few. To solve the model effectively, this paper also proposes a fix-and-optimize heuristic based on the evolutionary fire-fly algorithm. Finally, to validate the model and evaluate the algorithm’s performance, a series of test instances with up to 100 nodes and 600 candidate links with three different levels of quality are reported.     

A hybrid simulated annealing and column generation approach for capacitated multicommodity network design

This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.     

A MIP-based approach to solve the prize-collecting local access network design problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN).     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

A branch-and-cut algorithm for capacitated network design problems

We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report on our computational experience using real-life data. Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999     

A variational approach to the Steiner network problem

Supposen points are given in the plane. Their coordinates form a 2n-vectorX. To study the question of finding the shortest Steiner networkS connecting these points, we allowX to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the casesn=4, 5 are discussed. The variational approach was used by us to solve other cases of the ratio conjecture (n=6, see [11] and for arbitraryn points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. We have also solved Graham's problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method.     

A dual approach to solve the fuzzy linear programming problem

A concept of fuzzy objective based on the Fuzzification Principle is presented. In accordance with this concept, the Fuzzy Linear Mathematical Programming problem is easily solved. A relationship of duality among fuzzy constraints and fuzzy objectives is given. The dual problem of a Fuzzy Linear Programming problem is also defined.     

A genetic algorithm approach on tree-like telecommunication network design problem

In the context of telecommunication networks, the network terminals involve certain constraints that are either related with the performance of the corresponding network or with the availability of some classes of devices. In this paper, we discuss a tree-like telecommunication network design problem with the constraint limiting the number of terminals. First, this problem is formulated as a leaf-constrained minimum spanning tree (lc-MST). Then we develop a tree-based genetic representation to encode the candidate solutions of the lc-MST problem. Compared with the existing heuristic algorithm, the numerical results show the high effectiveness of the proposed GA approach on this problem.     

An improved Lagrangian relaxation and dual ascent approach to facility location problems

The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).     

A neural network approach to the vessel dispatching problem

The paper discusses the process of loading, transport and unloading of gravel by inland water transportation. At the loading port, the problem that needs to be solved is the assignment of load barges to pusher tugs for the planned period of one day. However, disturbances of planned schedules are very common. Whenever a disturbance in a daily schedule appears, the dispatcher urgently attempts to mitigate negative effects resulting from the disturbance. Real-time operations limit the amount of time that dispatchers in charge of traffic control have to make decisions and increase the level of stress associated with quick and adequate response. This paper aims to demonstrate the feasibility of a dispatch decision support system that could decrease the work load for the dispatcher and improve the quality of decisions. The proposed neural network with the ability to adapt or learn from examples of decisions can simulate the dispatcher's decision process.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

A mathematical approach to solve the network reconstruction problem

The reconstruction of biochemical and genetic networks from experimental data is an important challenge in biology and medical basic research. We formalize this problem mathematically and present an exact algorithm for its solution. Our procedure yields either a complete list of all alternative network structures that explain the observed phenomena or proves that no solution exists using the given data set. This work was supported by the German Ministry of Education and Research (BMBF) through the FORSYS initiative.