A dual ascent approach to the fixed-charge capacitated network design problem

In this paper we consider the problem of constructing a network over which a number of commodities are to be transported. Fixed costs are associated to the construction of network arcs and variable costs are associated to routing of commodities. In addition, one capacity constraint is related to each arc. The problem is to determine a network design that minimizes the total cost; i.e., it balances the construction and operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated network design problem is proposed. The method is shown to generate tighter lower bounds than the linear programming relaxation of the problem.     

Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0–1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak.     

LP-Based Heuristic Algorithms for Interconnecting Token Rings via Source Routing Bridges

We develop a method to determine the topology of a network that interconnects a number of token rings using source routing bridges. The purpose is to compute a topology that provides low response delays for network users at a minimal cost of bridge installations. We formulate this network design problem as a mixed binary integer linear program. We develop effective heuristic algorithms. The algorithms exploit the topology and routing solutions of the linear programming relaxation in a sophisticated manner which we believe is new in the literature. The model incorporates performance issues, such as network stability, bridge overflow, back pressure effect and broadcast storm, that are specific to the underlying communication technology. By formally incorporating these performance issues, we tighten the model formulation and improve the quality of the LP bound considerably. Computational results are reported for problems with up to 20 token rings and 190 potential bridge locations.     

Plant location with minimum inventory

We present an integer programming model for plant location with inventory costs. The linear programming relaxation has been solved by Dantzig-Wolfe decomposition. In this case the subproblems reduce to the minimum cut problem. We have used subgradient optimization to accelerate the convergence of the D-W algorithm. We present our experience with problems arising in the design of a distribution network for computer spare parts. In most cases, from a fractional solution we were able to derive integer solutions within 4% of optimality.     

A Comparison of Optimal Methods for Local Access Uncapacitated Network Design

We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values.     

The convex hull of two core capacitated network design problems

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost.This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Dynamic control of multicommodity fleet management problems

Dynamic fleet management problems with multiple equipment types and limited substitution can be modeled as dynamic, multicommodity network flow problems. These problems are further complicated by the presence of time windows on task arcs (a task, or load, can be handled at different points in time) and the need for integer solutions. In this paper, we formulate the problem as a dynamic control problem, and show that we can produce solutions within four to five percent of a linear relaxation. In addition, we can solve the ultra-large problems that arise in certain applications; these problems are beyond the capabilities of state-of-the-art linear programming solvers.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Models for a Steiner multi-ring network design problem with revenues

The Steiner multi-ring network design problem with revenues consists of designing node-disjoint multiple rings connected by a specific node (hub) and passing through all the nodes with high priority of service and some of the nodes with low priority of service. The number of nodes in each ring has an upper bound to assure a certain level of service. Besides the usual arc link costs, we also consider revenues between each pair of nodes in the same ring, even when they are not connected by a direct link. The objective is to minimize the difference between the total connection cost and total revenue. The problem is a generalization of the problem studied in Gouveia and Pires (Eur J Oper Res 133:21–31, 2001a) and it can also be seen as a combination of variants of two NP-Hard problems, the vehicle routing problem and the maximum edge-weighted clique problem. We introduce and discuss two types of integer linear programming formulations and propose some valid inequalities to strengthen the linear programming relaxation. Computational results are presented to evaluate the quality of the linear programming relaxation bounds associated with these formulations as well as efficiency of the models to obtain the optimal integer solutions.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

New formulation and relaxation to solve a concave-cost network flow problem

In this paper we study a minimum cost, multicommodity network flow problem in which the total cost is piecewise linear, concave of the total flow along the arcs. Specifically, the problem can be defined as follows. Given a directed network, a set of pairs of communicating nodes and a set of available capacity ranges and their corresponding variable and fixed cost components for each arc, the problem is to select for each arc a range and identify a path for each commodity between its source and destination nodes so as to minimize the total costs. We also extend the problem to the case of piecewise nonlinear, concave cost function. New mathematical programming formulations of the problems are presented. Efficient solution procedures based on Lagrangean relaxations of the problems are developed. Extensive computational results across a variety of networks are reported. These results indicate that the solution procedures are effective for a wide range of traffic loads and different cost structures. They also show that this work represents an improvement over previous work made by other authors. This improvement is the result of the introduction of the new formulations of the problems and their relaxations.     

On Linear Fractional Programming Problem and its Computation Using a Neural Network Model

In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity. We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove certain results involving the neural network model. A computational experience is also reported.      

Proprietor and customer costs in the incomplete hub location-routing network topology

The hub location problem finds the location of hubs and allocates the other nodes to them. It is widely supposed the network created with the hub nodes is complete in the extensive literature. Relaxation of this basic supposition forms the present work. The model minimizes the cost of the proprietor, including the fixed costs of hubs, hub links and spoke links. Costs of hub and spoke links are contemplated as fixed cost or maintenance cost. Moreover, the model considers routing costs of customers who want to travel from origins to destinations. In this study, we offer a model to the multiple allocations of the hub location problems, under the incomplete hub location-routing network design. This model is easily transformed to other hub location problems using one or more constraints. No network format is dictated on the hub network. We suggest a set of valid inequalities for the formulation. Some lower bounds are developed using a Lagrangian relaxation approach and the valid inequalities. Computational analyses evaluate the performances of the lower bounding implementations and valid inequalities. Furthermore, we explore the effects of several factors on the design and solution time of the problem formulation.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

Global optimization for sum of geometric fractional functions

This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm.     

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.     

A study of the lot-sizing polytope

The lot-sizing polytope is a fundamental structure contained in many practical production planning problems. Here we study this polytope and identify facet–defining inequalities that cut off all fractional extreme points of its linear programming relaxation, as well as liftings from those facets. We give a polynomial–time combinatorial separation algorithm for the inequalities when capacities are constant. We also report computational experiments on solving the lot–sizing problem with varying cost and capacity characteristics.Supported, in part, by NSF Grants 0070127 and 0218265, and a grant from ILOG, Inc.