Tight big-Ms for Optimal Transmission Switching Pineda, Salvador; Morales, Juan Miguel; Porras, Álvaro ...
Electric power systems research,
September 2024, 2024-09-00, Volume:
234
Journal Article
Peer reviewed
Open access
This paper addresses the Optimal Transmission Switching (OTS) problem in electricity networks, which aims to find an optimal power grid topology that minimizes system operation costs while satisfying ...physical and operational constraints. Existing methods typically convert the OTS problem into a Mixed-Integer Linear Program (MILP) using big-M constants. However, the computational performance of these approaches relies significantly on the tightness of these big-Ms. In this paper, we propose an iterative tightening strategy to strengthen the big-Ms by efficiently solving a series of bounding problems that account for the economics of the OTS objective function through an upper-bound on the generating cost. We also discuss how the performance of the proposed tightening strategy is enhanced if reduced line capacities are considered. Using the 118-bus test system we demonstrate that the proposed methodology outperforms existing approaches, offering tighter bounds and significantly reducing the computational burden of the OTS problem.
•Optimal Transmission Switching (OTS) finds the grid topology that minimizes cost.•OTS is formulated as a mixed-integer model and therefore belongs to the NP-hard class.•We propose an iterative tightening strategy to strengthen the big-Ms in the OTS model.•The proposed methodology outperforms existing approaches computationally.•Simulation results of a 118-bus network involve speedups of 8×–22×.
Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply, and in the building energy sector. In real-world applications, these systems are ...commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains two main approaches to approximate this computationally intensive multi-period investment problem. The first approach simplifies the temporal decision-making process collapsing the multi-stage decision to a two-stage decision, considering uncertainty in the second stage decision variables. The second approach considers multi-period investments under the assumption of perfect foresight. In this work, we propose a multi-stage stochastic optimization model that captures multi-period investment decisions under uncertainty and solves the problem to global optimality, serving as a first-best benchmark to the problem. To evaluate the performance of conventional approaches applied in a multi-year setup, we propose a rolling horizon heuristic that on the one hand reveals the performance of conventional approaches applied in a multi-period set-up and on the other hand enables planners to identify approximate solutions to the original multi-stage stochastic problem. We conduct a real-world case study and investigate solution quality as well as the computational performance of the proposed approaches. Our findings indicate that the approximation of multi-period investments by two-stage stochastic approaches yield the best results regarding constraint satisfaction, while deterministic multi-period approximations yield better economic and computational performance.
•Multi-stage stochastic programming applied to identify first best solution.•Rolling-horizon approach to evaluate conventional approaches in a multi-period setup.•Rolling horizon approach obtains solutions at much lower computational cost.•Consideration of future investments significantly increases economic performance.•Consideration of uncertain parameter distribution increases constraint satisfaction.
The prioritization of restoration actions after large power system outages plays a key role in how quickly power can be restored. It has been shown that fast and intuitive heuristics for restoration ...prioritization most often result in low-quality restoration plans. Meanwhile, mathematical optimization tools that find high-quality restoration plans are too slow to be applied to restoration planning problems of practical interest. This work makes a significant step in closing this quality vs compute time gap by proposing the Recursive Restoration Refinement heuristic for power system restoration. This heuristic is shown to produce near-optimal restoration plans up to 1000 times faster than other state-of-the-art solution methods on a range of test cases with up to 500 buses and 700 damaged components. The potential impact of this new heuristic is demonstrated by a preliminary analysis of the key features of high-quality restoration plans. The recursive restoration refinement algorithm and other methods explored in this work have been made available as part of the open-source software package, PowerModelsRestoration, to support ongoing research in power restoration algorithms.
•The paper considers how to quickly restore electric power to customers after an event that caused wide-spread damage to the grid.•A novel algorithm is developed to solve the restoration ordering problem (i.e., which components to restore first) faster.•The algorithm is benchmarked on cases up to 500 buses and 700 damaged components and accelerates solution times over state-of-the-art by 1000×.•The proposed algorithms as well as several other algorithms from the literature are provided in an open source package.
•A mixed-integer optimization considers material choice, thickness, and energy level.•Identify best material combinations and thicknesses for optics under five albedos.•Non-semi-transparent top ...subcells are preferred for high isc under high albedos.•Small perturbations in thicknesses do not significantly affect the optimum.isc•Predict a highest 50.9% bifacial equivalent PCE for devices under snow albedo.
We present a mixed-integer optimization for the optics of two-terminal perovskite-on-perovskite tandem solar cells, which accounts for thickness and material variations in all thin-film layers. The model, which is validated with experiments for both monofacial and bifacial devices, optimizes the short-circuit current density under six albedo conditions, identifying the best cell architectures and alternative material combinations that yield optimal and close-to-optimal results. In contrast to monofacial devices and low albedos, tandem devices with top subcells that are not semi-transparent are found to provide the highest short-circuit current densities under high albedos, such as albedos for white sand and snow. According to a sensitivity analysis, the short-circuit current densities in the optimized devices are not significantly affected by small perturbations in layer thicknesses. The device performances are also discussed in the context of the best optical structure. A power conversion efficiency of 34.6% and a bifacial equivalent efficiency of over 50% are predicted for the optimized monofacial device and bifacial device under high albedo values, respectively.
In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. ...This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we discover links between the convex hull of the set under study, and a family of polyhedral sets studied in the literature. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation.
A recently new intelligent optimization algorithm called discrete state transition algorithm is considered in this study, for solving unconstrained integer optimization problems. Firstly, some key ...elements for discrete state transition algorithm are summarized to guide its well development. Several intelligent operators are designed for local exploitation and global exploration. Then, a dynamic adjustment strategy “risk and restoration in probability” is proposed to capture global solutions with high probability. Finally, numerical experiments are carried out to test the performance of the proposed algorithm compared with other heuristics, and they show that the similar intelligent operators can be applied to ranging from traveling salesman problem, boolean integer programming, to discrete value selection problem, which indicates the adaptability and flexibility of the proposed intelligent elements.
•A systematic formulation of discrete state transition algorithm is firstly proposed, including the state space representation and five key elements.•A dynamic adjustment strategy called “risk and restoration in probability” is designed to improve the ability to escape from local optima.•The proposed algorithm is successfully integrated with several classical integer optimization problems.
Mixed integer Model Predictive Control (MPC) problems arise in the operation of systems where discrete and continuous decisions must be taken simultaneously to compensate for disturbances. The ...efficient solution of mixed integer MPC problems requires the computationally efficient online solution of mixed integer optimization problems, which are generally difficult to solve. In this paper, we propose a machine learning-based branch and check Generalized Benders Decomposition algorithm for the efficient solution of such problems. We use machine learning to approximate the effect of the complicating variables on the subproblem by approximating the Benders cuts without solving the subproblem, therefore, alleviating the need to solve the subproblem multiple times. The proposed approach is applied to a mixed integer economic MPC case study on the operation of chemical processes. We show that the proposed algorithm always finds feasible solutions to the optimization problem, given that the mixed integer MPC problem is feasible, and leads to a significant reduction in solution time (up to 97% or 50×) while incurring small error (in the order of 1%) compared to the application of standard and accelerated Generalized Benders Decomposition.
•A machine learning-aided branch and check algorithm is proposed for mixed integer MPC•Benders cuts are approximated via machine learning-based surrogate models•The returned solution is feasible, given that the optimization problem is feasible•Case studies highlight the computational efficiency of the proposed algorithm
In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized ...single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.
The aircraft scheduling problem consists in sequencing aircraft on airport runways and in scheduling their times of operations taking into consideration several operational constraints. It is known ...to be an NP-hard problem, an ongoing challenge for both researchers and air traffic controllers.
The aim of this paper is to present a focused review on the most relevant techniques in the recent literature (since 2010) on the aircraft runway scheduling problem, including exact approaches such as mixed-integer programming and dynamic programming, metaheuristics, and novel approaches based on reinforcement learning. Since the benchmark instances used in the literature are easily solved by high-performance computers and current versions of solvers, we propose a new data set with challenging realistic problems constructed from real-world air traffic.
•Focused review of the recent literature on the aircraft runway scheduling problem.•Includes exact methods, stochastic methods, and novel approaches based on reinforcement learning.•Benchmark instances are showed to be no longer challenging for current versions of solvers.•Introduction of realistic, challenging and publicly-available benchmark problems.
PDF
