Near-perfect token distribution

Suppose that n tokens are arbitrarily placed on the n nodes of a graph. At each parallel step one token may be moved from each node to an adjacent node. An algorithm for the near-perfect token distribution problem redistributes the tokens in a finite number of steps, so that, at the end, no more than O(1) tokens reside at each node. (In perfect distribution, at the end, exactly one token resides at each node.) In this paper we present a simple algorithm that works for all extrovert graphs, a new property which we define and study. In terms of connectivity requirements, extrovert graphs are roughly in-between expanders and compressors. Our results lead to an optimal solution for the near-perfect token distribution problem on almost all cubic graphs. The new solution is conceptually simpler than previous algorithms, and applies to graphs of minimum possible degree. © 1994 John Wiley & Sons, Inc.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

Book Notices

Finding Pareto-minimum vectors among r given vectors, each of dimension m, is a fundamental problem in multiobjective optimization problems or multiple-criteria decision-making problems. Corley and Moon (Ref. 1) have given an algorithm for finding all the Pareto-minimum paths of a multiobjective network optimization problem from the initial node to any other node. It uses another algorithm by Corley and Moon, which actually computes the Pareto-minimum vectors. We observed that the latter algorithm is incorrect. In this note, we correct the algorithm for computing Pareto-minimum vectors and present a modified algorithm.     

A branch-and-cut algorithm based on semidefinite programming for the minimum <Emphasis Type="Italic">k</Emphasis>-partition problem

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the MkP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

On the approximation of the single source k-splittable flow problem

This work deals with the minimum congestion single-source k-splittable flow problem: given a network and a set of terminal pairs sharing a common source node, the aim is to route concurrently all demands using at most k supporting paths for each commodity and minimizing the congestion on arcs. Dinitz et al. proposed in [Y. Dinitz, N. Garg, M.X. Goemans, On the single-source unsplittable flow problem, Combinatorica 19 (1999) 17–41] the best known constant factor approximated algorithm for the case of $k=1$, namely the single source unsplittable case. Here we consider an adaptation of such an algorithm to the k-splittable case. Moreover, we propose a heuristic improvement of the first step of this algorithm, that provides experimentally better results without affecting the approximation guarantee of the algorithm.     

Solving Toeplitz Least Squares Problems by Means of Newton's Iteration

We extend the algorithm of [4], based on Newton's iteration and on the concept of -displacement rank, to the computation of the generalized inverse A ⁺ of an m×n Toeplitz matrix A. We introduce new strategies for the dynamical control of the truncation level at each step of the iteration. Numerical experiments and an application to a problem of image restoration are shown. An object-oriented implementation in C++ is described.     

Fair transfer price and inventory holding policies in two-enterprise supply chains

A key issue in supply chain optimisation involving multiple enterprises is the determination of policies that optimise the performance of the supply chain as a whole while ensuring adequate rewards for each participant.In this paper, we present a mathematical programming formulation for fair, optimised profit distribution between echelons in a general multi-enterprise supply chain. The proposed formulation is based on an approach applying the Nash bargaining solution for finding optimal multi-partner profit levels subject to given minimum echelon profit requirements.The overall problem is first formulated as a mixed integer non-linear programming (MINLP) model. A spatial and binary variable branch-and-bound algorithm is then applied to the above problem based on exact and approximate linearisations of the bilinear terms involved in the model, while at each node of the search tree, a mixed integer linear programming (MILP) problem is solved. The solution comprises inter-firm transfer prices, production and inventory levels, flows of products between echelons, and sales profiles.The applicability of the proposed approach is demonstrated by a number of illustrative examples based on industrial processes.     

Optimum synthesis of discrete capacitated networks with multi-terminal commodity flow requirements

Network design problems arise in a wide range of applied areas including telecommunications, computer networks, and transportation. In this paper, we address the following discrete capacitated multi-terminal network design problem. Given a connected digraph G = (V,A), a set of L potential facilities to be installed on each arc, and a set of K multi-terminal (non-simultaneous) commodity flow requirements, the problem is to find a set of facilities to install in order to route the K nonsimultaneous flows while minimizing the total fixed plus variable costs. We describe an exact procedure for solving this problem based on Benders decomposition. Our algorithm includes several features that significantly improve the efficiency of the basic approach. Computational results attest to the efficacy of the proposed algorithm, which can solve medium- to large-scale problems to optimality.     

A power sparse approximate inverse preconditioning procedure for large sparse linear systems

Motivated by the Cayley–Hamilton theorem, a novel adaptive procedure, called a Power Sparse Approximate Inverse (PSAI) procedure, is proposed that uses a different adaptive sparsity pattern selection approach to constructing a right preconditioner M for the large sparse linear system Ax=b. It determines the sparsity pattern of M dynamically and computes the n independent columns of M that is optimal in the Frobenius norm minimization, subject to the sparsity pattern of M. The PSAI procedure needs a matrix–vector product at each step and updates the solution of a small least squares problem cheaply. To control the sparsity of M and develop a practical PSAI algorithm, two dropping strategies are proposed. The PSAI algorithm can capture an effective approximate sparsity pattern of A^?1 and compute a good sparse approximate inverse M efficiently. Numerical experiments are reported to verify the effectiveness of the PSAI algorithm. Numerical comparisons are made for the PSAI algorithm and the adaptive SPAI algorithm proposed by Grote and Huckle as well as for the PSAI algorithm and three static Sparse Approximate Inverse (SAI) algorithms. The results indicate that the PSAI algorithm is at least comparable to and can be much more effective than the adaptive SPAI algorithm and it often outperforms the static SAI algorithms very considerably and is more robust and practical than the static ones for general problems. Copyright © 2008 John Wiley & Sons, Ltd.     

Orthogonal similarity transformation into block‐semiseparable matrices of semiseparability rank k

Very recently, an algorithm, which reduces any symmetric matrix into a semiseparable one of semi‐ separability rank 1 by similar orthogonality transformations, has been proposed by Vandebril, Van Barel and Mastronardi. Partial execution of this algorithm computes a semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the Lanczos' process applied to the original matrix. Also a kind of nested subspace iteration is performed at each step. In this paper, we generalize the above results and propose an algorithm to reduce any symmetric matrix into a similar block‐semiseparable one of semiseparability rank k, with k ∈ ?, by orthogonal similarity transformations. Also in this case partial execution of the algorithm computes a block‐semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the block‐Lanczos' process with k starting vectors, applied to the original matrix. Subspace iteration is performed at each step as well. Copyright © 2005 John Wiley & Sons, Ltd.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

Exact and heuristic solutions of the global supply chain problem with transfer pricing

We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx [Vidal, C.J., Goetschalckx, M., 2001. A global supply chain model with transfer pricing and transportation cost allocation. European Journal of Operational Research 129 (1), 134–158] proposed a bilinear model of this problem and solved it by an Alternate heuristic. We propose a reformulation of this model reducing the number of bilinear terms and accelerating considerably the exact solution. We also present three other solution methods: an implementation of Variable Neighborhood Search (VNS) designed for any bilinear model, an implementation of VNS specifically designed for the problem considered here and an exact method based on a branch and cut algorithm. The solution methods are tested on artificial instances. These results show that our implementation of VNS outperforms the two other heuristics. The exact method found the optimal solution of all small instances and of 26% of medium instances.     

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths. A natural approach to this problem is through a multicommodity flow reduction. However, we show that the random walk approach leads to significantly stronger‐results than those recently obtained by Leighton and Rao [Proc. of 9th International Parallel Processing Symposium, 1995] using the multicommodity flow setup. In the dynamic version of the problem connection requests are continuously injected into the network. Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the path is deleted. Again each edge in the network should not be used by more than g paths at once. The dynamic version is a better model for the practical use of communication networks. Our random walk approach gives a simple and fully distributed solution for this problem. We show that if the injection to the network and the duration of connection are both controlled by Poisson processes then our algorithm achieves a steady state utilization of the network which is similar to the utilization achieved in the static case situation. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 87–109, 1999     

Thresholds and optimal binary comparison search trees

We present an O(n⁴)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n⁵) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree.     

Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

On fully discrete Galerkin methods of second-order temporal accuracy for the nonlinear Schrödinger equation

Summary We approximate the solutions of an initial- and boundary-value problem for nonlinear Schrödinger equations (with emphasis on the cubic nonlinearity) by two fully discrete finite element schemes based on the standard Galerkin method in space and two implicit. Crank-Nicolson-type second-order accurate temporal discretizations. For both schemes we study the existence and uniqueness of their solutions and proveL ² error bounds of optimal order of accuracy. For one of the schemes we also analyze one step of Newton's method for solving the nonlinear systems that arise at every time step. We then implement this scheme using an iterative modification of Newton's method that, at each time stept ⁿ , requires solving a number of sparse complex linear systems with a matrix that does not change withn. The effect of this inner iteration is studied theoretically and numerically.The work of these authors was supported by the Institute of Applied and Computational Mathematics of the Research Center of Crete-FORTH and the Science Alliance program of the University of TennesseeThe work of this author was supported by the AFOSR Grant 88-0019     

循环取货模式下的多车场协同运输问题研究

分析循环取货模式和协同运输问题的关联性,提出了供需节点分离下的多车场一体化协同运输路线优化问题,考虑运输价值和运输成本,引入节点-弧流量的概念,通过比较流量大小确定节点集合,构建了问题的多供应点、多需求点运输模型.考虑取货的单向性和送货的闭合性,构造了求解模型的两阶段算法,运用动态规划的递推解法确定取货最优路线,然后基于余弦定理的几何法求解出发点和返回点不相同的送货路径优化问题,最后通过算例分析,说明了模型的合理性和算法的有效性.