Computational Assessment of Nested Benders and Augmented Lagrangian Decomposition for Mean-Variance Multistage Stochastic Problems
20
Citation
33
Reference
10
Related Paper
Citation Trend
Abstract:
We consider decomposition approaches for the solution of multistage stochastic programs that appear in financial applications. In particular, we discuss the performance of two algorithms that we test on the mean-variance portfolio optimization problem. The first algorithm is based on a regularized version of Benders decomposition, and we discuss its extension to the quadratic case. The second algorithm is an augmented lagrangian method. Our results indicate that the algorithm based on regularized Benders decomposition is more efficient, which is in line with similar studies performed in the linear setting.Keywords:
Benders' decomposition
Augmented Lagrangian method
In this paper we describe a new Benders decomposition approach to solve power transmission network expansion planning problems. This new approach is characterized by using a linear (0-1) disjuntictive model that ensures the optimality of the solution found and by using additional constraints, iteratively evaluated, besides the traditional Benders cuts. The results obtained, considering a real world power transmission network expansion planning study with the southeastem Brazilian system, show the efficiency of this approach.
Benders' decomposition
Transmission network
Power network
Power transmission
Cite
Citations (407)
Benders' decomposition
Cite
Citations (8)
Many methods that have been proposed to solve large-scale MILP problems rely on the use of decomposition strategies. These methods exploit either the primal or dual structures of the problems by applying the Benders decomposition or Lagrangian dual decomposition strategy, respectively. In “The Benders Dual Decomposition Method,” Rahmaniani, Ahmed, Crainic, Gendreau, and Rei propose a new and high-performance approach that combines the complementary advantages of both strategies. The authors show that this method (i) generates stronger feasibility and optimality cuts compared with the classical Benders method, (ii) can converge to the optimal integer solution at the root node of the Benders master problem, and (iii) is capable of generating high-quality incumbent solutions at the early iterations of the algorithm. The developed algorithm obtains encouraging computational results when used to solve various benchmark MILP problems.
Benders' decomposition
Benchmark (surveying)
Cite
Citations (44)
Benders' decomposition
Cellular manufacturing
Cite
Citations (66)
Facility Location (FL) problems as one of the most important problems in operations research aim to determine the location of a set of facilities in a way that the total costs, including costs of opening facilities and transportation costs, are minimized. This study addresses an FL problem in which the capacity of each facility is limited. Because this problem is in the category of np-hard problems, we use the Benders Decomposition (BD) approach to efficiently solve the FL problem. In this paper, we implement the classic BD algorithm and some accelerating BD methods such as Pareto-optimality cut and L-shaped decomposition methods. Furthermore, we propose and implement the hybrid Pareto-L-shaped (PL) method, and evaluate the performance of the implemented algorithms. The results show that the L-shaped decomposition outperforms the other algorithms in terms of time and the number of iteration, while the classic BD converges slowly especially on large scales.
Benders' decomposition
Cite
Citations (0)
Abstract This paper proposes a methodology for solving a transmission expansion planning problem with N − 1 security constraints consideration. The problem is formulated using a disjunctive model solved by Benders decomposition. A local search procedure is applied to solve the master problem, i.e. investment problem. With this developed methodology, the computational time can be considerably reduced, especially for large system problems, and the global optimality of Bender decomposition can be preserved by solving the master problem in a complete search space for specified iteration numbers. The proposed methodology has been tested with the IEEE 24‐bus system and the southern Brazilian system with satisfactory results. © 2011 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.
Benders' decomposition
Cite
Citations (4)
In this paper, we aim to find the optimal planning strategy of fast-charging stations by minimizing the total planning cost with the consideration of uncertain charging demands. We construct a mixed integer nonlinear programming formulation for tackling the planning problem. We reformulate the original planning problem into tractable ones using the sample average approximation (SAA) method, and then, solve the reformulation using the Benders dual decomposition (BDD) method. Different from the standard Benders decomposition, BDD optimizes the optimal and feasible cuts generated in iterations, reducing the number of iterations and improving the solution efficiency. The simulation results are illustrated to validate the theoretical analysis. Computational results on a 25-node network show that compared to the Benders decomposition method, the BDD method has a higher performance for solving the planning problem of fast-charging stations.
Benders' decomposition
Cite
Citations (0)
In this report a new decomposition methodology for optimization problems is presented. The proposed procedure is general, simple and efficient. It avoids most disadvantages of other common decomposition techniques, such as Lagrangian Relaxation or Augmented Lagrangian Relaxation. The new methodology is applied to a problem coming from interconnected power systems. The application of the new method to this problem allows the computation of an optimal coordinated but decentralized solution. Local and global convergence properties of the proposed decomposition algorithm are described. Numerical results show that the new decentralized methodology has a lower computational cost than other decomposition techniques, and in large-scale cases even lower than a centralized approach.
Lagrangian relaxation
Augmented Lagrangian method
Cite
Citations (0)