Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

Optimization of strategic defenses to provide specified post-attack production capacities

This paper presents a model for choosing a minimum-cost mix of strategic defenses to assure that specified production capacities for several economic sectors survive after a nuclear attack. The defender selects a mix of strategic defenses for each of several geographic regions. The attacker chooses an allocation of attacking weapons to geographic regions, within specified weapon inventories. The attack is optimized against any economic sector. This formulation allows the defense planner the capability to assess the results of the optimal defense structure for a “worst case” attack. The model is a mathematical program with nonlinear programming problems in the constraints; an example of its application is given and is solved using recently developed optimization techniques.     

Demand shuffle—A method for multilevel proportional lot sizing and scheduling

This contribution acquaints the reader with a model for multilevel single-machine proportional lot sizing and scheduling problems (PLSPs) that appear in the scope of short-term production planning. It is one of the first articles that deals with dynamic capacitated multilevel lot sizing and scheduling, which is of great practical importance. The PLSP model refines well-known mixed-integer programming formulations for dynamic capacitated lot sizing and scheduling as, for instance, the DLSP or the CSLP. A special emphasis is given on a new method called demand shuffle to solve multilevel PLSP instances efficiently but suboptimally. Although the basic idea is very simple, it becomes clear that in the presence of precedence and capacity constraints many nontrivial details are to be concerned. Computational studies show that the presented approach decidedly improves recent results. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 319–340, 1997     

Optimal power control in a wireless network using a model with stochastic link coefficients

This paper addresses optimal power allocation in a wireless communication network under uncertainty. The paper introduces a framework for optimal transmit power allocation in a wireless network where both the useful and interference coefficients are random. The new approach to power control is based on a stochastic programming formulation with probabilistic SIR constraints. This allows to state the power allocation problem as a convex optimization problem assuming normally or log‐normally distributed communication link coefficients. Numerical examples illustrate the performance of the optimal stochastic power allocation. A distributed algorithm for the decentralized solution of the stochastic power allocation problem is discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

An efficient primal approach to bottleneck transportation problems

This article addresses bottleneck linear programming problems and in particular capacitated and constrained bottleneck transportation problems. A pseudopricing procedure based on the poly-ω procedure is used to facilitate the primal simplex procedure. This process allows the recent computational developments such as the Extended Threaded Index Method to be applied to bottleneck transportation problems. The impact on problem solution times is illustrated by computational testing and comparison with other current methods.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.     

基于Stateflow的PERT网络仿真方法

介绍了基于Stateflow的PERT网络仿真方法,详细阐述了建模思路、建模步骤以及难点问题的解决方法,并对PERT网络实例进行了仿真。该方法容许工序的持续时间服从任意分布,而且可以考虑所有可能出现的关键路线。     

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Minimal disconnecting sets in directed multi-commodity networks

The problem of finding minimal disconnecting sets for multi-commodity directed networks may be solved using an arc-path formulation and Gomory's all-integer integer programming algorithm. However, the number of network constraints may be astronomical for even moderately sized networks. This paper develops a finite algorithm similar to Gomory's, but requiring no more than m rows in the tableau, where m is the number of arcs in the network.     

A class of parametric properties of transportation problems

This paper studies certain “second order” parametric relations in capacitated transportation problems. These relations concern the question of what happens to the effect of a parameter (first derivative) as another parameter is varied. These relationships have been found quite useful in the solution of many types of facility location and capacity expansion problems. The paper presents several results on the parametric behavior of the dual multipliers from which second order parametric relations can be derived.     

多约束条件下互联网骨干网路由器级拓扑生成方法

互联网骨干网是网络流量的中枢传输系统,其路由器级拓扑结构对于网络抗毁性分析具有重要意义。由于难以获取互联网骨干网路由器级的真实拓扑,通过分析骨干网的形成因素,将地理位置、节点间联系强度、基础设施费用、鲁棒性等因素结合起来,提出一种多约束条件下的互联网骨干网路由器级拓扑生成方法。该方法既可以构造难以公开获取网络测量数据的骨干网,也可以用来生成某一骨干网的多种替身拓扑集。通过现实中的互联网骨干网作为实例,验证了方法的有效性。     

Economic ordering decisions with market choice flexibility

Standard approaches to classical inventory control problems treat satisfying a predefined demand level as a constraint. In many practical contexts, however, total demand is comprised of separate demands from different markets or customers. It is not always clear that constraining a producer to satisfy all markets is an optimal approach. Since the inventory‐related cost of an item depends on total demand volume, no clear method exists for determining a market's profitability a priori, based simply on per unit revenue and cost. Moreover, capacity constraints often limit a producer's ability to meet all demands. This paper presents models to address economic ordering decisions when a producer can choose whether to satisfy multiple markets. These models result in a set of nonlinear binary integer programming problems that, in the uncapacitated case, lend themselves to efficient solution due to their special structure. The capacitated versions can be cast as nonlinear knapsack problems, for which we propose a heuristic solution approach that is asymptotically optimal in the number of markets. The models generalize the classical EOQ and EPQ problems and lead to interesting optimization problems with intuitively appealing solution properties and interesting implications for inventory and pricing management. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An efficient heuristic procedure for the capacitated warehouse location problem

This paper introduces an efficient heuristic procedure for solving a special class of mixed integer programming problem called the capacitated warehouse (plant) location problem. This procedure parallels the work reported earlier in [9] on the uncapacitated warehouse location problem. The procedure can be viewed as tracing a judiciously selected path of the branch and bound tree (from the initial node to the terminal node) to arrive at a candidate solution. A simple backtracking scheme is also incorporated in the procedure to investigate possible improvement in the solution. Computational results on problems found in the literature look quite encouraging.     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Machine sequencing: Disjunctive graphs and degree-constrained subgraphs

In two earlier papers, we proposed algorithms for finding an optimal sequence of processing m items on q machines, by finding a minimaximal path in a disjunctive network. In a third paper, this latter model was generalized (from 2-state to 3-state disjunctive graphs) so as to accommodate project scheduling with resource constraints. In this paper, we discuss another algorithm for the (2-state) disjunctive network problem, closely related to those mentioned above. To make the paper self-contained, section 2 briefly describes the problem. Section 3 introduces a class of constraints which forms the basis of the algorithm discussed in section 4. The constraints have only 1, ?1, or 0 as coefficients on the left-hand side, integers on the right-hand side. The whole procedure of generating these constraints and finding a feasible solution whenever a new constraint is added, can be interpreted (section 5) as a process of generating a graph with degree-constraints on its nodes, and then finding a subgraph satisfying the degree-constraints. The nodes of the graph are generated by solving a critical-path-problem, the feasible subgraphs are found by implicit enumeration.     

An operator theory of parametric programming for the transportation problem-II

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-, the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. Operators that effect the transformation of optimum solution associated with such data changes, are shown to be a product of basis preserving operators (described in the earlier paper) that operate on a sequence of adjacent basis structures. Algorithms are provided for both rim and cost operators. The paper concludes with a discussion of the economic and managerial interpretations of the operators.     

Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety‐oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space‐time network representation in the formulations, the reliability‐based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0‐1 variables to denote the time‐dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small‐scale case and a real‐world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.     

An operator theory of parametric programming for the generalized transportation problem: II Rim,cost and bound operators

This paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when certain data of the problem are continuously varied as a linear function of a single parameter. First the rim conditions, then the cost coefficients, and finally the cell upper bounds are varied parametrically and the effect on the optimal solution, the associated change in costs and the dual changes are derived. Finally the effect of simultaneous changes in both cost coefficients and rim conditions are investigated. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum bases are preserved.     

An operator theory of parametric programming for the transportation problem-I

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. An operator theory is developed and algorithms provided for applying rim and cost operators that effect the transformation of optimum solution associated with changes in rim conditions and unit costs. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum basis structures are preserved.