Search

We consider the piecewise linear multicommodity network flow problem with the addition of a constraint specifying that the total flow on each arc must be an integer. This problem has applications in transportation and logistics, where total flows might represent vehicles or containers filled with different products. We introduce formulations that exploit this integrality constraint by adapting to our problem a technique known as discretization that has been used to derive mixed-integer programming models for several combinatorial optimization problems. We enhance the discretized models either by adding valid inequalities derived from cut-set inequalities or by using flow disaggregation techniques. Since the size of the formulations derived from discretization and flow disaggregation rapidly increases with problem dimensions, we develop an efficient and effective Lagrangian relaxation method to compute lower and upper bounds. We perform computational results on a large set of randomly generated instances that allow us to compare the relative efficiency of the different modeling alternatives (flow disaggregation plus addition of cut-set inequalities with or without discretization), when used within the Lagrangian relaxation approach.

We present a general optimization framework for locomotive models that captures different levels of detail, ranging from single and multicommodity flow models that can be solved using commercial integer programming solvers, to a much more detailed multiattribute model that we solve using approximate dynamic programming (ADP). Both models have been successfully implemented at Norfolk Southern for different planning applications. We use these models, presented using a common notational framework, to demonstrate the scope of different modeling and algorithmic strategies, all of which add value to the locomotive planning problem. We demonstrate how ADP can be used for both deterministic and stochastic models that capture locomotives and trains at a very high level of detail.

We develop a qualitative analysis theory for the convex-cost dynamic multicommodity production planning problem, which can be used, without performing any computational work, to provide invaluable insight to managers when faced with the task of deciding how to respond to changes in problem environment. We first formulate the problem as a multicommodity flow problem with parameters associated with each arc–commodity pair. We then reduce the problem to an equivalent single-commodity flow problem and develop a complete characterization of conformality among production, sales, and inventory activities in various instances of the problem. By combining the conformality characterizations with the monotonicity theory of Granot and Veinott [Granot F, Veinott AF Jr (1985) Substitutes, complements and ripples in network flow. Math. Oper. Res. 10:471–497] for single-commodity problems, we study the effects of changes in problem environment on optimal production, sales, and inventory schedules in the multicommodity problem. Numerous applications are presented and analyzed.

In an optical network a signal can only travel a maximum distance dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S = T = N, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances.

This paper considers the problem of designing a multicommodity network with single facility type subject to the requirement that under failure of any single edge, the network should permit a feasible flow of all traffic. We study the polyhedral structure of the problem by considering the multigraph obtained by shrinking the nodes, but not the edges, in a k-partition of the original graph. A key theorem is proved according to which a facet of the k-node problem defined on the multigraph resulting from a k-partition is also facet defining for the larger problem under a mild condition. After reviewing the prior work on two-partition inequalities, we develop two classes of three-partition inequalities and a large number of inequality classes based on four-partitions. Proofs of facet-defining status for some of these are provided, while the rest are stated without proof. Computational results show that the addition of three- and four-partition inequalities results in substantial increase in the bound values compared to those possible with two-partition inequalities alone. Problems of 35 nodes and 80 edges with fully dense traffic matrices have been solved optimally within a few minutes of computer time.

This paper addresses the problem of generating conflict-free train schedules on a microscopic model of the railway infrastructure. Conflicts arise if two or more trains are scheduled to block the same track section at the same time. A standard model for this problem is the so-called conflict graph, where each considered train path corresponds to a vertex, and edges represent pairwise conflicts so that a conflict-free schedule corresponds to a maximum independent set. Because the linear programming relaxation of the conflict graph formulation is typically very weak, we develop an alternative model using the sequence of resources that each train path passes, encoded in a resource tree. For each resource, we can efficiently determine the maximal conflict cliques by scanning through the blocking times of all train paths and use these cliques as strong cutting planes in an integer linear programming formulation. We show that the number of maximal conflict cliques is linear in the number of train paths, so the ILP formulation uses much fewer but stronger constraints compared to the conflict graph model. In tests with real-world data from the Swiss Federal Railways, the new Resource Tree Conflict Graph model generates for major stations within seconds, even though the underlying model contains about half a million binary variables. This corresponds to a reduction of the computation time of roughly two orders of magnitude when compared to previous approaches and thus allows us to tackle considerable larger problem instances.

The cell-transmission model-based single-destination system optimal dynamic traffic assignment problem proposed by Ziliaskopoulos was mostly solved by standard linear programming (LP) methods, e.g., simplex and interior point methods, which produce link-based flows involving vehicle-holding phenomenon. In this paper we present a network flow algorithm for this problem. We show that the problem is equivalent to the earliest arrival flow and then solve the earliest arrival flow on a time-expanded network. In particular, a scaled flow scheme is proposed to deal with the situation in which the ratio of backward wave speed to forward wave speed is less than one. The proposed algorithm produces path-based flows exhibiting realistic nonvehicle-holding properties. Complexity and numerical analyses show that the algorithm runs more efficiently than LP.

The objective of the classical minimum cost flow problem is to send units of a good that reside at one or more points in a network (sources or supply nodes) with arc capacities to one or more other points in the network (sinks or demand nodes), incurring minimum cost. We develop fast algorithms for previously unstudied specially structured minimum cost flow problems that have applications in many areas, such as locomotive and airline scheduling, repositioning of empty rail freight cars, highway and river transportation, congestion pricing, shop loading, and production planning. First, we consider the case where the n1 supply and n2 demand nodes lie on a circle (or line) (n = n1 + n2) and flow is allowed only in one direction; our algorithm solves this problem in O(n) time. Next, we consider a constrained version of this problem and show that it can be solved in O(n log n2) time. Finally, we consider the version where the nodes lie on a circle (or line), flow is allowed in both directions, and the costs of flow between two nodes in the clockwise and the counterclockwise direction are different; our algorithm solves this problem in O(n log n) time. Our algorithms are based on the successive shortest-path algorithm for the minimum cost flow problem. We exploit the special structure of the problem and use advanced data structures, when required, to achieve short run times.

The nodes and arcs of a network configuration replicated over time is a common structure found in many applications, particularly in the area of logistics. A common cost structure for flows in arcs for such problems involves both a fixed and variable cost. Combining the two concepts results in the uncapacitated time-space fixed-charge network flow problem. These problems can be modeled as mixed binary linear programs and can be solved with commercial software. To create these models for uncapacitated arcs requires determining artificial arc capacities that are sufficiently large so that the solution space has not been altered but are small enough that the linear programming relaxations are tight. In this investigation, we present a strategy for determining these artificial arc capacities for any time-space fixed-charge network flow problem. In extensive empirical tests, we provide statistical evidence that the strategy is superior to the usual techniques applied to this class of problem. Many of the most difficult problems were solved in only 5% of the computational time required by standard techniques.

In an incremental optimization problem, we are given a feasible solution x0 of an optimization problem P, and we want to make an incremental change in x0 that will result in the greatest improvement in the objective function. In this paper, we study the incremental optimization versions of six well-known network problems. We present a strongly polynomial algorithm for the incremental minimum spanning tree problem. We show that the incremental minimum cost flow problem and the incremental maximum flow problem can be solved in polynomial time using Lagrangian relaxation. We consider two versions of the incremental minimum shortest path problem, where increments are measured via arc inclusions and arc exclusions. We present a strongly polynomial time solution for the arc inclusion version and show that the arc exclusion version is NP-complete. We show that the incremental minimum cut problem is NP-complete and that the incremental minimum assignment problem reduces to the minimum exact matching problem, for which a randomized polynomial time algorithm is known.

Earliest arrival flows capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink “as quickly as possible.” The latter requirement is made more precise by the earliest arrival property, which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the successive shortest-path algorithm for min-cost flow computations. Although it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open for many years. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.

This paper discusses the notion of workflow congestion in the context of material handling equipment interruptions in a manufacturing or warehousing facility. Development of a combination of probabilistic and physics-based models for workflow interruptions permits evaluation of the expected link travel time. The problem is then of routing in a way that minimizes total expected travel time. The rerouting problem is modeled as a multicommodity flow problem with link capacity design. A greedy upper bounding and Lagrangean relaxation algorithm are developed to solve this efficiently. To calibrate our modeling process we develop an object-oriented simulation model that explicitly considers various workflow interruptions. Our major finding is that rerouting traffic in a congested facility can significantly alleviate congestion delays and improve the efficiency of material movement. A managerial insight derived from this work is that rerouting is most effective in medium traffic-intensity situations.

In a network where the cost of flow across an edge is nonlinear in the volume of flow, and where sources and destinations are uniform, one can consider the relationship between total volume of flow through the network and the minimum cost of any flow with given volume. Under a simple probability model (locally tree-like directed network, independent cost–volume functions for different edges) we show how to compute the minimum cost in the infinite-size limit. The argument uses a probabilistic reformulation of the cavity method from statistical physics and is not rigorous as presented here. The methodology seems potentially useful for many problems concerning flows on this class of random networks. Making arguments rigorous is a challenging open problem.

The availability of relatively cheap small jet planes has led to the creation of on-demand air transportation services in which travelers call a few days in advance to schedule a flight. A successful on-demand air transportation service requires an effective scheduling system to construct minimum-cost pilot and jet itineraries for a set of accepted transportation requests. We present an integer multicommodity network flow model with side constraints for such dial-a-flight problems. We develop a variety of techniques to control the size of the network and to strengthen the quality of the linear programming relaxation, which allows the solution of small instances. In Part II, we describe how this core optimization technology is embedded in a parallel, large-neighborhood, local search scheme to produce high-quality solutions efficiently for large-scale real-life instances.

This paper presents a branch-and-cut-and-price algorithm for the vehicle-routing problem with time windows. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set-partitioning problem as the master problem and an elementary shortest-path problem with resource constraints as the pricing problem. We introduce the subset-row inequalities, which are Chvatal-Gomory rank-1 cuts based on a subset of the constraints in the master problem. Applying a subset-row inequality in the master problem increases the complexity of the label-setting algorithm used to solve the pricing problem because an additional resource is added for each inequality. We propose a modified dominance criterion that makes it possible to dominate more labels by exploiting the step-like structure of the objective function of the pricing problem. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying subset-row inequalities in the master problem significantly improves the lower bound and, in many cases, makes it possible to prove optimality in the root node.

The line-planning problem is one of the fundamental problems in strategic planning of public and rail transport. It involves finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives: the transport company wishes to minimize operating costs, and the passengers want to minimize traveling times. We propose a new multicommodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and lines are generated dynamically. We discuss properties of this model, investigate its complexity, and present a column-generation algorithm for its solution. Computational results with data for the city of Potsdam, Germany, are reported.

In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to be the case in many practical problems.

In this paper, we consider a stochastic and time-dependent version of the min-cost integer multicommodity-flow problem that arises in the dynamic resource allocation context. In this problem class, tasks arriving over time have to be covered by a set of indivisible and reusable resources of different types. The assignment of a resource to a task removes the task from the system, modifies the resource, and generates a profit. When serving a task, resources of different types can serve as substitutes of each other, possibly yielding different revenues. We propose an iterative, adaptive dynamic-programming-based methodology that makes use of linear or nonlinear approximations of the value function. Our numerical work shows that the proposed method provides high-quality solutions and is computationally attractive for large problems.

We give an approximation scheme for separated continuous linear programming problems. Such problems arise as fluid relaxations of multiclass queueing networks and are used to find approximate solutions to complex job shop scheduling problems. In a network with linear flow costs and linear, per-unit-time holding costs, our algorithm finds a drainage of the network that, for given constants ε > 0 and δ > 0, has total cost (1 + ε)OPT + δ, where OPT is the cost of the minimum cost drainage. The complexity of our algorithm is polynomial in the size of the input network, 1/ε, and log(1/δ). The fluid relaxation is a continuous problem. While the problem is known to have a piecewise constant solution, it is not known to have a polynomially sized solution. We introduce a natural discretization of polynomial size and prove that this discretization produces a solution with low cost. This is the first polynomial time algorithm with a provable approximation guarantee for fluid relaxations.

The design of route guidance systems faces a well-known dilemma. The approach that theoretically yields the system-optimal traffic pattern may discriminate against some users in favor of others. Proposed alternate models, however, do not directly address the system perspective and may result in inferior performance. We propose a novel model and corresponding algorithms to resolve this dilemma. We present computational results on real-world instances and compare the new approach with the well-established traffic assignment model. The essence of this study is that system-optimal routing of traffic flow with explicit integration of user constraints leads to a better performance than the user equilibrium, while simultaneously guaranteeing superior fairness compared to the pure system optimum.

According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash equilibrium does not optimize any global criterion per se, and so there is no apparent reason why it should be close to a solution of minimal total travel time, i.e., the system optimum. In this paper, we offer positive results on the efficiency of Nash equilibria in traffic networks. In contrast to prior work, we present results for networks with capacities and for latency functions that are nonconvex, nondifferentiable, and even discontinuous. The inclusion of upper bounds on arc flows has early been recognized as an important means to provide a more accurate description of traffic flows. In this more general model, multiple Nash equilibria may exist and an arbitrary equilibrium does not need to be nearly efficient. Nonetheless, our main result shows that the best equilibrium is as efficient as in the model without capacities. Moreover, this holds true for broader classes of travel cost functions than considered hitherto.

We study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited.

In this paper1, we consider an integer convex optimization problem where the objective function is the sum of separable convex functions (that is, of the form ∑(i,j)ϵQF̄ij(wij) + ∑iϵPB̄i(μi)), the constraints are similar to those arising in the dual of a minimum cost flow problem (that is, of the form μi− μj≤ wij, (i,j)∈Q), with lower and upper bounds on variables. Letn= |P|,m= |Q| , andUbe the largest magnitude in the lower and upper bounds of variables. We call this problemthe convex cost integer dual network flow problem. In this paper, we describe several applications of the convex cost integer dual network flow problem arising in a dial-a-ride transit problem, inverse spanning tree problem, project management, and regression analysis. We develop network flow-based algorithms to solve the convex cost integer dual network flow problem. We show that using the Lagrangian relaxation technique, the convex cost integer dual network flow problem can be transformed into a convex cost primal network flow problem where each cost function is a piecewise linear convex function with integer slopes. Its special structure allows the convex cost primal network flow problem to be solved inO(nmlog(n 2/m)log(nU)time. This time bound is the same time needed to solve the minimum cost flow problem using the cost-scaling algorithm, and is also is best available time bound to solve the convex cost integer dual network flow problem.

We solve a central problem in the liner shipping industry called the liner shipping fleet repositioning problem (LSFRP). The LSFRP poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between routes in a liner shipping network. Liner carriers wish to reposition vessels as cheaply as possible without disrupting cargo flows. The LSFRP is characterized by chains of interacting activities with a multicommodity flow over paths defined by the activities chosen. Despite its industrial importance, the LSFRP has received little attention in the literature. We introduce a novel mathematical model and a simulated annealing algorithm for the LSFRP with cargo flows that makes use of a carefully constructed graph; we evaluate these approaches using real-world data from our industrial collaborator. Additionally, we compare the performance of our approach against an actual repositioning scenario, one of many undertaken by our industrial collaborator in 2011. Our simulated annealing algorithm is able to increase the profit from $18.1 to $31.8 million using only a few minutes of CPU time. This shows that our algorithm could be used in a decision support system to solve the LSFRP.

We consider the node-capacitated routing problem in an undirected ring network along with its fractional relaxation, the node-capacitated multicommodity flow problem. For the feasibility problem, Farkas' lemma provides a characterization for general undirected graphs, asserting roughly that there exists such a flow if and only if the so-called distance inequality holds for every choice of distance functions arising from nonnegative node weights. For rings, this (straightforward) result will be improved in two ways. We prove that, independent of the integrality of node capacities, it suffices to require the distance inequality only for distances arising from (0-1-2)-valued node weights, a requirement that will be called the double-cut condition. Moreover, for integer-valued node capacities, the double-cut condition implies the existence of a half-integral multicommodity flow. In this case there is even an integer-valued multicommodity flow that violates each node capacity by at most one. Our approach gives rise to a combinatorial, strongly polynomial algorithm to compute either a violating double-cut or a node-capacitated multicommodity flow. A relation of the problem to its edge-capacitated counterpart will also be explained.

We consider an aggregated version of a large-scale driver scheduling problem, derived from an application in less-than-truckload trucking, as a dynamic resource allocation problem. Drivers are aggregated into groups characterized by an attribute vector which capture the important attributes required to incorporate the work rules. The problem is very large: over 5,000 drivers and 30,000 loads in a four-day planning horizon. We formulate a problem that we call the heterogeneous resource allocation problem, which is more general than a classical multicommodity flow problem. Since the tasks have one-sided time windows, the problem is too large to even solve an LP relaxation. We formulate the problem as a multistage dynamic program and solve it using adaptive dynamic programming techniques. Since our problem is too large to solve using commercial solvers, we propose three independent benchmarks and demonstrate that our technique appears to be providing high-quality solutions in a reasonable amount of time.

Multicommodity network flow models arise in a wide variety of contexts, typical among which is the dimensioning of telecommunication networks. In this paper, we present various approaches based on specialization of the simplex algorithm and interior-point methods to solve nonoriented multicommodity flowproblems. Algorithms are tested with data from the France-Telecom Paris district transmission network. First, we focus on a specialization for the node-arc formulation of the problem. A Primal simplex and Dual Affine Scaling algorithms exploiting the particular structure of the constraint matrix are presented and compared. Numerical results are provided for problems up to about 800,000 constraints and 6,000,000 variables. However, much more powerful approaches based on specialized decomposition methods can be implemented for solving the problem. A Dantzig-Wolfe decomposition method is designed and compared with a specialized implementation of the Analytic Center Cutting Plane Method (ACCPM). Partitioning techniques are used to exploit the structure of the master programs involved in those methods.

Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.

We present a column-generation model and branch-and-price-and-cut algorithm for origin-destination integer multicommodity flow problems. The origin-destination integer multicommodity flow problem is a constrained version of the linear multicommodity flow problem in which flow of a commodity (defined in this case by an origin-destination pair) may use only one path from origin to destination. Branch-and-price-and-cut is a variant of branch-and-bound, with bounds provided by solving linear programs using column-and-cut generation at nodes of the branch-and-bound tree. Because our model contains one variable for each origin-destination path, for every commodity, the linear programming relaxations at nodes of the branch-and-bound tree are solved using column generation, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality. We devise a new branching rule that allows columns to be generated efficiently at each node of the branch-and-bound tree. Then, we describe cuts (cover inequalities) that can be generated at each node of the branch-and-bound tree. These cuts help to strengthen the linear programming relaxation and to mitigate the effects of problem symmetry. We detail the implementation of our combined column-and-cut generation method and present computational results for a set of test problems arising from telecommunications applications. We illustrate the value of our branching rule when used to find a heuristic solution and compare branch-and-price and branch-and-price-and-cut methods to find optimal solutions for highly capacitated problems.

We consider a dynamic network flow problem where the arc capacities are random variables. This gives a multistage stochastic linear program. We describe the randomness using a multi-scenario approach. Because of the multilayered structure, there are several ways to decompose the linear program. We classify different decomposition schemes, and we develop a scheme called compath decomposition, which is derived from path decomposition for network flows. We give a polynomial-time algorithm to find a cheapest compath that can solve the subproblems resulting from compath decomposition. Finally, compath decomposition is extended to multicommodity flow problems.

A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks; each source has a specified supply and each sink has a specified demand. The problem is to send exactly the right amount of flow out of each source and into each sink in the minimum overall time. Variations of the quickest transshipment problem have been studied extensively; the special case of the problem with a single sink is commonly used to model building evacuation. Similar dynamic network flow problems have numerous other applications; in some of these, the capacities are small integers and it is important to find integral flows. There are no polynomial-time algorithms known for most of these problems. In this paper we give the first polynomial-time algorithm for the quickest transshipment problem. Our algorithm provides an integral optimum flow. Previously, the quickest transshipment problem could only be solved efficiently in the special case of a single source and single sink.

The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set R ⊆ A of arcs and require that each arc in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all arc capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem—the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m + n logn) log (nU)) time, which is almost the same time needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem.

This work develops a polynomial-time dynamic-programming algorithm for minimum-aggregate-concave-cost multicommodity flow problems in strong-series-parallel networks. Many important problems from production and inventory management, capacity planning, network design and transportation can be formulated in these terms. Our results include a characterization of extreme flows in strong-series-parallel networks and an algorithm based on this characterization that searches extreme flows efficiently to find an optimal one. The algorithm runs in time proportional to A(N + K), where A, N and K are respectively the numbers of arcs, nodes and commodities in the network, and appears to be the first to solve the problem in polynomial time. When applied to the dynamic economic-order-quantity problem, the algorithm matches the performance of that of Wagner and Whitin (1958). Moreover, our algorithm has broader applications, including the multi-division capacity expansion problem and the generalization of the dynamic economic-order-quantity problem to series-parallel production processes in which subassemblies are assembled into a finished product.

We use variable redefinition (see R. Martin, 1987. Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition, Operations Research 35, 820–831) to strengthen a multicommodity flow (MCF) model for minimum spanning and Steiner trees with hop constraints between a root node and any other node. Hop constraints model quality of service constraints. The Lagrangean dual value associated with one Lagrangean relaxation derived from the MCF formulation dominates the corresponding LP value. However, the lower bounds given after a reasonable number of iterations of the associated subgradient optimization procedure are, for several cases, still far from the theoretical best limit. Martin's variable redefinition technique is used to obtain a generalization of the MCF formulation whose LP bound is equal to the previously mentioned Lagrangean dual bound. We use a set of instances with up to 100 nodes, 50 basic nodes, and 350 edges for comparing an LP approach based on solving the LP relaxation of the new model with the equivalent Lagrangean scheme derived from MCF.

The multicommodity-flow problem arises in a wide variety of important applications. Many communications, logistics, manufacturing, and transportation problems can be formulated as large multicommodity-flow problems. During the last few years researchers have made steady advances in solving extremely large multicommodity-flow problems. This improvement has been due both to algorithmic and to hardware advances. At present the primal simplex method using the basis-partitioning approach gives excellent solution times even on modest hardware. These results imply that we can now efficiently solve the extremely large multicommodity-flow models found in industry. The extreme-point solution can also be quickly reoptimized to meet the additional requirements often imposed upon the continuous solution. Currently practitioners are using EMNET, a primal basis-partitioning algorithm, to solve extremely large logistics problems with more than 600,000 constraints and 7,000,000 variables in the food industry.

The proportional equity flow problem extends a class of problems referred to as equity flow problems whose objective is to equitably distribute flow among the arcs in a flow circulation network. The proportionally bounded flow circulation problem places lower and upper bounds on each arc flow that are nondecreasing continuous functions of the flow through one special arc, and the objective is to maximize the flow through the special arc. The proportional equity flow problem for terminal arcs (Problem TA) is then defined as a special case where all the proportional arcs enter a sink vertex. Applications of both the general problem and Problem TA are given. Two optimality conditions for Problem TA are developed, as well as an algorithm that is polynomially bounded for many types of nondecreasing, continuous, proportional bounding functions. Specifically, the algorithm is shown to be polynomially bounded if the largest root of an equation can be found in polynomial time.

This article describes the authors’ experience solving large multicommodity flow problems with an embedded network simplex algorithm augmented with a fast-start heuristic for choosing an initial basis. The heuristic makes successive capacity allocations in an attempt to find a feasible initial basis. Our implementation of the heuristic makes use of piece-wise linear convex costs. The efficacy of our heuristic, and of the embedded network simplex method, is demonstrated on large publicly available multicommodity flow problems. Comparisons with other published computational results are given.

We present an advanced model for the formulation and solution of large scale fleet assignment problems that arise in the scheduling of air transportation. Fleet assignment determines the type of aircraft to operate each flight in a given schedule, subject to a variety of side constraints, due to marketing, operational, maintenance and crew restrictions. We model the problem as mixed-integer multicommodity flow on networks encoding activities linking flight departures. We focus on fully representing flight connection possibilities, while accurately capturing complex operational rules. We also provide a unified framework for the expression of resource constraints via piecewise linear penalties, which permits a profitability-based tradeoff between operational goals and revenue. Computational results on actual schedules show that high quality assignments for one-day problems can be obtained within an hour of computation. The use of the model at USAir results in an annual benefit of at least $15 million.

Suppose we are given an undirected graph with nonnegative integer-valued edge capacities and costs in which a subset of nodes is specified. We consider the problem of finding a collection of flows between arbitrary pairs of specified nodes such that the capacity constraints are satisfied and the sum of costs of flows is minimum, provided that the sum of values of flows is maximum. It is known that this problem has a half-integer optimal solution and such a solution can be found in strongly polynomial time using the ellipsoid method. In this paper we give two “purely combinatorial” polynomial algorithms for finding a half-integer optimal solution. These are based on capacity and cost scaling techniques and use the double covering method earlier worked out for the problem.

We formulate the Forest Management Problem as a Multicommodity Network Flow Problem with a convex cost function. We then show how to transfer the problem to an equivalent Single-Commodity Network Flow formulation in order to address several sensitivity analysis questions using results by Granot and Veinott (Granot, F., A. F. Veinott, Jr. 1985. Substitutes, complements and ripples in network flows. Math. Oper. Res. 10 471–497.). The answers can subsequently be used to help forest managers respond to changes in the environment such as fires or changes in market prices, without any additional computation. Furthermore, the characterization of the response we provide requires no prior knowledge of optimal management policies.

This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangian relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangian relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the nonpreemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem.

To remain competitive, manufacturers must seek transportation strategies that both reduce costs and maintain high levels of service. One approach is to consolidate inbound freight at transshipment points. This provides economies of scale and promotes capacity efficient mixes of high and low density items. When service level considerations are included via inventory holding costs, the approach yields a nonlinear network model with multiattribute multicommodity flows. The model is difficult to solve for global optimality in that the objective function is neither convex nor concave; therefore, a composite algorithm is proposed. The algorithm alternates between a linearization technique to find local optima and a heuristic search based on “adjacent concave flows” to provide local improvements. Computational results demonstrate the ability of the multiattribute approach to identify savings in overall transportation and inventory costs when compared to a single attribute approach.

In this paper, the routine problem in virtual circuit networks is considered. In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. We consider the problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network. We consider the formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables. The emphasis of this work is to develop a distributed algorithm to solve this optimization problem. The basic approach is Lagrangean Relaxation. We introduce a new multiplier update rule which facilitates the solution of the nonlinear integer programming problem using distributed computation. In computational experiments, our proposed distributed algorithm determines solutions that are within 1% of an optimal solution in less than 2 minutes of CPU time for networks with 26 to 61 nodes. In addition, the proposed multiplier adjustment procedure provides better bounds and is less sensitive to the algorithm parameters than the subgradient method. An analysis of the communication delays of the control messages needed to support a distributed implementation is given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Fourteen dissertations were submitted to the 1990–1991 Transportation Science Section dissertation prize competition. The first prize was awarded by Dr. Linos F. Frantzeskakis for “Dynamic Networks with Random Arc Capacities, with Application to the Stochastic Dynamic Vehicle Allocation Problem.” Three honorable mentions were also awarded. The recipients are listed in alphabetical order: Dr. Saad A. H. Al-Gadhi for “Characterization of Crowd Behavior and Movement,” Dr. Rina Schneur for “Scaling Algorithms for Multicommodity Flow Problems and Network Flow Problems with Side Constraints,” and Dr. Garrett van Ryzin for “Stochastic and Dynamic Vehicle Routing in Euclidean Service Regions.” The abstracts of all 14 theses submitted are reproduced.

Previous research on the multicommodity minimum cost flow problem (MMCFP) has assumed that there are two types of values associated with an arc. The first is the capacity of the arc and the second is the unit flow cost along the arc. This paper adds the third attribute—the degree of difficulty—into the conventional model of the MMCFP. In this way, a new problem, which is more general and difficult than the conventional MMCFP, is formed. However, we show that these two problems are indeed polynomially equivalent. With the equivalence, the techniques developed for solving the conventional MMCFP can be used to solve the new but more general problem.

We develop a new approach to solving minimum-cost circulation problems. Our approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. We measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. We propose a simple minimum-cost circulation algorithm, one version of which runs in O(n3log(nC)) time on an n-vertex network with integer arc costs of absolute value at most C. By incorporating sophisticated data structures into the algorithm, we obtain a time bound of O(nm log(n2/m)log(nC)) on a network with m arcs. A slightly different use of our approach shows that a minimum-cost circulation can be computed by solving a sequence of O(n log(nC)) blocking flow problems. A corollary of this result is an O(n2(log n)log(nC))-time, m-processor parallel minimum-cost circulation algorithm. Our approach also yields strongly polynomial minimum-cost circulation algorithms. Our results provide evidence that the minimum-cost circulation problem is not much harder than the maximum flow problem. We believe that a suitable implementation of our method will perform extremely well in practice.

The problem of multilocation facility modernization is described. An integer multicommodity flow formulation is presented. Because of the problem size, exact solutions are not practical, and approximate solution methods are examined. Upper bounds are obtained by LP and Lagrangian relaxation. Near-optimal feasible solutions are obtained by heuristic procedures. The relaxation methods and the heuristics are compared in terms of the computation cost and the quality of the modernization policies produced, where quality is measured by the net present value of cash flows for a number of test problems. Also included is an evaluation of an aggregate modeling approach to multilocation planning, where average costs are employed in a single-location model to determine a homogeneous multilocation modernization policy. This assessment is important, as aggregate models have been employed widely in practice.

This note is an erratum to Babonneau et al. (2006) in which some data were incorrectly described. In Babonneau et al. (2006), the ACCPM method is used to solve the linear multicommodity flow problem on four sets of instances, i.e., the planar and the grid instances, some telecommunication problems, and some transportation problems, from Bar-Gera (2007), http://www.bgu.ac.il/~bargera/tntp/ (Sioux Falls, Winnipeg, Barcelona, Chicago region, and Philadelphia). The mistakes concern the last category of instances. The new data and the associated results can now be found in the electronic companion at http://or.journal.informs.org/. This site also provides the full information on test instances in the multicommodity flow problem (MCF) and the traffic assignment problem to facilitate benchmarking. It gives the data and the results using three specific objective functions used in the literature, e.g., Bureau of Public Roads (BPR), Kleinrock, or linear. For more details on the optimization problem, we refer the reader to Babonneau et al. (2006) and Babonneau and Vial (2007).

Khachiyan, and recently Karmarkar, gave polynomial algorithms to solve the linear programming problem. These algorithms have a small theoretical drawback; namely, the number of arithmetic steps depends on the size of the input numbers. We present a polynomial linear programming algorithm whose number of arithmetic steps depends only on the size of the numbers in the constraint matrix, but is independent of the size of the numbers in the right-hand side and objective vectors. In particular, it gives a polynomial algorithm for the minimum cost flow and multicommodity flow problems in which the number of arithmetic steps is independent of the size of the costs and capacities. The algorithm makes use of an existing polynomial linear programming algorithm. The problem of whether any algorithm has a running time that is independent even of the size of the numbers in the constraint matrix remains open.

We consider a network model of a system of transportation links, with nodes representing locations of existing facilities, and study the problem of finding a new facility location on the network that minimizes the maximum of linear increasing functions of the “network distances” between the new facility and the existing facilities. The problem is formulated with respect to a metric space which is defined on the network, and a number of properties of the problem are developed. The properties lead to a new, simple algorithm for solving the problem when the network is a tree, and to a new, equivalent spanning tree problem for a general network.