Patent Publication Number: US-2020279340-A1

Title: Optimal Convex Hull Pricing Procedure for Electricity Whole Sale Market

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The current application claims priority to U.S. Provisional Application, Ser. No. 62/812,634, filed Mar. 1, 2019, the entire disclosure of which is incorporated herein by reference. 
    
    
     BACKGROUND 
     For most wholesale electricity grid markets in the U.S., Independent System Operators (ISOs) (also referred to herein as “Controllers”) collect the bids from the generation and load sides and then run the security-constrained unit commitment (SCUC) problem to decide the local marginal prices (LMPs) for transactions. As indicated in [1], the unit commitment (UC) problem is in general a mixed-integer program, in which the convexity is not maintained. Thus, there could be no set of uniform prices that supports a welfare-maximizing solution. For instance, a generation unit could have a “lost opportunity cost,” which is defined as the gap between a unit&#39;s maximum possible profit under the clearing price and the actual profit obtained by following the ISO&#39;s solution. To address this issue, one approach is still to maintain uniform energy prices based on marginal energy costs and meanwhile ISOs pay the side payments to units, so as to cover their “lost opportunity costs.” This payment is referred to as “uplift” payment. In other words, due to the non-convexity of the SCUC problems, there is a positive non-zero gap between the objective value of the primal formulation used by ISOs and the sum of the objectives of the profit maximization models used by each market participant. ISOs need to pay this positive non-zero gap, i.e., uplift payment, to the resources owned by market participants. To minimize the uplift payments, a convex hull pricing approach was recently introduced and received significant attention [1], [2], [3]. This pricing approach aims to minimize the uplift payments over all possible uniform prices. The Midcontinent ISO has implemented an approximation of convex hull pricing, named extended locational marginal prices [4]. 
     In general, the optimization problem of minimizing the uplift payments is computationally challenging. The main difficulties lie in two aspects: 1) discrete decision variables (on and off statuses of each generator) in the formulation and 2) general convex functions of the generation costs. To address these, significant progress has been made in [2], among others, in which a convex hull description for the UC polytope without considering ramping is introduced and convex envelop is introduced to reformulate the problem as a second-order cone programming. For real world market clearing problems, more advanced convex hull UC formulation with consideration of generator physical constraints including ramping is required. 
     SUMMARY 
     In this disclosure, an integral formulation as described in [5] is introduced for the single-generator UC problem. The integral formulation can provide an integral solution for a general single-generator UC problem considering min-up/-down time, generation capacity, ramping and variant start-up cost restrictions with a general convex cost function. 
     In an aspect of the current disclosure a method for operating an electrical power grid is provided. The electrical power grid includes an electrical power grid, a plurality of power generation participants providing electric power to the electrical power grid, a plurality of consumers drawing electrical power from the electrical power grid, and a Controller that administers the market for the power generation participants and the consumers on the electrical power grid. The method includes: collecting bids, by the controller, from the power generation participants and the power generation recipients; and setting, by the controller, one or more uniform prices for the providing of electric power from the power generation participants to the power generations consumers; where the setting step utilizes a convex hull pricing approach; and where the convex hull pricing approach utilizes an integral formulation of the single-generator unit commitment problem to facilitate the calculation of an accurate convex hull price that achieves the most efficient market clearing price. In a detailed embodiment, the calculation of the improved convex hull price involves only solving a linear program, and the calculation has guaranteed convergence and fast solving time for practical real-world application. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block-diagram representation of an exemplary electric power grid according to the current disclosure; and 
         FIG. 2  is a flow diagram representation of a market clearing process according to the current disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     Referring to  FIG. 1 , an exemplary ISO or controller  10 , according to the current disclosure, administers the market for electricity producers  12  and users  14  on an electric power grid  16 . Some exemplary functions of the controller  10  include monitoring energy transfers on the transmission system, scheduling transmission service, managing power congestion, operating DA and RT energy and operating reserves (“OR”) markets, and regional transmission planning. Both the electricity producers  12  and the users  14  may be considered to be market participants (MPs) as they conduct business within the controller&#39;s  10  region. Traditionally, the electricity producers will provide offers  18  of electrical power and the users will provide bids  20  for power. The controller  10  will process the offers  18  and bids  20  with consideration of the transfer limits on grid  16  to determine commitments of electrical power and then controlling the dispatch  22  of electricity flowing through the grid  16  based upon the commitments. 
     I. An Integral Formulation 
     Notation. For a T-period problem, let L (l) be the min-up (-down) time limit,  C  ( C ) be the generation upper (lower) bound when the generator is online, V be the start-up/shut-down ramp rate, and V be the ramp-up/-down rate in the stable generation region. Binary decision variable w t  represents whether the generator starts at time t for the first time (w t =1) or not (w t =0), binary decision variable y tk  represents whether the generator starts up at t and shuts down at k+1 (y tk =1) or not (y tk =0), binary decision variable z tk  represents whether the generator shuts down at time t+1 and starts up again at time k (z tk =1) or not (z tk =0), and binary decision variable θ t  represents whether the generator shuts down at time t+1 and stays offline to the end (θ t =1) or not (θ t =0). Further, let q tk   s  be the generation amount at time s corresponding to the “on” interval y tk =1. The corresponding generation cost ƒ tk   s (q tk   s ) is usually denoted as a convex function  ƒ   tk   s (q tk   s )=a s (q tk   s ) 2 +b s q tk   s +c s . The following formulation described in [5] (formulation (8) in [5]) based on a revised dynamic programming can provide an integral solution, in which the general convex cost function is approximated by a piecewise linear function with N pieces (N can be a very large number). That is, instead of solving a mixed-integer program with a convex cost function, the optimal solution can be obtained by solving the following linear program if ƒ tk   s (q tk   s ) is approximated by a piecewise linear function with N pieces as in most practice. We denote this formulation as new UC (NUC) formulation. 
     
       
         
           
             
               
                 
                   
                     min 
                      
                     
                       
                         ∑ 
                         
                           t 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                         
                           
                             g 
                             + 
                           
                            
                           
                             ( 
                             
                               
                                 s 
                                 o 
                               
                               + 
                               t 
                               - 
                               1 
                             
                             ) 
                           
                         
                          
                         
                           w 
                           t 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         t 
                         = 
                         1 
                       
                       T 
                     
                      
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           
                             t 
                             + 
                             L 
                             - 
                             1 
                           
                         
                         
                           T 
                           - 
                           
                               
                           
                            
                           1 
                         
                       
                        
                       
                         
                           
                             g 
                             - 
                           
                            
                           
                             ( 
                             
                               k 
                               - 
                               t 
                               + 
                               1 
                             
                             ) 
                           
                         
                          
                         
                            
                           tk 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         t 
                         = 
                         L 
                       
                       
                         T 
                         - 
                          
                         - 
                         1 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           
                             t 
                             + 
                              
                             + 
                             1 
                           
                         
                         T 
                       
                        
                       
                         
                           
                             g 
                             + 
                           
                            
                           
                             ( 
                             
                               k 
                               - 
                               t 
                               - 
                               1 
                             
                             ) 
                           
                         
                          
                         
                           z 
                           
                             t 
                              
                             k 
                           
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         tk 
                          
                         
                             
                         
                          
                         ϵ 
                          
                         
                             
                         
                          
                         TK 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           s 
                           = 
                           t 
                         
                         k 
                       
                        
                       
                         φ 
                         tk 
                         s 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                         
                             
                         
                          
                         
                           
                             ∑ 
                             
                               t 
                               = 
                               1 
                             
                             T 
                           
                            
                           
                             w 
                             t 
                           
                         
                       
                       ≤ 
                       1 
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               
                                 m 
                                  
                                 
                                     
                                 
                                  
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 n 
                                  
                                 
                                   { 
                                   
                                     
                                       t 
                                       + 
                                       L 
                                       - 
                                       1 
                                     
                                     , 
                                     T 
                                   
                                   } 
                                 
                               
                             
                             T 
                           
                            
                           
                              
                             tk 
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               K 
                               = 
                               L 
                             
                             
                               t 
                               - 
                                
                               - 
                               1 
                             
                           
                            
                           
                             z 
                             
                               k 
                                
                               t 
                             
                           
                         
                       
                       = 
                       
                         w 
                         t 
                       
                     
                     , 
                     
                       ∀ 
                       
                         t 
                         ∈ 
                         
                           
                             [ 
                             
                               1 
                               , 
                               T 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             
                               t 
                               - 
                               L 
                               + 
                               1 
                             
                           
                            
                           
                              
                             
                               k 
                                
                               t 
                             
                           
                         
                         - 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               
                                 t 
                                 + 
                                  
                                 + 
                                 1 
                               
                             
                             T 
                           
                            
                           
                             z 
                             tk 
                           
                         
                       
                       = 
                       
                         θ 
                         t 
                       
                     
                     , 
                     
                       ∀ 
                       
                         t 
                         ∈ 
                         
                           
                             [ 
                             
                               L 
                               , 
                               
                                 T 
                                 - 
                                  
                                 - 
                                 1 
                               
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           C 
                           _ 
                         
                          
                         
                             
                         
                          
                         
                            
                           tk 
                         
                       
                       ≤ 
                       
                         q 
                         tk 
                         s 
                       
                       ≤ 
                       
                         
                           C 
                           ¯ 
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         s 
                         ∈ 
                         
                           
                             [ 
                             
                               t 
                               , 
                               k 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         tk 
                         ∈ 
                         TK 
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         q 
                         
                           t 
                            
                           k 
                         
                         k 
                       
                       ≤ 
                       
                         
                           V 
                           ¯ 
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         tk 
                         ∈ 
                         TK 
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         q 
                         tk 
                         k 
                       
                       ≤ 
                       
                         
                           V 
                           ¯ 
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         tk 
                         ∈ 
                         TK 
                       
                     
                     , 
                     
                       k 
                       ≤ 
                       
                         T 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           q 
                           tk 
                           
                             s 
                             - 
                             1 
                           
                         
                         - 
                         
                           q 
                           tk 
                           s 
                         
                       
                       ≤ 
                       
                         V 
                          
                         
                             
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         s 
                       
                        
                       
                         ∈ 
                         
                           
                             [ 
                             
                               
                                 t 
                                 + 
                                 1 
                               
                               , 
                               k 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         tk 
                         ∈ 
                         TK 
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           q 
                           tk 
                           s 
                         
                         - 
                         
                           q 
                           tk 
                           
                             s 
                             - 
                             1 
                           
                         
                       
                       ≤ 
                       
                         V 
                          
                         
                             
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         s 
                       
                        
                       
                         ∈ 
                         
                           
                             [ 
                             
                               
                                 t 
                                 + 
                                 1 
                               
                               , 
                               k 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                     
                       ∀ 
                       
                         
                           t 
                            
                           k 
                         
                         ∈ 
                         TK 
                       
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           φ 
                           tk 
                           s 
                         
                         - 
                         
                           
                             m 
                             j 
                           
                            
                           
                             q 
                             tk 
                             s 
                           
                         
                       
                       ≥ 
                       
                         
                           n 
                           j 
                         
                          
                         
                             
                         
                          
                         
                            
                           tk 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         s 
                       
                        
                       
                         ∈ 
                         
                           
                             [ 
                             
                               t 
                               , 
                               k 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         j 
                       
                        
                       
                         ∈ 
                         
                           
                             [ 
                             
                               1 
                               , 
                               N 
                             
                             ] 
                           
                           ℤ 
                         
                       
                     
                     , 
                     
                       
                         ∀ 
                         tk 
                       
                       , 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     w 
                     , 
                     θ 
                     , 
                     y 
                     , 
                     
                       z 
                       ≥ 
                       0 
                     
                     , 
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     where TK represents the set of all possible combinations of each t∈[1, T] Z  and each k∈[min{t+L−1, T}, T] Z  to construct a time interval [t, k] Z , g + (s) represents the start-up cost when the generator has been down for s time units (with parameter s 0  being the initial down time for the generator), g − (s) represents the shut-down cost when the generator has been up for s time units. Constraints (2) to (4) keep track of the “on” and “off” statuses of the unit. 
     Constraints (5) represent the generation upper and lower bounds. Constraints (6) and (7) represent the start-up and shut-down ramping restrictions. Constraints (8) and (9) represent the ramp-up and ramp-down restrictions. Constraints (10) represent the piecewise linear approximation of the general convex function ƒ tk   s (q tk   s ). 
     Remark 1: 
     The above constraints (2) to (4) form a network flow formulation without the redundant constraint (i.e., Σ t  θ t ≤1). If the generator has to be down at the end of time period T, then we only need to restrict w t =0 for t=T−L+2, . . . , T. If the generator is originally on, then this model can be updated by adding an additional variable w 0 , updating constraint (2) to Σ t=1   T  w t +w 0 ≤1, and setting w 0 =1. Meanwhile, the following are added: 
     1. Let y 0t , t=t 0 , t 0 +1, . . . T, where t 0 =max{L−s 0   − , 0}; with s 0   −  being the initial on time, represent the first on interval. 
     2. Add constraint w 0 =Σ t=t     0     T y 0t . 
     3. Add the term y 0t  to the left side of constraint (4). 
     4. Update constraints (5)-(11) to include the terms corresponding to y 0t . 
     5. Add the shut down and generation cost terms corresponding to y 0t  in the objective function. 
     Note here that this model is more general and captures the case when initially the generator is off, by simply setting w 0 =0. 
     Remark 2: 
     The reserve component can be included in constraints (5) to (9). 
     For notation brevity in the next section, the feasible region describing constraints (2) to (11) is defined as set X 1 . That is, X 1 ={(w, Ø, θ, y, z, q): Constraints (2)-(11)}. In general, network flow formulations with general convex cost functions cannot guarantee an integral solution. However, due to the problem structure, it is shown in [5] that the NUC formulation can provide an integral solution as stated below, based on the strong duality proof, i.e., the NUC formulation is the dual formulation of a revised dynamic programming formulation. 
     Theorem 1: 
     If the general cost function ƒ tk   s (q tk   s ) is convex, then the NUC formulation provides at least one integral optimal solution for UC and the same optimal objective value as that of the corresponding mixed-integer programming formulation. 
     II. Uplift Payment Minimization 
     The following describes the uplift payment minimization formulation and shows how the calculation of the uplift payment minimization problem can be implemented through solving a linear programming problem. The system optimization problem for a T-period UC problem (with A representing the set of generators) without considering transmission constraints run by an ISO can be abstracted as follows: 
     
       
         
           
             
               
                 
                   
                     Z 
                     QIP 
                     * 
                   
                   = 
                   
                     
                       min 
                       
                         
                           w 
                           j 
                         
                         , 
                         
                           φ 
                           j 
                         
                         , 
                         
                           θ 
                           j 
                         
                         , 
                         
                            
                           j 
                         
                         , 
                         
                           z 
                           j 
                         
                         , 
                         
                           q 
                           j 
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           Λ 
                         
                       
                        
                       
                         
                           g 
                           j 
                         
                          
                         
                           ( 
                           
                             
                               w 
                               j 
                             
                             , 
                             
                               φ 
                               j 
                             
                             , 
                             
                               θ 
                               j 
                             
                             , 
                             
                                
                               j 
                             
                             , 
                             
                               z 
                               j 
                             
                             , 
                             
                               q 
                               j 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           Λ 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             
                               t 
                                
                               k 
                             
                             ∈ 
                             
                               T 
                                
                               K 
                             
                           
                         
                          
                         
                           q 
                           
                             t 
                              
                             k 
                           
                           j 
                         
                       
                     
                   
                   = 
                   d 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ( 
                       
                         
                           w 
                           j 
                         
                         , 
                         
                             
                         
                          
                         
                           φ 
                           j 
                         
                         , 
                         
                             
                         
                          
                         
                           θ 
                           j 
                         
                         , 
                         
                            
                           j 
                         
                         , 
                         
                           z 
                           j 
                         
                         , 
                         
                           q 
                           j 
                         
                       
                       ) 
                     
                     ∈ 
                     
                       X 
                       I 
                       j 
                     
                   
                   , 
                   
                     ∀ 
                     
                       j 
                       ∈ 
                       Λ 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     
                        
                       j 
                     
                      
                     
                         
                     
                      
                     and 
                      
                     
                         
                     
                      
                     
                       z 
                       j 
                     
                      
                     
                         
                     
                      
                     are 
                      
                     
                         
                     
                      
                     binary 
                   
                   , 
                   
                     ∀ 
                     
                       j 
                       ∈ 
                       Λ 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     where X l   j  is the feasible region for generator j as shown above. Let Z QP * be the optimal objective value of the above formulation without the binary restriction constraints (15). It is easy to observe that Z QIP *≥Z QP * because the latter is the objective value of a relaxed problem. Now consider the profit maximization problem of each generator. For a given price vector π offered by the ISO, the profit maximization problem for each generator can be described as follows: 
     
       
         
           
             
               
                 
                   
                     
                       v 
                       j 
                     
                      
                     
                       ( 
                       π 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         max 
                         
                           
                             
                               w 
                               
                                 j 
                                 , 
                               
                             
                              
                             
                               φ 
                               
                                 j 
                                 , 
                               
                             
                              
                             
                               θ 
                               
                                 j 
                                 , 
                               
                             
                              
                             
                                
                               j 
                             
                           
                           , 
                           
                             z 
                             j 
                           
                           , 
                           
                             q 
                             j 
                           
                         
                       
                        
                       
                         
                           π 
                           T 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 t 
                                  
                                 k 
                               
                               ∈ 
                               
                                 T 
                                  
                                 K 
                               
                             
                           
                            
                           
                             q 
                             
                               t 
                                
                               k 
                             
                             j 
                           
                         
                       
                     
                     - 
                     
                       
                         g 
                         j 
                       
                        
                       
                         ( 
                         
                           
                             w 
                             j 
                           
                           , 
                           
                             φ 
                             j 
                           
                           , 
                           
                             θ 
                             j 
                           
                           , 
                           
                              
                             j 
                           
                           , 
                           
                             z 
                             j 
                           
                           , 
                           
                             q 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                      
                     
                       ( 
                       
                         
                           w 
                           j 
                         
                         , 
                         
                           φ 
                           j 
                         
                         , 
                         
                           θ 
                           j 
                         
                         , 
                         
                            
                           j 
                         
                         , 
                         
                           z 
                           j 
                         
                         , 
                         
                           q 
                           j 
                         
                       
                       ) 
                     
                   
                   ∈ 
                   
                     
                        
                       l 
                       j 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
             
               
                 
                   
                     y 
                     j 
                   
                    
                   
                       
                   
                    
                   and 
                    
                   
                       
                   
                    
                   
                     z 
                     j 
                   
                    
                   
                       
                   
                    
                   are 
                    
                   
                       
                   
                    
                   binary 
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
     On the other hand, the profit generator j can obtain following the ISO&#39;s schedule is equal to π T  Σ tk∈TK    q   tk   j −g j ( w   j ,  Ø   j ,  θ   j ,  y   j ,  z   j ,  q   j ), defined as  v   j (π) where ( w   j ,  Ø   j ,  θ   j ,  y   j ,  z   j ,  q   j ) is an optimal solution for generator j in the system optimization problem corresponding to Z QIP *. 
     Since v j (π) is no smaller than  v   j (π), there is a lost opportunity cost (LOC) of each generator following the ISO for each generator. Uplift payment is triggered as described in [1] and [2] and can be represented in the following form: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           U 
                           j 
                         
                          
                         
                           ( 
                           
                             π 
                             , 
                             
                               
                                 w 
                                 _ 
                               
                               j 
                             
                             , 
                             
                               
                                 φ 
                                 _ 
                               
                               j 
                             
                             , 
                             
                               
                                 θ 
                                 _ 
                               
                               j 
                             
                             , 
                             
                               
                                  
                                 _ 
                               
                               j 
                             
                             , 
                             
                               
                                 z 
                                 _ 
                               
                               j 
                             
                             , 
                             
                               
                                 q 
                                 _ 
                               
                               j 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         
                           
                             v 
                             j 
                           
                            
                           
                             ( 
                             π 
                             ) 
                           
                         
                         - 
                         
                           
                             π 
                             T 
                           
                            
                           
                             
                               ∑ 
                               
                                 
                                   t 
                                    
                                   k 
                                 
                                 ∈ 
                                 
                                   T 
                                    
                                   K 
                                 
                               
                             
                              
                             
                               
                                 q 
                                 ¯ 
                               
                               
                                 t 
                                  
                                 k 
                               
                               j 
                             
                           
                         
                         - 
                         
                           
                             g 
                             j 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   w 
                                   ¯ 
                                 
                                 j 
                               
                               , 
                               
                                 
                                   φ 
                                   ¯ 
                                 
                                 j 
                               
                               , 
                               
                                 
                                   θ 
                                   ¯ 
                                 
                                 j 
                               
                               , 
                               
                                 
                                   y 
                                   ¯ 
                                 
                                 j 
                               
                               , 
                               
                                 
                                   z 
                                   ¯ 
                                 
                                 j 
                               
                               , 
                               
                                 
                                   q 
                                   ¯ 
                                 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                     
                     ) 
                   
                   . 
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     To reduce the discrepancy, we need to find an optimal price π that minimizes the total uplift cost. That is, we want to 
     
       
         
           
             
               
                 
                   
                       
                   
                    
                   
                     
                       min 
                       π 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           Λ 
                         
                       
                        
                       
                         
                           U 
                           j 
                         
                          
                         
                           ( 
                           
                             π 
                             , 
                             
                               
                                 w 
                                 ¯ 
                               
                               j 
                             
                             , 
                             
                               
                                 φ 
                                 ¯ 
                               
                               j 
                             
                             , 
                             
                               
                                 θ 
                                 ¯ 
                               
                               j 
                             
                             , 
                             
                               
                                 y 
                                 ¯ 
                               
                               j 
                             
                             , 
                             
                               
                                 z 
                                 ¯ 
                               
                               j 
                             
                             , 
                             
                               
                                 q 
                                 ¯ 
                               
                               j 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
             
               
                 
                   = 
                   
                     
                       min 
                       π 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           Λ 
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               v 
                               j 
                             
                              
                             
                               ( 
                               π 
                               ) 
                             
                           
                           - 
                           
                             ( 
                             
                               
                                 
                                   π 
                                   T 
                                 
                                  
                                 
                                   
                                     ∑ 
                                     
                                       
                                         t 
                                          
                                         k 
                                       
                                       ∈ 
                                       
                                         T 
                                          
                                         K 
                                       
                                     
                                   
                                    
                                   
                                     
                                       q 
                                       ¯ 
                                     
                                     
                                       t 
                                        
                                       k 
                                     
                                     j 
                                   
                                 
                               
                               - 
                               
                                 
                                   g 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         w 
                                         ¯ 
                                       
                                       j 
                                     
                                     , 
                                     
                                       
                                         φ 
                                         ¯ 
                                       
                                       j 
                                     
                                     , 
                                     
                                       
                                         θ 
                                         ¯ 
                                       
                                       j 
                                     
                                     , 
                                     
                                       
                                         y 
                                         ¯ 
                                       
                                       j 
                                     
                                     , 
                                     
                                       
                                         z 
                                         ¯ 
                                       
                                       j 
                                     
                                     , 
                                     
                                       
                                         q 
                                         ¯ 
                                       
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     = 
                     
                       
                         
                           min 
                           π 
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               ∈ 
                               Λ 
                             
                           
                            
                           
                             
                               g 
                               j 
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     w 
                                     ¯ 
                                   
                                   j 
                                 
                                 , 
                                 
                                   
                                     φ 
                                     ¯ 
                                   
                                   j 
                                 
                                 , 
                                 
                                   
                                     θ 
                                     ¯ 
                                   
                                   j 
                                 
                                 , 
                                 
                                   
                                     y 
                                     ¯ 
                                   
                                   j 
                                 
                                 , 
                                 
                                   
                                     z 
                                     ¯ 
                                   
                                   j 
                                 
                                 , 
                                 
                                   
                                     q 
                                     ¯ 
                                   
                                   j 
                                 
                               
                               ) 
                             
                           
                         
                       
                       - 
                       
                         ( 
                         
                           
                             
                               π 
                               T 
                             
                              
                             d 
                           
                           - 
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 Λ 
                               
                             
                              
                             
                               
                                 v 
                                 j 
                               
                                
                               
                                 ( 
                                 π 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
         
         
           
             where (21) follows from (19) and (22) follows from (13). The above (22) is equivalent to solving the following maximization problem, since Σ j∈Λ g j ( w   j ,  ϕ   j ,  θ   j ,  y   j ,  z   j ,  q   j ) is a fixed value (the total generation cost for the system), as indicated in [1]: 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           max 
                           π 
                         
                          
                         
                           
                             π 
                             T 
                           
                            
                           d 
                         
                       
                       - 
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             Λ 
                           
                         
                          
                         
                           
                             v 
                             j 
                           
                            
                           
                             ( 
                             π 
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         
                           max 
                           π 
                         
                          
                         
                           
                             π 
                             T 
                           
                            
                           d 
                         
                       
                       - 
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             Λ 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 max 
                                 
                                   ( 
                                   
                                     
                                       w 
                                       j 
                                     
                                     , 
                                     
                                       φ 
                                       j 
                                     
                                     , 
                                     
                                       θ 
                                       j 
                                     
                                     , 
                                     
                                       y 
                                       j 
                                     
                                     , 
                                     
                                       z 
                                       j 
                                     
                                     , 
                                     
                                       q 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   π 
                                   T 
                                 
                                  
                                 
                                   
                                     ∑ 
                                     
                                       
                                         t 
                                          
                                         k 
                                       
                                       ∈ 
                                       
                                         T 
                                          
                                         K 
                                       
                                     
                                   
                                    
                                   
                                     q 
                                     
                                       t 
                                        
                                       k 
                                     
                                     j 
                                   
                                 
                               
                             
                             - 
                             
                               
                                 g 
                                 j 
                               
                                
                               
                                 ( 
                                 
                                   
                                     w 
                                     j 
                                   
                                   , 
                                   
                                     φ 
                                     j 
                                   
                                   , 
                                   
                                       
                                   
                                    
                                   
                                     θ 
                                     j 
                                   
                                   , 
                                   
                                     y 
                                     j 
                                   
                                   , 
                                   
                                     z 
                                     j 
                                   
                                   , 
                                   
                                     q 
                                     j 
                                   
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                       
                   
                    
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         ( 
                         
                           
                             w 
                             j 
                           
                           , 
                           
                             φ 
                             j 
                           
                           , 
                           
                               
                           
                            
                           
                             θ 
                             j 
                           
                           , 
                           
                             y 
                             j 
                           
                           , 
                           
                             z 
                             j 
                           
                           , 
                           
                             q 
                             j 
                           
                         
                         ) 
                       
                     
                     ∈ 
                     
                       
                          
                         l 
                         j 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       y 
                       j 
                     
                      
                     
                         
                     
                      
                     and 
                      
                     
                         
                     
                      
                     
                       z 
                       j 
                     
                      
                     
                         
                     
                      
                     are 
                      
                     
                         
                     
                      
                     
                       binary 
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         max 
                         π 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             Λ 
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 min 
                                 
                                   ( 
                                   
                                     
                                       w 
                                       j 
                                     
                                     , 
                                     
                                       φ 
                                       j 
                                     
                                     , 
                                     
                                       θ 
                                       j 
                                     
                                     , 
                                     
                                       y 
                                       j 
                                     
                                     , 
                                     
                                       z 
                                       j 
                                     
                                     , 
                                     
                                       q 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   g 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       w 
                                       j 
                                     
                                     , 
                                     
                                       φ 
                                       j 
                                     
                                     , 
                                     
                                       θ 
                                       j 
                                     
                                     , 
                                     
                                       y 
                                       j 
                                     
                                     , 
                                     
                                       z 
                                       j 
                                     
                                     , 
                                     
                                       q 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                             
                             - 
                             
                               
                                 π 
                                 T 
                               
                                
                               
                                 
                                   ∑ 
                                   
                                     
                                       t 
                                        
                                       k 
                                     
                                     ∈ 
                                     
                                       T 
                                        
                                       K 
                                     
                                   
                                 
                                  
                                 
                                   q 
                                   
                                     t 
                                      
                                     k 
                                   
                                   j 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         π 
                         T 
                       
                        
                       d 
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                        
                       
                         ( 
                         
                           
                             w 
                             j 
                           
                           , 
                           
                             φ 
                             j 
                           
                           , 
                           
                             θ 
                             j 
                           
                           , 
                           
                             y 
                             j 
                           
                           , 
                           
                             z 
                             j 
                           
                           , 
                           
                             q 
                             j 
                           
                         
                         ) 
                       
                     
                     ∈ 
                     
                       
                          
                         l 
                         j 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       y 
                       j 
                     
                      
                     
                         
                     
                      
                     and 
                      
                     
                         
                     
                      
                     
                       z 
                       j 
                     
                      
                     
                         
                     
                      
                     are 
                      
                     
                         
                     
                      
                     
                       binary 
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
     It is easy to observe that model (25)-(27) is essentially the Lagrangian relaxation of the original problem (12)-(15) to obtain Z QIP * and the corresponding optimal value π, i.e., π*, is the optimal convex hull price. 
     Based on Theorem 1, it can be concluded that constraints (18), (24), and (27) can be relaxed. Thus, since (12)-(14) is a linear program and (25)-(26) is a Lagrangian relaxation of (12)-(14), due to strong duality theorem, the linear program (12)-(14) can be solved and the optimal convex hull price π* is equal to the dual value corresponding to the load balance constraints (13). This main conclusion is highlighted in the following theorem. 
     Theorem 2: 
     If the general cost function ƒ tk   s (q tk   s ) is convex, then the optimal convex hull price can be obtained by solving the linear program (12)-(14), in which ƒ tk   s (q tk   s ) is approximated by a piecewise linear function and the optimal convex hull price is equal to the dual values corresponding to the load balance constraints (13). 
     III. An Example 
     Let T=3 with d 1 =70 MW, d 2 =80 MW, and d 3 =90 MW. There are two generators (G1 and G2) in the system. For G1, there are no start-up cost and binary decisions. The generation bounds are  C   1 =0 and  C   1 =40 MW. The unit generation cost in each time period is c 1 =$4/MWh; c 2 =$5/MWh, and c 3 =$5/MWh. For G2, we have  C   2 =20 MW,  C   2 =100 MW,  V   2 =55 MW/h, V 2 =5 MW/h and L 2 =l 2 =2. The start-up cost for G2 is $100. The convex generation cost for G2 is approximated by a two-piece piecewise linear function (e.g., ϕ tk   s ≥100y tk +q tk   s  and ϕ tk   s ≥370 y tk −q tk   s ). The corresponding system optimization problem using the traditional 2-Bin UC model is as follows: 
       min 4 x   1   1 +5 x   1   1 +5 x   3   1 +100( u   1   2   +u   2   2   +u   3   2 )+ϕ 1 +ϕ 2 +ϕ 3  
 
         s.t. x   i   1   +x   1   2   =d   i   ,x   i   1 ≤40,20 i   2   ≤x   1   2 ≤100 y   i   2   ,i= 1,2,3
 
     
       
      
       u 
       1 
       2 
       ≤y 
       1 
       2 
       ,u 
       1 
       2 
       +u 
       2 
       2 
       ≤y 
       2 
       2 
       ,u 
       2 
       2 
       +u 
       3 
       2 
       ≤y 
       3 
       2  
      
     
         y   i   2   −y   i-1   2   ≤u   i   2   ,i= 1,2,3 
         x   1   2 ≤55 u   1   2   ,x   i   2   −x   i-1   2 ≤5 y   i-1   2 +55(1− y   i-1   2 ), i= 2,3
 
         x   i-1   2   −x   i   2 ≤5 y   i   1 +100(1− y   i   2 ), i= 2,3
 
       ϕ i ≤100 y   i   2   +x   i   2 ,ϕ i ≥370 y   i   2   −x   i   2   ,i= 1,2,3
 
         x   i   1 ≥0; y   i   2  and  u   i   2  binary, i= 1,2,3
 
     We have Z QIP *=$1315 with the optimal solution  x   1   1= 15,  x   2   1 =20,  x   3   1 =25,  x   1   2 =55,  x   2   2 =60,  x   3   2 =65 for both the 2-Bin and NUC mixed integer linear programming (MILP) formulations. The corresponding LMPs are π 1   1 =4, π 2   1 =5, and π 3   1 =5 (the optimal dual values corresponding to the load balance constraints in solving the economic dispatch problem when the unit commitment is fixed). Meanwhile, we have Z QP   2B =$940 (the optimal objective value for the 2-Bin LP relaxation model) with the corresponding dual values π 1   2 =5.459, π 2   2 =5, and π 3   2 =5 and Z QP *=$1267.27 with the corresponding dual values π 1   3 =4.41, π 2   3 =5, and π 3   3 =7.5 (the corresponding nonzero fractional solution is x 1   1 =40, x 2   1 =34, x 3   1 =40, q 13   1 =30, q 13   2 =32.7, q 13   3 =35.5, q 23   2 =13.3, q 23   3 =14.5, y 13 =0.545, y 23 =0.242). Using π 1 , π 2 , and π 3  as the input for (25)-(26), combining (22), we can obtain the uplift payments to be $185, $141.23, and $47.75, respectively, which shows that the convex hull price provided by the NUC formulation leads to the smallest uplift payment and further, we need to solve a linear program to achieve this. 
     IV. Market Clearing Process 
     An exemplary market clearing process is shown in  FIG. 2 . As shown in Step  30 , a controller  10  receives offers  18  and bids  20  from market participants. Input may also include the network model from the grid and other inputs. As shown in Step  32 , the controller  10  may then formulate unit commitment problem Z QIP *, solving with a Mixed Integer Programming solver and then publishes unit commitment results. As shown in Step  34 , the controller  10  then uses the same setoff inputs to formulate pricing problem Z QP * for convex hull pricing with Linear Programming solver. The controller  10  then publishes market clearing prices. 
     The following references are incorporated herein by reference:
     [1] P. Gribik, W. Hogan, and S. Pope, “Market-clearing electricity prices and energy uplift,” Cambridge, Mass., 2007.   [2] B. Hua and R. Baldick, “A convex primal formulation for convex hull pricing,”  IEEE Transactions on Power Systems , vol. 32, no. 5, pp. 3814-3823, 2017.   [3] D. A. Schiro, T. Zheng, F. Zhao, and E. Litvinov, “Convex hull pricing in electricity markets: Formulation, analysis, and implementation challenges,”  IEEE Transactions on Power Systems , vol. 31, no. 5, pp. 4068-4075, 2016.   [4] C. Wang, P. B. Luh, P. Gribik, T. Peng, and L. Zhang, “Commitment cost allocation of fast-start units for approximate extended locational marginal prices,”  IEEE Transactions on Power Systems , vol. 31, no. 6, pp. 4176-4184, 2016.   [5] Y. Guan, K. Pan, and K. Zhou, “Polynomial time algorithms and extended formulations for unit commitment problems,”  IISE Transactions , vol. 50, no. 8, pp. 735-751, 2018 (first available at https://arxiv.org/abs/1608.00042 in July 2016).