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.展开更多
In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by prop...In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by proposing a novel problem formulation for a two stage transshipment problem. Later, special structure of our problem formulation is utilized to devise two dual based heuristics solutions with computational complexity of O (n2), and O (n3) respectively. These methods are motivated by the methods developed by Sharma and Saxena [1], Sinha and Sharma [2]. Our methods differ in the initialization and the subsequent variation of the dual variables associated with the transshipment nodes along the shortest path. Lastly, a method is proposed to extract a very good primal solution from the given dual solutions with a computational complexity of O (n2). Efficacy of these methods is demonstrated by our numerical analysis on 200 random problems.展开更多
In this article, we propose novel reformulations for capacitated lot sizing problem. These reformulations are the result of reducing the number of variables (by eliminating the backorder variable) or increasing the nu...In this article, we propose novel reformulations for capacitated lot sizing problem. These reformulations are the result of reducing the number of variables (by eliminating the backorder variable) or increasing the number of constraints (time capacity constraints) in the standard problem formulation. These reformulations are expected to reduce the computational time complexity of the problem. Their computational efficiency is evaluated later in this article through numerical analysis on randomly generated problems.展开更多
文摘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.
文摘In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by proposing a novel problem formulation for a two stage transshipment problem. Later, special structure of our problem formulation is utilized to devise two dual based heuristics solutions with computational complexity of O (n2), and O (n3) respectively. These methods are motivated by the methods developed by Sharma and Saxena [1], Sinha and Sharma [2]. Our methods differ in the initialization and the subsequent variation of the dual variables associated with the transshipment nodes along the shortest path. Lastly, a method is proposed to extract a very good primal solution from the given dual solutions with a computational complexity of O (n2). Efficacy of these methods is demonstrated by our numerical analysis on 200 random problems.
文摘In this article, we propose novel reformulations for capacitated lot sizing problem. These reformulations are the result of reducing the number of variables (by eliminating the backorder variable) or increasing the number of constraints (time capacity constraints) in the standard problem formulation. These reformulations are expected to reduce the computational time complexity of the problem. Their computational efficiency is evaluated later in this article through numerical analysis on randomly generated problems.
