Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

The Estermann cubic problem with almost equal summands

We prove an asymptotic formula for the number of representations of a sufficiently large natural number N as the sum of two primes p ₁ and p ₂ and the cube of a natural numbermsatisfying the conditions |p _i ? N/3| ≤ H, |m ³ ? N/3| ≤ H, H ≥ N ^5/6 ? ¹⁰.     

The quickest flow problem

Consider a network =(G, c, ) whereG=(N, A) is a directed graph andc _ij and _ij , respectively, denote the capacity and the transmission time of arc (i, j) A. The quickest flow problem is then to determine for a given value the minimum numberT() of time units that are necessary to transmit (send) units of flow in from a given sources to a given sinks.In this paper we show that the quickest flow problem is closely related to the maximum dynamic flow problem and to linear fractional programming problems. Based on these relationships we develop several polynomial algorithms and a strongly polynomial algorithm for the quickest flow problem.Finally we report computational results on the practical behaviour of our metholds. It turns out that some of them are practically very efficient and well-suited for solving large problem instances.Partial financial support by the Air Force Office of Scientific Research under grants AFOSR-89-0512 and AFOSR-90-0008 is gratefully acknowledged by the first author.     

The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

The hub covering flow problem

The hub covering flow problem (HCFP) seeks to find the minimal cost hub-and-spoke network by optimally locating hub nodes and assigning non-hub nodes to the hub nodes subject to a coverage constraint. The cost of establishing such a hub network is based on a fixed cost of opening hubs and the cost of transporting demand flow through the network. We also present an extension called the multi-aircraft HCFP. The results from computational experiments are presented and discussed.     

The generalized Estermann ternary problem for noninteger powers with almost equal summands

An asymptotic formula in the generalized Estermann ternary problem for noninteger powers with almost equal summands dealing with the representation of a sufficiently large natural number as the sum of two primes and the integer part of a noninteger power of a natural number is proved.     

Nonadaptive search problem with sets of equal sum

Consider the set A={1,2,3,…,2 ⁿ }, n≥3 and let x∈ A be unknown element. For given natural number S we are allowed to ask whether x belongs to a subset B of A such that the sum of the elements of B equals S. We investigate for which S it is possible to find x using a nonadaptive search.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

The inverse maximum dynamic flow problem

We consider the inverse maximum dynamic flow (IMDF) problem. IMDF problem can be described as: how to change the capacity vector of a dynamic network as little as possible so that a given feasible dynamic flow becomes a maximum dynamic flow. After discussing some characteristics of this problem, it is converted to a constrained minimum dynamic cut problem. Then an efficient algorithm which uses two maximum dynamic flow algorithms is proposed to solve the problem.     

Geodesic flow on three-dimensional ellipsoids with equal semi-axes

Following on from our previous study of the geodesic flow on three dimensional ellipsoid with equal middle semi-axes, here we study the remaining cases: Ellipsoids with two sets of equal semi-axes with SO(2) × SO(2) symmetry, ellipsoids with equal larger or smaller semiaxes with SO(2) symmetry, and ellipsoids with three semi-axes coinciding with SO(3) symmetry. All of these cases are Liouville-integrable, and reduction of the symmetry leads to singular reduced systems on lower-dimensional ellipsoids. The critical values of the energy-momentum maps and their singular fibers are completely classified. In the cases with SO(2) symmetry there are corank 1 degenerate critical points; all other critical points are non-degenreate. We show that in the case with SO(2) × SO(2) symmetry three global action variables exist and the image of the energy surface under the energy-momentum map is a convex polyhedron. The case with SO(3) symmetry is non-commutatively integrable, and we show that the fibers over regular points of the energy-casimir map are T ² bundles over S ².      

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

Multicommodity flow problem

The problem of nonmixing multicommodity flow is investigated. The theorem on the number of nonmixing flows of different commodities passing simultaneously through an oriented network is proved.Translated from Dinamicheskie Sistemy, No. 5, pp. 95–97, 1986.     

Non-isothermal gas flow in microchannel with equal wall temperatures

A non-isothermal two-dimensional compressible subsonic slip gas flows is analyzed in this paper. It is pressure-driven steady flow in microchannels with variable cross section (convergent, divergent, and constant height channel). Since the flows correspond to microspaces, the rarefaction effect is taken in account. The obtained gas temperature profiles are non-uniform. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

The two-machine total completion time flow shop problem

In this paper we study the NP-hard scheduling problem of minimizing total completion time in a two-machine flow shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criterion is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower bounds. A heuristic procedure is also presented that uses a constructive O(n²) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computational results show that the exact method can handle problems of up to 30 jobs in size within a reasonable amount of time and that the heuristic procedure has an average error of less than 0.5% from the optimal value and less than 2.7% from the lower bound.     

The fractional minimal cost flow problem on network

A problem and a new algorithm are given for the linear fractional minimal cost flow problem on network. Using a new check number and combining the characteristic of network to extend the traditional theories of minimum cost flow problem, discussed the relation between it and its dual problem. Optimality conditions are derived and a Network Simplex Algorithm is proposed that leads to optimal solution assuming certain properties. Finally, an numerical example test is also developed.     

The missing boundary problem for smooth manifolds of dimension greater than or equal to six

Let M be a non-compact differentiable manifold of dimension ?6. Suppose both M and ?M are 1-ended spaces. We give necessary and sufficient conditions for M to be diffeomorphic to the complement of a compact subset of the boundary of a compact manifold. There are four conditions: two geometric conditions and two algebraic obstructions. We give examples to show that these obstructions are not always trivial. In particular, an example of a manifold is constructed which does not have a completion but any tubular neighborhood of codimension ?3 has a completion. We also classify the different ways to complete a given manifold.     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.