Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

Unit Commitment by Augmented Lagrangian Relaxation: Testing Two Decomposition Approaches

One of the main drawbacks of the augmented Lagrangian relaxation method is that the quadratic term introduced by the augmented Lagrangian is not separable. We compare empirically and theoretically two methods designed to cope with the nonseparability of the Lagrangian function: the auxiliary problem principle method and the block coordinated descent method. Also, we use the so-called unit commitment problem to test both methods. The objective of the unit commitment problem is to optimize the electricity production and distribution, considering a short-term planning horizon.     

Bundle Relaxation and Primal Recovery in Unit Commitment Problems. The Brazilian Case

We consider the inclusion of commitment of thermal generation units in the optimal management of the Brazilian power system. By means of Lagrangian relaxation we decompose the problem and obtain a nondifferentiable dual function that is separable. We solve the dual problem with a bundle method. Our purpose is twofold: first, bundle methods are the methods of choice in nonsmooth optimization when it comes to solve large-scale problems with high precision. Second, they give good starting points for recovering primal solutions. We use an inexact augmented Lagrangian technique to find a near-optimal primal feasible solution. We assess our approach with numerical results.     

Stochastic programming approaches to stochastic scheduling

Practical scheduling problems typically require decisions without full information about the outcomes of those decisions. Yields, resource availability, performance, demand, costs, and revenues may all vary. Incorporating these quantities into stochastic scheduling models often produces diffculties in analysis that may be addressed in a variety of ways. In this paper, we present results based on stochastic programming approaches to the hierarchy of decisions in typical stochastic scheduling situations. Our unifying framework allows us to treat all aspects of a decision in a similar framework. We show how views from different levels enable approximations that can overcome nonconvexities and duality gaps that appear in deterministic formulations. In particular, we show that the stochastic program structure leads to a vanishing Lagrangian duality gap in stochastic integer programs as the number of scenarios increases.This author's work was supported in part by the National Science Foundation under Grants ECS 88-15101, ECS 92-16819, and SES 92-11937.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-5489 and by the UK Engineering and Physical Sciences Research Council under Grants J90855 and K17897.     

pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

Stochastic programming approach to optimization under uncertainty

In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the number of stages. We discuss an extension of coherent risk measures to a multistage setting and, in particular, dynamic programming equations for such problems.      

Bundle Methods in Stochastic Optimal Power Management: A Disaggregated Approach Using Preconditioners

A specialized variant of bundle methods suitable for large-scale problems with separable objective is presented. The method is applied to the resolution of a stochastic unit-commitment problem solved by Lagrangian relaxation. The model includes hydro- as well as thermal-powered plants. Uncertainties lie in the demand, which evolves in time according to a tree of scenarios. Dual variables are preconditioned by using probabilities associated to nodes in the tree The approach is illustrated by numerical results, obtained on a model of the French production mix over a time horizon of 10 days and 1 month.     

Generation Supply Bidding in Perfectly Competitive Electricity Markets

This paper reports on the development of a comprehensive framework for the analysis and formulation of bids in competitive electricity markets. Competing entities submit offers of power and energy to meet the next day's load. We use the England and Wales Power Pool as the basis for the development of a very general competitive power pool (CPP) framework. The framework provides the basis for solving the CPP dispatcher problem and for specifying the optimal bidding strategies. The CPP dispatcher selects the winning bids for the right to serve load each period of the scheduling horizon. The dispatcher must commit sufficient generation to meet the forecasted load and reserve requirements throughout the scheduling horizon. All the unique constraints under which electrical generators operate including start-up and shut-down time restrictions, reserve requirements and unit output limits must be taken into account. We develop an analytical formulation of the problem faced by a bidder in the CPP by specifying a strategy that maximizes his profits. The optimal bidding strategy is solved analytically for the case of perfect competition. The study in this work takes into account the principal sources of uncertainty—the load forecast and the actions of the other competitors. The formulation and solution methodology effectively exploit a Lagrangian relaxation based approach. We have conducted a wide range of numerical studies; a sample of numerical results are presented to illustrate the robustness and superiority of the analytically developed bidding strategies.     

Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.     

A Lagrangian relaxation approach to the mixed-product assembly line sequencing problem: A case study of a door-lock company in Taiwan

In mixed-product assembly line sequencing, the production resources required for the assembly lines should be scheduled to minimize the overall cost and meet customer demand. In this paper, we study an assembly line sequencing problem for the door-lock industry in Taiwan and develop an integer programming formulation with realistic constraints. The complex solution space makes the resulting program difficult to solve using commercial optimization packages. Therefore, a heuristic based on the Lagrangian relaxation principle is developed to solve this problem efficiently. We evaluate the efficiency of the developed Lagrangian relaxation heuristic by comparing its solutions with those obtained using a commercial optimization package: the computational results show that the developed heuristic solves the real-world problem faster than the optimization package by almost 15 times in CPU time at a comparable solution quality.     

Optimal Production Planning in a Stochastic Manufacturing System with Long-Run Average Cost

This paper is concerned with the optimal production planning in a dynamic stochastic manufacturing system consisting of a single machine that is failure prone and facing a constant demand. The objective is to choose the rate of production over time in order to minimize the long-run average cost of production and surplus. The analysis proceeds with a study of the corresponding problem with a discounted cost. It is shown using the vanishing discount approach that the Hamilton–Jacobi–Bellman equation for the average cost problem has a solution giving rise to the minimal average cost and the so-called potential function. The result helps in establishing a verification theorem. Finally, the optimal control policy is specified in terms of the potential function.     

Application of a Fuzzy Programming Through Stochastic Particle Swarm Optimization to Assessment of Filter Management Strategies in Fluid Power System Under Uncertainty

A fuzzy programming through stochastic particle swarm optimization is developed for the assessment of filter allocation and replacement strategies in fluid power system (FPS) under uncertainty. It can not only handle uncertainties expressed as L-R fuzzy numbers but also enhance the system robustness by transforming the fuzzy inequalities into inclusive constraints. As the simulation results indicate, the developed model can successfully decrease the total cost and enhanced the safety of system. Generally, it is believed that the model can help identify excellent filter allocation and replacement strategy with minimized operation cost and system failure risk while protecting the system.