Adaptive dynamic cost updating procedure for solving fixed charge network flow problems

We approximate the objective function of the fixed charge network flow problem (FCNF) by a piecewise linear one, and construct a concave piecewise linear network flow problem (CPLNF). A proper choice of parameters in the CPLNF problem guarantees the equivalence between those two problems. We propose a heuristic algorithm for solving the FCNF problem, which requires solving a sequence of CPLNF problems. The algorithm employs the dynamic cost updating procedure (DCUP) to find a solution to the CPLNF problems. Preliminary numerical experiments show the effectiveness of the proposed algorithm. In particular, it provides a better solution than the dynamic slope scaling procedure in less CPU time. Research was partially supported by NSF and Air Force grants.     

Estimation of flows in flow networks

Let G be a directed graph with an unknown flow on each edge such that the following flow conservation constraint is maintained: except for sources and sinks, the sum of flows into a node equals the sum of flows going out of a node. Given a noisy measurement of the flow on each edge, the problem we address, which we call the Most Probable Flow Estimation problem (MPFE), is to estimate the most probable assignment of flow for every edge such that the flow conservation constraint is maintained. We provide an algorithm called ΔY-mpfe for solving the MPFE problem when the measurement error is Gaussian (Gaussian-MPFE). The algorithm works in O(∣E∣ + ∣V∣²) when the underlying undirected graph of G is a 2-connected planar graph, and in O(∣E∣ + ∣V∣) when it is a 2-connected serial-parallel graph or a tree. This result is applicable to any Minimum Cost Flow problem for which the cost function is τ_e(X_e − μ_e)² for edge e where μ_e and τ_e are constants, and X_e is the flow on edge e. We show that for all topologies, the Gaussian-MPFE’s precision for each edge is analogous to the equivalent resistance measured in series to this edge in an electrical network built by replacing every edge with a resistor reflecting the measurement’s precision on that edge.     

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.     

A note on the parametric maximum flow problem and some related reoptimization issues

In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in Gallo, Grigoriadis, and Tarjan (1989), and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property (Arai, Ueno, and Kajitani, 1993). A consequence is that the corresponding parametric maximum flow value function has at most n −1 breakpoints. All the minimum cut capacities can therefore be computed by O(1) maximum flow computations. We will show then that, given O(n) increasing values of the parameter, it is possible to compute the corresponding maximum flows by O(1) maximum flow computations, by suitably extending Goldberg and Tarjan’s maximum flow algorithm.     

On the plane problem of the flow around a submerged beam

We consider the problem of the steady flow of an ideal heavy fluid around a submerged beam. The problem is obtained from the free-boundary problem of the flow past a submerged obstacle in the limit of bodies of vanishing thickness. We introduce a special Sobolev space formulation of the problem in term of a perturbed stream function and prove its unique solvability for every value of the unperturbed flow velocity, with the possible exception of a discrete set depending on the geometry of the domain. The asymptotic properties of the solutions are discussed.     

Local optimality conditions for multicommodity flow problems with separable piecewise convex costs

We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case.     

New mathematical models of the generalized vehicle routing problem and extensions

The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta [1]. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bekta? formulation [2], but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case.     

节点有自环的网络流数学模型

以网络流中节点有自环的情形为对象进行研究,把节点分开为入点和出点,节点自环转换为流量相同,方向相反的两条弧,改进了网络流数学模型.改进后的数学模型在处理原来网络流中节点发生异常情况时,即节点不遵守流量守恒条件时,其节点自环的流能够起特殊的调节作用.在描述网络流异常状态时,给出了网络流状态周期的阶跃性质.通过网络模型对应的邻接矩阵对网络流进行计算和监控,给出一个节点环流的应用实例.     

Diagnosing infeasibilities in network flow problems

We consider the problem of finding a feasible flow in a directed networkG = (N,A) in which each nodei N has a supplyb(i), and each arc(i,j) A has a zero lower bound on flow and an upper boundu _ij . It is well known that this feasibility problem can be transformed into a maximum flow problem. It is also well known that there is no feasible flow in the networkG if and only if there is a subsetS of nodes such that the net supplies of the nodes inS exceeds the capacity of the arcs emanating fromS. Such a setS is called awitness of infeasibility (or, simply, awitness) of the network flow problem. In the case that there are many different witnesses for an infeasible problem, a small cardinality witness may be preferable in practice because it is generally easier for the user to assimilate, and may provide more guidance to the user on how to identify the cause of the infeasibility. Here we show that the problem of finding a minimum cardinality witness is NP-hard. We also consider the problem of determining aminimal witness, that is, a witnessS such that no proper subset ofS is also a witness. In this paper, we show that we can determine a minimal witness by solving a sequence of at mostn maximum flow problems. Moreover, if we use the preflow-push algorithm to solve the resulting maximum flow problems and organize computations properly, then the total time taken by the algorithm is comparable to that of solving a single maximum flow problem. This approach determines a minimal cardinality witness in O(n ² m ^1/2) time using simple data structures and in O(nm logn) time using the standard implementation of the dynamic tree data structures. We also show that the recognition version of the minimal witness problem is equivalent to a recognition version of a related problem known as theminimum rooted cut problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

The firefighter problem for cubic graphs

We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two.     

Note on “Inverse minimum cost flow problems under the weighted Hamming distance”

Jiang et al. proposed an algorithm to solve the inverse minimum cost flow problems under the bottleneck-type weighted Hamming distance [Y. Jiang, L. Liu, B. Wuc, E. Yao, Inverse minimum cost flow problems under the weighted Hamming distance, European Journal of Operational Research 207 (2010) 50–54]. In this note, it is shown that their proposed algorithm does not solve correctly the inverse problem in the general case due to some incorrect results in that article. Then, a new algorithm is proposed to solve the inverse problem in strongly polynomial time. The algorithm uses the linear search technique and solves a shortest path problem in each iteration.     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

Gas dynamics applications of a characteristic Cauchy problem

Some initial-boundary-value problems for a system of quasilinear partial differential equations of gas dynamics with the initial data prescribed on the characteristic surface (characteristic Cauchy problem) are considered. The following three-dimensional flow problems are investigated: the flow produced by a motion of an impermeable piston; the flow produced by a permeable piston with a given pressure; and the flow produced by the moving free boundary. In the first two problems, the piston motion is prescribed; in the last problem, the free boundary motion cannot be prescribed in advance and must be determined as a part of the problem. It is shown that those problems can be reduced to a characteristic Cauchy problem of a certain standard type that satisfies the analog of Cauchy-Kowalewski's existence theorem in the class of analytical functions (Differential Equations 12 (1977) 1438-1444). Thus, it is proved that, in the case of the analyticity of the input data, the considered problems have unique piecewise analytic solutions which may be expressed by infinite power series (the procedure of constructing the power series solution is described in Differential Equations 12 (1977) 1438-1444 as a part of the proof of the theorem).     

Multicomponent flow modeling

We present multicomponent flow models derived from the kinetic theory of gases and investigate the symmetric hyperbolic-parabolic structure of the resulting system of partial differential equations.We address the Cauchy problem for smooth solutions as well as the existence of deflagration waves,also termed anchored waves.We further discuss related models which have a similar hyperbolic-parabolic structure,notably the SaintVenant system with a temperature equation as well as the equations governing chemical equilibrium flows.We next investigate multicomponent ionized and magnetized flow models with anisotropic transport fluxes which have a different mathematical structure.We finally discuss numerical algorithms specifically devoted to complex chemistry flows,in particular the evaluation of multicomponent transport properties,as well as the impact of multicomponent transport.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

A knapsack intersection hierarchy

We introduce a knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs. In level t of the hierarchy, all valid cuts are added for the integer hull of the intersection of all t-row relaxations. This model captures the maximum possible strength of t-row cuts, an approach often used by solvers for small t. We investigate the integrality gap of the strengthened formulations on the all-or-nothing flow problem in trees (also called unsplittable flow on trees).     

Constraint preserving implicit finite element discretization of harmonic map flow into spheres

Discretization of the harmonic map flow into spheres often uses a penalization or projection strategy, where the first suffers from the proper choice of an additional parameter, and the latter from the lack of a discrete energy law, and restrictive mesh-constraints. We propose an implicit scheme that preserves the sphere constraint at every node, enjoys a discrete energy law, and unconditionally converges to weak solutions of the harmonic map heat flow.

     

对称的运输问题及其逆问题

本文对［１,２,６］中提出的运输问题进行了推广,并提出了一个强多项式算法,从而改进了原有的结果．同时对对称的运输问题的逆问题进行了研究,并借助于最小费用循环流技术得到了一个强多项式算法．