Efficient algorithms for combined heat and power production planning under the deregulated electricity market

Combined heat and power (CHP) production is an important energy production technology that can yield much higher total energy efficiency than separate heat and power generation. In CHP production, the heat and power production follows a joint characteristic, which means that the production planning must be done in coordination. Cost-efficient operation of a CHP system can be planned by using an optimization model. A long-term planning model decomposes into thousands of hourly models. Earlier, in the regulated electric power market, the planning problem was symmetrically driven by heat and power demand. The liberalization of the power market has created an asymmetrical planning problem, where heat production responds to the demand and power production to the volatile market price. In this paper, we utilize this asymmetry to develop novel envelope-based dual algorithms for solving the hourly CHP models efficiently. The basic idea is to transform the three-dimensional characteristic operating region for heat and power production of each CHP plant into a two-dimensional envelope by taking the power price as a parameter. Then the envelopes of each plant are used for looking up the optimal solution rapidly. We propose two versions of the algorithm: the on-line envelope construction algorithm (ECON) where the envelopes are constructed for each hour based on the power price and the off-line envelope construction algorithm (ECOFF) where envelopes are pre-computed for all different power price ranges. We derive the theoretical time complexity of the two algorithms and compare their performance empirically with realistic test models against the ILOG CPLEX solver and the Power Simplex (PS) algorithm. PS is an extremely efficient specialized primal algorithm developed for the symmetrical CHP planning problem under the regulated market. On average, when reusing previous basic solutions, ECON is 603 times faster than CPLEX and 1.3 times faster than PS. ECOFF is 1860 times faster than CPLEX and four times faster than PS.     

An efficient envelope-based Branch and Bound algorithm for non-convex combined heat and power production planning

Combined heat and power (CHP) production is universally accepted as one of the most energy-efficient technologies to produce energy with lower fuel consumption and fewer emissions. In CHP technology, heat and power generation follow a joint characteristic. Traditional CHP production is usually applied in backpressure plants, where the joint characteristic can often be represented by a convex model. Advanced CHP production technologies such as backpressure plants with condensing and auxiliary cooling options, gas turbines, and combined gas and steam cycles may require non-convex models. Cost-efficient operation of a CHP system can be planned using an optimization model based on forecasts for heat load and power price. A long-term planning model decomposes into thousands of single-period models, which can be formulated in the convex case as linear programming (LP) problems, and in the non-convex case as mixed integer programming (MIP) problems.     

CO2 emissions trading planning in combined heat and power production via multi-period stochastic optimization

The EU emissions trading scheme (ETS) taking effect in 2005 covers CO₂ emissions from specific large-scale industrial activities and combustion installations. A large number of existing and potential future combined heat and power (CHP) installations are subject to ETS and targeted for emissions reduction. CHP production is an important technology for efficient and clean provision of energy because of its superior carbon efficiency. The proper planning of emissions trading can help its potential into full play, making it become a true “winning technology” under ETS. Fuel mix or fuel switch will be the reasonable choices for fossil fuel based CHP producers to achieve their emissions targets at the lowest possible cost. In this paper we formulate CO₂ emissions trading planning of a CHP producer as a multi-period stochastic optimization problem and propose a stochastic simulation and coordination approach for considering the risk attitude of the producer, penalty for excessive emissions, and the confidence interval for emission estimates. In test runs with a realistic CHP production model, the proposed solution approach demonstrates good trading efficiency in terms of profit-to-turnover ratio. Considering the confidence interval for emission estimates can help the producer to reduce the transaction costs in emissions trading. Comparisons between fuel switch and fuel mix strategies show that fuel mix can provide good tradeoff between profit-making and emissions reduction.     

Lagrangian relaxation based algorithm for trigeneration planning with storages

Trigeneration is a booming power production technology where three energy commodities are simultaneously produced in a single integrated process. Electric power, heat (e.g. hot water) and cooling (e.g. chilled water) are three typical energy commodities in the trigeneration system. The production of three energy commodities follows a joint characteristic. This paper presents a Lagrangian relaxation (LR) based algorithm for trigeneration planning with storages based on deflected subgradient optimization method. The trigeneration planning problem is modeled as a linear programming (LP) problem. The linear cost function poses the convergence challenge to the LR algorithm and the joint characteristic of trigeneration plants makes the operating region of trigeneration system more complicated than that of power-only generation system and that of combined heat and power (CHP) system. We develop an effective method for the long-term planning problem based on the proper strategy to form Lagrangian subproblems and solve the Lagrangian dual (LD) problem based on deflected subgradient optimization method. We also develop a heuristic for restoring feasibility from the LD solution. Numerical results based on realistic production models show that the algorithm is efficient and near-optimal solutions are obtained.     

Non-convex power plant modelling in energy optimisation

The European electricity market has been deregulated recently. This means that energy companies must optimise power generation considering the rapidly fluctuating price on the spot market. Optimisation has also become more difficult. New production technologies, such as gas turbines (GT), combined heat and power generation (CHP), and combined steam and gas cycles (CSG) require non-convex models. Risk analysis through stochastic simulation requires solving a large number of models rapidly. These factors have created a need for more versatile and efficient decision-support tools for energy companies.We formulate the decision-problem of a power company as a large mixed integer programming (MIP) model. To make the model manageable we compose the model hierarchically from modular components. To speed up the optimisation procedure, we decompose the problem into hourly sub-problems, and develop a customised Branch-and-Bound algorithm for solving the sub-problems efficiently. We demonstrate the use of the model with a real-life application.     

Joint planning of combined heat and power and electric power systems: An efficient model formulation

The growing importance of combined heat and power (CHP) around the world has increased the need to consider its role within electric power systems. In this paper, we show how the problem of joint planning of CHP and electric power systems may be formulated more efficiently than has previously been done, by exploiting the special structure of the optimal solution. Numerical tests indicate that this reformulation typically allows a reduction in the time required for problem solution by a factor of two to five.     

A simplex-based numerical framework for simple and efficient robust design optimization

The Simplex Stochastic Collocation (SSC) method is an efficient algorithm for uncertainty quantification (UQ) in computational problems with random inputs. In this work, we show how its formulation based on simplex tessellation, high degree polynomial interpolation and adaptive refinements can be employed in problems involving optimization under uncertainty. The optimization approach used is the Nelder-Mead algorithm (NM), also known as Downhill Simplex Method. The resulting SSC/NM method, called Simplex², is based on (i) a coupled stopping criterion and (ii) the use of an high-degree polynomial interpolation in the optimization space for accelerating some NM operators. Numerical results show that this method is very efficient for mono-objective optimization and minimizes the global number of deterministic evaluations to determine a robust design. This method is applied to some analytical test cases and a realistic problem of robust optimization of a multi-component airfoil.     

The Complex Interior-Boundary method for linear and nonlinear programming with linear constraints

In this paper we develop the Complex method; an algorithm for solving linear programming (LP) problems with interior search directions. The Complex Interior-Boundary method (as the name suggests) moves in the interior of the feasible region from one boundary point to another of the feasible region bypassing several extreme points at a time. These directions of movement are guaranteed to improve the objective function. As a result, the Complex method aims to reach the optimal point faster than the Simplex method on large LP programs. The method also extends to nonlinear programming (NLP) with linear constraints as compared to the generalized-reduced gradient.The Complex method is based on a pivoting operation which is computationally efficient operation compared to some interior-point methods. In addition, our algorithm offers more flexibility in choosing the search direction than other pivoting methods (such as reduced gradient methods). The interior direction of movement aims at reducing the number of iterations and running time to obtain the optimal solution of the LP problem compared to the Simplex method. Furthermore, this method is advantageous to Simplex and other convex programs in regard to starting at a Basic Feasible Solution (BFS); i.e. the method has the ability to start at any given feasible solution.Preliminary testing shows that the reduction in the computational effort is promising compared to the Simplex method.     

On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

An improved unit decommitment algorithm for combined heat and power systems

This paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning, considering the possibility to trade power on the spot market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning for both heat and power must be done in coordination. We present an improved unit decommitment (IUD) algorithm that starts with an improved initial solution with less heat surplus so that the relative cost-efficiency of the plants can be determined more accurately. Then the subsequent decommitment procedures can decommit (switch off) the least cost-efficient plants properly. The improved initial solution for the committed plants is generated by a heuristic procedure. The heuristic procedure utilizes both the Lagrangian relaxation principle that relaxes the system-wide (heat and power) demand constraints and a linear relaxation of the ON/OFF states of the plants. We compare the IUD algorithm with realistic test data against a generic unit decommitment (UD) algorithm. Numerical results show that IUD is an overall improvement of UD. The solution quality of IUD is better than that of UD for almost all of tested cases. The maximum improvement is 11.3% and the maximum degradation is only 0.04% (only two sub-cases out of 216 sub-cases) with an average improvement of 0.3–0.5% for different planning horizons. Moreover, IUD is more efficient (1.1–3 times faster on average) than UD.     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.     

A variant of the dynamic programming algorithm for unit commitment of combined heat and power systems

The paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning under the deregulated power market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning must be done in coordination. We introduce in this paper the DP-RSC1 algorithm, which is a variant of the dynamic programming (DP) algorithm based on linear relaxation of the ON/OFF states of the units and sequential commitment of units one by one. The time complexity of DP-RSC1 is proportional to the number of generating units in the system, the number of periods over the planning horizon and the time for solving a single-period economic dispatch problem. We have compared the DP-RSC1 algorithm with realistic power plants against the unit decommitment algorithm and the traditional priority listing method. The results show that the DP-RSC1 algorithm gives somewhat more accurate results (0.08–0.5% on average, maximum 10% for the individual sub-case) and executes 3–5 times faster on average than the unit decommitment algorithm. It is not surprising that the solution quality of the DP-RSC1 algorithm is much better than that of the priority listing method.     

Markov decision processes for infinite horizon problems solved with the cosine simplex method

This article presents a new method of linear programming (LP) for solving Markov decision processes (MDPs) based on the simplex method (SM). SM has shown to be the most efficient method in many practical problems; unfortunately, classical SM has an exponential complexity. Therefore, new SMs have emerged for obtaining optimal solutions in the most efficient way. The cosine simplex method (CSM) is one of them. CSM is based on the Karush Kuhn Tucker conditions, and is able to efficiently solve general LP problems. This work presents a new method named the Markov Cosine Simplex Method (MCSM) for solving MDP problems, which is an extension of CSM. In this article, the efficiency of MCSM is compared to the traditional revised simplex method (RSM); experimental results show that MCSM is far more efficient than RSM.     

Combined Cost and Linear Programming Models of Industrial Complexes

Many industrial complexes are chains of unit processes, the end-product of one process being the raw material for another; often the same process can also make several end-products sequentially and, furthermore, intermediate products can be bought in or sold. In managing these "multi-processes", cost accountants often use input/output models to measure historic internal costs while simultaneously, planners calculate the most profitable future mix of end-products from linear programming (LP) models. A general combined cost/LP model is proposed here, usable either for costing purposes or for LP planning. Its cost version can include standard cost techniques; when used with the planning version, it leads to the concept of "super-standard" costs for the most profitable way of running the multiprocess. The combined model is thus a basic part of an overall management information and control system.     

Integrating DEA-oriented performance assessment and target setting using interactive MOLP methods

Data envelopment analysis (DEA) and multiple objective linear programming (MOLP) are tools that can be used in management control and planning. Whilst these two types of model are similar in structure, DEA is directed to assessing past performances as part of management control function and MOLP to planning future performance targets. This paper is devoted to investigating equivalence models and interactive tradeoff analysis procedures in MOLP, such that DEA-oriented performance assessment and target setting can be integrated in a way that the decision makers’ preferences can be taken into account in an interactive fashion. Three equivalence models are investigated between the output-oriented dual DEA model and the minimax reference point formulations, namely the super-ideal point model, the ideal point model and the shortest distance model. These models can be used to support efficiency analysis in the same way as the conventional DEA model does and also support tradeoff analysis for setting target values by individuals or groups. A case study is conducted to illustrate how DEA-oriented efficiency analysis can be conducted using the MOLP methods and how such performance assessment can be integrated into an interactive procedure for setting realistic target values.     

A simple direct cosine simplex algorithm

Linear programming (LP) is the core model of constrained optimization. The Simplex method (Simplex in short) has been proven in practice to perform very well in small- or medium-sized LP problems. A new algorithm called the direct cosine Simplex algorithm (DCA) is presented here to improve upon Simplex and to solve LP problems. The proposed DCA implements a specific cosine criterion to choose the entering variable instead of the traditional most negative rule used in Simplex. Three examples are given to illustrate the implementation of the proposed DCA to improve Simplex and to serve as the optimization tool. The utility of the proposed approach is evident from the extensive computational results on test problems adapted from NETLIB. DCA reduced the number of iterations of Simplex in most cases in our computational experiment. Preliminary results for medium-sized problems are encouraging.     

Linear programming models with planned lead times for supply chain operations planning

This paper contributes to the development of models for capacity constrained Supply Chain Operations Planning (SCOP). We focus on production environments with arbitrary supply chain structures. The demand for the end items is assumed to be exogenously determined. We solve the SCOP problem with Linear Programming models using planned lead times with multi-period capacity consumption. Using planned lead times increases the reliability of the communication between SCOP and Scheduling with regard to the feasibility of the planning. Planned lead times also reduce the nervousness in the system. We model capacity constraints on the quantity of items that can be assembled within a time interval. In particular, items can be assigned to multiple resources. We discuss two LP approaches which plan the production of items so that a sum of inventory costs and costs due to backordering is minimized.     

Multi-product production planning: A goal programming approach

Cost minimization multi-product production problems with static production resource usage and internal product flow requirements have been solved by linear programming (LP) with input/output analysis. If the problem is complicated by interval resource estimates, interval linear programming (ILP) can be used. The solution of realistic problems by the above method is cumbersome. This paper suggests that linear goal programming (LGP) can be used to model a multi-product production system. LGP's unique modeling capabilities are used to solve a production planning problem with variable resource parameters. Input/output analysis is used to determine the technological coefficients for the goal constraints and is also used to derive an information sub-model that is used to reduce the number of variable resource goal constraints. Preliminary findings suggest that the LGP approach is more cost-efficient (in terms of CPU time) and in addition provides valuable information for aggregate planning.