Improved Unit Commitment with Accurate Dynamic Scenarios Clustering Based on Multi-Parametric Programming and Benders Decomposition

Stochastic unit commitment is one of the most powerful methods to address uncertainty. However, the existingscenario clustering technique for stochastic unit commitment cannot accurately select representative scenarios,which threatens the robustness of stochastic unit commitment and hinders its application. This paper providesa stochastic unit commitment with dynamic scenario clustering based on multi-parametric programming andBenders decomposition. The stochastic unit commitment is solved via the Benders decomposition, which decouplesthe primal problem into the master problem and two types of subproblems. In the master problem, the committedgenerator is determined, while the feasibility and optimality of generator output are checked in these twosubproblems. Scenarios are dynamically clustered during the subproblem solution process through the multiparametric programming with respect to the solution of the master problem. In other words, multiple scenariosare clustered into several representative scenarios after the subproblem is solved, and the Benders cut obtainedby the representative scenario is generated for the master problem. Different from the conventional stochasticunit commitment, the proposed approach integrates scenario clustering into the Benders decomposition solutionprocess. Such a clustering approach could accurately cluster representative scenarios that have impacts on theunit commitment. The proposed method is tested on a 6-bus system and the modified IEEE 118-bus system.Numerical results illustrate the effectiveness of the proposed method in clustering scenarios. Compared withthe conventional clustering method, the proposed method can accurately select representative scenarios whilemitigating computational burden, thus guaranteeing the robustness of unit commitment.

Application of Modified Benders Decomposition to Single-Stage Multi-Commodity Multi-Period Warehouse Location Problem: An Empirical Investigation

In the past, researchers have applied Bender’s decomposition to distribution problem and used feasibility constraint to speed up the performance of Bender’s decomposition. Further, the application of Branch and Bound to single-stage multi-commodity single-period warehouse location problem (SSMCSPWLP) with strong constraints has shown that they are more effective. It was also shown in the previous research (in the context of Branch and Bound Methodology) that hybrid formulation for the single-stage single-period multi-commodity warehouse location problem yielded superior results. In this paper we apply Benders’ decomposition to strong and weak formulations of single-stage multi-commodity multi-period warehouse location problem (SSMCMPWLP). As suggested in the previous literature we put feasibility constraints in the pure integer sub- problem to speed up the performance of Benders’ decomposition. We also develop an additional cut (constraint that is again added to pure integer sub-problem) and show that it further speeded up Benders’ Decomposition. This research led to the possibility of applying Benders’ Decomposition to the hybrid formulation of SSMCMPWLP in future.

Heuristic Benders Decomposition Efficiency Improvement for SCUC

The Benders Decomposition method is widely used to manage large-scale problems in power system optimization.In this paper,a simple but effective method is proposed to improve the Benders Decomposition efficiency using the security constrained unit commitment(SCUC)problem as an example.The heuristic weights are introduced for constraint violations to accelerate their elimination,and thereby improving the Benders Decomposition efficiency.The validity of the proposed method is verified through case studies on multiple IEEE test systems.

Developing a new model for simultaneous scheduling of two grand projects based on game theory and solving the model with Benders decomposition

Grand infrastructure projects,such as dam,power plant,petroleum,and gas industry projects,have several contractors working on them in several independent sub-projects.The concern of reducing the duration of these projects is one of the important issues among various aspects;thus,our aim is to fulfill the requirements by using the game theory approach.In this study,a mixed-integer programming model consisting of game theory and project scheduling is developed to reduce the duration of projects with a minimum increase in costs.In this model,two contractors in successive periods are entered into a step-by-step competition by the employer during dynamic games,considering an exchange in their limited resources.The optimum solution of the game in each stage are selected as the strategy,and the resources during the game are considered to be renewable and limited.The strategy of each contractor can be described as follows:1)share their resources with the other contractor and 2)not share the resources with the other contractor.This model can act dynamically in all circumstances during project implementation.If a player chooses a non-optimum strategy,then this strategy can immediately update itself at the succeeding time period.The proposed model is solved using the exact Benders decomposition method,which is coded in GAMS software.The results suggest the implementation of four step-by-step games between the contractors.Then,the results of our model are compared with those of the conventional models.The projects’duration in our model is reduced by 22.2%.The nominal revenue of both contractors has also reached a significant value of 46078 units compared with the relative value of zero units in the original model.Moreover,we observed in both projects the decreases of 19.5%,20.9%,and 19.7%in the total stagnation of resources of types 1,2,and 3,respectively.

Task scheduling for multi-electro-magnetic detection satellite with a combined algorithm

Task scheduling for electro-magnetic detection satellite is a typical combinatorial optimization problem. The count of constraints that need to be taken into account is of large scale. An algorithm combined integer programming with constraint programming is presented. This algorithm is deployed in this problem through two steps. The first step is to decompose the original problem into master and sub-problem using the logic-based Benders decomposition; then a circus combines master and sub-problem solving process together, and the connection between them is general Benders cut. This hybrid algorithm is tested by a set of derived experiments. The result is compared with corresponding outcomes generated by the strength Pareto evolutionary algorithm and the pure constraint programming solver GECODE, which is an open source software. These tests and comparisons yield promising effect.

Two-Stage Robust Optimization Under Decision Dependent Uncertainty

In the conventional robust optimization(RO)context,the uncertainty is regarded as residing in a predetermined and fixed uncertainty set.In many applications,however,uncertainties are affected by decisions,making the current RO framework inapplicable.This paper investigates a class of two-stage RO problems that involve decision-dependent uncertainties.We introduce a class of polyhedral uncertainty sets whose right-hand-side vector has a dependency on the here-and-now decisions and seek to derive the exact optimal wait-and-see decisions for the second-stage problem.A novel iterative algorithm based on the Benders dual decomposition is proposed where advanced optimality cuts and feasibility cuts are designed to incorporate the uncertainty-decision coupling.The computational tractability,robust feasibility and optimality,and convergence performance of the proposed algorithm are guaranteed with theoretical proof.Four motivating application examples that feature the decision-dependent uncertainties are provided.Finally,the proposed solution methodology is verified by conducting case studies on the pre-disaster highway investment problem.

Robust transmission expansion planning model considering multiple uncertainties and active load

Uncertainty must be well addressed in transmission expansion planning(TEP)problem,and it significantly affects the reliability and cost-effectiveness of power systems.Owing to the complex operating environment of power systems,it is crucial to consider different types of uncertainties during the planning stage.In this paper,a robust TEP model is proposed by considering multiple uncertainties and active load.Specifically,in this model,the uncertainties of wind power output and contingency probability are considered simultaneously.The uncertainties are described by scenario and interval,and the Benders decomposition technique is applied to solve the model.The feasibility and effectiveness of the proposed model are illustrated using the IEEE RTS and IEEE 118-node systems.

Two-stage stochastic approach for spinning reserve allocation in dynamic economic dispatch

A novel approach was proposed to allocate spinning reserve for dynamic economic dispatch.The proposed approach set up a two-stage stochastic programming model to allocate reserve.The model was solved using a decomposed algorithm based on Benders' decomposition.The model and the algorithm were applied to a simple 3-node system and an actual 445-node system for verification,respectively.Test results show that the model can save 84.5 US $ cost for the testing three-node system,and the algorithm can solve the model for 445-node system within 5 min.The test results also illustrate that the proposed approach is efficient and suitable for large system calculation.

Power Generation Expansion Planning Using an Interior Point with Cutting Plane （IP/CP） Method

The generation expansion planning is one of complex mixed-integer optimization problems, which involves a large number of continuous or discrete decision variables and constraints. In this paper, an interior point with cutting plane （IP/CP） method is proposed to solve the mixed-integer optimization problem of the electrical power generation expansion planning. The IP/CP method could improve the overall efficiency of the solution and reduce the computational time. Proposed method is combined with the Bender＇s decomposition technique in order to decompose the generation expansion problem into a master investment problem and a slave operational problem. The numerical example is presented to compare with the effectiveness of the proposed algorithm.

DG Hosting Capacity Assessment Considering Dependence Among Wind Speed,Solar Radiation,and Load Demands

Dependence of distributed generation(DG)outputs and load plays an essential role in renewable energy accommodation.This paper presents a novel DG hosting capacity(DGHC)evaluation method for distribution networks considering highdimensional dependence relations among solar radiation,wind speed,and various load types(i.e.,commercial,residential,and industrial).First,an advanced dependence modeling method called regular vine(R-vine)is applied to capture the complex dependence structure of solar radiation,wind speed,commercial loads,industrial loads,and residential loads.Then,a chanceconstrained DGHC evaluation model is employed to figure out maximum hosting capacity of each DG and its optimal allocation plan with different operational risks.Finally,a Benders decomposition algorithm is also employed to reduce computational burden.The proposed approaches are validated using a set of historical data from China.Results show dependence among different DGs and loads has significant impact on hosting capacity.Results also suggest using the R-vine model to capture dependence among distributed energy resources(DERs)and load.This finding provides useful advice for distribution networks in installing renewable energy generations.

Resource Allocation to Minimize the Makespan with Multi-Resource Operations

This paper investigates a new resource-allocation problem involving multi-resource operations,where completing an operation requires simultaneous use of multiple(renewable)resources,probably of different types.The goal of the study is to provide a solution method that minimizes the makespan.The authors formulate the problem into a novel mixed-integer linear program(MILP)model.To efficiently solve practical-sized instances,an exact Benders decomposition algorithm is developed.This algorithm divides the original problem into a master problem of allocating resources and a subproblem of calculating the makespan,and both are linked via Benders cuts.The convergence is sped up by improving the mathematical model and embedding the variable neighborhood search algorithm.Compared with CPLEX,a commonly used MILP solver,the computational results demonstrate that the proposed algorithm provides tighter upper and lower bounds in most instances.In particular,compared with CPLEX,the proposed method can on average improve the upper and lower bounds by 4.76%and 4.39%,respectively,in solving practical-sized instances.

Solving Multi-period Interdiction via Generalized Bender's Decomposition

This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.

Distributionally Robust Optimal Dispatch of Offshore Wind Farm Cluster Connected by VSC-MTDC Considering Wind Speed Correlation

Multi-terminal voltage source converter-based highvoltage direct current(VSC-MTDC)transmission technology has become an important mode for connecting adjacent offshore wind farms(OWFs)to power systems.Optimal dispatch of an OWF cluster connected by the VSC-MTDC can improve economic operation under the uncertainty of wind speeds.A two-stage distributionally robust optimal dispatch(DROD)model for the OWF cluster connected by VSC-MTDC is established.The first stage in this model optimizes the unit commitment of wind turbines to minimize mechanical loss cost of units under the worst joint probability distribution(JPD)of wind speeds,while the second stage searches for the worst JPD of wind speeds in the ambiguity set(AS)and optimizes active power output of wind turbines to minimize the penalty cost of the generation deviation and active power loss cost of the system.Based on the Kullback–Leibler(KL)divergence distance,a data-driven AS is constructed to describe the uncertainty of wind speed,considering the correlation between wind speeds of adjacent OWFs in the cluster by their joint PD.The original solution of the two-stage DROD model is transformed into the alternating iterative solution of the master problem and the sub-problem by the column-and-constraint generation(C&CG)algorithm,and the master problem is decomposed into a mixedinteger linear programming and a continuous second-order cone programming by the generalized Benders decomposition method to improve calculation efficiency.Finally,case studies on an actual OWF cluster with three OWFs demonstrate the correctness and efficiency of the proposed model and algorithm.

Cooperation Mechanism Design for Integrated Electricity‑Heat Systems with Information Asymmetry

Cooperation between electric power networks(EPNs)and district heating networks(DHNs)has been extensively studied under the assumption that all information exchanged is authentic.However,EPNs and DHNs belonging to different entities may result in marketing fraud.This paper proposes a cooperation mechanism for integrated electricity-heat systems(IEHSs)to overcome information asymmetry.First,a fraud detection method based on multiparametric programming with guaranteed feasibility reveals the authenticity of the information.Next,all honest entities are selected to form a coalition.Furthermore,to maintain operational independence and distribute benefits fairly,Benders decomposition is enhanced to calculate Shapley values in a distributed fashion.Finally,the cooperative surplus generated by the coalition is allocated according to the marginal contribution of each entity.Numerical results show that the proposed mechanism stimulates cooperation while achieving Pareto optimality under asymmetric information.

Stochastic Joint Replenishment Optimization under Joint Inbound Operational Cost

With e-commerce concentrating retailers and customers onto one platform,logistics companies(e.g.,JD Logistics)have launched integrated supply chain solutions for corporate customers(e.g.,online retailers)with warehousing,transportation,last-mile delivery,and other value-added services.The platform’s concentration of business flows leads to the consolidation of logistics resources,which allows us to coordinate supply chain operations across different corporate customers.This paper studies the stochastic joint replenishment problem of coordinating multiple suppliers and multiple products to gain the economies of scale of the replenishment setup cost and the warehouse inbound operational cost.To this end,we develop stochastic joint replenishment models based on the general-integer policy(SJRM-GIP)for the multi-supplier and multi-product problems and further reformulate the resulted nonlinear optimization models into equivalent mixed integer second-order conic programs(MISOCPs)when the inbound operational cost takes the square-root form.Then,we propose generalized Benders decomposition(GBD)algorithms to solve the MISOCPs by exploiting the Lagrangian duality,convexity,and submodularity of the sub-problems.To reduce the computational burden of the SJRM-GIP,we further propose an SJRM based on the power-of-two policy and extend the proposed GBD algorithms.Extensive numerical experiments based on practical datasets show that the stochastic joint replenishment across multiple suppliers and multiple products would deliver 13∼20%cost savings compared to the independent replenishment benchmark,and on average the proposed GBD algorithm based on the enhanced gradient cut can achieve more than 90%computational time reduction for large-size problem instances compared to the Gurobi solver.The power-of-two policy is capable of providing high-quality solutions with high computational efficiency.

Robust N−k Security-constrained Optimal Power Flow Incorporating Preventive and Corrective Generation Dispatch to Improve Power System Reliability

As extreme weather events have become more frequent in recent years,improving the resilience and reliability of power systems has become an important area of concern.In this paper,a robust preventive-corrective security-constrained optimal power flow(RO-PCSCOPF)model is proposed to improve power system reliability under N−k outages.Both the short-term emergency limit(STL)and the long-term operating limit(LTL)of the post-contingency power flow on the branch are considered.Compared with the existing robust corrective SCOPF model that only considers STL or LTL,the proposed ROPCSCOPF model can achieve a more reliable generation dispatch solution.In addition,this paper also summarizes and compares the solution methods for solving the N−k SCOPF problem.The computational efficiency of the classical Benders decomposition(BD)method,robust optimization(RO)method,and line outage distribution factor(LODF)method are investigated on the IEEE 24-bus Reliability Test System and 118-bus system.Simulation results show that the BD method has the worst computation performance.The RO method and the LODF method have comparable performance.However,the LODF method can only be used for the preventive SCOPF and not for the corrective SCOPF.The RO method can be used for both.

基于二阶段随机规划的城市医疗废弃物回收网络设计

城市医疗废弃物日益增加,且回收需求量受诸多因素的影响,难以准确预测,假定回收需求为确定值的医疗废弃物网络优化设计不能与实际需求相匹配。本文考虑了离散随机参数环境下,医疗回收网络设计中选址规划、分配计划及运输规划的协同优化问题,建立了以选址成本、运输成本最小为目标,设施与车辆能力限制为约束的二阶段随机规划模型。根据模型特点,设计了基于Benders decomposition的求解算法,同时,设计了一系列加速技术用于提高算法的求解效率。最后,以国内某城市医疗回收网络为背景设计算例,检验本文模型和求解策略的可行性和有效性。结果表明:相比确定性规划,随机规划的解能够节约总成本,结合一系列加速技术的Benders decomposition方法比CPLEX与纯的Benders decomposition更有优势。

Coordinated Dispatch of Integrated Electricity-Natural Gas System and the Freight Railway Network

With the significant development of liquefied natural gas(LNG)rail transport,the railway system is increasingly more closely connected with the integrated electricity-natural gas system(IEGS).To coordinate the economic operations of the two systems,this paper innovatively proposes a coordinated dispatch model of IEGS with LNG infrastructures and a freight railway network with LNG transport.First,an operational scheduling model of the railway network,considering energy consumption,is put forward for both LNG transmission and ordinary freight transport.Then,the coordinated dispatch problem of IEGS and the railway network is formulated into a mixed-integer linear programming model via the big M method and a modified incremental linearization approach.Finally,a bi-level optimization algorithm based on generalized benders decomposition(GBD)is presented to solve the coordinated dispatch problem due to the restrictions on exchanging private information.Case studies demonstrate the effectiveness of the proposed model and algorithm as well as the potential benefit for wind power accommodation.

Assessment Model for Distributed Wind Generation Hosting Capacity Considering Complex Spatial Correlations

To facilitate the large-scale integration of distributed wind generation(DWG), the uncertainty of DWG outputs needs to be quantified, and the maximum DWG hosting capacity(DWGHC) of distribution systems must be assessed. However, the structure of the high-dimensional nonlinear dependencies and the abnormal marginal distributions observed in geographically dispersed DWG outputs lead to the increase of the complexity of the uncertainty analysis. To address this issue,this paper proposes a novel assessment model for DWGHC that considers the spatial correlations between distributed generation(DG) outputs. In our method, an advanced dependence modeling approach called vine copula is applied to capture the high-dimensional correlation between geographically dispersed DWG outputs and generate a sufficient number of correlated scenarios. To avoid an overly conservative hosting capacity in some extreme scenarios, a novel chance-constrained assessment model for DWGHC is developed to determine the optimal sizes and locations of DWG for a given DWG curtailment probability. To handle the computational challenges associated with large-scale scenarios, a bilinear variant of Benders decomposition(BD) is employed to solve the chance-constrained problem.The effectiveness of the proposed method is demonstrated using a typical 38-bus distribution system in eastern China.

Distributionally Robust Transmission Expansion Planning Considering Uncertainty of Contingency Probability

The outage of power system equipment is one of the most important factors that affect the reliability and economy of power system.It is crucial to consider the influence of contingencies elaborately in planning problem.In this paper,a distributionally robust transmission expansion planning model is proposed in which the uncertainty of contingency probability is considered.The uncertainty of contingency probability is described by uncertainty interval based on the outage rate of single equipment.An epigraph reformulation and Benders decomposition are applied to solve the proposed model.Finally,the feasibility and effectiveness of the proposed model are illustrated on the IEEE RTS system and the IEEE 118-bus system.