Abstract A typical network design problem consists of identifying a subnetwork of a given network that satisfies a set of constraints and minimizes the cost of flow. We consider degree‐constrained network design problems where we specify an upper limit on the number of arcs built at each node. We propose two lower bounding techniques using the concept of lower planes. The first lower bound is based on a known lower plane for network design problems; our second lower bound is stronger than the first, yet has the same polynomial computational complexity. We illustrate both lower bounds using a numerical example, test their performance, and present a real‐life case study from the area of railroad planning problems. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Railroad planning involves solving two optimization problems: (i) the blocking problem, which determines what blocks to make and how to route traffic over these blocks; and (ii) the train schedule design problem, which determines train origins, destinations, and routes. Once the blocking plan and train schedule have been obtained, the next step is to determine which trains should carry which blocks. This problem, known as the block‐to‐train assignment problem, is considered in this paper. We provide two formulations for this problem: an arc‐based formulation and a path‐based formulation. The latter is generally smaller than the former, and it can better handle practical constraints. We also propose exact and heuristic algorithms based on the path‐based formulation. Our exact algorithm solves an integer programming formulation with CPLEX using both a priori generation and dynamic generation of paths. Our heuristic algorithms include a Lagrangian relaxation‐based method as well as a greedy construction method. We present computational results of our algorithms using the data provided by a major US railroad. We show that we can obtain an optimal solution of the block‐to‐train assignment problem within a few minutes of computational time, and can obtain heuristic solutions with 1–2% deviations from the optimal solutions within a few seconds. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

The fleet-assignment model (FAM) for an airline assigns fleet types to the set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. A through connection at a station is a connection between an arrival flight and a departure flight at the station, both of which have the same fleet type assigned to them, which ensures that the same plane flies both legs. Typically, passengers are willing to pay a premium for through connections. The through-assignment model (TAM) identifies a set of profitable throughs between arrival and departure flights flown by the same fleet type at each station to maximize the through benefits. TAM is usually solved after obtaining the solution from FAM. In this sequential approach, TAM cannot change the fleeting to get a better through assignment, and FAM does not take into account the through benefits. The goal of the combined through-fleet-assignment model (ctFAM) is to come up with a fleeting and through assignment that achieves the maximum combined benefit of the integrated model. We give a mixed integer-programming (MIP) formulation of ctFAM that is too large to be solved to even near optimality within allowable time for the data obtained by a major U.S. airline. We thus focus on neighborhood search algorithms for solving ctFAM, in which we start with the solution obtained by the previous sequential approach (that is, solving FAM first, followed by TAM) and improve it successively. Our approach is based on generalizing the swap-based neighborhood search approach of Talluri (1996) for FAM, which proceeds by swapping the fleet assignment of two flight paths flown by two different plane types that originate and terminate at the same stations and the same times. An important feature of our approach is that the size of our neighborhood is very large; hence the suggested algorithm is in the category of very large-scale neighborhood (VLSN) search algorithms. Another important feature of our approach is that we use integer programming to identify improved neighbors. We provide computational results that indicate that the neighborhood search approach for ctFAM provides substantial savings over the sequential approach of solving FAM and TAM.

The multi-period single-sourcing problem that we address in this paper can be used as a tool for evaluating logistics network designs in a dynamic environment. We consider the assignment of retailers to facilities, taking into account the timing, location, and size of production and inventories, in the presence of various types of constraints. We formulate the problem as a nonlinear assignment problem, and develop efficient algorithms for solving the capacitated lot-sizing subproblems that form the objective function of this formulation. We propose a greedy heuristic, and prove that this heuristic is asymptotically optimal in a probabilistic sense when retailer demands share a common seasonality pattern. In addition, we develop an efficient implementation of the very-large-scale-neighborhood-search method that can be used to improve the greedy solution. We perform extensive tests on a set of randomly generated problem instances, and conclude that our approach produces very high quality solutions in limited time.

The quadratic assignment problem (QAP) consists of assigning n facilities to n locations to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse settings, is known to be NP-hard, and can be solved to optimality only for fairly small instances (typically, n ≤ 30). Neighborhood search algorithms are the most popular heuristic algorithms for solving larger instances of the QAP. The most extensively applied neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities; its size is therefore O(n2). Previous efforts to explore larger neighborhoods (such as 3-exchange or 4-exchange neighborhoods) were not very successful, as it took too long to evaluate the larger set of neighbors. In this paper, we propose very large-scale neighborhood (VLSN) search algorithms when the size of the neighborhood is very large, and we propose a novel search procedure to enumerate good neighbors heuristically. Our search procedure relies on the concept of an improvement graph that allows us to evaluate neighbors much faster than existing methods. In this paper, we present extensive computational results of our algorithms when applied to standard benchmark instances.

Abstract In this article, we study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated by decomposing a given m × n integer matrix into a positive linear combination of (0, 1) matrices with the strict consecutive 1's property in rows. We consider a special case in which no technical constraints have to be taken into account. In this situation, the rows of the intensity matrix are independent of each other and the problem is equivalent to decomposing m intensity rows—independent of each other—into positive linear combinations of (0, 1) rows with the consecutive 1's property. We demonstrate that this problem can be transformed into a minimum cost flow problem in a directed network that has the following special structures: (1) the network is acyclic; (2) it is a complete graph (that is, there is an arc ( i , j ) whenever i < j ); (3) each arc cost is 1; and (4) each arc is uncapacitated (that is, it has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in O( n ) time. Because we need to solve m such problems, the total running time of our algorithm is O( nm ), which is an optimal algorithm to decompose a given m × n integer matrix into a positive linear combination of (0, 1) matrices. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 36–41 2005

Abstract The fleet assignment model (FAM) for an airline assigns fleet types to a set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. The through assignment model matches inbound flight legs into a city with the outbound flight legs at the same city that are flown by the same plane types and creates through connections (that is, flight connections with one stopover). The combined through and fleet assignment model (ctFAM) integrates both the models into a single model and obtains optimal fleet and through assignments by varying both sets of decision variables simultaneously. In a recent article, Ahuja et al. ( 2001 ) proposed a very large‐scale neighborhood (VLSN) search algorithm for the ctFAM. In this article, we generalize this approach to incorporate time windows. In the model considered in this article, each flight leg has a time window associated with its departure time. The objective is to determine fleet assignment, departure time of all flight legs, and through connections between flights to minimize the total cost of fleet assignment and through connections. We call this model ctFAM with time windows or ctFAM‐TW. Allowing flexibility in the flight departure time creates greater opportunities for fleet assignment and through connections, and can reduce costs substantially. We describe the details of a VLSN search algorithm for ctFAM‐TW and also present computational results of our algorithm on the data provided by a large U.S. airline. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 160–171 2004

Abstract In this paper, we study dynamic shortest path problems that determine a shortest path from a specified source node to every other node in the network where arc travel times change dynamically. We consider two problems: the minimum‐time walk problem and the minimum‐cost walk problem. The minimum‐time walk problem is to find a walk with the minimum travel time. The minimum‐cost walk problem is to find a walk with the minimum weighted sum of the travel time and the excess travel time (over the minimum possible travel time). The minimum‐time walk problem is known to be polynomially solvable for a class of networks called FIFO networks. In this paper, (i) we show that the minimum‐cost walk problem is an NP‐hard problem; (ii) we develop a pseudopolynomial‐time algorithm to solve the minimum‐cost walk problem (for integer travel times); and (iii) we develop a polynomial‐time algorithm for the minimum‐time walk problem arising in road networks with traffic lights. © 2003 Wiley Periodicals, Inc.

Abstract An inverse optimization problem is defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x0 ∈ S. We want to perturb the cost vector c to d so that x0 is an optimal solution of P with respect to the cost vector d, and w∥d − c∥p is minimum, where ∥ · ∥p denotes some selected lp norm and w is a vector of weights. In this paper, we consider inverse minimum‐cut and minimum‐cost flow problems under the l1 normal (where the objective is to minimize ∑j∈Jwj|dj − cj| for some index set J of variables) and under the l∞ norm (where the objective is to minimize max{wj|dj − cj|: j ∈ J}). We show that the unit weight (i.e., wj = 1 for all j ∈ J) inverse minimum‐cut problem under the l1 norm reduces to solving a maximum‐flow problem, and under the l∞ norm, it requires solving a polynomial sequence of minimum‐cut problems. The unit weight inverse minimum‐cost flow problem under the l1 norm reduces to solving a unit capacity minimum‐cost circulation problem, and under the l∞ norm, it reduces to solving a minimum mean cycle problem. We also consider the nonunit weight versions of inverse minimum‐cut and minimum‐cost flow problems under the l∞ norm. © 2002 Wiley Periodicals, Inc.

The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum-cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting flows along negative-cost directed cycles in the residual network G(x) and thereby canceling them. For the minimum-cost flow problem with integral data, the generic version of the cycle-canceling algorithm runs in pseudopolynomial time, but several polynomial-time specific implementations can be obtained by specifying the choices of cycles to be canceled. In this paper, we describe a new polynomial-time implementation of the cycle-canceling algorithm. Our algorithm is a scaling algorithm and proceeds by augmenting flows along negative cycles with “sufficiently large” residual capacity. Further, it identifies such a cycle by solving a shortest path problem with nonnegative arc lengths. For a network with n nodes and m arcs, our cycle-canceling algorithm performs O(m log(nU)) augmentations and runs in O(m(m + n log n) log (nU)) time, where U is an upper bound on the node supplies/demands and finite arc capacities. We also show that the cycle-canceling algorithm (i) can solve the uncapacitated minimum-cost flow problem in O(n(m + n log n) log (nU)) time; (ii) can obtain an integer optimal solution of the convex cost-flow problem in O(m(m + n log n) log (nU)) time; and (iii) can be modified so that it runs in O(m(m + n log n) min {log (nU), m log n}) time, which is a strongly polynomial time bound. © 2000 John Wiley & Sons, Inc.

The feature article by Reeves presents an excellent survey of genetic algorithms (GAs). It covers the history of GAs and the application of GAs to combinatorial problems, while providing useful background and a balanced operations research (OR) perspective. In this commentary, we hope to complement the survey by focusing on some aspects of GAs that Reeves did not have an opportunity to comment on in depth.

In the mathematical programming literature, researchers have conducted a large number of computational studies to assess the empirical behavior of various algorithms and have utilized CPU time as the primary measure of performance. CPU time has the following drawbacks as a measure of an algorithm's performance: it is implementation dependent, hard to replicate, and limited in the insight it provides into an algorithm's behavior. In this paper, we illustrate the notion of representative operation counts that can complement the conventional CPU time analysis and can help us (i) to identity the asymptotic bottleneck operations in an algorithm, (ii) to estimate an algorithm's running time for different problem sizes, and (iii) to obtain a fairer comparison of several algorithms. These concepts are easily incorporated into empirical studies and often yield valuable insights into an algorithm's behavior.

Abstract The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more thanD. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow, and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in O((m log M) S(n, m)) time, wherenis the number of nodes in the network;m, the number of arcs; M, an upper bound on the largest element in the data: and S(n, m), the time required to solve a shortest path problem with nonnegative arc lengths. Our algorithms are generalizations of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.

In this paper, network flow algorithms for bipartite networks are studied. A network $G = (V,E)$ is called bipartite if its vertex set V can be partitioned into two subsets $V_1 $ and $V_2 $ such that all edges have one endpoint in $V_1 $ and the other in $V_2 $. Let $n = |V|$, $n_1 = |V_1 |$ , $n_2 = |V_2 |$, $m = |E|$ and assume without loss of generality that $n_1 \leqslant n_2 $. A bipartite network is called unbalanced if $n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow algorithms can be substantially sped up when applied to unbalanced networks. The basic idea in these improvements is a two-edge push rule that allows one to “charge” most computation to vertices in $V_1 $, and hence develop algorithms whose running times depend on $n_1 $ rather than n. For example, it is shown that the two-edge push version of Goldberg and Tarjan’s FIFO preflow-push algorithm runs in $O(n_1 m + n_1^3 )$ time and that the analogous version of Ahuja and Orlin’s excess scaling algorithm runs in $O(n_1 m + n_1^2 \log U)$ time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].

Recently, Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in $O(n^3 )$ time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of $O(nm\log (n^2 /m)$ on m-arc networks. Ahuja and Orlin developed a variant of Goldberg’s algorithm that uses scaling and runs in $O(nm + (n^2 \log U)$ time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of $O(nm + n^2 \log U/\log \log U)$ is obtained by using a nonconstant scaling factor. Second, an even better bound of $O(nm + n^2 (\log U)^{1/2} )$ is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to $O(nm\log (({n / m})(\log U)^{{1 / 2}} + 2))$. This result shows that the combined use of three different techniques, results in speed not obtained by using any of the techniques alone. The above bounds are all for a unit-cost random access machine. Also considered is a semilogarithmic computation model in which the bounds increase by an additive term of $O(m\log _n U)$, which is the time needed to read the input in the model.