In this article, we devise two dual based methods for obtaining very good solution to a single stage un-capacitated minimum cost flow problem. These methods are an improvement to the methods already developed by Sharm...In this article, we devise two dual based methods for obtaining very good solution to a single stage un-capacitated minimum cost flow problem. These methods are an improvement to the methods already developed by Sharma and Saxena [1]. We further develop a method to extract a very good primal solution from a given dual solution. We later demonstrate the efficacies and the significance of these methods on 150 random problems.展开更多
This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programmin...This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.展开更多
In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second meth...In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.展开更多
Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we c...Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.展开更多
This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building...This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.展开更多
In the electricity market, charging based on the traditional spot electricity price often results in the payment imbalance of electric network, and goes against the development of the power system. So, it is necessary...In the electricity market, charging based on the traditional spot electricity price often results in the payment imbalance of electric network, and goes against the development of the power system. So, it is necessary to modify the spot price. The key of the modification lies in how to calculate the fixed unit transmission cost of each node, that is how to allocate the fixed transmission cost to users.To solve this problem, we develop a power flow tracing algrithm to modify the spot price. We put forward a path searching method based on the graph theory after studying the fundamental principle of power flow tracing and apply the method to the downstream tracing algorithm and upstream tracing algorithm according to the proportional distribution principle. Furthermore, to improve the computational efficiency of the algorithm, we introduce the branch expunction method to optimize the node order. By using the result of power flow tracing to get fixed node transmission cost and introducing it to modify the spot price, we obtain the synthetical price.The application to a 5-bus system prove the algorithm feasible.展开更多
文摘In this article, we devise two dual based methods for obtaining very good solution to a single stage un-capacitated minimum cost flow problem. These methods are an improvement to the methods already developed by Sharma and Saxena [1]. We further develop a method to extract a very good primal solution from a given dual solution. We later demonstrate the efficacies and the significance of these methods on 150 random problems.
基金the National Natural Science Foundation of China ( 1 0 4 71 0 94) ,the ScienceFoundation of Shanghai Technical Sciences Committee ( 0 2 ZA1 40 70 ) and the Science Foundation ofShanghai Education Committee( 0 2 DK0 6)
文摘This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.
文摘In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.
文摘Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.
文摘This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.
文摘In the electricity market, charging based on the traditional spot electricity price often results in the payment imbalance of electric network, and goes against the development of the power system. So, it is necessary to modify the spot price. The key of the modification lies in how to calculate the fixed unit transmission cost of each node, that is how to allocate the fixed transmission cost to users.To solve this problem, we develop a power flow tracing algrithm to modify the spot price. We put forward a path searching method based on the graph theory after studying the fundamental principle of power flow tracing and apply the method to the downstream tracing algorithm and upstream tracing algorithm according to the proportional distribution principle. Furthermore, to improve the computational efficiency of the algorithm, we introduce the branch expunction method to optimize the node order. By using the result of power flow tracing to get fixed node transmission cost and introducing it to modify the spot price, we obtain the synthetical price.The application to a 5-bus system prove the algorithm feasible.
