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.

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)\).

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 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.

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 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 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.

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.

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.

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.

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.

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.

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.

The Frank-Wolfe algorithm has been extensively adopted in recent decades to solve the user-equilibrium problem because of its simple structure and low memory requirements. However, Dial observed that the results obtained by the Frank-Wolfe algorithm differed markedly from the B algorithm of Dial in terms of link flows, and the results obtained via Frank-Wolfe algorithm could be incorrect. This study attempts to provide a clear example showing that the Frank-Wolfe algorithm has difficulty in achieving an ϵ-user equilibrium state when ϵ is sufficiently small. An Augmented Frank-Wolfe algorithm is presented that overcomes the weaknesses of the conventional arc-based Frank-Wolfe algorithm.

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.

The maximum flow problem is one of the classic combinatorial optimization problems with many applications, such as electrical powers, traffics, communications, computer networks and logistics. The problem is to find a flow of maximum value on a network from a source to a sink. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching the nodes and edges implicitly. For the maximum flow problem in networks, we present the symbolic algebraic decision diagram (ADD) formulation and symbolic algorithms. The augmenting-path-based symbolic algorithm is the combination of the Gabow's scaling algorithm with the binary decision diagram (BDD)-based symbolic algorithm for the maximum flow in 0–1 networks. The Karzanov's algorithm is implemented implicitly, resulting in the preflow-based symbolic algorithm (PSA), in which the vertices on each layer of the layered networks are partitioned by the vertex's input preflow and the total capacity of its outgoing edges, and the edges to push or pull the preflow are selected in terms of the priority function. The improved PSA is developed by integrating the heuristic of Traff's algorithm and the assistant layered networks into the PSA. The symbolic algorithms do not require explicit enumeration of the nodes and edges, and therefore can handle large-scale networks.

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.

This paper presents an algorithm for finding a global minimum of a multimodal, multivariate and nondifferentiable function. The algorithm is a modification to the new version of the Price's algorithm given in Brachetti et al. [J. Global Optim. 10, 165---184 (1997)]. Its distinguishing features include: (1) The number-theoretic method is applied to generate the initial population so that the points in the initial population are uniformly scattered, and therefore the algorithm could explore uniformly the region of interest at the initial iteration; (2) The simplified quadratic approximation with the three best points is employed to improve the local search ability and the accuracy of the minimum function value, and to reduce greatly the computational overhead of the algorithm. Two sets of experiments are carried out to illustrate the efficiency of the number-theoretic method and the simplified quadratic model separately. The proposed algorithm has also been compared with the original one by solving a wide set of benchmark problems. Numerical results show that the proposed algorithm requires a smaller number of function evaluations and, in many cases, yields a smaller or more accurate minimum function value. The algorithm can also be used to deal with the medium size optimization problems.

Fujishige proposed a polynomial-time maximum flow algorithm using maximum adjacency (MA) orderings. Computational results by Fujishige and Isotani showed that the algorithm was slower in practice than Goldberg and Tarjan's algorithm. In this paper we propose an improved version of Fujishige's algorithm using preflows. Our computational results show that the improved version is much faster than the original one in practice.

The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations.

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.

This paper is concerned with an efficient global optimization algorithm for solving a kind of fractional program problem(P), whose objective and constraints functions are all defined as the sum of ratios generalized polynomial functions. The proposed algorithm is a combination of the branch-and-bound search and two reduction operations, based on an equivalent monotonic optimization problem of(P). The proposed reduction operations specially offer a possibility to cut away a large part of the currently investigated region in which the global optimal solution of(P)does not exist, which can be seen as an accelerating device for the solution algorithm of(P). Furthermore, numerical results show that the computational efficiency is improved by using these operations in the number of iterations and the overall execution time of the algorithm, compared with other methods. Additionally, the convergence of the algorithm is presented, and the computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem(P)provided that the number of variables is not too large.

Abstract Some special cases of the Maximum Flow Problem under nonnegative lower bounds on arc flows are investigated. Assuming that at least one of these bounds is strictly positive, a class of problems has been identified for which a single phase algorithm suffices to prove optimality. This situation contrasts with the two phases algorithm which is commonly used in the literature to solve these problems. In spite of having the same overall complexity of the two phases algorithm, the single phase one appears to be, computationally speaking, more attractive.

Goldberg and Rao recently proposed the blocking flow method based on a binary length function to obtain a better algorithm for the maximum flow problem. The previous algorithms based on the blocking flow method proposed by Dinic use the unit length function: every residual edge is of length 1. In this paper, we survey properties of the distance function defined by a length function and give an overview on the representative maximum flow algorithms proposed so far in a systematic way by utilizing these properties. Among them are included two new algorithms: the Goldberg-Rao algorithm which finds a maximum flow on an integral capacity network N of n vertices and m edges in ~(min{ml/~, n2/3}7n log(n2/m) log U) time, where U is the maximum edge capacity of N, and the Karger-Levine algorithm which finds a maximum flow on an undirected network N with unit capacity and no parallel edges in 0(m + nv3/2) time, where v is the value of a maximum flow of N.

In this paper, we present a new polynomial time algorithm for solving the minimum cost network flow problem. This algorithm is based on Edmonds-Karp's capacity scaling and Orlin's excess scaling algorithms. Unlike these algorithms, our algorithm works directly with the given data and original network, and dynamically adjusts the scaling factor between scaling phases, so that it performs at least one flow augmentation in each phase. Our algorithm has a complexity of O(m(m+nlogn)log(B/(m+n))), where n is the number of nodes, m is the number of arcs, and B is the sum of the finite arc capacities and supplies in the network.

The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set R ⊆ A of arcs and require that each arc in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all arc capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem—the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m + n logn) log (nU)) time, which is almost the same time needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem.

The Stoer‐Wagner algorithm computes a minimum cut in a weighted undirected graph. The algorithm works inn 1 phases, wheren is the number of nodes ofG. Each phase takes time O.mCn logn/ ,w herem is the number of edges ofG, and computes a pair of vertices s and t and a minimum cut separatings and t . We show how to extend the algorithm such that each phase also computes a maximum flow from s tot . The flow is computed in O.m/ additional time and certifies the cut computed in the phase. © 1999 Elsevier Science B.V. All rights reserved. We give a correctness certificate for the min-cut algorithm of Stoer and Wagner [6]. This algorithm refines the algorithm of Nagamochi and Ibaraki [5,4]; it has the same time complexity, but is simpler. The algorithm is deterministic. There are faster randomized algorithms [2,3]. No certificates are known for the randomized algorithms. Let G be an undirected graph with n vertices and m edges. The algorithm of Stoer and Wagner works inn 1 phases. In each phase it identifies two vertices and a minimum cut separating them and then collapses the two vertices into one. The global min-cut is the minimum cut found in any phase. Each phase runs in time O.mCn logn/. We extend the algorithm such that it also finds a flow equal to the min-cut in each phase. The additional time required to find the flow is O.m/ in each phase.

We present an alternate linear algorithm for finding the minimum flow in (s, t)-planar networks using a new concept of minimal removable sets developed here. The iterative nature of the algorithm facilitates the adjustment of solutions for systems in developmental stages. The minimum flow algorithm presented here requires O(|V|) time, where V denotes the set of vertices. The minimum flow problem arises in many transportation and communication systems.

Query optimization of database management systems is aimed at finding an optimal access path for a query to minimize the evaluation cost. This research addresses the problem of query optimization for databases in which objects frequently change their values. A greedy, adaptive query optimization algorithm is proposed to evaluate relational queries and queries containing complex objects. Rather than constructing a full plan for an access path and executing it, the algorithm constructs a partial plan, executes it, updates the statistics, and constructs a new partial plan. Since a partial plan is constructed based on the latest statistics, the algorithm is adaptive to data modifications and errors from the statistics. It is proved that the algorithm can produce an optimal solution for a class of queries. Furthermore, experiments show that the overhead associated with the algorithm is negligible and the algorithm is efficient for other cases. An adaptive query optimization algorithm for distributed environments is also proposed. The algorithm extends the SDD-1 algorithm to local area networks by considering local processing cost as well as communication cost. Whereas the SDD-1 algorithm only uses semi-joins to reduce communication cost, the algorithm reduces it with joins as well. It is proved that the adaptive algorithm is more efficient than the SDD-1 algorithm.

The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O ( n 1.5 ) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.

We propose a strongly polynomial algorithm for the minimum cost tension problem. Our algorithm is inspired by Goldberg and Tarjan's ideas which deal with the minimum cost circulation problem. It consists of repeatedly canceling minimum mean-cost residual cuts. Hence, we had to consider two other combinatorial optimization problems which possess interesting practical applications: the min-cost and min-mean-cost residual cut problems (Hadjiat and Maurras, 1995).