The unit commitment model with concave emissions costs: a hybrid Benders’ Decomposition with nonconvex master problems

We present a unit commitment model which determines generator schedules, associated production and storage quantities, and spinning reserve requirements. Our model minimizes fixed costs, fuel costs, shortage costs, and emissions costs. A constraint set balances the load, imposes requirements on the way in which generators and storage devices operate, and tracks reserve requirements. We capture cost functions with piecewise-linear and (concave) nonlinear constructs. We strengthen the formulation via cut addition. We then describe an underestimation approach to obtain an initial feasible solution to our model. Finally, we constitute a Benders’ master problem from the scheduling variables and a subset of those variables associated with the nonlinear constructs; the subproblem contains the storage and reserve requirement quantities, and power from generators with convex (linear) emissions curves. We demonstrate that our strengthening techniques and Benders’ Decomposition approach solve our mixed integer, nonlinear version of the unit commitment model more quickly than standard global optimization algorithms. We present numerical results based on a subset of the Colorado power system that provide insights regarding storage, renewable generators, and emissions.     

Stochastic optimization for power system configuration with renewable energy in remote areas

This paper presents a stochastic mixed integer programming model for a comprehensive hybrid power system design problem, including renewable energy generation, storage device, transmission network, and thermal generators, for remote areas. Given the complexity of the model, we developed a Benders’ decomposition algorithm with two additional types of cutting planes: Pareto-optimal cuts generated using a modified Magnanti-Wong method and cuts generated from a maximum feasible subsystem. Computational results show significant improvement in our ability to solve this type of problem in comparison to a state-of-the-art professional solver. This model and the solution algorithm provide an analytical decision support tool for the hybrid power system design problem.     

基于随机规划的建筑集群冷热电联供系统优化研究

面向建筑集群的冷热电联供系统的设计和优化是实现建筑楼宇能源成本节约的重要途径。随机因素对该联供系统的优化决策,具有显著的影响。考虑建筑楼宇的能源需求为随机变量,构建随机混合整数规划模型,解决以最小化建筑楼宇总费用为目标时建筑集群冷热电联供系统的优化问题;其次,提出采用Benders多割平面方法求解多目标规划问题,从而寻找冷热电联供系统的设备配置和系统运行的Pareto最优决策;最后,通过实验验证了模型和算法的有效性。实验结果表明建筑集群在协作模式下,相比于非协作模式,具有更低的总费用。     

An application of Lagrangian relaxation to a capacity planning problem under uncertainty

A supply chain network-planning problem is presented as a two-stage resource allocation model with 0-1 discrete variables. In contrast to the deterministic mathematical programming approach, we use scenarios, to represent the uncertainties in demand. This formulation leads to a very large scale mixed integer-programming problem which is intractable. We apply Lagrangian relaxation and its corresponding decomposition of the initial problem in a novel way, whereby the Lagrangian relaxation is reinterpreted as a column generator and the integer feasible solutions are used to approximate the given problem. This approach addresses two closely related problems of scenario analysis and two-stage stochastic programs. Computational solutions for large data instances of these problems are carried out successfully and their solutions analysed and reported. The model and the solution system have been applied to study supply chain capacity investment and planning.     

Energy contracts management by stochastic programming techniques

We consider the problem of optimal management of energy contracts, with bounds on the local (time step) amounts and global (whole period) amounts to be traded, integer constraint on the decision variables and uncertainty on prices only. After building a finite state Markov chain by using vectorial quantization tree method, we rely on the stochastic dual dynamic programming (SDDP) method to solve the continuous relaxation of this stochastic optimization problem. An heuristic for computing sub optimal solutions to the integer optimization problem, based on the Bellman values of the continuous relaxation, is provided. Combining the previous techniques, we are able to deal with high-dimensional state variables problems. Numerical tests applied to realistic energy markets problems have been performed.     

A heuristic decomposition approach to optimal control in a water supply model

The optimal pump control problem in a water supply system can be formulated as a mixed integer programming problem. In general, this problem is very difficult to solve by conventional integer programming algorithms, because the number of decision variables is as large as the total number of combinations of pump stations and control periods. However, it possesses a certain block triangular structure, which offers an attractive computational scheme. Taking advantage of this structure, this paper proposes a heuristic decomposition algorithm for finding a good feasible solution to this type of mixed integer programming problems. Numerical results for an actual pump control problem are also reported.     

Reliability stochastic optimization for a series system with interval component reliability via genetic algorithm

This paper deals with chance constraints based reliability stochastic optimization problem in the series system. This problem can be formulated as a nonlinear integer programming problem of maximizing the overall system reliability under chance constraints due to resources. The assumption of traditional reliability optimization problem is that the reliability of a component is known as a fixed quantity which lies in the open interval (0, 1). However, in real life situations, the reliability of an individual component may vary due to some realistic factors and it is sensible to treat this as a positive imprecise number and this imprecise number is represented by an interval valued number. In this work, we have formulated the reliability optimization problem as a chance constraints based reliability stochastic optimization problem with interval valued reliabilities of components. Then, the chance constraints of the problem are converted into the equivalent deterministic form. The transformed problem has been formulated as an unconstrained integer programming problem with interval coefficients by Big-M penalty technique. Then to solve this problem, we have developed a real coded genetic algorithm (GA) for integer variables with tournament selection, uniform crossover and one-neighborhood mutation. To illustrate the model two numerical examples have been solved by our developed GA. Finally to study the stability of our developed GA with respect to the different GA parameters, sensitivity analyses have been done graphically.     

Stochastic and Risk Management Models and Solution Algorithm for Natural Gas Transmission Network Expansion and LNG Terminal Location Planning

Due to the increasing demands for natural gas, it is playing a more important role in the energy system, and its system expansion planning is drawing more attentions. In this paper, we propose expansion planning models which include both natural gas transmission network expansion and LNG (Liquified Natural Gas) terminals location planning. These models take into account the uncertainties of demands and supplies in the future, which make the models stochastic mixed integer programs with discrete subproblems. Also we consider risk control in our models by including probabilistic constraints, such as a limit on CVaR (Conditional Value at Risk). In order to solve large-scale problems, especially with a large number of scenarios, we propose the embedded Benders decomposition algorithm, which applies Benders cuts in both first and second stages, to tackle the discrete subproblems. Numerical results show that our algorithm is efficient for large scale stochastic natural gas transportation system expansion planning problems.     

Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems

Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage stochastic network flow problem with integer variables in both stages.     

Two-stage network constrained robust unit commitment problem

For a current deregulated power system, a large amount of operating reserve is often required to maintain the reliability of the power system using traditional approaches. In this paper, we propose a two-stage robust optimization model to address the network constrained unit commitment problem under uncertainty. In our approach, uncertain problem parameters are assumed to be within a given uncertainty set. We study cases with and without transmission capacity and ramp-rate limits (The latter case was described in Zhang and Guan (2009), for which the analysis part is included in Section 3 in this paper). We also analyze solution schemes to solve each problem that include an exact solution approach and an efficient heuristic approach that provides tight lower and upper bounds for the general network constrained robust unit commitment problem. The final computational experiments on an IEEE 118-bus system verify the effectiveness of our approaches, as compared to the nominal model without considering the uncertainty.     

An adaptive model with joint chance constraints for a hybrid wind-conventional generator system

We analyze scheduling a hybrid wind-conventional generator system to make it dispatchable, with the aim of profit maximization. Our models ensure that with high probability we satisfy the day-ahead power promised by the model, using combined output of the conventional and wind generators. We consider two scenarios, which differ in whether the conventional generator must commit to its schedule prior to observing the wind-power realizations or has the flexibility to adapt in near real-time to these realizations. We investigate the synergy between the conventional generator and wind farm in these two scenarios. Computationally, the non-adaptive model is relatively tractable, benefiting from a strong extended-variable formulation as an integer program. The adaptive model is a two-stage stochastic integer program with joint chance constraints. Such models have seen limited attention in the literature because of the computational challenges they pose. However, we develop an iterative regularization scheme in which we solve a sequence of sample average approximations under a growing sample size. This reduces computational effort dramatically, and our empirical results suggest that it heuristically achieves high-quality solutions. Using data from a wind farm in Texas, we demonstrate that the adaptive model significantly outperforms the non-adaptive model in terms of synergy between the conventional generator and the wind farm, with expected profit more than doubled.     

Stochastische Modelle zur optimalen Lastverteilung in einem Kraftwerksverbund

Kurzfassung Die Lastverteilung in einem Kraftwerksverbund erfolgt in zwei Schritten. Im ersten Schritt werden die Kraftwerkseinheiten ausgewählt, die zu jedem Zeitpunkt des Planungszeitraumes in Betrieb sind, damit die erwartete Energieanforderung erfüllt werden kann (Einsatzoptimierung). Im zweiten Schritt wird die Last, die in einem bestimmten Zeitpunkt tatsächlich anfällt, auf die in Betrieb befindlichen Einheiten verteilt (Belastungsoptimierung). Die Einsatzoptimierung erfolgt gewöhnlich mit Hilfe eines gemischt-ganzzahligen linearen Programms und die Belastungsoptimierung mit dem sogenannten Zuwachskostenverfahren. In diesem Aufsatz werden stochastische Modelle für die Einsatz- und Belastungsoptimierung formuliert.

---

The economic operation of an electric power system over a short time horizon involves two separate steps. The first of these is the predispatch or selection of equipment to be operated to meet the expected loads at each point in time of the horizon (unit commitment). The second step is the on-line economic dispatch which determines, instant to instant, the load to be carried on each unit selected in the first step. The unit commitment problem is usually solved by mixed integer programming and the economic dispatch problem by an incremental cost method. In this paper stochastic programming models for the unit commitment and economic dispatch problems are presented.

---

     

A two-stage fuzzy robust integer programming approach for capacity planning of environmental management systems

In this study, a two-stage fuzzy robust integer programming (TFRIP) method has been developed for planning environmental management systems under uncertainty. This approach integrates techniques of robust programming and two-stage stochastic programming within a mixed integer linear programming framework. It can facilitate dynamic analysis of capacity-expansion planning for waste management facilities within a multi-stage context. In the modeling formulation, uncertainties can be presented in terms of both possibilistic and probabilistic distributions, such that robustness of the optimization process could be enhanced. In its solution process, the fuzzy decision space is delimited into a more robust one by specifying the uncertainties through dimensional enlargement of the original fuzzy constraints. The TFRIP method is applied to a case study of long-term waste-management planning under uncertainty. The generated solutions for continuous and binary variables can provide desired waste-flow-allocation and capacity-expansion plans with a minimized system cost and a maximized system feasibility.     

Solution sensitivity-based scenario reduction for stochastic unit commitment

A two-stage stochastic program is formulated for day-ahead commitment of thermal generating units to minimize total expected cost considering uncertainties in the day-ahead load and the availability of variable generation resources. Commitments of thermal units in the stochastic reliability unit commitment are viewed as first-stage decisions, and dispatch is relegated to the second stage. It is challenging to solve such a stochastic program if many scenarios are incorporated. A heuristic scenario reduction method termed forward selection in recourse clusters (FSRC), which selects scenarios based on their cost and reliability impacts, is presented to alleviate the computational burden. In instances down-sampled from data for an Independent System Operator in the US, FSRC results in more reliable commitment schedules having similar costs, compared to those from a scenario reduction method based on probability metrics. Moreover, in a rolling horizon study, FSRC preserves solution quality even if the reduction is substantial.     

Dynamic economic dispatch using Lbest-PSO with dynamically varying sub-swarms

Dynamic economic dispatch (DED) is one of the major planning problem in a power system. It is a non-linear optimization problem with various operational constraints, which includes the constraints of the generators operating characteristics and the system constraints. Its principal aim is to minimize the cost of power production of all the participating generators over a time horizon of 24 h, while satisfying the system constraints. This problem deals with non-convex characteristics if generation unit valve-point effects are taken into account. The paper intends to solve the DED problem with valve-point effects, using our modified form of Local-best variant of Particle Swarm Optimization (Lbest PSO) algorithm. We have tested our algorithm on 5-unit, 10-unit and 110-unit test system with non-smooth fuel cost functions to prove the effectiveness of the suggested method over different state of the art methods.     

The sample average approximation method for empty container repositioning with uncertainties

One of the challenges faced by liner operators today is to effectively operate empty containers in order to meet demand and to reduce inefficiency in an uncertain environment. To incorporate uncertainties in the operations model, we formulate a two-stage stochastic programming model with random demand, supply, ship weight capacity, and ship space capacity. The objective of this model is to minimize the expected operational cost for Empty Container Repositioning (ECR). To solve the stochastic programs with a prohibitively large number of scenarios, the Sample Average Approximation (SAA) method is applied to approximate the expected cost function. To solve the SAA problem, we consider applying the scenario aggregation by combining the approximate solution of the individual scenario problem. Two heuristic algorithms based on the progressive hedging strategy are applied to solve the SAA problem. Numerical experiments are provided to show the good performance of the scenario-based method for the ECR problem with uncertainties.     

基于可信性理论的模糊广义指派问题研究

鉴于广义指派问题的参数确定上通常包含不确定性,因此,将模型的主要参数,即单位费用、资源消耗量,用梯形模糊变量来刻画,从而建立模糊广义指派模型.在模型求解过程中,结合到决策者的实际要求,利用可信性理论将目标函数和约束条件进行清晰化处理,进而通过参数分解法求解.最后,通过数值例子说明模糊广义指派问题的应用,并检验所提方法的有效性.     

Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the $L$ -shaped or Benders’ methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illustrate our algorithms using examples from the literature. We report computational results using the stochastic server location problem instances which suggest that our decomposition-based approach scales better with increases in the number of scenarios than a state-of-the art solver which was used to solve the deterministic equivalent formulation.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

The new Fundamental Tree Algorithm for production scheduling of open pit mines

The problem of annual production scheduling in surface mining consists of determining an optimal sequence of extracting the mineralized material from the ground. The main objective of the optimization process is usually to maximize the total Net Present Value of the operation. Production scheduling is typically a mixed integer programming (MIP) type problem. However, the large number of integer variables required in formulating the problem makes it impossible to solve. To overcome this obstacle, a new algorithm termed “Fundamental Tree Algorithm” is developed based on linear programming to aggregate blocks of material and decrease the number of integer variables and the number of constraints required within the MIP formulation. This paper proposes the new Fundamental Tree Algorithm in optimizing production scheduling in surface mining. A case study on a large copper deposit summarized in the paper shows substantial economic benefit of the proposed algorithm compared to existing methods.