Search

We propose an algorithm for constructing orthogonal n-ary operations which is called a block composition algorithm here. Input data of the algorithm are two series of different arity operations being distributed by blocks. The algorithm consists of two parts: composition algorithm for constructing n-ary operations with orthogonal retracts from given blocks of operations and block-wise recursive algorithm for constructing orthogonal n-ary operations from obtained operations. Obtained results are illustrated by examples of orthogonal n-ary operations which are constructible by block-wise recursive algorithm and non-constructible by the well-known trivial recursive algorithm.

This paper proposes an efficient segregated solution procedure for the two-dimensional incompressible fluid flow on unstructured grids. The new algorithm is called SIMPLERR (SIMPLERR-revised algorithm). It includes an inner iterative process that consists of a pressure equation solution and an explicit velocity correction, and then, the pressure field is obtained by another solving process for the pressure equation. The features and advantages of the SIMPLERR algorithm are demonstrated by solving a benchmark flow problem, and the results indicate that the SIMPLERR algorithm can maintain a strong stability as the IDEAL algorithm and can converge faster than the SIMPLER algorithm or even than the IDEAL algorithm. The advantage of the SIMPLERR algorithm is especially evident for high-Re and fine-mesh fluid flow cases, where the SIMPLERR algorithm and the IDEAL algorithm can obtain a convergence result but the SIMPLER algorithm cannot. The SIMPLERR algorithm is about two times faster than the IDEAL al...

Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set \(\{0,1,\ldots ,T\}\) of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is \(O(n^2m)\).

Given a directed graph with a capacity and a transit time for each arc and with single source and single sink nodes, the quickest flow problem is to find the minimum time horizon to send a given amount of flow from the source to the sink. This is one of the fundamental dynamic flow problems. Parametric search is one of the basic approaches to solving the problem. Recently, Lin and Jaillet (SODA, 2015) proposed an algorithm whose time complexity is the same as that of the minimum cost flow algorithm. Their algorithm employs a cost scaling technique, and its time complexity is weakly polynomial time. In this article, we modify their algorithm by adopting a technique to construct a strongly polynomial time algorithm for solving the minimum cost flow problem. The proposed algorithm runs in O ( n m 2 ( log n ) 2 ) time, where n and m are the numbers of nodes and arcs, respectively. © 2016 Wiley Periodicals, Inc. NETWORKS, 2016

We investigate variants of the max-flow problem in a network under k attacks. The network interdiction problem is to find the minimum max-flow value among (mk) networks that can be obtained by deleting each set of k links. The adaptive network flow problem is to find a flow of the network such that the flow value is maximum against any set of k links attack, when deleting the corresponding flow to those k links in the original flow. First, we prove that max-(k+1)-route flow is a (k+1)-approximation for both problems. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Then in a second phase, we investigate properties of the function taking the real value h to the max h-route flow value, and apply the result to solve both of the problems. We show that the function is piecewise hyperbolic, and modify a standard parametric optimization technique to find this function. The running time of the algorithm is O(T), when is a sourcesink edge connectivity of our network and T the computation time of a max-flow algorithm. We show that for some instances, when h is optimally chosen, the max- h-route flow is an exact solution for both problems. Maximum multiroute flow algorithm is a (k+1)-approximation algorithm for the network interdiction and adaptive network flow problems.If a parameter of the algorithm is optimally adjusted, the algorithm can be an exact algorithm when the input network satisfies a condition.Experimental results shown that most of the problem instances satisfy the condition.

A novel predictive measure that predicts which algorithm is best at any given point in time. Always select the predicted best algorithm to run for the next generation.The performance of our method is very competitive if viewed as another novel "individual" algorithm.A very interesting positive synergistic effect is found between algorithms in our method.A novel performance evaluation method that makes a lot of sense when one has an absolute maximum number of function evaluations allowed in your application.Application on a Heating Ventilation and Air Conditioning design problem demonstrates that the method can be used to solve real world problems with constraints and that it performs better than choosing an algorithm randomly. Many good evolutionary algorithms have been proposed in the past. However, frequently, the question arises that given a problem, one is at a loss of which algorithm to choose. In this paper, we propose a novel algorithm portfolio approach to address the above problem for single objective optimization. A portfolio of evolutionary algorithms is first formed. Covariance Matrix Adaptation Evolution Strategy (CMA-ES), History driven Evolutionary Algorithm (HdEA), Particle Swarm Optimization (PSO2011) and Self adaptive Differential Evolution (SaDE) are chosen as component algorithms. Each algorithm runs independently with no information exchange. At any point in time, the algorithm with the best predicted performance is run for one generation, after which the performance is predicted again. The best algorithm runs for the next generation, and the process goes on. In this way, algorithms switch automatically as a function of the computational budget. This novel algorithm is named Multiple Evolutionary Algorithm (MultiEA). The predictor we introduced has the nice property of being parameter-less, and algorithms switch automatically as a function of budget. The following contributions are made: (1) experimental results on 24 benchmark functions show that MultiEA outperforms (i) Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO); (ii) Population-based Algorithm Portfolio (PAP); (iii) a multiple algorithm approach which chooses an algorithm randomly (RandEA); and (iv) a multiple algorithm approach which divides the computational budget evenly and execute all algorithms in parallel (ExhEA). This shows that it outperforms existing portfolio approaches and the predictor is functioning well. (2) Moreover, a neck to neck comparison of MultiEA with CMA-ES, HdEA, PSO2011, and SaDE is also made. Experimental results show that the performance of MultiEA is very competitive. In particular, MultiEA, being a portfolio algorithm, is sometimes even better than all its individual algorithms, and has more robust performance. (3) Furthermore, a positive synergic effect is discovered, namely, MultiEA can sometimes perform better than the sum of its individual EAs. This gives interesting insights into why an algorithm portfolio is a good approach. (4) It is found that MultiEA scales as well as the best algorithm in the portfolio. This suggests that MultiEA scales up nicely, which is a desirable algorithmic feature. (5) Finally, the performance of MultiEA is investigated on a real world problem. It is found that MultiEA can select the most suitable algorithm for the problem and is much better than choosing algorithms randomly.

Maximum Flow Problem (MFP) discusses the maximum amount of flow that can be sent from the source to sink. Edmonds-Karp algorithm is the modified version of Ford-Fulkerson algorithm to solve the MFP. This paper presents some modifications of Edmonds-Karp algorithm for solving MFP. Solution of MFP has also been illustrated by using the proposed algorithm to justify the usefulness of proposed method.

We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in 11] for Fisher's model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. Our algorithm performs O ( n 6 log ? ( n U ) ) maximum flow computations, where n is the number of agents and U is the maximum integer utility. The flows have to be presented as numbers of bitlength O ( n log ? ( n U ) ) to guarantee an exact solution. Previously, 22,29] have given polynomial time algorithms for this problem, which are based on solving convex programs using the ellipsoid algorithm and the interior-point method, respectively.

We consider the problem of finding a maximum flow in networks with strictly and nonstrictly determined flow distribution. We show that, for each condition of flow distribution, a solution to the problem under consideration exists and is unique. Some algorithms for finding a maximum flow are developed for each condition of flow distribution. We find bounds for the maximum flow value in networks with strict flow distribution.

Most of the techniques of nonlinear optimization assume the existence of a differential function, but there also exist other approaches. In this paper, we propose a non-differential algorithm that solves the problem of minimization and maximization for any objective function of several unknown variables. The algorithm searches for a solution vector of variables that yields the optimal result of the objective function, using a trial-and-error process. The algorithm is not fast, but it converges to a non-trivial solution, if it exists. The method will be used to determine the minimum and the maximum of the outputs of a socio-political model of E-Democracy. This model of E-Democracy is based on a Mamdani fuzzy inference system. We provide formalization and Matlab implementation for our fuzzy system and for the algorithm

This paper investigates uncertain maximum flow problem. To obtain the uncertainty distribution of the maximum flow, an α -maximum flow model is formulated under uncertainty theory framework. It is proved that there exists an equivalence relationship between the α -maximum flow model and the classic deterministic maximum flow model. Furthermore, some important properties of α -maximum flow model are analyzed, based on which a polynomial algorithm is proposed. Finally, a numerical example is presented to illustrate the model and the algorithm.

The paper presents a 1.692nnO(1)-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890nnO(1)-time polynomial-space algorithm by Eppstein and the 1.733nnO(1)-time exponential-space algorithm by Gebauer.

The Map Maker algorithm which converts survey data into geometric data with 2-dimensional Cartesian coordinates has been previously published. Analysis of the performance of this algorithm is continuing. The algorithm is suitable for generating 2D maps and it would be helpful to have this algorithm generalized to generate 3D and higher dimensional coordinates. The trigonometric approach of the Map Maker algorithm does not extend well into higher dimensions however this paper reports on an algebraic approach which solves the problem. A similar algorithm called the Coordinatizator algorithm has been published which converts survey data defining a higher dimensional space of measured sites into the lowest dimensionalcoordinatization accurately fitting the data. Therefore the Coordinatizator algorithm is not a projection transformation whereas the n-dimensional Map Maker algorithm is.

A new Evolutionary algorithm was presented based on intermediate value theorem of continuous function. The global search ability and the local search ability of this algorithm are well balanced, and operators used in the algorithm are simple, Further, small size of population scale is used. Initial numerical experiments show that the mean evolutionary algorithm is better than differential evolution algorithm in solving high dimension function optimization.

The maximum flow problem is a type of network optimization problem in the flow graph theory. Many important applications used the maximum flow problem and thus it has been studied by many researchers using different methods. Ford Fulkerson algorithm is the most popular algorithm that used to solve the maximum flow problem, but its complexity is high. In this paper, a parallel Genetic algorithm is applied to find a maximum flow in a weighted directed graph, by finding the objective function value for each augmenting path from the source to the sink simultaneously in the parallel steps in every iteration. The algorithm is implemented using Message Passing Interface (MPI) library, and results are conducted from a real distributed system IMAN1 supercomputer and were compared with a sequential version of Genetic-Maxflow. The simulation results show this parallel algorithm speedup the running time by achieving up to 50% parallel efficiency.

This paper presents a comparison between the performance of Chemical Reaction Optimization algorithm and Genetic algorithm in solving maximum flow problem with the performance of Ford-Fulkerson algorithm in that. The algorithms have been implemented sequentially using JAVA programming language, and executed to find maximum flow problem using different network size. Ford-Fulkerson algorithm which is based on the idea of finding augmenting path is the most popular algorithm used to find maximum flow value but its time complexity is high. The main aim of this study is to determine which algorithm will give results closer to the Ford-Fulkerson results in less time and with the same degree of accuracy. The results showed that both algorithms can solve Max Flow problem with accuracy results close to Ford Fulkerson results, with a better performance achieved when using the genetic algorithm in term of time and accuracy.

The optimization of the Electromagnetism-like Mechanism (EM) algorithm is analyzed, and a Hybrid Chaos Search (CS) Electromagnetism-like Mechanism Algorithm (CEM) is proposed in this paper. The new algorithm combines the advantages of both the CS method and the EM algorithm. To make the initial population more uniform, the CEM algorithm constructs it with the theory of good point set in number theory. The CS method, rather than the random linear search algorithm, is used in the new algorithm, which can effectively prevent the search process from terminating prematurely. Besides, an adaptive movement is used in the improved algorithm to speed up convergence, and a genetic coefficient is added to the update formula to update the locations of particles so that the particles are more likely to move into the other feasible regions. Experimental results show that the improved algorithm can converge to global optimums more effectively and accurately.

This paper presents a simple and efficient near optimal algorithm, named Maximum Adjacent Minimum degree Algorithm (MAMA) for optimization of minimum vertex cover problem. The proposed algorithm at each step add that maximum degree vertex which is adjacent to minimum degree vertex. The computational complexity and optimality comparison are carried with other state of the art algorithms on small benchmark instances as well as on large benchmark instances to check the efficiency of the proposed algorithm. The proposed algorithm outperforms the other well-known algorithm and returns near optimal result in quick time.

To solve the static traffic grooming problems for differentiated traffic model a MO — DSG algorithm is proposed. The algorithm defines the business value to describe the requirements for QoS performance. Let traffic grooming method be equivalent to gene, and grooming scheme to chromosome, hence the original problem of traffic grooming is transformed into a typical mathematical model which can be solved by multi target optimization algorithm. To prove the superiority of the algorithm, we compared the proposed algorithm with the NSGA-II algorithm by using the classical test functions. In addition, simulation based on the actual scene of MO-DSG algorithm proves its superior performance to TBSG-c algorithm, IONT algorithm, on construction cost and risk.

A decentralized random algorithm for flow distribution in complex networks is proposed. The aim is to maintain the maximum flow while satisfying the flow limits of the nodes and links in the network. The algorithm is also used for flow redistribution after a failure in (or attack on) a complex network to avoid a cascaded failure while maintaining the maximum flow in the network. The proposed algorithm is based only on the information about the closest neighbours of each node. A mathematically rigorous proof of convergence with probability 1 of the proposed algorithm is provided.

In this paper, we are concerned with maximum flow problems with non-zero lower bounds. The common approach to this problem is transforming the network into a bigger one with zero lower bounds, whose optimal solution yields a feasible solution to the original problem and then using one of the established methods for maximum flow problems with little to no modifications. Expanding upon the labelling techniques of Goldfarb and Hao we show that a variant of the monotonic build-up simplex algorithm runs in strongly polynomial time on the original network. The main characteristic of the MBU algorithm is that starting from an arbitrary basis solution it decreases the number of infeasible variables monotonically, without letting any feasible variables turn infeasible in the process. We show that this algorithm terminates after at most pivots which makes it the first strongly polynomial pivot algorithm that solves the problem without transforming the network.

This paper presents a heuristic algorithm for the earliest arrival flow problem. Existing exact algorithms, even polynomial in the output size, contain submodular function optimization as a frequently called subroutine, and thus are not practical in real-life applications. In this paper we propose an algorithm that does not involve the submodular function optimization. Although solving an EAF near-optimal, the algorithm is remarkably simple and efficient as it only involves shortest path computations on a static network. A numerical example illustrates how the algorithm works. As an application, we demonstrate the algorithm’s solution quality and computational performance by solving a real-size network.

The ill-condition of the load-flow is caused by a variety of reasons. Among them, heavy load and a long line of radiation type slip(large r/x) are the two important reasons. In connection with the ill-conditon above, Newton-homotopy algorithm is introduced in this paper. The algorithm mixes the locally quadratic convergence of Newton-raphison with wide range convergence of homopoty algorithm, so it improves the ill-condition of Jacobian matrix in the process of load-flow calculating, and speeds the convergence. Finally, several examples show the efficiency of the algorithm.

The capacity scaling algorithm for the maximum flow problem runs in O(nmlogU) time where n is the number of nodes, m is the number of arcs, and U is the largest arc capacity in the network. The two-phase capacity scaling algorithm reduces this bound to O(nmlog(U/n)). This running time is achieved with the restriction that flows are pushed on individual arcs while paths are being identified, but this causes slower empirical run times compared to the single-phase capacity scaling algorithm. In this research, we prove that the two-phase algorithm runs in the same theoretical time without the mentioned restriction. We also show that in practice, it runs significantly faster than the single-phase capacity scaling algorithm.

The constrained maximum flow problem is a variant of the classical maximum flow problem in which the flow from a source node to a sink node is maximized in a directed capacitated network with arc costs subject to the constraint that the total cost of flow should be within a budget. It is important to study this problem because it has important applications, such as in logistics, telecommunications and computer networks; and because it is related to variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications as well. In this research, we present an O(n^2mlog(nC)) time cost scaling algorithm and compare its empirical performance against the two existing polynomial combinatorial algorithms for the problem: the capacity scaling and the double scaling algorithms. We show that the cost scaling algorithm is on average 25 times faster than the double scaling algorithm, and 32 times faster than the capacity scaling algorithm.

The routing problems pertain to the search for a shortest route (minimum cost or minimum distance or maximum flow, etc.) connecting two specified stations or nodes described as ‘source’ and ‘sink’. The paper aims at obtaining an optimal route of a more realistic situation as to scheduling maximum flows at a minimum cost from a source to a destination. The distance (cost) and arc capacity between any two stations are given. The objective is to find the maximum flow with the minimum cost from the source to the destination in a network. The problem has many applications in the field of network flow theories. Several special cases of the problem were intensively studied in the literature and proposed various techniques to solve. Here we solved the present problem by the lexicographic search technique, which gives the exact solution to the problem. The solution procedure is illustrated with a suitable example. The algorithm is also tested in C-language and the computational details are also reported.

Based on rough graph theory, this paper gives a new algorithm in rough network, which generalizes the classical algorithm of exploring maximum flow. This algorithm successfully deals with a kind of complex relationship mining problem between different relationship levels. Simulation shows the effectiveness of this algorithm.

The Vortex Search (VS) algorithm is one of the recently proposed metaheuristic algorithms which was inspired from the vortical flow of the stirred fluids. Although the VS algorithm is shown to be a good candidate for the solution of certain optimization problems, it also has some drawbacks. In the VS algorithm, candidate solutions are generated around the current best solution by using a Gaussian distribution at each iteration pass. This provides simplicity to the algorithm but it also leads to some problems along. Especially, for the functions those have a number of local minimum points, to select a single point to generate candidate solutions leads the algorithm to being trapped into a local minimum point. Due to the adaptive step-size adjustment scheme used in the VS algorithm, the locality of the created candidate solutions is increased at each iteration pass. Therefore, if the algorithm cannot escape a local point as quickly as possible, it becomes much more difficult for the algorithm to escape from that point in the latter iterations. In this study, a modified Vortex Search algorithm (MVS) is proposed to overcome above mentioned drawback of the existing VS algorithm. In the MVS algorithm, the candidate solutions are generated around a number of points at each iteration pass. Computational results showed that with the help of this modification the global search ability of the existing VS algorithm is improved and the MVS algorithm outperformed the existing VS algorithm, PSO2011 and ABC algorithms for the benchmark numerical function set.

This study presents an algorithm for MaxFlow problem using "Chemical Reaction Optimization algorithm (CRO)". CRO is a recently established meta-heuristics algorithm for optimization, inspired by the nature of chemical reactions. The main concern is to find the best maximum flow value at which the flow can be shipped from the source node to the sink node in a flow network without violating any capacity constraints in which the flow of each edge remains within the upper bound value of the capacity. The proposed MaxFlow-CRO algorithm is presented, analyzed asymptotically and experimental test is conducted. Asymptotic runtime is derived theoretically. The algorithm is implemented using JAVA programming language. Results show a good performance with a complexity of O(I E2), for I iterations and E edges. The number of iterations I in the algorithm, is an important factor that will affect the results obtained. As number of iterations is increased, best possible max-Flow value is obtained.

The flow decomposition algorithm transforms an arc flow-based solution to a network flow problem into flows on directed paths and cycles. When the undirected graph induced by arcs with positive flow is a tree, a circle, or an augmented tree (with n nodes), the standard implementation of the algorithm runs in O (n2) time. In this article, we exploit the structure of the network to develop an O (n) flow decomposition algorithm. The run-time relies on the property that for these networks, paths or cycles can be represented implicitly in O (1) space. The algorithm is easy to implement and does not use complicated data structures. Because the size of the input is O (n), our algorithm is the fastest possible for flow decomposition on these special networks. Our algorithm can be used to improve run-times for solving matching and transportation problems on trees and circles. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.

an algorithm which reduces the arbitrary instance of the network flow problem to a simple path disjoint network in polynomial time. Then the flow in each path is taken as the minimum of the arc capacities of that path from where the flow in each arc can be easily determined. The polynomial time algorithm can determine any instance of the network flow problem faster than the previously existing algorithms . An example has been given to elucidate the process. At the end a MATLAB program based on this algorithm has been given.

The problem of finding maximum flow in network graph is extremely interesting and practically applicable in many fields in our daily life, especially in transportation. Therefore, a lot of researchers have been studying this problem in various methods. Especially in 2013, we has developed a new algorithm namely, postflow-pull algorithm to find the maximum flow on traditional networks. In this paper, we revised postflow-push methods to solve this problem of finding maximum flow on extended mixed network. In addition, to take more advantage of multi-core architecture of the parallel computing system, we build this parallel algorithm. This is a completely new method not being announced in the world. The results of this paper are basically systematized and proven. The idea of this algorithm is using multi processors to work in parallel by postflow_push algorithm. Among these processors, there is one main processor managing data, sending data to the sub processors, receiving data from the sub-processors. The sub-processors simultaneously execute their work and send their data to the main processor until the job is finished, the main processor will show the results of the problem.

Computing flow in a directed graph is a fundamental problem to which other programs can be reduced. The objective associated with the flow networks problem is to maximize the flow through the network. So it is usually studied within the field of Optimization. A parallel approach for obtaining maximum flow in a network is presented here. The concept of layered network is used here. The algorithm proceeds in two passes, forward and backward passes. Each node in a layer are processed in parallel. The time complexity of the algorithm is analyzed to be O(n2logkn).

The ML-EM (maximum likelihood expectation maximization) algorithm is the most popular image reconstruction method when the measurement noise is Poisson distributed. This short paper considers the problem that for a given noisy projection data set, whether the ML-EM algorithm is able to provide an approximate solution that is close to the true solution. It is well-known that the ML-EM algorithm at early iterations converges towards the true solution and then in later iterations diverges away from the true solution. Therefore a potential good approximate solution can only be obtained by early termination. This short paper argues that the ML-EM algorithm is not optimal in providing such an approximate solution. In order to show that the ML-EM algorithm is not optimal, it is only necessary to provide a different algorithm that performs better. An alternative algorithm is suggested in this paper and this alternative algorithm is able to outperform the ML-EM algorithm.

A new hybrid genetic algorithm was developed which combines a stochastic evolutionary algorithm with a deterministic adaptive step steepest descent hill climbing algorithm in order to optimize complex multivariate problems. By combining both algorithms computational resources are conserved and the solution converges rapidly as compared to either algorithm alone. In genetic algorithms natural selection is mimicked by random events such as breeding and mutation. In the adaptive step steepest descent algorithm the solution moves toward the lowest surrounding point. Step sizes start big and get progressively smaller, increasing computational efficiency. The genetic algorithm ensures the solution samples the entire global search space, thus a global minimum is found. The steepest descent method fine tunes the solution by moving it to the nearest local minimum. The code was developed, including a graphical user interface, in MATLAB. Additional features such as bounding the input, weighting the objective functions individually, and constraining the output are also built into the interface. The algorithm developed was used to optimize the response surface models which use process variables (feedstock moisture content, die speed, and preheating temperature) to predict pellet properties (pellet moisture content, unit, bulk and tapped density, durability, and specific energy consumption). The solution found by the hybrid algorithm was validated experimentally. Execution times were decreased by approximately 40%, based on 1,0000 trials with each method, using the new hybrid algorithm as compared to using a genetic algorithm alone with the same parameters, both developed at INL. Performance of the hybrid algorithm versus the commercial Matlab genetic algorithm is investigated. Results show that the hybrid genetic algorithm converged to the global maximum for bulk density in one iteration, whereas the commercial genetic algorithm took twenty nine iterations to converge.

The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O ( mn log ( nU )), where U is the value of maximum upper bound. Our algorithm improves the O ( m 2 log ( nU ))-time algorithm in [12] . Hence the current algorithm improves the running time in [12] by a factor of n . Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O ( mn log n ) time, see [5] . Under similarity assumption [11] , our algorithm runs in O ( mn log n ) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network.

The well-known sequential minimal optimization (SMO) algorithm is the most commonly used algorithm for numerical solutions of the support vector learning problems. At each iteration in the traditional SMO algorithm, also called 2PSMO algorithm in this paper, it jointly optimizes only two chosen parameters. The two parameters are selected either heuristically or randomly, whilst the optimization with respect to the two chosen parameters is performed analytically. The 2PSMO algorithm is naturally generalized to the three-parameter sequential minimal optimization (3PSMO) algorithm in this paper. At each iteration of this new algorithm, it jointly optimizes three chosen parameters. As in 2PSMO algorithm, the three parameters are selected either heuristically or randomly, whilst the optimization with respect to the three chosen parameters is performed analytically. Consequently, the main difference between these two algorithms is that the optimization is performed at each iteration of the 2PSMO algorithm on a line segment, whilst that of the 3PSMO algorithm on a two-dimensional region consisting of infinitely many line segments. This implies that the maximum can be attained more efficiently by 3PSMO algorithm. Main updating formulae of both algorithms for each support vector learning problem are presented. To assess the efficiency of the 3PSMO algorithm compared with the 2PSMO algorithm, 14 benchmark datasets, 7 for classification and 7 for regression, will be tested and numerical performances are compared. Simulation results demonstrate that the 3PSMO outperforms the 2PSMO algorithm significantly in both executing time and computation complexity.

Maximum-flow problems occur in a wide range of applications. Although already well-studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting-path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (Math. Programming (47), 1990) for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and in computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods.

In this paper, we present a novel asynchronous multithreaded algorithm for the maximum network flow problem. The algorithm is based on the classical push-relabel algorithm, which is essentially sequential and requires intensive and costly lock usages to parallelize it. The novelty of the algorithm is in the removal of lock and barrier usages, thereby enabling a much more efficient multithreaded implementation. The newly designed push and relabel operations are executed completely asynchronously and each individual process/thread independently decides when to terminate itself. We further propose an asynchronous global relabeling heuristic to speed up the algorithm. We prove that our algorithm finds a maximum flow with O(|V|2||-E|) operations, where |V| is the number of vertices and |E| is the number of edges in the graph. We also prove the correctness of the relabeling heuristic. Extensive experiments show that our algorithm exhibits better scalability and faster execution speed than the lock-based parallel push-relabel algorithm.

The minimum cut problem is to minimize c(S,T), that is, to determine source S and sink T such that the capacity of the S-T cut is minimal. The flow-based algorithm is mostly used to find the bottleneck arcs by calculating flow network, and does not presents the minimum cut. This paper suggests an algorithm that simply includes the maximum capacity vertex to adjacent set S or T and finds the minimum cut without obtaining flow network in advance. On applying the suggested algorithm to 13 limited graphs, it can be finds the minimum cut value (S, T) with simply and correctly.

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.

K-Means algorithm is one of the mostly used foundation algorithm in data mining, it base on a greedy clustering algorithm. This paper will introduce this algorithm and analysis. Then prove the correctness of the algorithm. And then show the productivity of this algorithm. And at last, this paper will show some improvement to K-Means algorithm, including how to choose initial center points, and how to calculate the means. This will improve the algorithm at a certain extent.

Preemptive open-shop scheduling problem was studied, and a network flow based algorithm was presented. Firstly, based on the characteristics of the preemptive open-shop, the scheduling problem was formulated as a mixed-integer programming model with the objective to minimize the make-span. The maximum flow model of the preemptive open-shop was developed to model the machine resource allocation and time constraints. Moreover a new preflow push algorithm for the maximum flow model was put forward. Based on the solution of machine resource allocation problem got by preflow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set. Finally, the validity of the developed scheduling algorithm is illustrated by randomly generated example.

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.

This research presents efficient methods for computing the maximum sum in a subarray problem. Firstly, one of the presented methods uses an efficient algorithm that determines the boundaries of a convex shape to calculate the optimal gain. The time complexity of this algorithm is the same as that for other existing algorithms, such as Kadane’s algorithm. Furthermore, even though this algorithm involves complicated operations, the involved processes return the shape of the optimised solution. Secondly, a generalization of the derived efficient algorithm is presented in this paper. This algorithm finds the first maximum sum, second maximum sum and up to the k th maximum sum. Finding the kth maximum convex sum can be utilized in many applications, such as accurately and efficiently locating the spreading of cancer.

The Minimum Capacity s-t Cut Problem (MinCut) is an intensively studied problem in combinatorial optimization. A natural extension is the problem of choosing a minimum capacity s-t cut when arc capacities are unknown but confined to known intervals. This motivates the Robust Minimum Capacity s-t Cut Problem (RobuCut), which has applications such as open-pit mining and project scheduling. In this paper, we show how RobuCut can be reduced to solving a sequence of maximum flow problems and provide an efficient algorithm for rapidly solving this sequence of problems. We demonstrate that our algorithm solves instances of RobuCut in seconds that would require hours if a standard maximum flow solver is iteratively used as a black-box subroutine.

This paper presents a new grid-associated algorithm to improve the performance of a D8 algorithm based distributed hydrological model computation. The algorithm is based on the well known single-flow D8 algorithm of grid flow. This algorithm allocates calculation priorities according to the distance between the units and the outlet, then carries out the ergodic computations of the hydrological units according to the priority division. For the parallelized algorithm, a standard thread-level shared memory system for parallel programming (OpenMP-Open specifications for Multi Processing) was introduced, and the parallel coding was implemented in C language. A case study showed that the absolute speed-up ratio of the grid-associated algorithm is 1.64 over the original D8 algorithm, and the linear speed-up ratio of the parallel associated algorithm is 2.42 under 4 cores. The parallel grid-associated algorithm can be applied to a variety of research fields that use the grid method.