Cornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]

Unit commitment problem

2021-12-16T05:41:34Z

Kk733: /* Flowchart for the UC problem by Dynamic programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators. This avoids the need for constantly running the generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that

<math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>

<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math> 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 
<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math>T = \text{Number of hours}</math> 
<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="430">
<gallery>
<gallery>
DP.png|'''Fig. 1''' Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>

==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 6-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a set energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 6-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 6-hour period.png|alt=|none|thumb|500x500px|'''Fig. 2''' Energy load profile over 6-hour period]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

'''Table 1''' Generator power and unit cost
{| class="wikitable"
|
|'''G1'''
|'''G2'''
|'''G3'''
|-
|Power (MW)
|800
|700
|1200
|-
|$ / MWh
|88
|110
|125
|}

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 6-hour period, while minimize operating cost, using a dynamic programming approach.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}, \forall t \in T</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

The feasible unit combinations (states) of the generators are determined by calculating the power output for each generator combination and denoting which combination is able to satisfy the energy demand at each interval.
[[File:Feasible unit combinations.png|alt=|none|thumb|501x501px|'''Fig. 3''' Energy load profile over 6-hour period]]

Costs are then calculated for each combination and the optimum combination that minimizes cost for each period may be selected, as seen below.
[[File:Optimized unit combinations.png|left|thumb|501x501px|'''Fig. 4''' Optimized unit combinations]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Single-Period Unit Commitment===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Multi-Period Unit Commitment===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit Commitment with Additional Constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit Commitment and Economic Dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-16T04:26:58Z

Kk733: /* Flowchart for the UC problem by Dynamic programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators. This avoids the need for constantly running the generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that

<math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>

<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math> 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 
<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math>T = \text{Number of hours}</math> 
<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="460" >
DP.png|Fig 1, Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>

==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Single-Period Unit Commitment===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Multi-Period Unit Commitment===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit Commitment with Additional Constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit Commitment and Economic Dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-15T18:01:10Z

Kk733: /* Introduction */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators. This avoids the need for constantly running the generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="360" >
DP.png|Fig 1, Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>

==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-15T17:38:11Z

Kk733: /* Flowchart for the UC problem by Dynamic programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="360" >
DP.png|Fig 1, Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>

==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-15T17:22:59Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-15T17:21:31Z

Kk733: /* Introduction */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the level of production from generators.

Higher generation from renewable energy sources (RES) and responsive demand participation has made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-15T17:20:03Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the production from generators.

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator <math>(g)</math>, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T20:07:23Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the production from generators.

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized for the computational speed up<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T20:06:04Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the production from generators.

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g})</math> determines how the generator interacts with the system requirements<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>.

General technical constraints presented are <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T20:03:47Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the production from generators.

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements.

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T19:50:12Z

Kk733: /* Introduction */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is a fundamentally NP-hard, mixed-integer nonlinear, non-convex optimization problem. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. The problem involves integer decision variables- to operate the generators and the production from generators.

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T19:40:57Z

Kk733: /* Dynamic Programming Based Approach */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear, Non-convex programming optimization problem. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math>
===== Flowchart for the UC problem by Dynamic programming =====
<gallery class="center" mode="packed" heights="310" >
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T19:35:14Z

Kk733: /* Dynamic Programming Based Approach */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear, Non-convex programming optimization problem. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math> F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where 
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>, 
<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math> 

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{ to } (T,R)</math> 
<math> T = \text{Number of hours}</math>, 

<math>R = \text{Stage of DP execution}</math> <gallery>
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T19:13:12Z

Kk733: /* Dynamic Programming Based Approach */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear, Non-convex programming optimization problem. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where <math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,
<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{to} (T,R)</math>,

<math>T = \text{Number of hours}</math>, <math>R = \text{Stage of DP execution}</math> <gallery>
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-12-13T19:12:18Z

Kk733: Equations reformatting

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear, Non-convex programming optimization problem. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where <math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>, <math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) \text{to} (T,R)</math>,

<math>T = \text{Number of hours}</math>, <math>R = \text{Stage of DP execution}</math> <gallery>
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==
The unit commitment problem considers how to best deploy energy generation resources to meet energy demand imposed by the market, while optimizing for some target – typically operating costs. There are several methods that may be utilized to solve the UC problem, including Mixed Integer Non-Linear Programming and Dynamic Programming based approaches. The implications of the UC problem extend far beyond the cost saving benefits, including resource conservation and sustainability domains.

==References==
<references />

Unit commitment problem

2021-11-29T00:17:40Z

Kk733:

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear, Non-convex programming optimization problem. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref name = "Abdou">Abdou,I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref name = "Knu">Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref name = "Krsn">Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

=== Single Period Unit Commitment ===
Consider an electricity market with a particular load profile, as seen below. This demand varies throughout the course of a 24-hour period and must be satisfied by the electrical energy output from a set of three generators. Each generator has a minimum and maximum energy output limit, as well as unit production cost associated with energy generation. Each generator may be in an on or off state and may be started or stopped throughout the 24-hour period. The utility may wish to operate the system so that the load demand is met while minimizing cost.
[[File:Energy load profile over 24-hour period.png|thumb|500x500px|Energy load profile over 24-hour period|alt=|none]]

==== Solution ====
The following variables are assigned to the system:

<math>I \qquad</math> set of generators indexed by i

<math>T \qquad</math> Set of time intervals indexed by t

<math>g_i \qquad </math> power output of generator i

<math>c_i \qquad </math> cost of unit generation of generator i

<math>u_{i,t} \qquad </math> binary on / off decision of generator i at time t

<math>G_{i,min} \qquad </math> minimum output of generator i

<math>G_{i,max} \qquad </math> maximum output of generator i

The three generators have the following characteristics:

''Generator 1''

<math>G_{1,min} </math>= 300 MW, <math>G_{1,max} </math>= 800 MW

<math>c_1 </math>= $88 / MWh

''Generator 2''

<math>G_{2,min} </math>= 250 MW, <math>G_{2,max} </math>= 700 MW

<math>c_2 </math>= $110 / MWh

''Generator 3''

<math>G_{3,min} </math>= 400 MW, <math>G_{3,max} </math>= 1200 MW

<math>c_3 </math>= $125 / MWh

To determine the generator schedule, we carry out the following optimization problem to meet demand over the 24-hour period, while minimize operating cost.

min <math>\sum_{i\in I} g_i * c_i </math>

such that

<math>G_{i,min} * u_{i,t} \leq g_i \leq G_{i,max} * u_{i,t}, \forall i \in I</math>

`<math>\sum_{i \in I} g_i * u_{i,t} \geq d_{i,t}</math>

<math>u_{i,t} \in \{0,1\}, \forall i \in I, \forall t \in T</math>

Modeling the system in the GAMS software package, we are able to obtain an optimized schedule for when each generator should be active or inactive throughout the course of the 24-hour period. Below are the optimized generator schedules superimposed on the load profile.
[[File:Generator schedule on load profile.png|none|thumb|501x501px|Optimized generator schedule for load profile]]

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:28:53Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
==== Other methods in literature ====
Apart from these two methods, there are other several methods outlined <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:23:35Z

Kk733: /* Dynamic Programming Based Approach */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure<ref>Dynamic Programming. (n.d.). Retrieved November 28, 2021, from http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf.</ref>. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.
Following is the dynamic programming problem formulation <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
</gallery>
Apart from these two methods, there are other several methods outlined <ref>Krishna Mohan, R., Gopichand Naik, M., & Rajendra Prasad, S. (2021). A comparative study of unit commitment problem by dynamic programming and genetic algorithm. Lecture Notes in Electrical Engineering, 61–77. https://doi.org/10.1007/978-981-15-8439-8_6 </ref>
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:18:26Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref>

General technical constraints presented in <ref>Knueven, B., Ostrowski, J., & Watson, J.-P. (2020). On mixed-integer programming formulations for the unit commitment problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2019.0944 </ref> are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure[4]. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.

<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on [3]
</gallery>
Apart from these two methods, there are other several methods outlined on [3]
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:15:06Z

Kk733: /* Mixed Integer Non-Linear Programming */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized<ref>Knueven, B., Ostrowski, J., & Watson, J. P. (n.d.). (rep.). Mixed Integer Programming Formulations for the Unit Commitment Problem. Retrieved November 27, 2021, from https://www.ferc.gov/sites/default/files/2020-09/W1-A-1-Knueven.pdf. </ref>

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation [2]

General technical constraints presented in [1] are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure[4]. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.

<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on [3]
</gallery>
Apart from these two methods, there are other several methods outlined on [3]
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:10:40Z

Kk733: /* Introduction */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements<ref>Frangioni, A., & Gentile, C. (2006). Solving nonlinear single-unit commitment problems with ramping constraints. Operations Research, 54(4), 767–775. https://doi.org/10.1287/opre.1060.0309 </ref>. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372</ref>

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized[http://www.optimization-online.org/DB_FILE/2019/10/7426.pdf 1].

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation [2]

General technical constraints presented in [1] are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure[4]. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.

<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on [3]
</gallery>
Apart from these two methods, there are other several methods outlined on [3]
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:08:19Z

Kk733: /* Introduction */

Authors: Fah Kumdokrub, Malcolm Hegeman, Kapil Khanal (SYSEN 6800 Fall 2021)

==Introduction==
Unit commitment(UC) is fundamentally NP-hard scheduling and mixed-integer. Nonlinear,Non-convex programming optimization problem<ref>Abdou, I., & Tkiouat, M. (2018). Unit commitment problem in electrical power system: A literature review. International Journal of Electrical and Computer Engineering (IJECE), 8(3), 1357. https://doi.org/10.11591/ijece.v8i3.pp1357-1372 </ref>. The problem involves integer decision variables- to turn generators ON or OFF. It is used for optimizing the power generators schedule such that their operating cost is kept low over some time units(planning horizon) and within operating requirements[1]. A very simple problem involving UC is to try to minimize the operating cost for two power generators with different max/min power output , startup costs and operating costs for one hour. How will the problem change in n hours with n generators?

Recently, higher generation from renewable energy sources (RES) and more price responsive demand participation have made the UC problem a hard challenge, mainly due to the unpredictability and the high variability of RES[2]

==Theory, methodology, and/or algorithmic discussions==
=== Mixed Integer Non-Linear Programming===
The Unit Commitment Problem (UC) is a large-scale mixed-integer nonlinear program for finding a
the low-cost operating schedule for power generators.
These problems typically have quadratic objective functions and nonlinear, non-convex transmission
Constraints. Typically both of these are linearized[http://www.optimization-online.org/DB_FILE/2019/10/7426.pdf 1].

Objective function = <math>\min \sum_{g \in G}\sum_{t \in T}c_{g}(t) </math>

such that <math> \sum_{g\in{G}}A_{g}(p_{g},\bar{p}_{g}, u_{g}) + N(s) = L</math>

<math>(p_{g},\bar{p}_{g}, u_{g}) \in \prod_{g}</math>

Here <math>c_{g}</math> is the cost vector associated with <math>p_{g}, \bar{p}_{g},u_{g}</math>, such that the objective function (1a) is to
minimize system operation cost. The vectors <math>p_{g}, \bar{p}_{g},u_{g}</math> represent the feasible generation
schedule, maximum power available, and the on/off status for generator g, respectively. The
matrix <math>A_{g}(p_{g},\bar{p}_{g}, u_{g}</math> determines how the generator interacts with the system requirements,
which are written in matrix form as equation [2]

General technical constraints presented in [1] are
* Convex productions costs
* Minimum and maximum output levels
* Ramping constraints
* Minimum up and downtime

=== Dynamic Programming Based Approach ===
Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure[4]. It takes some creativity in coming up with the formulations of dynamic programming for
a problem. Also, various heuristics are applied to decrease the search space and computation time.

<math>obj = F_{cost}(T,R) = \min_{P}{P_{cost}(T,R) + S_{cost}(T-1,P:T,R) + F_{cost}(T-1,P)}</math>

where,
<math>F_{cost}(T,R)= \text{Minimum cost price at state}(T,R)</math>,

<math>P_{cost}(T,R)= \text{The production cost at state}(T,R)</math>,

<math>S_{cost}(T-1,P:T,R) = \text{The transition cost price from state}(T-1,P) to (T,R)</math>,

<math>T = \text{Number of hours}</math>

<math>R = \text{Stage of DP execution}</math>

<gallery>
DP.png|Flowchart provided on [3]
</gallery>
Apart from these two methods, there are other several methods outlined on [3]
* Priority List Method
* Lagrangian Relaxation method
* Branch and Bound Method
* Genetic algorithm based approach

==Numerical example==

==Applications==
Unit commitment problems can be further adjusted for components that reflect the real-world problem. A simple categorization can be divided into two major groups. One is related to the commitment of power generation/production/manufacturing process, and the other group involves output allocation to the committed units, often known as unit commitment and economic dispatch <ref>A.J. Conejo, L. Baringo, “Power System Operations,” Power Electronics and Power
Systems, p. 197-232, 2018, doi:https://link.springer.com/chapter/10.1007%2F978-3-319-69407-8_7 </ref>.

===Unit commitment: Single period===
This type of problem usually optimizes the number of power generators for each facility/plant to meet the demand in a specific period. Although this might not be the case study in real-world scenarios, starting off with this type of unit commitment optimization problem might help check the correctness of other constraints before adding the complexity of time and other power generating units’ components.

===Unit commitment: Multi-period===
Many times, the production of power should be planned in advance. This planned period could be for months, weeks, or even overnight to avoid under or over-power generation and minimize the total number of generators needed. And these problems would require a multi-period unit commitment optimization.

===Unit commitment: Additional constraints===
There are many more criteria that can be added to the unit commitment problem to truly reflect the system. Some scenarios may be required reserve constraints to ensure sufficient supply in response to a spike in demand <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Ramping constraints can also be added since the generators take time to start and stop the process which both affect the cost and amount of power output <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Types of power affect the optimization whether they come from a single source or multiple sources <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref> <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

===Unit commitment and Economic dispatch===
With any attributes to the unit commitment problem, the economic aspects are always involved meaning that the allocation of power generation (energy output) for each committing unit must be economical with all the costs and revenues. Power generator plants not only need to meet the demand, but they also need to operate in the most economical ways, at the lowest possible cost or the highest possible profit. There are many costs involved in generating power, for example, the cost per unit of power generations, the cost of shutting down or starting up the generator, the cost of over generating power since it may cause damage to the plant, and there are many other costs and benefits that could be considered to the problem.

Commercialized unit commitment software is also available for use. For example, Power Optimisation company developed a software named POWEROP which is more generalized to wide ranges of users or power companies, customized software for Northern Ireland Electricity (NIE), and software developed specifically for the British Electricity Trading and Transmission Arrangements (BETTA) <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. Software for NIE considers power from multiple sources, including gas, coal, and oil-fired steam <ref name='L.A.'>L.A. Wolsey, Integer Programming. Wiley, 1998.</ref>. Additionally, software for BETTA can generate electricity prices for both the general market and individuals by contract <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>. The software was developed from a multi-stage mixed-integer linear programming (MILP) and adapted the constraints to serve customers’ specific requirements <ref name='Unit'>“Unit Commitment and Economic Dispatch Software to Optimise the Short-Term Scheduling of Electrical Power Generation” https://msi-jp.com/xpress/learning/square/unit_en.pdf (accessed Nov. 13, 2021).</ref>.

==Conclusion==

==References==
<references />

Unit commitment problem

2021-11-28T03:04:53Z

Kk733: /* Mixed Integer Non-Linear Programming */

Unit commitment problem

2021-11-28T03:03:09Z

Kk733: /* Dynamic Programming Based Approach */

Unit commitment problem

2021-11-28T03:02:32Z

Kk733: /* Dynamic Programming Based Approach */

File:DP.png

2021-11-28T03:00:50Z

Kk733: Accessed from https://link.springer.com/sharelink/10.1007/978-981-15-8439-8_6

== Summary ==
Accessed from https://link.springer.com/sharelink/10.1007/978-981-15-8439-8_6

Unit commitment problem

2021-11-28T02:55:51Z

Kk733: /* Dynamic Programming Based Approach */

Unit commitment problem

2021-11-28T02:55:21Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Unit commitment problem

2021-11-28T02:54:16Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Unit commitment problem

2021-11-28T02:51:33Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Unit commitment problem

2021-11-28T02:41:37Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Unit commitment problem

2021-11-28T02:32:56Z

Kk733: /* Theory, methodology, and/or algorithmic discussions */

Unit commitment problem

2021-11-28T02:23:07Z

Kk733: /* Introduction */

Data driven robust optimization

2021-11-22T00:49:41Z

Kk733: Blanked the page

Unit commitment problem

2021-11-22T00:47:45Z

Kk733:

Authors: Fah Kumdokrub, Malcolm Hegeman , Kapil Khanal (SYSEN 6800 Fall 2021)

Data driven robust optimization

2021-11-08T22:26:01Z

Kk733:

Kapil Khanal \n
Data Driven robust optimization

Data driven robust optimization

2021-11-08T22:25:26Z

Kk733: Created page with "Kapil Khanal Data Driven robust optimization"

Kapil Khanal
Data Driven robust optimization