•Optimization of farm drainage channel network (FDCN) has been investigated.•The modified minimal spanning tree, the shortest path and the out-of-kilter models have been considered.•The modified ...minimal spanning tree model has been improved to a better algorithm.•The new model has been applied to optimize a part of the Sansad irrigation network project.•The new model, gives the shortest channel network length compared with the other three models.
Collection, conveyance and discharge of farm drainage water using open channel network is an important task in an agricultural area. Design of an open channel network is based on the total length and conveying capacity of the channel, topography of the area and specific local conditions. Therefore, designing proper channel paths is an effective factor in the optimum network design. In this study, three optimization models have been considered: the modified minimal spanning tree, the shortest path and the out-of-kilter algorithms. The modified minimal spanning tree model for optimization of a farm drainage channel network (FDCN) has been improved to a better algorithm. The algorithm has been applied to optimize a part of the Sansad irrigation network project. Then, the FDCN system of the Jiroft and Roodbar plain was mathematically modeled considering regional constraints and optimized using the presented models. Results showed that the improved modified minimal spanning tree model, gives the shortest channel network length compared to the other three models.
The out-of-kilter method was first proposed by Fulkerson (1961) for linear-cost network flow and independently by Minty (1961) for piecewise-linear-cost network flow and was then extended by ...Rockafellar (1984, Section 11K) to piecewise-linear-cost monotropic programming. We propose an extension of this method, based on Rockafellar's work and on ideas from -relaxation methods for convex-cost network flow (Bertsekas et al. 1997a, De Leone et al. 1999) to monotropic programming in general. The proposed method is amenable to a complexity analysis and its convergence is based on (essentially) a monotone decrease in vertical distance to the characteristic curve for each index.
As size of the traveling salesman problem (TSP) increases, it is unreasonable to find efficiently an optimum or near-optimum. Instead of considering all arcs, if we select and consider only some arcs ...more likely to be included in an optimal solution, we can find efficiently an optimum or near-optimum. A candidate arc set is a group of some good arcs. For the lack of study in the asymmetric TSP, it needs to research systematically for the candidate arc set of the asymmetric TSP. In this paper, we suggest a regression function determining a candidate arc set for the asymmetric TSP. We established the regression function based on 2100 experiments, and we proved the goodness of fit for it through various 787 problems. Also, we applied it to the Out-of-Kilter heuristic. We tested it on 220 random instances and 23 real-world instances. Because the complexity of the heuristic depends on the number of arcs and we considered only the candidate arc set, we found good solutions about 2–5 fold faster than considering all arcs.
Some hypermedia synchronization issues request the resolution of the minimum convex piecewise linear cost tension problem (CPLCT problem) on directed graphs that are close to two-terminal ...series-parallel graphs (TTSP-graphs), the so-called quasi-k series-parallel graphs (k-QSP graphs). An aggregation algorithm has already been introduced for the CPLCT problem on TTSP-graphs. We propose here a reconstruction method, based on the aggregation and the well-known out-of-kilter techniques, to solve the problem on k-QSP graphs. One of the main steps being to decompose a graph into TTSP-subgraphs, methods based on the recognition of TTSP-graphs are thoroughly discussed.
The out-of-kilter method was first proposed by Fulkerson (1961) for linear-cost network flow and independently by Minty (1961) for piecewise-linear-cost network flow and was then extended by ...Rockafellar (1984, Section 11K) to piecewise-linear-cost monotropic programming. We propose an extension of this method, based on Rockafellar's work and on ideas from ε-relaxation methods for convex-cost network flow (Bertsekas et al. 1997a, De Leone et al. 1999) to monotropic programming in general. The proposed method is amenable to a complexity analysis and its convergence is based on (essentially) a monotone decrease in vertical distance to the characteristic curve for each index.
Farm drainage channel network optimization by improved modified minimal spanning tree Ashrafi, M; M.J. KhanjaniauthorDepartment of Civil Engineering, Faculty of Engineering,Shahid Bahonar University of Kerman, Kerman, PO Box 76169-133, Iran; E. Fadaei-KermaniauthorDepartment of Civil Engineering, Faculty of Engineering,Shahid Bahonar University of Kerman, Kerman, PO Box 76169-133, Iran ...
2015
Journal Article
The Minimum Cost Tension problem (MCT) is a network combinatorial optimization problem which has been relatively ignored by the literature. This problem appears however in many applications ...concerning networks such as timing of events, location of facilities, shared cost problems, and so on.
The most known algorithm for solving the minimum cost tension problem is the classical ‘out-of-kilter’ method which was developed by J.M. Pla in 1971. In this paper, we prove that this algorithm is non-polynomial by giving a graph family
T
n
,
n ⩾2, on which it runs necessarily in an exponential number of iterations, namely 2
n
+ 2
n−1
+ 2
n−2
− 2 calls to a linear labeling process. The demonstration is based on the fact that the execution on
T
n
can be seen as divided into two main stages: the first one repeats the same execution as that on
T
n−1
, and the second stage undo one by one the iterations of the first stage. By analogy with Greek mythology, we called this family of instances
Penelope's graphs.
In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network ...model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.
Natural gas flows in the USSR are modeled using the out-of-kilter algorithm after the transmission system is abstracted into a network of demand and supply nodes and bounded arcs. Evaluation of the ...resulting flow pattern is done for 1970, 1975, 1980, and 1985. Shifts in gas supplies from the European area to Central Asia and now to West Siberia have necessitated changes in the Soviet natural gas pipeline system. The system is entering a period of long run stability between the geographic distribution of supply and demand in contrast to a continually changing distribution pattern before 1980.
PDF
