# Patent

## Title
Solving large-scale security-constrained economic dispatch problem in real-time

## Abstract

A system, a method and a computer program product for determining an amount of an electric power to be generated in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request. The system creates an optimization problem for calculating amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint. The system runs the optimization problem in real-time. The system outputs, from the optimization problem, an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.

## Background
RELATED APPLICATIONS
This application is a continuation application of U.S. application Ser. No. 13/183,865, filed Jul. 15, 2011.


BACKGROUND
The present application generally relates to dispatching energy, e.g., an electric power. More particularly, the present application relates to determining an amount of electric power to be generated and their cost to generate while meeting at least one contingency constraint and one or more customer requests.
Electricity markets in the United States are comprised of two interconnected markets: a day ahead market and a real-time or balancing market. The day-ahead market focuses on an electricity power generation schedule per an electric power generator. The real-time market focuses on economic dispatch, i.e., determining an output of an electric power generator and its cost to generate the electric power.
Currently, linear direct current (DC) approximation of a (nonlinear, non-convex) AC (Alternating Current) power flow equation is mostly used in the existing electric power generation systems. A reference to P. N. Biskas and A. G. Bakirtzis, entitled “A decentralized solution to the security constrained DC-OPF problem of multi-area power systems,” Power Tech, 2005 IEEE Russia, pp. 1-7, June 2005, wholly incorporated by reference as if set forth herein, describes the linear direct current approximation of the AC power flow equation in detail. A main drawback of the linear DC approximation is that it does not capture a physical electric power flow more realistically than the AC power flow equation. Currently, solving the AC power flow equation without the linear DC approximation requires large amount of memory usage (e.g., more than one Terabyte, etc.) and cannot be performed in real-time. Currently, the solution of the AC optimal power flow problem is usually a low quality, i.e., far from an optimal solution (i.e., optimality referring to ideal amount of electric power to be generated at an ideal cost to generate the ideal amount of electric power). The linear DC approximation requires trials and errors to ensure a feasibility of its solution and does not provide an optimal solution.
SUMMARY OF THE INVENTION
The present disclosure describes a system, method and computer program product for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request.
In one embodiment, there is provided a system for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request. The system includes, but is not limited to: at least one memory device and at least one processor connected to the memory device. The system is configured to create an optimization problem for calculating an amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint and the one or more customer request. The contingency constraint includes one or more of: a transmission line failure, a power generator failure, a transformer failure, a structure of a power distribution network, and a topology of the power distribution network. The system is configured to run the optimization problem in real-time. The system is configured to output, from the optimization problem, an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.
In a further embodiment, to run the optimization problem, the system is configured to solve the optimization problem without considering the at least one contingency constraint. The system is configured to check whether a result of the computed optimization problem satisfies the at least one contingency constraint. The system is configured to output the result in response to determining that the result satisfies the at least one contingency constraint. The system is configured to prune, in response to determining that the result does not satisfy the at least one contingency constraint, one or more results of the optimization problem that do not satisfy the at least one contingency constraint. The system is configured to solve the optimization problem with the pruned results.
In a further embodiment, to run the optimization problem, the system is configured to generate a template to solve the optimization problem. The system is configured to reformulate the optimization problem based on the generated template. The system is configured to form an augmented Lagrangian for the reformulated optimization problem. The system is configured to initialize Lagrangian multipliers and decision variables according to the at least one contingency constraint. The system is configured to solve the reformulated optimization problem with the initialized Lagrangian multipliers and decision variables, based on an alternating direction method of multipliers.
In a further embodiment, the system is further configured to break the reformulated optimization problem into one or more sub-problems. The system is configured to solve the one or more sub-problems with the initialized Lagrangian multipliers and decision variables, based on the formed augmented Lagrangian. The system is configured to evaluate whether a solution of the one or more sub-problems meets a stopping criterion. The system is configured to output the solution in response to determining that the solution meets the stopping criterion. The system is configured to update the Lagrangian multipliers based on the solution, in response to determining that the solution does not meet the stopping criterion.
In a further embodiment, to run the optimization problem, the system is configured to build a tree data structure. Each node of the tree data structure describes a possible solution of the optimization problem. The system is configured to compute, at each node of the built tree data structure, an upper bound and lower bound of an objective function. The objective function determines the cost for generating the electric power. The lower bound is calculated from Lagrange duality. The upper bound is calculated from an interior-point method. The system is configured to evaluate, at each node of the built tree data structure, whether the computed upper bound and computed lower bound satisfy a stopping criterion. The system is configured to output the computed upper bound and the computed lower bound in response to determining that the computed upper bound and computed lower bound satisfy the stopping criterion. The system is configured to apply at least one branching procedure on the tree data structure in response to determining that the computed upper bound and computed lower bound do not satisfy the stopping criteria. The system is configured to re-compute the lower bound in a region in the tree data structure branched according to the applied branching procedure. The system is configured to update the upper bound in the region in the tree data structure. The system is configured to delete nodes in the region based on the re-computed the lower bound and updated upper bound or an intersection of the branched region and an original feasible set. The original feasible set refers to possible solutions of the optimization problem satisfying the at least one contingency constraint. The system is configured to repeat the evaluating, the outputting, the applying, the re-computing, the updating, and the deleting.
In a further embodiment, the stopping criterion includes one or more of: a gap between the smallest computed lower bound and the computed upper bound is lower than a pre-determined threshold, or the tree data structure is empty.
In a further embodiment, the one or more customer request includes: a demand or load for a certain amount of the electric power.



BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings are included to provide a further understanding of the present invention, and are incorporated in and constitute a part of this specification.
FIG. 1 is a flow chart that describes method steps for solving an optimization problem that calculates an amount of electric power to be generated and a total cost for generating the calculated amount while meeting at least one contingency constraint and one or more customer request in one embodiment.
FIG. 2 is another flow chart that describes method steps for solving an optimization problem that calculates an amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting at least one contingency constraint and the one or more customer request in another embodiment.
FIG. 3 is another flow chart that describes method steps for solving an optimization problem that calculates amount of electric power to be generated and a total cost for generating the calculated amount electric power while meeting at least one contingency constraint and the one or more customer request in another embodiment.
FIG. 4 illustrates an exemplary hardware configuration for implementing the flow charts depicted in FIGS. 1-3 in one embodiment.
FIG. 5 is a flow chart for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request in one embodiment.



DETAILED DESCRIPTION
In this disclosure, there are provided a method, a system and a computer program product for solving an AC (Alternative Current) electric optimal power flow problem (e.g., problem (1) described below) in real-time to generate an optimal solution. The optimal solution specifies an ideal amount of electric power to be generated and a cost for generating the ideal amount of the electric power while satisfying at least one contingency constraint and one or more customer request. The contingency constraint includes one or more of: a transmission line failure, a power generator failure, a transformer failure, a structure of a power distribution network, and a topology of the power distribution network. The one or more customer request comprises: a demand or load for a certain amount of an electric power, etc. In one embodiment, the customer request, e.g., the demand, is incorporated in the definitions of functions h, and g, in problem (1) described below.
In one embodiment, to solve the AC electric optimal power flow problem, a computing system (e.g., a computing system 400 shown in FIG. 4) is configured to apply method steps described in FIG. 1 or FIG. 2 or FIG. 3 on the AC electric optimal power flow problem. Method steps described in FIGS. 1-2 are heuristics that generate sub-optimal solutions of the AC electric optimal power flow problem. Method steps described in FIG. 3 generate the optimal solution of the AC electric optimal power flow problem. Benefits of these method steps described in FIGS. 1-3 include, but are not limited to: (1) these method steps can handle a nonlinear non-convex optimization problem (e.g., AC electric optimal power flow problem), which outputs a result that specifies one or more of: (a) amount of electric power to be generated to satisfy the contingency constraint and customers' requests; and (b) a lowest cost to generate the amount of the electric power; (2) The computing system 400 or any traditional computing system can run these method steps in FIGS. 1-3 in real-time; (3) The computing system 400 or traditional computing system can run method steps in FIG. 1 and/or FIG. 2 and/or FIG. 3 in parallel to improve running time of these method steps; and (4) The output from method steps in FIG. 3 can be used to determine quality of outputs of method steps in FIGS. 1-2 because the output from the method steps in FIG. 3 provides the optimal solution of the AC electric optimal power flow problem.
In another embodiment, to solve the AC electric optimal power flow problem, the computing system 400 is configured to utilize one or more of: Benders decomposition algorithm, Alternating direction method of multipliers, and Branch-and-bound algorithm. A reference to A. M. Geoffrion, “Generalized Benders decomposition,” Journal of Optimization Theory and Applications, vol. 10, no. 4, 1972, wholly incorporated by reference as set forth herein, describes Benders decomposition algorithm in detail. A reference to N. Parikh, et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Jan. 27, 2011, wholly incorporated by reference as set forth herein, describes alternating direction method of multipliers in detail. A reference to Leo Liberti, “Introduction to global optimization,” Lix, Ecole Polytechnique, Feb. 15, 2008, wholly incorporated by reference as set forth herein, describes Branch-and-bound algorithm in detail.
By solving the AC electric optimal power flow problem, e.g., by running the method steps in FIG. 1 or FIG. 2 or FIG. 3, the computing system 400 solves a security-constrained economic dispatch problem (i.e., determining an amount of electric power to be generated under a constraint) because the output of the method steps in FIG. 1 or FIG. 2 or FIG. 3 specifies an amount of electric power to be generated per an electric power generator and a cost to operate the generator and a cost to generate the electric power under the contingency constraint. By running method steps in FIG. 1 or FIG. 2 or FIG. 3, an electric power company (e.g., Con Edison®, etc.) can provide electric power reliably to all of its customers even though there exists an occurrence of a transmission line failure, an electric power generator failure or a transformer failure.
The AC electric optimal power flow problem can be formulated as follows:




  
    
      
        
          min
          ⁢
          
            
          
          ⁢
          
            f
            ⁡
            
              (
              
                u
                0
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            s
            .
            t
            .
            
              

            
            ⁢
            
              
                h
                c
              
              ⁡
              
                (
                
                  
                    x
                    c
                  
                  ,
                  
                    u
                    c
                  
                
                )
              
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              g
              c
            
            ⁡
            
              (
              
                
                  x
                  c
                
                ,
                
                  u
                  c
                
              
              )
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              
              
                
                  u
                  c
                  i
                
                -
                
                  u
                  0
                  i
                
              
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                u
                i
                max
              
            
          
          ,
          
            

          
          ⁢
          
            i
            ∈
            G
          
          ,
          
            

          
          ⁢
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
          ,
        
      
    
    
      
        (
        1
        )
      
    
  




where c=0 represents an electric power system at a normal case (i.e., no occurrence of contingency constraint), c=1, . . . , C, is a variable representing a contingency constraint, xc is a vector of state variables (e.g., complex voltages) for a c-th configuration, uc is a vector of control variables (e.g., the active and reactive powers, etc.), a generation cost f(u0)=ΣiεG(c0i(u0i)2+c1iu0i+c2i) with cost parameters c0i, c1i, c2i≦0 (G is a set of generators), and C is the number of contingency constraints. Δuimax is a pre-determined maximal allowed variation of control variables, and hc and gc are operational constraints including AC power flow balance equations (e.g., P1+P2+P3=0, where P1 represents an electric power at an electric node “1,” P2 represents an electric power at an electric node “2,” P3 represents an electric power at an electric node “3.”). Note that the optimization problem (i.e., the problem (1)) allows control variables to be reinitialized in order to satisfy contingency constraints. The problem (1) is advantageously solved in real-time.

FIG. 5 is a flow chart that describes method steps for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request in one embodiment. At step 500, the computing system 400 is configured to create the optimization problem (e.g., the problem (1) described above) for calculating an amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint and the one or more customer request. At step 510, the computing system is configured to solve the optimization problem in real-time, e.g., by running the method steps in FIG. 1 or FIG. 2 or FIG. 3. The computing system is configured to output, from the optimization problem, an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.
By running method steps in FIG. 1, the computing system 400 is configured to decompose the optimization problem into a master problem (e.g., the problem (10) described below) and sub-problems (e.g., problems (5) and (6) described below). The computing system 400 is configured to check a feasibility of a solution of each sub-problem for the master problem. This feasibility check can be performed in parallel, e.g., by using two or more processors 411 in the computing system 400. Method steps in FIG. 1 can also solve the optimization problem even if the optimization problem is non-convex. By running method steps in FIG. 2, the computing system 400 is configured to improve quality of the solution from method steps in FIG. 1.
FIG. 1 is a flow chart that describes method steps for solving the optimization problem in one embodiment. At step 110, the computing system 400 is configured to compute the optimization problem without considering the contingency constraint. In one embodiment, the optimization problem (1) is expressed as a general nonlinear non-convex optimization problem:




  
    
      
        
          min
          ⁢
          
            
          
          ⁢
          
            f
            ⁡
            
              (
              x
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            s
            .
            t
            .
            
              

            
            ⁢
            x
          
          ∈
          X
        
        ⁢
        
          

        
        ⁢
        
          
            G
            ⁡
            
              (
              y
              )
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            H
            ⁡
            
              (
              y
              )
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            Ax
            +
            By
            +
            b
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              y
              L
            
            ≤
            y
            ≤
            
              y
              U
            
          
          ,
        
      
    
    
      
        (
        2
        )
      
    
  




where X⊂Pn and yεPm, A and B are matrices. In one embodiment, f is a convex function, whereas G, H and X are non-convex, b is a constant vector, yL is a lower bound of the variable y, and the yu is an upper bound of the variable y.

An initial master problem is of the problem (2) is as follows:




  
    
      
        
          min
          ⁢
          
            
          
          ⁢
          
            f
            ⁡
            
              (
              x
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          x
          ∈
          
            X
            .
          
        
      
    
    
      
        (
        3
        )
      
    
  




Let x be a solution of the initial master problem. Then, the computing system 400 is configured to check if the following subproblem is feasible

G(y)≦0

H(y)=0

A x+By+b≦0

yL≦y≦yU.  (4)

Note that each contingency constraint associated with each c in the problem (1) may be written in a form of problem (4).

Returning to FIG. 1, at step 120, the computing system is configured to check whether a result of the computed optimization problem (e.g., problem (3)) satisfies the contingency constraint described above, e.g., by running problem (4). Note that the optimization problem (1) can be compactly expressed as the problem (2). Each contingency constraint associated with c in the problem (1) can be expressed in the form of problem (4). So, checking the contingency constraint for each c is equivalent to evaluating the feasibility of the problem (4). In response to determining that the result satisfies the contingency constraint, the system is configured to output the result. In other words, if the equation (4) is feasible for the given x, at step 150, the computing system 400 terminates running the method steps in FIG. 1. Otherwise, at step 130, the computing system 400 is configured to prune, in response to determining that the result does not satisfy the contingency constraint, one or more results of the computed optimization problem (e.g., problem (3)) that do not satisfy the contingency constraint. To prune the one or more results, the computing system 400 is configured to generate a cut that is added to the initial master problem (e.g., problem (3)).
To check the feasibility of the problem (4) or generate the cut, the computing system is configured to solve, for the fixed x, a sub-problem




  
    
      
        
          
            min
            
              y
              ,
              
                α
                i
              
            
          
          ⁢
          
            
              ∑
              i
            
            ⁢
            
              α
              i
            
          
        
        ⁢
        
          

        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
          ⁢
          
            :
          
        
        ⁢
        
          

        
        ⁢
        
          
            G
            ⁡
            
              (
              y
              )
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            H
            ⁡
            
              (
              y
              )
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              A
              ⁢
              
                x
                _
              
            
            +
            By
            +
            b
            -
            α
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            y
            L
          
          ≤
          y
          ≤
          
            y
            U
          
        
        ⁢
        
          

        
        ⁢
        
          
            α
            ≥
            0
          
          ,
        
      
    
    
      
        (
        5
        )
      
    
  




where αi is a new slack variable.

Assume, in one embodiment, that an optimal result of the problem (5) is strictly positive, i.e., the problem (4) is infeasible, i.e., for the given x, there is no y satisfying constraints (4). Further in one embodiment, it is assumed that ( y, α) is an optimal solution of the problem (5). Then, by substituting z≈y−yL and using the Taylor expansions of G(y) and H(y) at y−yL, the computing system is configured to obtain a relaxed linear programming:




  
    
      
        
          
            min
            
              α
              ,
              z
            
          
          ⁢
          
            
              ∑
              i
            
            ⁢
            
              α
              i
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              G
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
            +
            
              
                
                  ∇
                  y
                
                ⁢
                
                  G
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
              
              ⁢
              
                (
                
                  z
                  -
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
                )
              
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              H
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
            +
            
              
                
                  ∇
                  y
                
                ⁢
                
                  H
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
              
              ⁢
              
                (
                
                  z
                  -
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
                )
              
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            Bz
            -
            α
            +
            
              A
              ⁢
              
                x
                _
              
            
            +
            b
            +
            
              By
              L
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          z
          ≤
          
            
              y
              U
            
            -
            
              y
              L
            
          
        
        ⁢
        
          

        
        ⁢
        
          α
          ,
          
            z
            ≥
            0.
          
        
      
    
    
      
        (
        6
        )
      
    
  




For a general optimization problem, the problem (5) can be still infeasible if the computing system is configured to introduce the auxiliary variable a for a constraint A x+By+b−α≦0. To construct a new optimization problem whose feasible set is definitely non-empty, the computing system is configured to consider constraints G(y)≦0 and H(y)=0. However, in an electric power system analysis, for α is large enough (e.g., larger than 1000, etc.), the problem (5) is feasible.
Assume that an optimal result of the problem (6) is strictly positive. The computing system 400 is configured to construct linear cuts (e.g., equations (7) and (8)-(9) below) based on Lagrange multipliers arising from the problems (5) or (6). Lagrange multipliers refer to a method that finds a maximum and a minimum of a function subject to constraints. Yan-Bin Jia, “Lagrange Multipliers,” Nov. 18, 2008, wholly incorporated by reference as if set forth herein, describes Lagrange multipliers in detail. Note that if the optimal result of the problem (6) is strictly positive, then (4) is infeasible, since the optimal result of the problem (6) is less than or equal to the optimal result of the problem (5).
In solving the optimization problem under one or more constraints, it is possible to convert the optimization problem (e.g., problem (6)) to a dual problem (e.g., Lagrangian dual problem, etc.). The Lagrangian dual problem is formulated by using Lagrangian multipliers to incorporate the constraints to an objective function. A reference to Eric P. Xing and Guang Xiang, entitled “Optimal Margin Principle and Lagrangian Duality,” 2007, Carnegie Mellon University, wholly incorporated by reference as if set forth herein, describes Lagrangian dual problem in detail.
The Lagrange dual problem of the problem (6) is as follows:



  
    
      
        
          
            max
            
              
                π
                ≥
                0
              
              ,
              
                μ
                ≥
                0
              
              ,
              η
            
          
          ⁢
          
            
              min
              
                
                  0
                  ≤
                  α
                
                
                  0
                  ≤
                  z
                  ≤
                  
                    
                      y
                      U
                    
                    -
                    
                      y
                      L
                    
                  
                
              
            
            ⁢
            
              
                ∑
                i
              
              ⁢
              
                
              
              ⁢
              
                α
                i
              
            
          
        
        +
        
          
            π
            T
          
          ⁡
          
            (
            
              Bz
              -
              α
              +
              
                A
                ⁢
                
                  x
                  _
                
              
              +
              
                By
                L
              
              +
              b
            
            )
          
        
        +
        
          
            η
            T
          
          ⁡
          
            (
            
              
                H
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
              +
              
                
                  
                    ∇
                    y
                  
                  ⁢
                  
                    H
                    ⁡
                    
                      (
                      
                        y
                        _
                      
                      )
                    
                  
                
                ⁢
                
                  (
                  
                    z
                    -
                    
                      (
                      
                        
                          y
                          _
                        
                        -
                        
                          y
                          L
                        
                      
                      )
                    
                  
                  )
                
              
            
            )
          
        
        +
        
          
            μ
            T
          
          ⁡
          
            (
            
              
                G
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
              +
              
                
                  
                    ∇
                    y
                  
                  ⁢
                  
                    G
                    ⁡
                    
                      (
                      
                        y
                        _
                      
                      )
                    
                  
                
                ⁢
                
                  (
                  
                    z
                    -
                    
                      (
                      
                        
                          y
                          _
                        
                        -
                        
                          y
                          L
                        
                      
                      )
                    
                  
                  )
                
              
            
            )
          
        
      
      =
      
        
          
            
              max
              
                
                  π
                  ≥
                  0
                
                ,
                
                  μ
                  ≥
                  0
                
                ,
                η
              
            
            ⁢
            
              
                min
                
                  
                    0
                    ≤
                    α
                  
                  
                    0
                    ≤
                    z
                    ≤
                    
                      
                        y
                        U
                      
                      -
                      
                        y
                        L
                      
                    
                  
                
              
              ⁢
              
                
                  ∑
                  i
                
                ⁢
                
                  
                
                ⁢
                
                  
                    α
                    i
                  
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        π
                        i
                      
                    
                    )
                  
                
              
            
          
          +
          
            
              
                (
                
                  
                    
                      B
                      T
                    
                    ⁢
                    π
                  
                  +
                  
                    
                      
                        ∇
                        y
                        T
                      
                      ⁢
                      
                        H
                        ⁡
                        
                          (
                          
                            y
                            _
                          
                          )
                        
                      
                    
                    ⁢
                    η
                  
                  +
                  
                    
                      
                        ∇
                        y
                        T
                      
                      ⁢
                      
                        G
                        ⁡
                        
                          (
                          
                            y
                            _
                          
                          )
                        
                      
                    
                    ⁢
                    μ
                  
                
                )
              
              T
            
            ⁢
            z
          
          +
          
            
              π
              T
            
            ⁡
            
              (
              
                
                  A
                  ⁢
                  
                    x
                    _
                  
                
                +
                
                  By
                  L
                
                +
                b
              
              )
            
          
          -
          
            
              η
              T
            
            ⁢
            
              
                ∇
                y
              
              ⁢
              
                H
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
            
            ⁢
            
              (
              
                
                  y
                  _
                
                -
                
                  y
                  L
                
              
              )
            
          
          +
          
            
              μ
              T
            
            ⁡
            
              (
              
                
                  G
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
                -
                
                  
                    
                      ∇
                      y
                    
                    ⁢
                    
                      G
                      ⁡
                      
                        (
                        
                          y
                          _
                        
                        )
                      
                    
                  
                  ⁢
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
              
              )
            
          
        
        =
        
          
            
              max
              
                
                  0
                  ≤
                  
                    π
                    i
                  
                  ≤
                  1
                
                ,
                
                  μ
                  ≥
                  0
                
              
            
            ⁢
            
              
                π
                T
              
              ⁡
              
                (
                
                  
                    A
                    ⁢
                    
                      x
                      _
                    
                  
                  +
                  
                    By
                    L
                  
                  +
                  b
                
                )
              
            
          
          -
          
            
              η
              T
            
            ⁢
            
              
                ∇
                y
              
              ⁢
              
                H
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
            
            ⁢
            
              (
              
                
                  y
                  _
                
                -
                
                  y
                  L
                
              
              )
            
          
          +
          
            
              μ
              T
            
            ⁡
            
              (
              
                
                  G
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
                -
                
                  
                    
                      ∇
                      y
                    
                    ⁢
                    
                      G
                      ⁡
                      
                        (
                        
                          y
                          _
                        
                        )
                      
                    
                  
                  ⁢
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
              
              )
            
          
          +
          
            
              ∑
              i
            
            ⁢
            
              
            
            ⁢
            
              
                l
                i
              
              ⁡
              
                (
                π
                )
              
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    where
  




  
    
      
        l
        i
      
      ⁡
      
        (
        π
        )
      
    
    =
    
      {
      
        
          
            0
          
          
            
              
                
                  if
                  ⁢
                  
                    
                  
                  [
                  
                    
                      
                        
                          
                            
                              B
                              T
                            
                            ⁢
                            π
                          
                          +
                          
                            
                              
                                ∇
                                y
                                T
                              
                              ⁢
                              
                                H
                                ⁡
                                
                                  (
                                  
                                    y
                                    _
                                  
                                  )
                                
                              
                            
                            ⁢
                            η
                          
                          +
                        
                      
                    
                    
                      
                        
                          
                            
                              ∇
                              y
                              T
                            
                            ⁢
                            
                              G
                              ⁡
                              
                                (
                                
                                  y
                                  _
                                
                                )
                              
                            
                          
                          ⁢
                          μ
                        
                      
                    
                  
                  ]
                
                i
              
              ≥
              0
            
          
        
        
          
            
              
                
                  
                    [
                    
                      
                        
                          
                            
                              
                                B
                                T
                              
                              ⁢
                              π
                            
                            +
                            
                              
                                
                                  ∇
                                  y
                                  T
                                
                                ⁢
                                
                                  H
                                  ⁡
                                  
                                    (
                                    
                                      y
                                      _
                                    
                                    )
                                  
                                
                              
                              ⁢
                              η
                            
                            +
                          
                        
                      
                      
                        
                          
                            
                              
                                ∇
                                y
                                T
                              
                              ⁢
                              
                                G
                                ⁡
                                
                                  (
                                  
                                    y
                                    _
                                  
                                  )
                                
                              
                            
                            ⁢
                            μ
                          
                        
                      
                    
                    ]
                  
                  i
                
                ⁡
                
                  [
                  
                    
                      y
                      U
                    
                    -
                    
                      y
                      L
                    
                  
                  ]
                
              
              i
            
          
          
            
              otherwise
              ,
            
          
        
      
    
  



and π, μ, η, and z, are new decision variables. Suppose that ( π, η, μ) is the optimal solution to the dual problem. By applying Lagrangian duality to the problem (6), the computing system 400 is configured to obtain





  
    
      
        
          π
          _
        
        T
      
      ⁡
      
        (
        
          
            A
            ⁢
            
              
            
            ⁢
            
              x
              _
            
          
          +
          
            By
            L
          
          +
          b
        
        )
      
    
    -
    
      
        
          η
          _
        
        T
      
      ⁢
      
        
          ∇
          y
        
        ⁢
        
          H
          ⁡
          
            (
            
              y
              _
            
            )
          
        
      
      ⁢
      
        (
        
          
            y
            _
          
          -
          
            y
            L
          
        
        )
      
    
    +
    
      
        
          μ
          _
        
        T
      
      ⁡
      
        (
        
          
            G
            ⁡
            
              (
              
                y
                _
              
              )
            
          
          -
          
            
              ∇
              y
            
            ⁢
            
              G
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
          
          -
          
            
              
                ∇
                y
              
              ⁢
              
                G
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
            
            ⁢
            
              (
              
                
                  y
                  _
                
                -
                
                  y
                  L
                
              
              )
            
          
        
        )
      
    
    +
    
      
        ∑
        i
      
      ⁢
      
        
          l
          i
        
        ⁡
        
          (
          
            π
            _
          
          )
        
      
    
  
  =
  
    
      ∑
      i
    
    ⁢
    
      
        α
        i
        *
      
      .
    
  




Note that Σili( π)≦0. Together with the strict positiveness of Σiαi*, it follows that

 πT(A x+ByL+b)− ηT∇yH( y)( y−yL)+ μT(G( y)−∇yG( y)( y−yL))>0.

Hence, the computing system 400 is configured to construct a first cut as follows:

 πT(A x+ByL+b)− ηT∇yH( y)( y−yL)+ μT(G( y)−∇yG( y)( y−yL)≦0,  (7)

which is an affine function of x. An affine function refers to a linear transformation using a matrix and a vector.

The computing system 400 can be configured to create another Lagrange dual problem for the problem (6) as follows:




  
    
      
        
          max
          
            π
            ,
            μ
            ,
            
              θ
              ≥
              0
            
            ,
            η
          
        
        ⁢
        
          
            min
            
              α
              ,
              
                z
                ≥
                0
              
            
          
          ⁢
          
            
              ∑
              i
            
            ⁢
            
              
            
            ⁢
            
              α
              i
            
          
        
      
      +
      
        
          π
          T
        
        ⁡
        
          (
          
            Bz
            -
            α
            +
            
              A
              ⁢
              
                x
                _
              
            
            +
            
              By
              L
            
            +
            b
          
          )
        
      
      +
      
        
          η
          T
        
        ⁡
        
          (
          
            
              H
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
            +
            
              
                
                  ∇
                  y
                
                ⁢
                
                  H
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
              
              ⁢
              
                (
                
                  z
                  -
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
                )
              
            
          
          )
        
      
      +
      
        
          μ
          T
        
        ⁡
        
          (
          
            
              G
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
            +
            
              
                
                  ∇
                  y
                
                ⁢
                
                  G
                  ⁡
                  
                    (
                    
                      y
                      _
                    
                    )
                  
                
              
              ⁢
              
                (
                
                  z
                  -
                  
                    (
                    
                      
                        y
                        _
                      
                      -
                      
                        y
                        L
                      
                    
                    )
                  
                
                )
              
            
          
          )
        
      
      +
      
        
          θ
          T
        
        ⁡
        
          (
          
            z
            -
            
              (
              
                
                  y
                  U
                
                -
                
                  y
                  L
                
              
              )
            
          
          )
        
      
    
    =
    
      
        
          
            max
            
              π
              ,
              μ
              ,
              
                θ
                ≥
                0
              
              ,
              η
            
          
          ⁢
          
            
              min
              
                α
                ,
                
                  z
                  ≥
                  0
                
              
            
            ⁢
            
              
                ∑
                i
              
              ⁢
              
                
              
              ⁢
              
                
                  α
                  i
                
                ⁡
                
                  (
                  
                    1
                    -
                    
                      π
                      i
                    
                  
                  )
                
              
            
          
        
        +
        
          
            
              (
              
                
                  
                    B
                    T
                  
                  ⁢
                  π
                
                +
                
                  
                    
                      ∇
                      y
                      T
                    
                    ⁢
                    
                      H
                      ⁡
                      
                        (
                        
                          y
                          _
                        
                        )
                      
                    
                  
                  ⁢
                  η
                
                +
                
                  
                    
                      ∇
                      y
                      T
                    
                    ⁢
                    
                      G
                      ⁡
                      
                        (
                        
                          y
                          _
                        
                        )
                      
                    
                  
                  ⁢
                  μ
                
                +
                θ
              
              )
            
            T
          
          ⁢
          z
        
        +
        
          
            π
            T
          
          ⁡
          
            (
            
              
                A
                ⁢
                
                  x
                  _
                
              
              +
              
                By
                L
              
              +
              b
            
            )
          
        
        -
        
          
            η
            T
          
          ⁢
          
            
              ∇
              y
            
            ⁢
            
              H
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
          
          ⁢
          
            (
            
              
                y
                _
              
              -
              
                y
                L
              
            
            )
          
        
        +
        
          
            μ
            T
          
          ⁡
          
            (
            
              
                G
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
              -
              
                
                  
                    ∇
                    y
                  
                  ⁢
                  
                    G
                    ⁡
                    
                      (
                      
                        y
                        _
                      
                      )
                    
                  
                
                ⁢
                
                  (
                  
                    
                      y
                      _
                    
                    -
                    
                      y
                      L
                    
                  
                  )
                
              
            
            )
          
        
        -
        
          
            θ
            T
          
          ⁡
          
            (
            
              
                y
                U
              
              -
              
                y
                L
              
            
            )
          
        
      
      =
      
        
          
            max
            
              
                1
                ≥
                
                  π
                  i
                
                ≥
                0
              
              
                
                  μ
                  ,
                  
                    θ
                    ≥
                    0
                  
                  ,
                  η
                
                
                  
                    
                      
                        B
                        T
                      
                      ⁢
                      π
                    
                    +
                    
                      
                        
                          ∇
                          y
                          T
                        
                        ⁢
                        
                          G
                          ⁡
                          
                            (
                            
                              y
                              _
                            
                            )
                          
                        
                      
                      ⁢
                      μ
                    
                    +
                    
                      
                        
                          ∇
                          y
                          T
                        
                        ⁢
                        
                          H
                          ⁡
                          
                            (
                            
                              y
                              _
                            
                            )
                          
                        
                      
                      ⁢
                      η
                    
                    +
                    θ
                  
                  ≥
                  0
                
              
            
          
          ⁢
          
            
              π
              T
            
            ⁡
            
              (
              
                
                  A
                  ⁢
                  
                    x
                    _
                  
                
                +
                
                  By
                  L
                
                +
                b
              
              )
            
          
        
        -
        
          
            η
            T
          
          ⁢
          
            
              ∇
              y
            
            ⁢
            
              H
              ⁡
              
                (
                
                  y
                  _
                
                )
              
            
          
          ⁢
          
            (
            
              
                y
                _
              
              -
              
                y
                L
              
            
            )
          
        
        +
        
          
            μ
            T
          
          ⁡
          
            (
            
              
                G
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
              -
              
                
                  
                    ∇
                    y
                  
                  ⁢
                  
                    G
                    ⁡
                    
                      (
                      
                        y
                        _
                      
                      )
                    
                  
                
                ⁢
                
                  (
                  
                    
                      y
                      _
                    
                    -
                    
                      y
                      L
                    
                  
                  )
                
              
            
            )
          
        
        -
        
          
            θ
            T
          
          ⁡
          
            (
            
              
                y
                U
              
              -
              
                y
                L
              
            
            )
          
        
      
    
  
  ,




where θ is a new decision variable.

Again, suppose that ({circumflex over (π)}, {circumflex over (η)}, {circumflex over (μ)}, {circumflex over (θ)}) is the optimal solution to the dual problem. By solving the Lagrangian dual problem of the problem (6), the computing system is configured to obtain





  
    
      
        
          π
          ^
        
        T
      
      ⁡
      
        (
        
          
            A
            ⁢
            
              
            
            ⁢
            
              x
              _
            
          
          +
          
            By
            L
          
          +
          b
        
        )
      
    
    -
    
      
        
          η
          ^
        
        T
      
      ⁢
      
        
          ∇
          y
        
        ⁢
        
          H
          ⁡
          
            (
            
              y
              _
            
            )
          
        
      
      ⁢
      
        (
        
          
            y
            _
          
          -
          
            y
            L
          
        
        )
      
    
    +
    
      
        
          μ
          ^
        
        T
      
      ⁡
      
        (
        
          
            G
            ⁡
            
              (
              
                y
                _
              
              )
            
          
          -
          
            
              
                ∇
                y
              
              ⁢
              
                G
                ⁡
                
                  (
                  
                    y
                    _
                  
                  )
                
              
            
            ⁢
            
              (
              
                
                  y
                  _
                
                -
                
                  y
                  L
                
              
              )
            
          
        
        )
      
    
    -
    
      
        
          θ
          ^
        
        T
      
      ⁡
      
        (
        
          
            y
            U
          
          -
          
            y
            L
          
        
        )
      
    
  
  =
  
    
      
        ∑
        i
      
      ⁢
      
        α
        i
        *
      
    
    >
    0
  




that implies a second cut as follows:

{circumflex over (π)}T(A x+ByL+b)−{circumflex over (η)}T∇yH( y)( y−yL)+{circumflex over (μ)}T(G( y)−∇yG( y)( y−yL))−{circumflex over (θ)}T(yU−yL)≦0.  (8)

Motivated by equations (7) and (8), the computing system 400 is configured to obtain a third cut (e.g., equation (9)), provided that the optimal result of (5) is strictly positive, i.e., (4) is infeasible. Denote ({tilde over (π)}, {tilde over (μ)}, {tilde over (η)}) by the Lagrange multipliers in the nonlinear optimization problem (5). The third cut is as follows:

{tilde over (π)}T(Ax+ByL+b)−{tilde over (η)}T∇yH( y)( y−yL)+{tilde over (μ)}T∇yG( y)( y−yL))≦0.  (9)

By using these cuts (e.g., equations (7)-(9)), the computing system 400 is configured to prune one or more results of the optimization problem (e.g., problem (5) or problem (6)). Returning to FIG. 1, at step 140, the computing system 400 is configured to solve the optimization problem (e.g., problem (5) or problem (6)) to obtain the pruned result. In one embodiment, the master optimization problem with the pruned result is as follows:




  
    
      
        
          
            min
          
          
            
              f
              ⁡
              
                (
                
                  u
                  0
                
                )
              
            
          
        
        
          
            
              
            
          
          
            
              
                
                  g
                  0
                
                ⁡
                
                  (
                  
                    
                      x
                      0
                    
                    ,
                    
                      u
                      0
                    
                  
                  )
                
              
              ≤
              0
            
          
        
        
          
            
              
            
          
          
            
              
                
                  h
                  0
                
                ⁡
                
                  (
                  
                    
                      x
                      0
                    
                    ,
                    
                      u
                      0
                    
                  
                  )
                
              
              =
              0
            
          
        
        
          
            
              
            
          
          
            
              
                
                  
                    Pu
                    0
                  
                  +
                  q
                
                ≤
                0
              
              ,
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




where Pμ0+q≦0 includes the feasibility cuts (e.g., equations (7)-(9)) with P is a matrix, q is a vector.

In other words, by running the method steps in FIG. 1, the computing system 400 is first configured to solve the problem (11) to get (x0(1), u0(1)) (x0(1) and u0(1) are solutions obtained by solving the equation (11).)




  
    
      
        
          
            min
          
          
            
              f
              ⁡
              
                (
                
                  u
                  0
                
                )
              
            
          
        
        
          
            
              
            
          
          
            
              
                
                  g
                  0
                
                ⁡
                
                  (
                  
                    
                      x
                      0
                    
                    ,
                    
                      u
                      0
                    
                  
                  )
                
              
              ≤
              0
            
          
        
        
          
            
              
            
          
          
            
              
                
                  h
                  0
                
                ⁡
                
                  (
                  
                    
                      x
                      0
                    
                    ,
                    
                      u
                      0
                    
                  
                  )
                
              
              =
              0
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




Then, for an iteration k=1, 2, . . . and each contingency c=1, . . . , C, the computing system 400 is configured to solve the problem (5) for a given (x0(k), u0(k)). If Σiαi>0, the computing system 400 is configured to add the third cut (e.g., equation (9)) into the problem (10). If Σiαi=0 for all c=1, . . . , C, the computing system is configured to terminate the method steps in FIG. 1. Otherwise, if Σiαi≠0, the computing system 400 is configured to solve the problem (10) after adding the cut (e.g., equation (7) or (8) or (9)) to obtain (x0(k+1), u0(k+1)). By solving problem (10), the computing system 400 is configured to output a result that specifies an amount of electric power to be generated to meet the one or more customer request under the contingency constraint and a lowest cost to generate the amount of the electric power.

In one embodiment, the computing system is configured to utilize one or more of these cuts (e.g., equations (7)-(9)) in an adaptive manner. For example, in one embodiment, if it is supposed that c(x)≦0 is a valid cut for x, then c(x)−αc( x)≦0, for any α<1 is also a cut. By choosing a adaptively based on a constraint infeasibility measure for x, for example, the measurement can be an optimal result of the problem (5), the quality of the solution of the optimization problem (1) can be improved. The idea is that if the constraint infeasibility measure is large (e.g. larger than 10, etc.), the computing system 400 is configured to select α close to 1, otherwise the computing system 400 is configured to select α close to 0.
FIG. 2 is a flow chart that describes method steps for solving the optimization problem (1) that calculates amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting at least one contingency constraint and one or more customer request in one embodiment.
The computing system 400 is configured to generate a template to solve the optimization problem (e.g., problem (1)). An example of the template includes, but is not limited to:




  
    
      
        
          min
          
            x
            ,
            y
          
        
        ⁢
        
          
            {
            
              
                
                  
                    F
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    
                      G
                      ⁡
                      
                        (
                        y
                        )
                      
                    
                    ⁢
                    
                      :
                    
                    ⁢
                    
                      
                    
                    ⁢
                    M
                    ⁢
                    
                      
                    
                    ⁢
                    x
                  
                  +
                  Ny
                
                =
                d
              
              ,
              
                x
                ∈
                X
              
              ,
              
                y
                ∈
                Y
              
            
            }
          
          .
        
      
    
    
      
        (
        14
        )
      
    
  




where xεPn, yεPm, MεPp×n, NεPp×m and dεPp. Assume that F and G are closed, convex, and differentiable functions, and X and Y are closed and nonconvex sets.

The computing system 400 is configured to form an augmented Lagrangian for the problem (14) as follows:




  
    
      
        
          
            
              L
              β
            
            ⁡
            
              (
              
                x
                ,
                y
                ,
                λ
              
              )
            
          
          =
          
            
              F
              ⁡
              
                (
                x
                )
              
            
            +
            
              G
              ⁡
              
                (
                y
                )
              
            
            +
            
              
                λ
                T
              
              ⁡
              
                (
                
                  Mx
                  +
                  Ny
                  -
                  d
                
                )
              
            
            +
            
              
                1
                2
              
              ⁢
              β
              ⁢
              
                
                  
                  
                    Mx
                    +
                    Ny
                    -
                    d
                  
                  
                
                2
              
            
          
        
        ,
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            where
            ⁢
            
              
            
            ⁢
            β
          
          >
          0.
        
      
    
    
      
        (
        15
        )
      
    
  




A classical augmented Lagrangian multiplier method involves a joint optimization and multiplier update step:

(xk+1,yk+1):=argminxεX,yεYLβ(x,y,λk)

λk+1=λk+β(Mxk+1+Nyk+1−d).

The computing system 400 is configured to iterate:

xk+1:=argminxεXLβ(x,yk,λk)

yk+1:=argminyεYLβ(xk+1,y,λk)

λk+1=λk+β(Mxk+1+Nyk+1−d),

where x:=argminxεΩf(x), means x* is the optimal solution of min f(x) s.t. xεΩ.

At step 210 in FIG. 2, in a further embodiment, the system is configured to reformulate the optimization problem (1) based on the generated template. In particular, the optimization problem (1) can be reformulated, e.g., by introducing an auxiliary variable u0c as follows:




  
    
      
        
          min
          ⁢
          
            
          
          ⁢
          
            f
            ⁡
            
              (
              
                u
                0
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            s
            .
            t
            .
            
              
            
            ⁢
            
              
                h
                0
              
              ⁡
              
                (
                
                  
                    x
                    0
                  
                  ,
                  
                    u
                    0
                  
                
                )
              
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              g
              0
            
            ⁡
            
              (
              
                
                  x
                  0
                
                ,
                
                  u
                  0
                
              
              )
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              h
              c
            
            ⁡
            
              (
              
                
                  x
                  c
                
                ,
                
                  u
                  c
                
              
              )
            
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              g
              c
            
            ⁡
            
              (
              
                
                  x
                  c
                
                ,
                
                  u
                  c
                
              
              )
            
          
          ≤
          0
        
        ⁢
        
          

        
        ⁢
        
          
            
              
              
                
                  u
                  c
                  i
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                  i
                
              
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                u
                i
                max
              
            
          
          ,
          
            i
            ∈
            G
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                u
                0
                i
              
              -
              
                u
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  c
                
                i
              
            
            =
            0
          
          ,
          
            i
            ∈
            G
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            .
          
        
      
    
    
      
        (
        16
        )
      
    
  
  
    
      
        
          Consider
          ⁢
          
            
          
          ⁢
          that
          ⁢
          
            :
          
        
        ⁢
        
          

        
        ⁢
        
          
            x
            :=
            
              (
              
                
                  x
                  0
                
                ,
                
                  u
                  0
                
              
              )
            
          
          ,
          
            y
            :=
            
              (
              
                
                  x
                  1
                
                ,
                
                  u
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  x
                  c
                
                ,
                
                  u
                  c
                
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              F
              ⁡
              
                (
                x
                )
              
            
            :=
            
              f
              ⁡
              
                (
                
                  u
                  0
                
                )
              
            
          
          ,
          
            
              G
              ⁡
              
                (
                y
                )
              
            
            :=
            0
          
        
        ⁢
        
          

        
        ⁢
        
          X
          :=
          
            {
            
              
                
                  
                    (
                    
                      
                        x
                        0
                      
                      ,
                      
                        u
                        0
                      
                    
                    )
                  
                  ⁢
                  
                    :
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      h
                      0
                    
                    ⁡
                    
                      (
                      
                        
                          x
                          0
                        
                        ,
                        
                          u
                          0
                        
                      
                      )
                    
                  
                
                =
                0
              
              ,
              
                
                  
                    g
                    0
                  
                  ⁡
                  
                    (
                    
                      
                        x
                        0
                      
                      ,
                      
                        u
                        0
                      
                    
                    )
                  
                
                ≤
                0
              
            
            }
          
        
        ⁢
        
          

        
        ⁢
        
          
            Y
            :=
            
              (
              
                
                  Y
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  Y
                  C
                
              
              )
            
          
          ,
          
            

          
          ⁢
          where
        
        ⁢
        
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              Y
              c
            
            :=
            
              {
              
                
                  
                    
                      
                        
                          
                            (
                            
                              
                                x
                                c
                              
                              ,
                              
                                u
                                c
                              
                              ,
                              
                                u
                                
                                  0
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  c
                                
                              
                            
                            )
                          
                          ⁢
                          
                            :
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              h
                              c
                            
                            ⁡
                            
                              (
                              
                                
                                  x
                                  c
                                
                                ,
                                
                                  u
                                  c
                                
                              
                              )
                            
                          
                        
                        =
                        0
                      
                      ,
                    
                  
                
                
                  
                    
                      
                        
                          
                            g
                            c
                          
                          ⁡
                          
                            (
                            
                              
                                x
                                c
                              
                              ,
                              
                                u
                                c
                              
                            
                            )
                          
                        
                        ≤
                        0
                      
                      ,
                      
                        
                          
                          
                            
                              u
                              c
                              i
                            
                            -
                            
                              u
                              
                                0
                                ⁢
                                
                                  
                                
                                ⁢
                                c
                              
                              i
                            
                          
                          
                        
                        ≤
                        
                          Δ
                          ⁢
                          
                            
                          
                          ⁢
                          
                            u
                            i
                            max
                          
                        
                      
                      ,
                      
                        i
                        ∈
                        G
                      
                    
                  
                
              
              }
            
          
          ,
          
            

          
          ⁢
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
            
              Mx
              +
              Ny
            
            =
            
              
                
                  d
                  ⁢
                  
                    :
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    u
                    0
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              =
              0
            
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
            M
            :=
            
              [
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    ...
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    ...
                  
                  
                    0
                  
                
                
                  
                    ⋮
                  
                  
                    
                      
                    
                  
                  
                    ⋱
                  
                  
                    ⋮
                  
                
                
                  
                    0
                  
                  
                    ...
                  
                  
                    0
                  
                  
                    1
                  
                
              
              ]
            
          
          ,
          
            N
            :=
            
              -
              
                [
                
                  
                    
                      1
                    
                    
                      0
                    
                    
                      ...
                    
                    
                      0
                    
                  
                  
                    
                      0
                    
                    
                      1
                    
                    
                      ...
                    
                    
                      0
                    
                  
                  
                    
                      ⋮
                    
                    
                      
                        
                      
                    
                    
                      ⋱
                    
                    
                      ⋮
                    
                  
                  
                    
                      0
                    
                    
                      ...
                    
                    
                      0
                    
                    
                      1
                    
                  
                
                ]
              
            
          
          ,
          
            d
            =
            
              
                [
                
                  
                    
                      0
                    
                  
                  
                    
                      ⋮
                    
                  
                  
                    
                      0
                    
                  
                
                ]
              
              .
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




Returning to FIG. 2, at step 220, the computing 400 is configured to form the Lagrangian for the reformulated optimization problem (16):



  
    
      
        L
        β
      
      ⁡
      
        (
        
          x
          ,
          y
          ,
          λ
        
        )
      
    
    =
    
      
        f
        ⁡
        
          (
          
            u
            0
          
          )
        
      
      +
      
        
          ∑
          
            c
            =
            1
          
          C
        
        ⁢
        
          
        
        ⁢
        
          
            λ
            c
          
          ⁡
          
            (
            
              
                u
                0
              
              -
              
                u
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  c
                
              
            
            )
          
        
      
      +
      
        
          β
          2
        
        ⁢
        
          
            ∑
            
              c
              =
              1
            
            C
          
          ⁢
          
            
          
          ⁢
          
            
              
              
                
                  u
                  0
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              
            
            2
          
        
      
    
  




  
    
      where
      ⁢
      
        
      
      ⁢
      β
    
    >
    0.
  



The computing system 400 is configured to iterate, based on an alternating direction method of multipliers, as follows:

For k=1, 2, . . . .




  
    
      (
      
        
          x
          0
          
            (
            
              k
              +
              1
            
            )
          
        
        ,
        
          u
          0
          
            (
            
              k
              +
              1
            
            )
          
        
      
      )
    
    =
    
      
        
          argmin
          
            
              (
              
                
                  x
                  0
                
                ,
                
                  u
                  0
                
              
              )
            
            ∈
            X
          
        
        ⁢
        
          f
          ⁡
          
            (
            
              u
              0
            
            )
          
        
      
      +
      
        
          ∑
          c
        
        ⁢
        
          
        
        ⁢
        
          
            λ
            c
            
              (
              k
              )
            
          
          ⁡
          
            (
            
              
                u
                0
              
              -
              
                u
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  c
                
                
                  (
                  k
                  )
                
              
            
            )
          
        
      
      +
      
        
          β
          2
        
        ⁢
        
          
            ∑
            c
          
          ⁢
          
            
          
          ⁢
          
            
              
              
                
                  u
                  0
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                  
                    (
                    k
                    )
                  
                
              
              
            
            2
          
        
      
    
  




  
    
      (
      
        
          x
          c
          
            (
            
              k
              +
              1
            
            )
          
        
        ,
        
          u
          c
          
            (
            
              k
              +
              1
            
            )
          
        
        ,
        
          u
          
            0
            ⁢
            
              
            
            ⁢
            c
          
          
            (
            
              k
              +
              1
            
            )
          
        
      
      )
    
    =
    
      
        
          argmin
          
            
              (
              
                
                  x
                  c
                
                ,
                
                  
                    u
                    c
                  
                  ⁢
                  
                    u
                    
                      0
                      ⁢
                      
                        
                      
                      ⁢
                      c
                    
                  
                
              
              )
            
            ∈
            
              Y
              c
            
          
        
        ⁢
        
          
            ∑
            c
          
          ⁢
          
            
          
          ⁢
          
            
              λ
              c
              
                (
                k
                )
              
            
            ⁡
            
              (
              
                
                  u
                  0
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              )
            
          
        
      
      +
      
        
          β
          2
        
        ⁢
        
          
            ∑
            c
          
          ⁢
          
            
          
          ⁢
          
            
              
              
                
                  u
                  0
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              
            
            2
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        c
        =
        1
      
      ,
      ...
      ⁢
      
        
      
      ,
      C
    
    ⁢
    
      
    
  




  
    
      
    
    ⁢
    
      
        
          λ
          c
          
            (
            
              k
              +
              1
            
            )
          
        
        =
        
          
            λ
            c
            
              (
              k
              )
            
          
          +
          
            β
            ⁡
            
              (
              
                
                  u
                  0
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
              
              )
            
          
        
      
      ,
      
        c
        =
        1
      
      ,
      ...
      ⁢
      
        
      
      ,
      C
      ,
    
  



The computing system solves the optimization problem (1) to determine (x0, u0), where x0 are voltages, u0 are the amount of an electric power generated at generators. The final iterate (x0(k+1), u0(k+1)) provides (x0, u0).

Returning to FIG. 2, at step 230, the computing system 400 is configured to initialize Lagrangian multipliers and decision variables according to each contingency constraint: u0c(1), λc(1), c=1, . . . , C.
At step 240, the computing system 400 is configured to solve the reformulated optimization problem (e.g., problem (16), “base case optimization problem” shown at step 240 in FIG. 2) with the initialized Lagrangian multipliers and decision variables of contingencies:




  
    (
    
      
        x
        0
        
          (
          
            k
            +
            1
          
          )
        
      
      ,
      
        u
        0
        
          (
          
            k
            +
            1
          
          )
        
      
    
    )
  
  =
  
    
      
        argmin
        
          
            (
            
              
                x
                0
              
              ,
              
                u
                0
              
            
            )
          
          ∈
          X
        
      
      ⁢
      
        f
        ⁡
        
          (
          
            u
            0
          
          )
        
      
    
    +
    
      
        ∑
        c
      
      ⁢
      
        
      
      ⁢
      
        
          λ
          c
          
            (
            k
            )
          
        
        ⁡
        
          (
          
            
              u
              0
            
            -
            
              u
              
                0
                ⁢
                
                  
                
                ⁢
                c
              
              
                (
                k
                )
              
            
          
          )
        
      
    
    +
    
      
        β
        2
      
      ⁢
      
        
          ∑
          c
        
        ⁢
        
          
        
        ⁢
        
          
            
            
              
                u
                0
              
              -
              
                u
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  c
                
                
                  (
                  k
                  )
                
              
            
            
          
          2
        
      
    
  




At step 250, the computing system 400 is further configured to break the reformulated optimization problem (e.g., equation (16)) into one or more sub-problems, which can be run in parallel. The computing system 400 is configured to solve the one or more sub-problems with the initialized Lagrangian multipliers and decision variables of the base case (e.g., problem (16)), based on the formed augmented Lagrangian.



  
    
      (
      
        
          x
          c
          
            (
            
              k
              +
              1
            
            )
          
        
        ,
        
          u
          c
          
            (
            
              k
              +
              1
            
            )
          
        
        ,
        
          u
          
            0
            ⁢
            
              
            
            ⁢
            c
          
          
            (
            
              k
              +
              1
            
            )
          
        
      
      )
    
    =
    
      
        
          argmin
          
            
              (
              
                
                  x
                  c
                
                ,
                
                  
                    u
                    c
                  
                  ⁢
                  
                    u
                    
                      0
                      ⁢
                      
                        
                      
                      ⁢
                      c
                    
                  
                
              
              )
            
            ∈
            
              Y
              c
            
          
        
        ⁢
        
          
            ∑
            c
          
          ⁢
          
            
          
          ⁢
          
            
              λ
              c
              
                (
                k
                )
              
            
            ⁡
            
              (
              
                
                  u
                  0
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              )
            
          
        
      
      +
      
        
          β
          2
        
        ⁢
        
          
            ∑
            c
          
          ⁢
          
            
          
          ⁢
          
            
              
              
                
                  u
                  0
                  
                    (
                    
                      k
                      +
                      1
                    
                    )
                  
                
                -
                
                  u
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                
              
              
            
            2
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        c
        =
        1
      
      ,
      ...
      ⁢
      
        
      
      ,
      C
    
    ⁢
    
      
    
  



At step 260, the computing system 400 is configured to evaluate whether a solution of the one or more sub-problems meets a stopping criterion. The stopping criterion includes, but is not limited to: a gap between u0(k+1) and u0c(k+1) is lower than a pre-determined threshold for all c=1, . . . , C.
At step 280, the computing system 400 is configured to output the solution in response to determining that the solution meets the stopping criterion. The solution specifies ideal amount of electric power to be generated to meet the customers' requests under the contingency constraint and a lowest cost to generate the ideal amount of the electric power. At step 270, the computing system 400 is configured to update the Lagrangian multipliers based on the solutions from steps 270 and 280, in response to determining that the solution does not meet the stopping criterion, and the process returns to step 240.
FIG. 3 is a flow chart that describes method steps for solving an optimization problem that calculates amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting at least one contingency constraint and one or more customer request in one embodiment. At step 310, the computing system 400 is configured to build a tree data structure (not shown). Each node of the tree data structure describes a possible solution of the optimization problem (e.g., problem (1)). The system is configured to compute, at each node of the built tree data structure, an upper bound and lower bound of a function (e.g., an objective function of the problem (1)). The function determines an amount of electric power to be generated to meet the one or more customer request under the contingency constraint and a cost for generating the amount of the electric power. The lower bound is calculated from Lagrange dual problem (i.e., Lagrange duality). The upper bound is calculated from an interior-point method. A reference to Andreas Wachter, et al., “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Math. Program. Ser. A 106, pp. 25-57, Apr. 28, 2005, wholly incorporated by reference as set forth herein, describes interior-point method in detail. At step 320, the computing system 400 is configured to evaluate, at each node of the built tree data structure, whether the computed upper bound and computed lower bound satisfy a stopping criterion. The stopping criterion includes, but is not limited to, one or more of: a gap between a smallest computed lower bound and the computed upper bound is lower than a pre-determined threshold, and the tree data structure is empty. At step 370, the computing system 400 is configured to output the computed upper bound and the computed lower bound in response to determining that the computed upper bound and smallest computed lower bound satisfy the stopping criterion or the tree data structure is empty.
In one embodiment, the computing system 400 is configured to divide the feasible set by using rectangular bisection or ellipsodial bisection to form the tree data structure. If an optimization problem min f(x) s.t. xεΩ, then SI is called the feasible set. Consider an electric power system with N nodes where PiG and QiG are dispatchable active and reactive powers, PiD and QiD are active and reactive power demands at node i. Denote Γ by a set of electric power generators and Δ by a set of demand buses, whereas T is a set of transmission lines. Every complex nodal voltage can be written in rectangular form Vi=e1+ifi, for all iεN, where i is the imaginary unit, ei is the real part of the complex nodal voltage Vi and fi the imaginary part of the complex nodal voltage Vi. In an electric power system analysis, power system networks can be represented as graphs where electrical nodes correspond to graph nodes, transmission lines are graph edges. In turn, each graph can be expressed as an admittance matrix Y. The complex elements at row i and column j of the matrix Y are as follows: Yij=gij+ibij, where G=(gij) is a conductance matrix, and B=(bij) is a susceptance matrix. Conductance matrix and susceptance matrix represent the physical characteristics, e.g. resistance and reactance, of an electric power network between electric transmission lines i and j. From Kirchoffs law, electric power flow equations at each node i can be formulated as the following quadratic equations:




  
    
      
        ∑
        
          j
          ∈
          N
        
      
      ⁢
      
        
      
      ⁢
      
        (
        
          
            
              e
              i
            
            ⁡
            
              (
              
                
                  
                    g
                    ij
                  
                  ⁢
                  
                    e
                    j
                  
                
                -
                
                  
                    b
                    ij
                  
                  ⁢
                  
                    f
                    j
                  
                
              
              )
            
          
          +
          
            
              f
              i
            
            ⁡
            
              (
              
                
                  
                    g
                    ij
                  
                  ⁢
                  
                    f
                    j
                  
                
                +
                
                  
                    b
                    ij
                  
                  ⁢
                  
                    e
                    j
                  
                
              
              )
            
          
        
        )
      
    
    =
    
      
        P
        i
        G
      
      -
      
        P
        i
        D
      
    
  
  ,
  
    

  
  ⁢
  
    
      
        ∑
        
          j
          ∈
          N
        
      
      ⁢
      
        
      
      ⁢
      
        (
        
          
            
              f
              i
            
            ⁡
            
              (
              
                
                  
                    g
                    ij
                  
                  ⁢
                  
                    e
                    j
                  
                
                -
                
                  
                    b
                    ij
                  
                  ⁢
                  
                    f
                    j
                  
                
              
              )
            
          
          -
          
            
              e
              i
            
            ⁡
            
              (
              
                
                  
                    g
                    ij
                  
                  ⁢
                  
                    f
                    j
                  
                
                +
                
                  
                    b
                    ij
                  
                  ⁢
                  
                    e
                    j
                  
                
              
              )
            
          
        
        )
      
    
    =
    
      
        Q
        i
        G
      
      -
      
        
          Q
          i
          D
        
        .
      
    
  




An upper limit constraint on an active electric power flow in a transmission line (i, j) is represented as follows:

Pij=(eifj−ejfi)bi,j+(ei2+fi2−eiej−fifj)gij≦Pijmax,

where Pijmax is the maximum active (MW) electic power flow in the transmission line (i, j).

A node “1” is selected as a reference node, which implies from a zero angular condition at this reference node that f1=0. Taking into account the physical and operational limits to insure secure operating states for both the pre-contingency (normal case) constraints and post-contingency constraints, this leads to the optimization problem:




  
    
      
        
          
            
              min
              
                
                  e
                  i
                  c
                
                ,
                
                  f
                  i
                  c
                
                ,
                
                  P
                  i
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  Q
                  i
                  
                    G
                    ,
                    c
                  
                
              
            
            ⁢
            
              
                ∑
                
                  i
                  ∈
                  Γ
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    c
                    
                      0
                      ⁢
                      
                        
                      
                      ⁢
                      i
                    
                  
                  ⁡
                  
                    (
                    
                      P
                      i
                      
                        G
                        ,
                        0
                      
                    
                    )
                  
                
                2
              
            
          
          +
          
            
              c
              
                1
                ⁢
                
                  
                
                ⁢
                i
              
            
            ⁢
            
              P
              i
              
                G
                ,
                0
              
            
          
          +
          
            c
            
              2
              ⁢
              
                
              
              ⁢
              i
            
          
        
        ⁢
        
          

        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
          ⁢
          
            
          
          ⁢
          
            (
            
              
                
                  for
                  ⁢
                  
                    
                  
                  ⁢
                  c
                
                =
                0
              
              ,
              ...
              ⁢
              
                
              
              ,
              C
            
            )
          
          ⁢
          
            :
          
        
      
    
    
      
        (
        18
        )
      
    
  
  
    
      
        
          
            
              ∑
              
                j
                ∈
                N
              
            
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  
                    e
                    i
                    c
                  
                  ⁡
                  
                    (
                    
                      
                        
                          g
                          ij
                          c
                        
                        ⁢
                        
                          e
                          j
                          c
                        
                      
                      -
                      
                        
                          b
                          ij
                          c
                        
                        ⁢
                        
                          f
                          j
                          c
                        
                      
                    
                    )
                  
                
                +
                
                  
                    f
                    i
                    c
                  
                  ⁡
                  
                    (
                    
                      
                        
                          g
                          ij
                          c
                        
                        ⁢
                        
                          f
                          j
                          c
                        
                      
                      +
                      
                        
                          b
                          ij
                          c
                        
                        ⁢
                        
                          e
                          j
                          c
                        
                      
                    
                    )
                  
                
              
              )
            
          
          =
          
            
              P
              i
              
                G
                ,
                c
              
            
            -
            
              P
              i
              D
            
          
        
        ,
        
          i
          ∈
          N
        
      
    
    
      
        (
        19
        )
      
    
  
  
    
      
        
          
            
              ∑
              
                j
                ∈
                N
              
            
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  
                    f
                    i
                    c
                  
                  ⁡
                  
                    (
                    
                      
                        
                          g
                          ij
                          c
                        
                        ⁢
                        
                          e
                          j
                          c
                        
                      
                      -
                      
                        
                          b
                          ij
                          c
                        
                        ⁢
                        
                          f
                          j
                          c
                        
                      
                    
                    )
                  
                
                -
                
                  
                    e
                    i
                    c
                  
                  ⁡
                  
                    (
                    
                      
                        
                          g
                          ij
                          c
                        
                        ⁢
                        
                          f
                          j
                          c
                        
                      
                      +
                      
                        
                          b
                          ij
                          c
                        
                        ⁢
                        
                          e
                          j
                          c
                        
                      
                    
                    )
                  
                
              
              )
            
          
          =
          
            
              Q
              i
              
                G
                ,
                c
              
            
            -
            
              Q
              i
              D
            
          
        
        ,
        
          i
          ∈
          N
        
      
    
    
      
        (
        20
        )
      
    
  
  
    
      
        
          
            
              
                (
                
                  
                    
                      e
                      i
                      c
                    
                    ⁢
                    
                      f
                      j
                      c
                    
                  
                  -
                  
                    
                      e
                      j
                      c
                    
                    ⁢
                    
                      f
                      i
                      c
                    
                  
                
                )
              
              ⁢
              
                b
                
                  i
                  ,
                  j
                
                c
              
            
            +
            
              
                (
                
                  
                    
                      (
                      
                        e
                        i
                        c
                      
                      )
                    
                    2
                  
                  +
                  
                    
                      (
                      
                        f
                        i
                        c
                      
                      )
                    
                    2
                  
                  -
                  
                    
                      e
                      i
                      c
                    
                    ⁢
                    
                      e
                      j
                      c
                    
                  
                  -
                  
                    
                      f
                      i
                      c
                    
                    ⁢
                    
                      f
                      j
                      c
                    
                  
                
                )
              
              ⁢
              
                g
                ij
                c
              
            
          
          ≤
          
            P
            ij
            max
          
        
        ,
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            (
            
              i
              ,
              j
            
            )
          
          ∈
          T
        
      
    
    
      
        (
        21
        )
      
    
  
  
    
      
        
          f
          1
          c
        
        =
        0
      
    
    
      
        (
        22
        )
      
    
  
  
    
      
        
          
            P
            i
            min
          
          ≤
          
            P
            i
            
              G
              ,
              c
            
          
          ≤
          
            P
            i
            max
          
        
        ,
        
          i
          ∈
          Γ
        
      
    
    
      
        (
        23
        )
      
    
  
  
    
      
        
          
            Q
            i
            min
          
          ≤
          
            Q
            i
            
              G
              ,
              c
            
          
          ≤
          
            Q
            i
            max
          
        
        ,
        
          i
          ∈
          Γ
        
      
    
    
      
        (
        24
        )
      
    
  
  
    
      
        
          
            
              (
              
                V
                i
                min
              
              )
            
            2
          
          ≤
          
            
              
                (
                
                  e
                  i
                  c
                
                )
              
              2
            
            +
            
              
                (
                
                  f
                  i
                  c
                
                )
              
              2
            
          
          ≤
          
            
              (
              
                V
                i
                max
              
              )
            
            2
          
        
        ,
        
          i
          ∈
          N
        
      
    
    
      
        (
        25
        )
      
    
  
  
    
      
        
          
            
            
              
                P
                i
                
                  G
                  ,
                  c
                
              
              -
              
                P
                i
                
                  G
                  ,
                  0
                
              
            
            
          
          ≤
          
            Δ
            ⁢
            
              
            
            ⁢
            
              P
              i
            
          
        
        ,
        
          i
          ∈
          Γ
        
      
    
    
      
        (
        26
        )
      
    
  
  
    
      
        
          
            
            
              
                Q
                i
                
                  G
                  ,
                  c
                
              
              -
              
                Q
                i
                
                  G
                  ,
                  0
                
              
            
            
          
          ≤
          
            Δ
            ⁢
            
              
            
            ⁢
            
              Q
              i
            
          
        
        ,
        
          i
          ∈
          Γ
        
        ,
      
    
    
      
        (
        27
        )
      
    
  




where Pimin and Pimax are active power generation limits, Qimin and Qimax are reactive power generation limits, Vimin and Vimax are voltage limits. ΔPi and ΔQi are pre-determined maximal allowed variation of control variables, c0i, c1i, and c2i are cost parameters, and index c represents a contingency c.

Let Ω be a feasible set defined by equations (19)-(27) and assume SI is non-empty. An immediate result can be deduced is that SI is a compact and non-convex set. Note that the problem defined by (18)-(27) is a continuous optimization problem with a convex quadratic objective subject to non-convex quadratic constraints. Decision variables is required to satisfy the non-convex quadratic constraints. The optimization problem (18)-(27) is equivalent to




  
    min
    ⁢
    
      
    
    ⁢
    
      
        ∑
        
          i
          ∈
          Γ
        
      
      ⁢
      
        
      
      ⁢
      
        
          
            c
            
              0
              ⁢
              
                
              
              ⁢
              i
            
          
          ⁡
          
            (
            
              P
              i
              G
            
            )
          
        
        2
      
    
  
  +
  
    
      c
      
        1
        ⁢
        
          
        
        ⁢
        i
      
    
    ⁢
    
      P
      i
      G
    
  
  +
  
    c
    
      2
      ⁢
      
        
      
      ⁢
      i
    
  




subject to
the constraints (19)-(27)




  
    
      
        
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  
                    (
                    
                      e
                      i
                      c
                    
                    )
                  
                  2
                
                +
                
                  
                    (
                    
                      f
                      i
                      c
                    
                    )
                  
                  2
                
              
              )
            
          
          ≤
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
            
            ⁢
            
              
                (
                
                  V
                  i
                  max
                
                )
              
              2
            
          
        
        ,
        
          
        
        ⁢
        
          c
          =
          0
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          C
          .
        
      
    
    
      
        (
        28
        )
      
    
  




The equations (23)-(24) represent constraints associated with the rectangular branch and bound algorithm. The equation (28) represents a constraint associated with the ellipsoidal branch and bound algorithm. The rectangular branch and bound algorithm and the ellipsoidal branch and bound algorithm are described in detail below.
Returning to FIG. 3, at step 330 the system is configured to apply at least one branching procedure on the tree data structure in response to determining that the computed upper bound and computed lower bound do not satisfy the stopping criteria. The branching procedure includes, but is not limited to: the rectangular bisection and the ellipsoidal bisection. The branching procedure in these branch and bound algorithms is accomplished by dividing the feasible set to form the tree data structure, e.g., by using either successive ellipsoidal bisections of the ellipsoidal constraint (e.g., equation (28)) or rectangular bisections of the rectangular constraints (e.g., equations (23)-(24)).
The following describes the ellipsoidal bisection in detail. Consider an ellipsoid E with a center c in the form of:

E={xεPn:(x−c)TB−1(x−c)≦1},  (29)

where B is a symmetric, positive definite matrix. Given a nonzero vector vεPn, the sets

H−={xεE:vTx≦vTc} and H+={xεE:vTx≧vTc}  (30)

partition E into two sets of equal volume. Note that the hyperplane {x:vTx=vTc} passes through the center c of E. The centers c+ and c− and the matrix B± of the ellipsoids E± of minimum volume containing H± are given as follows:





  
    
      
        
          
            c
            ±
          
          =
          
            c
            ±
            
              d
              
                n
                +
                1
              
            
          
        
        ,
        
          
            B
            ±
          
          =
          
            
              
                n
                2
              
              
                
                  n
                  2
                
                -
                1
              
            
            ⁢
            
              (
              
                B
                -
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      dd
                      T
                    
                  
                  
                    n
                    +
                    1
                  
                
              
              )
            
          
        
        ,
        
          d
          =
          
            Bv
            
              
                
                  v
                  T
                
                ⁢
                Bv
              
            
          
        
        ,
      
    
    
      
        (
        31
        )
      
    
  




where n is the size of vector xεPn.

A ratio R of the ellipsoid of E± to the ellipsoid of E is





  
    
      
        R
        =
        
          
            
              (
              
                
                  
                    (
                    
                      n
                      
                        n
                        +
                        1
                      
                    
                    )
                  
                  
                    n
                    +
                    1
                  
                
                ⁢
                
                  
                    (
                    
                      n
                      
                        n
                        -
                        1
                      
                    
                    )
                  
                  
                    n
                    -
                    1
                  
                
              
              )
            
            
              1
              2
            
          
          <
          
            e
            
              -
              
                1
                
                  2
                  ⁢
                  n
                
              
            
          
          <
          1.
        
      
    
    
      
        (
        32
        )
      
    
  




Thus R depends on the dimension n, but not on the vector v.

The following describes an ellipsoidal branch and bound algorithm that uses an ellipsoidal bisection(s) in detail. For any ellipse E, define l(E) the lower bound of f(PQ,0) over E∩Ω obtained from the optimal result of the problem (44) described below. Assume that uk is the best upper bound value at k-th iteration. Likewise, lk is the smallest lower bound, and let Sk be the set containing direct-product ellipsoids at the k-th iteration. Denote




  
    
      E
      c
    
    =
    
      {
      
        
          
            (
            
              
                e
                c
              
              ,
              
                f
                c
              
            
            )
          
          ⁢
          
            :
          
          ⁢
          
            
          
          ⁢
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              (
              
                
                  
                    (
                    
                      e
                      i
                      c
                    
                    )
                  
                  2
                
                +
                
                  
                    (
                    
                      f
                      i
                      c
                    
                    )
                  
                  2
                
              
              )
            
          
        
        ≤
        
          
            ∑
            
              i
              ∈
              N
            
          
          ⁢
          
            
              (
              
                V
                i
                max
              
              )
            
            2
          
        
      
      }
    
  
  ,
  
    c
    =
    0
  
  ,
  ...
  ⁢
  
    
  
  ,
  C
  ,
  
    

  
  ⁢
  
    
      E
      0
    
    =
    
      
        E
        0
      
      ×
      
        E
        1
      
      ×
      ...
      ×
      
        
          E
          C
        
        .
      
    
  




[Ellipsoidal Branch and Bound Algorithm]
1. Set S0={E0}, evaluate l(E0) and apply a local algorithm to get an initial upper bound u0, let l0=l(E0).
2. For k=0, 1, 2, . . . .


    
    
        (a) If Sk=Ø or uk=lk:=min{l(E):EεSk}, then the optimal solution of the problem (1) has been found
        (b) Choose EkεSk such that lk=l(Ek). Bisect the ellipse associated with the largest diameter of Ek. Use the equations (29)-(31) to cover Ek with two new direct-product ellipsoids denoted Ek1 and Ek2 
        (c) Check if Eki∩Ω=Ø set l(Eki)=∞;
        otherwise evaluate l(Eki) and compute a feasible point yki of Eki∩Ω, i=1, 2
        (d) Let xk+1 denote a feasible point associated with the lowest function value that has been generated up to this iteration including the current step. We have f(xk+1)≦f(yki) i=1, 2. If f(xk+1)<uk, then define uk+1=f(xk+1);
        otherwise, uk+1=uk 
        (e) Set Sk+1={EεSk∪{Ek1}∪{Ek2}:l(E)<uk+1,E≠Ek}
    
    


Since the union of two direct-product ellipsoids Ek1∪Ek2 is always greater than Ek, it is possible that at a given stage of the ellipsoidal branch and bound algorithm the set Eki∩Ω is empty. If so, the computing system is configured to prune Eki from the tree data structure as shown in step 2(c).
Suppose that in step 2(b) the vector v pointing along the axis is used. Then either the ellipsoidal branch and bound algorithm reaches an optimal solution of the optimization problem (18)-(27) in a finite number of iterations, or every accumulation point of the sequence xk is a solution of the problem (18)-(27).
The following describes rectangular bisection in detail. The branching process in the this branch and bound algorithm is based on successive rectangular bisections of bound constraints for the active and reactive powers: PG,c and QG,c




  
    B
    c
  
  =
  
    
      {
      
        
          (
          
            
              P
              
                G
                ,
                c
              
            
            ,
            
              Q
              
                G
                ,
                c
              
            
          
          )
        
        ⁢
        
          :
        
        ⁢
        
          
        
        ⁢
        
          
            
              
                
                  
                    P
                    i
                    min
                  
                  ≤
                  
                    P
                    i
                    
                      G
                      ,
                      c
                    
                  
                  ≤
                  
                    P
                    i
                    max
                  
                
                ,
                
                  i
                  ∈
                  Γ
                
              
            
          
          
            
              
                
                  
                    Q
                    i
                    min
                  
                  ≤
                  
                    Q
                    i
                    
                      G
                      ,
                      c
                    
                  
                  ≤
                  
                    Q
                    i
                    max
                  
                
                ,
                
                  i
                  ∈
                  Γ
                
              
            
          
        
      
      }
    
    .
  




Denote B0=B0×B1× . . . ×BC. Consider a rectangle B in general form B={xεPn:a≦v≦b}, a point vεB, and an index jε{1, . . . , n}. Suppose that B is partitioned into two subrectangles B− and B+ determined by the hyperplane {x:xj=vj}:

B−={x:aj≦xjvj,ai≦xi≦bi for all i≠j}, 

B+={x:vj≦xjbj,ai≦xi≦bi for all i≠j}, 

A subdivision of B via (v, j) is a bisection of ratio α if an index j corresponds to a longest side of B and v is a point of this side such that

min(vj−aj,bj−vj)=α(bj−aj).

Over a new generated rectangle

Bk={ Pimin,c,k≦PiG,c≦ Pimax,c,k, Qimin,c,k≦QiG,c≦ Qimax,c,k, for all iεΓ,c=1, . . . ,C}, 

the Lagrange dual problem is given by





  
    
      
        
          
            q
            ⁡
            
              (
              
                λ
                ,
                β
                ,
                μ
                ,
                γ
                ,
                θ
              
              )
            
          
          =
          
            
              min
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
                ,
                
                  P
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  Q
                  
                    G
                    ,
                    c
                  
                
              
            
            ⁢
            
              L
              ⁡
              
                (
                
                  
                    e
                    c
                  
                  ,
                  
                    f
                    c
                  
                  ,
                  
                    P
                    
                      G
                      ,
                      c
                    
                  
                  ,
                  
                    Q
                    
                      G
                      ,
                      c
                    
                  
                  ,
                  λ
                  ,
                  β
                  ,
                  μ
                  ,
                  γ
                  ,
                  θ
                
                )
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              f
              1
              c
            
            =
            0
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              
                ∑
                
                  i
                  ∈
                  N
                
              
              ⁢
              
                
                  (
                  
                    V
                    i
                    min
                  
                  )
                
                2
              
            
            ≤
            
              
                ∑
                
                  i
                  ∈
                  N
                
              
              ⁢
              
                (
                
                  
                    
                      (
                      
                        e
                        i
                        c
                      
                      )
                    
                    2
                  
                  +
                  
                    
                      (
                      
                        f
                        i
                        c
                      
                      )
                    
                    2
                  
                
                )
              
            
            ≤
            
              
                ∑
                
                  i
                  ∈
                  N
                
              
              ⁢
              
                
                  (
                  
                    V
                    i
                    max
                  
                  )
                
                2
              
            
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              P
              i
              
                min
                ,
                c
                ,
                k
              
            
            ≤
            
              P
              i
              
                G
                ,
                c
              
            
            ≤
            
              P
              i
              
                max
                ,
                c
                ,
                k
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              Q
              i
              
                min
                ,
                c
                ,
                k
              
            
            ≤
            
              Q
              i
              
                G
                ,
                c
              
            
            ≤
            
              Q
              i
              
                max
                ,
                c
                ,
                k
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              
              
                
                  P
                  i
                  
                    G
                    ,
                    c
                  
                
                -
                
                  P
                  i
                  
                    G
                    ,
                    0
                  
                
              
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                P
                i
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              
              
                
                  Q
                  i
                  
                    G
                    ,
                    c
                  
                
                -
                
                  Q
                  i
                  
                    G
                    ,
                    0
                  
                
              
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                Q
                i
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
          ,
        
      
    
    
      
        (
        33
        )
      
    
  




where L is defined in equation (37) below, the minimum can be calculated by solving the problem (40) described below and the following





  
    
      
        
          
            
              minimize
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
              
            
            ⁢
            
              
                ∑
                
                  i
                  ∈
                  N
                
              
              ⁢
              
                
                  λ
                  i
                  c
                
                ⁡
                
                  (
                  
                    
                      ∑
                      
                        j
                        ∈
                        N
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            e
                            i
                            c
                          
                          ⁡
                          
                            (
                            
                              
                                
                                  g
                                  ij
                                  c
                                
                                ⁢
                                
                                  e
                                  j
                                  c
                                
                              
                              -
                              
                                
                                  b
                                  ij
                                  c
                                
                                ⁢
                                
                                  f
                                  j
                                  c
                                
                              
                            
                            )
                          
                        
                        +
                        
                          
                            f
                            i
                            c
                          
                          ⁡
                          
                            (
                            
                              
                                
                                  g
                                  ij
                                  c
                                
                                ⁢
                                
                                  f
                                  j
                                  c
                                
                              
                              +
                              
                                
                                  b
                                  ij
                                  c
                                
                                ⁢
                                
                                  e
                                  j
                                  c
                                
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                  )
                
              
            
          
          +
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                β
                i
                c
              
              ⁡
              
                (
                
                  
                    ∑
                    
                      j
                      ∈
                      N
                    
                  
                  ⁢
                  
                    (
                    
                      
                        
                          f
                          i
                          c
                        
                        ⁡
                        
                          (
                          
                            
                              
                                g
                                ij
                                c
                              
                              ⁢
                              
                                e
                                j
                                c
                              
                            
                            -
                            
                              
                                b
                                ij
                                c
                              
                              ⁢
                              
                                f
                                j
                                c
                              
                            
                          
                          )
                        
                      
                      -
                      
                        
                          e
                          i
                          c
                        
                        ⁡
                        
                          (
                          
                            
                              
                                g
                                ij
                                c
                              
                              ⁢
                              
                                f
                                j
                                c
                              
                            
                            +
                            
                              
                                b
                                ij
                                c
                              
                              ⁢
                              
                                e
                                j
                                c
                              
                            
                          
                          )
                        
                      
                    
                    )
                  
                
                )
              
            
          
          +
          
            
              ∑
              
                
                  (
                  
                    i
                    ,
                    j
                  
                  )
                
                ∈
                T
              
            
            ⁢
            
              
                μ
                
                  i
                  ,
                  j
                
                c
              
              ⁡
              
                (
                
                  
                    
                      (
                      
                        
                          
                            e
                            i
                            c
                          
                          ⁢
                          
                            f
                            j
                            c
                          
                        
                        -
                        
                          
                            e
                            j
                            c
                          
                          ⁢
                          
                            f
                            i
                            c
                          
                        
                      
                      )
                    
                    ⁢
                    
                      b
                      ij
                      c
                    
                  
                  +
                  
                    
                      (
                      
                        
                          
                            
                              
                                
                                  (
                                  
                                    e
                                    i
                                    c
                                  
                                  )
                                
                                2
                              
                              +
                              
                                
                                  (
                                  
                                    f
                                    i
                                    c
                                  
                                  )
                                
                                2
                              
                              -
                            
                          
                        
                        
                          
                            
                              
                                
                                  e
                                  i
                                  c
                                
                                ⁢
                                
                                  e
                                  j
                                  c
                                
                              
                              -
                              
                                
                                  f
                                  i
                                  c
                                
                                ⁢
                                
                                  f
                                  j
                                  c
                                
                              
                            
                          
                        
                      
                      )
                    
                    ⁢
                    
                      g
                      ij
                      c
                    
                  
                
                )
              
            
          
          +
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                (
                
                  
                    θ
                    i
                    c
                  
                  -
                  
                    γ
                    i
                    c
                  
                
                )
              
              ⁢
              
                (
                
                  
                    
                      (
                      
                        e
                        i
                        c
                      
                      )
                    
                    2
                  
                  +
                  
                    
                      (
                      
                        f
                        i
                        c
                      
                      )
                    
                    2
                  
                
                )
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            f
            i
            c
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                (
                
                  V
                  i
                  min
                
                )
              
              2
            
          
          ≤
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              (
              
                
                  
                    (
                    
                      e
                      i
                      c
                    
                    )
                  
                  2
                
                +
                
                  
                    (
                    
                      f
                      i
                      c
                    
                    )
                  
                  2
                
              
              )
            
          
          ≤
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                
                  (
                  
                    V
                    i
                    max
                  
                  )
                
                2
              
              .
            
          
        
      
    
    
      
        (
        34
        )
      
    
  




Note that the definition of this q(λ, β, γ, θ) is slightly different from the equation (38) described below, the computing system 400 is configured to add the lower bound constraints




  
    
      
        
          
            ∑
            
              i
              ∈
              N
            
          
          ⁢
          
            
              (
              
                V
                i
                min
              
              )
            
            2
          
        
        ≤
        
          
            ∑
            
              i
              ∈
              N
            
          
          ⁢
          
            
              (
              
                
                  
                    (
                    
                      e
                      i
                      c
                    
                    )
                  
                  2
                
                +
                
                  
                    (
                    
                      f
                      i
                      c
                    
                    )
                  
                  2
                
              
              )
            
            .
          
        
      
    
    
      
        (
        35
        )
      
    
  




Define the set F by

F={(ec,fc,PG,c,QG,c,c=0, . . . ,C):(19),(20),(21),(22),(25),(26),(27) and (35)}.

For any direct-product box Bk, define l(Bk) the lower bound of f(PQ) over Bk∪F. Now, the rectangular branch and bound algorithm that uses a rectangular bisection(s) can be stated as follows:

[Rectangular Branch and Bound Algorithm]
1. Set S0={B0}, evaluate l(B0) and apply a local algorithm to get an initial upper bound u0, let l0=l(B0)
2. For k=0, 1, 2, . . . .


    
    
        (a) If Sk=Ø or uk=lk:=min{l(B):BεSk}, then the optimal solution of the problem (1) has been found
        (b) Choose BkεSk such that lk=l(Bk). Bisect Bk into two direct-product boxes denoted Bk1 and Bk2 
        (c) Check if Bki∩F=Ø set l(Bki)=∞;
        otherwise evaluate l(Bki) and compute a feasible point yki of Bki∩F, i=1, 2
        (d) Let xk+1 denote a feasible point associated with the lowest function value that has been generated up to this iteration including the current step. We have f(xk+1)≦f(yki) i=1, 2. If f(xk+1)<uk, then define uk+1=f(xk+1);
        otherwise, uk+1=uk 
        (e) Set Sk+1={BεSk∪{Bk1}∪{Bk2}:l(B)<uk+1,B≠Bk}.
    
    


At the root of the tree data structure, calculating the lower bounds for the two branch and bound algorithms are identical. If an objective function to be minimized is the active power losses of all branches




  
    
      f
      ⁡
      
        (
        
          
            e
            0
          
          ,
          
            f
            0
          
        
        )
      
    
    =
    
      
        ∑
        
          i
          ∈
          N
        
      
      ⁢
      
        
          ∑
          
            j
            ∈
            N
          
        
        ⁢
        
          
            
              (
              
                g
                ij
                0
              
              )
            
            2
          
          ⁢
          
            (
            
              
                
                  (
                  
                    
                      e
                      i
                      0
                    
                    -
                    
                      e
                      j
                      0
                    
                  
                  )
                
                2
              
              +
              
                
                  (
                  
                    
                      f
                      i
                      0
                    
                    -
                    
                      f
                      j
                      0
                    
                  
                  )
                
                2
              
            
            )
          
        
      
    
  
  ,




or any additional quadratic constraints are included, these two branch and bound algorithms still apply.

Returning to FIG. 3, at step 340, the computing system 400 is configured to re-compute the lower bound in a region in the tree data structure branched according to the applied branching procedure. At step 350, the computing system 400 is configured to update the upper bound in the region in the tree data structure and the update of the upper bound is based on the best feasible point (i.e., the point whose value is the smallest among all generated feasible points) in the tree data structure. At step 360, the computing system 400 is configured to delete nodes in the region based on the re-computed the lower bound and updated upper bound. The system is configured to repeat steps 320-360 until stopping criteria is met in which case method terminates at 370.
The following describes re-computing the lower bound for the ellipsoidal branch and bound algorithm in detail, e.g., by using the Lagrange dual problem. Assume that there exist an original feasible set Ω (i.e., the original tree data structure where each node describes a possible solution of the problem (1)) and a direct-product (i.e., cartesian product) of ellipsoids E=E0×E1× . . . ×EC. Consider that




  
    
      
        
          minimize
          ⁢
          
            
          
          ⁢
          
            f
            ⁡
            
              (
              
                P
                
                  G
                  ,
                  0
                
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              
            
            ⁢
            
              (
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
                ,
                
                  P
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  
                    
                      Q
                      
                        G
                        ,
                        c
                      
                    
                    ⁢
                    
                      :
                    
                    ⁢
                    
                      
                    
                    ⁢
                    c
                  
                  =
                  0
                
                ,
                ...
                ⁢
                
                  
                
                ,
                C
              
              )
            
          
          ∈
          
            Ω
            ⋂
            
              E
              .
            
          
        
      
    
    
      
        (
        36
        )
      
    
  




Then, define the Lagrangian L by incorporating all the constraints in the problem (1) as follows:




  
    
      
        
          
            L
            ⁡
            
              (
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
                ,
                
                  P
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  Q
                  
                    G
                    ,
                    c
                  
                
                ,
                λ
                ,
                β
                ,
                μ
                ,
                γ
                ,
                θ
              
              )
            
          
          =
          
            
              f
              ⁡
              
                (
                
                  P
                  
                    G
                    ,
                    0
                  
                
                )
              
            
            +
            
              
                ∑
                
                  
                    c
                    =
                    0
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  C
                
              
              ⁢
              
                {
                
                  
                    
                      
                        
                          
                            ∑
                            
                              i
                              ∈
                              N
                            
                          
                          ⁢
                          
                            
                              λ
                              i
                              c
                            
                            ⁡
                            
                              (
                              
                                
                                  
                                    ∑
                                    
                                      j
                                      ∈
                                      N
                                    
                                  
                                  ⁢
                                  
                                    (
                                    
                                      
                                        
                                          
                                            
                                              
                                                e
                                                i
                                                c
                                              
                                              ⁡
                                              
                                                (
                                                
                                                  
                                                    
                                                      g
                                                      ij
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      e
                                                      j
                                                      c
                                                    
                                                  
                                                  -
                                                  
                                                    
                                                      b
                                                      ij
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      f
                                                      j
                                                      c
                                                    
                                                  
                                                
                                                )
                                              
                                            
                                            +
                                          
                                        
                                      
                                      
                                        
                                          
                                            
                                              f
                                              i
                                              c
                                            
                                            ⁡
                                            
                                              (
                                              
                                                
                                                  
                                                    g
                                                    ij
                                                    c
                                                  
                                                  ⁢
                                                  
                                                    f
                                                    j
                                                    c
                                                  
                                                
                                                +
                                                
                                                  
                                                    b
                                                    ij
                                                    c
                                                  
                                                  ⁢
                                                  
                                                    e
                                                    j
                                                    c
                                                  
                                                
                                              
                                              )
                                            
                                          
                                        
                                      
                                    
                                    )
                                  
                                
                                +
                                
                                  P
                                  i
                                  D
                                
                              
                              )
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          
                            ∑
                            
                              i
                              ∈
                              N
                            
                          
                          ⁢
                          
                            
                              β
                              i
                              c
                            
                            ⁢
                            
                              (
                              
                                
                                  
                                    ∑
                                    
                                      j
                                      ∈
                                      N
                                    
                                  
                                  ⁢
                                  
                                    (
                                    
                                      
                                        
                                          
                                            
                                              
                                                f
                                                i
                                                c
                                              
                                              ⁡
                                              
                                                (
                                                
                                                  
                                                    
                                                      g
                                                      ij
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      e
                                                      j
                                                      c
                                                    
                                                  
                                                  -
                                                  
                                                    
                                                      b
                                                      ij
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      f
                                                      j
                                                      c
                                                    
                                                  
                                                
                                                )
                                              
                                            
                                            -
                                          
                                        
                                      
                                      
                                        
                                          
                                            
                                              e
                                              i
                                              c
                                            
                                            ⁡
                                            
                                              (
                                              
                                                
                                                  
                                                    g
                                                    ij
                                                    c
                                                  
                                                  ⁢
                                                  
                                                    f
                                                    j
                                                    c
                                                  
                                                
                                                +
                                                
                                                  
                                                    b
                                                    ij
                                                    c
                                                  
                                                  ⁢
                                                  
                                                    e
                                                    j
                                                    c
                                                  
                                                
                                              
                                              )
                                            
                                          
                                        
                                      
                                    
                                    )
                                  
                                
                                +
                                
                                  Q
                                  i
                                  D
                                
                              
                              )
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          
                            ∑
                            
                              
                                (
                                
                                  i
                                  ,
                                  j
                                
                                )
                              
                              ∈
                              T
                            
                          
                          ⁢
                          
                            
                              μ
                              
                                i
                                ,
                                j
                              
                              c
                            
                            ⁡
                            
                              (
                              
                                
                                  
                                    
                                      
                                        
                                          (
                                          
                                            
                                              
                                                e
                                                i
                                                c
                                              
                                              ⁢
                                              
                                                f
                                                j
                                                c
                                              
                                            
                                            -
                                            
                                              
                                                e
                                                j
                                                c
                                              
                                              ⁢
                                              
                                                f
                                                i
                                                c
                                              
                                            
                                          
                                          )
                                        
                                        ⁢
                                        
                                          b
                                          ij
                                          c
                                        
                                      
                                      +
                                    
                                  
                                
                                
                                  
                                    
                                      
                                        
                                          (
                                          
                                            
                                              
                                                
                                                  
                                                    
                                                      (
                                                      
                                                        e
                                                        i
                                                        c
                                                      
                                                      )
                                                    
                                                    2
                                                  
                                                  +
                                                  
                                                    
                                                      (
                                                      
                                                        f
                                                        i
                                                        c
                                                      
                                                      )
                                                    
                                                    2
                                                  
                                                  -
                                                
                                              
                                            
                                            
                                              
                                                
                                                  
                                                    
                                                      e
                                                      i
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      e
                                                      j
                                                      c
                                                    
                                                  
                                                  -
                                                  
                                                    
                                                      f
                                                      i
                                                      c
                                                    
                                                    ⁢
                                                    
                                                      f
                                                      j
                                                      c
                                                    
                                                  
                                                
                                              
                                            
                                          
                                          )
                                        
                                        ⁢
                                        
                                          g
                                          ij
                                          c
                                        
                                      
                                      -
                                      
                                        P
                                        ij
                                        max
                                      
                                    
                                  
                                
                              
                              )
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          
                            ∑
                            
                              i
                              ∈
                              N
                            
                          
                          ⁢
                          
                            
                              γ
                              i
                              c
                            
                            ⁢
                            
                              (
                              
                                
                                  
                                    (
                                    
                                      V
                                      i
                                      min
                                    
                                    )
                                  
                                  2
                                
                                -
                                
                                  
                                    (
                                    
                                      e
                                      i
                                      c
                                    
                                    )
                                  
                                  2
                                
                                -
                                
                                  
                                    (
                                    
                                      f
                                      i
                                      c
                                    
                                    )
                                  
                                  2
                                
                              
                              )
                            
                          
                        
                        +
                      
                    
                  
                  
                    
                      
                        
                          
                            
                              
                                
                                  ∑
                                  
                                    i
                                    ∈
                                    N
                                  
                                
                                ⁢
                                
                                  
                                    θ
                                    i
                                    
                                      c
                                      ⁢
                                      
                                        
                                      
                                    
                                  
                                  ⁡
                                  
                                    (
                                    
                                      
                                        
                                          (
                                          
                                            e
                                            i
                                            c
                                          
                                          )
                                        
                                        2
                                      
                                      +
                                      
                                        
                                          (
                                          
                                            f
                                            i
                                            c
                                          
                                          )
                                        
                                        2
                                      
                                      -
                                      
                                        
                                          (
                                          
                                            V
                                            i
                                            max
                                          
                                          )
                                        
                                        2
                                      
                                    
                                    )
                                  
                                
                              
                              -
                            
                          
                        
                        
                          
                            
                              
                                
                                  ∑
                                  
                                    i
                                    ∈
                                    Γ
                                  
                                
                                ⁢
                                
                                  
                                    λ
                                    i
                                    c
                                  
                                  ⁢
                                  
                                    P
                                    i
                                    
                                      G
                                      ,
                                      c
                                    
                                  
                                
                              
                              -
                              
                                
                                  ∑
                                  
                                    i
                                    ∈
                                    Γ
                                  
                                
                                ⁢
                                
                                  
                                    β
                                    i
                                    c
                                  
                                  ⁢
                                  
                                    Q
                                    i
                                    
                                      G
                                      ,
                                      c
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
                }
              
            
          
        
        ,
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            where
            ⁢
            
              
            
            ⁢
            λ
          
          =
          
            (
            
              
                λ
                0
              
              ,
              
                λ
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                λ
                C
              
            
            )
          
        
        ,
        
          β
          =
          
            
              (
              
                
                  β
                  0
                
                ,
                
                  β
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  β
                  C
                
              
              )
            
            ⁢
            
              
            
            ⁢
            
              etc
              .
            
          
        
      
    
    
      
        (
        37
        )
      
    
  




The Lagrange dual problem of the problem (1) is given by




  
    
      
        
          
            q
            ⁡
            
              (
              
                λ
                ,
                β
                ,
                μ
                ,
                γ
                ,
                θ
              
              )
            
          
          =
          
            
              min
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
                ,
                
                  P
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  Q
                  
                    G
                    ,
                    c
                  
                
              
            
            ⁢
            
              L
              ⁡
              
                (
                
                  
                    e
                    c
                  
                  ,
                  
                    f
                    c
                  
                  ,
                  
                    P
                    
                      G
                      ,
                      c
                    
                  
                  ,
                  
                    Q
                    
                      G
                      ,
                      c
                    
                  
                  ,
                  λ
                  ,
                  β
                  ,
                  μ
                  ,
                  γ
                  ,
                  θ
                
                )
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              f
              1
              c
            
            =
            0
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              (
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
              
              )
            
            ∈
            
              E
              c
            
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              P
              i
              min
            
            ≤
            
              P
              i
              
                G
                ,
                c
              
            
            ≤
            
              P
              i
              max
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            ⁢
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                Q
                i
                min
              
              ≤
              
                Q
                i
                
                  G
                  ,
                  c
                
              
              ≤
              
                Q
                i
                max
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            ⁢
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                
                
                  
                    P
                    i
                    
                      G
                      ,
                      c
                    
                  
                  -
                  
                    P
                    i
                    
                      G
                      ,
                      0
                    
                  
                
                
              
              ≤
              
                Δ
                ⁢
                
                  
                
                ⁢
                
                  P
                  i
                
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              C
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              
                
                
                  
                    Q
                    i
                    
                      G
                      ,
                      c
                    
                  
                  -
                  
                    Q
                    i
                    
                      G
                      ,
                      0
                    
                  
                
                
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                Q
                i
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            .
          
        
      
    
    
      
        (
        38
        )
      
    
  




For any value of the Lagrange multipliers {(λ, β, γ, θ):γ≦0, θ≧0}, the value of the dual function provides a lower bound on an optimal result of the problem (1). To obtain the best lower bound for all possible Lagrange multipliers, the computing system is configured to solve the dual problem as follows:




  
    
      
        
          
            maximize
            
              λ
              ,
              β
              ,
              μ
              ,
              γ
              ,
              θ
            
          
          ⁢
          
            
          
          ⁢
          
            q
            ⁡
            
              (
              
                λ
                ,
                β
                ,
                μ
                ,
                γ
                ,
                θ
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              subject
              ⁢
              
                
              
              ⁢
              to
              ⁢
              
                
              
              ⁢
              μ
            
            ≥
            0
          
          ,
          
            γ
            ≥
            0
          
          ,
          
            θ
            ≥
            0.
          
        
      
    
    
      
        (
        39
        )
      
    
  




The computing system 400 is configured to decompose the problem (38) into C+2 sub-problems as follows:




  
    
      
        
          
            
              minimize
              
                
                  P
                  
                    G
                    ,
                    c
                  
                
                ,
                
                  Q
                  
                    G
                    ,
                    c
                  
                
              
            
            ⁢
            
              f
              ⁡
              
                (
                
                  P
                  
                    G
                    ,
                    0
                  
                
                )
              
            
          
          -
          
            
              ∑
              
                
                  c
                  =
                  0
                
                ,
                ...
                ⁢
                
                  
                
                ,
                C
              
            
            ⁢
            
              {
              
                
                  
                    ∑
                    
                      i
                      ∈
                      Γ
                    
                  
                  ⁢
                  
                    
                      λ
                      i
                      c
                    
                    ⁢
                    
                      P
                      i
                      
                        G
                        ,
                        c
                      
                    
                  
                
                +
                
                  
                    ∑
                    
                      i
                      ∈
                      Γ
                    
                  
                  ⁢
                  
                    
                      β
                      i
                      c
                    
                    ⁢
                    
                      Q
                      i
                      
                        G
                        ,
                        c
                      
                    
                  
                
              
              }
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              P
              i
              min
            
            ≤
            
              P
              i
              
                G
                ,
                c
              
            
            ≤
            
              P
              i
              max
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            ⁢
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                Q
                i
                min
              
              ≤
              
                Q
                i
                
                  G
                  ,
                  c
                
              
              ≤
              
                Q
                i
                max
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            0
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            ⁢
            
              

            
            ⁢
            
              
            
            ⁢
            
              
                
                
                  
                    P
                    i
                    
                      G
                      ,
                      c
                    
                  
                  -
                  
                    P
                    i
                    
                      G
                      ,
                      0
                    
                  
                
                
              
              ≤
              
                Δ
                ⁢
                
                  
                
                ⁢
                
                  P
                  i
                
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              C
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              
                
                
                  
                    Q
                    i
                    
                      G
                      ,
                      c
                    
                  
                  -
                  
                    Q
                    i
                    
                      G
                      ,
                      0
                    
                  
                
                
              
            
            ≤
            
              Δ
              ⁢
              
                
              
              ⁢
              
                Q
                i
              
            
          
          ,
          
            i
            ∈
            Γ
          
          ,
          
            c
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          C
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        and
      
    
    
      
        (
        40
        )
      
    
  
  
    
      
        
          
            
              minimize
              
                
                  e
                  c
                
                ,
                
                  f
                  c
                
              
            
            ⁢
            
              
                ∑
                
                  i
                  ∈
                  N
                
              
              ⁢
              
                
                  λ
                  i
                  c
                
                ⁡
                
                  (
                  
                    
                      ∑
                      
                        j
                        ∈
                        N
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            e
                            i
                            c
                          
                          ⁡
                          
                            (
                            
                              
                                
                                  g
                                  ij
                                  c
                                
                                ⁢
                                
                                  e
                                  j
                                  c
                                
                              
                              -
                              
                                
                                  b
                                  ij
                                  c
                                
                                ⁢
                                
                                  f
                                  j
                                  c
                                
                              
                            
                            )
                          
                        
                        +
                        
                          
                            f
                            i
                            c
                          
                          ⁡
                          
                            (
                            
                              
                                
                                  g
                                  ij
                                  c
                                
                                ⁢
                                
                                  f
                                  j
                                  c
                                
                              
                              +
                              
                                
                                  b
                                  ij
                                  c
                                
                                ⁢
                                
                                  e
                                  j
                                  c
                                
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                  )
                
              
            
          
          +
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                β
                i
                c
              
              ⁡
              
                (
                
                  
                    ∑
                    
                      j
                      ∈
                      N
                    
                  
                  ⁢
                  
                    (
                    
                      
                        
                          f
                          i
                          c
                        
                        ⁡
                        
                          (
                          
                            
                              
                                g
                                ij
                                c
                              
                              ⁢
                              
                                e
                                j
                                c
                              
                            
                            -
                            
                              
                                b
                                ij
                                c
                              
                              ⁢
                              
                                f
                                j
                                c
                              
                            
                          
                          )
                        
                      
                      -
                      
                        
                          e
                          i
                          c
                        
                        ⁡
                        
                          (
                          
                            
                              
                                g
                                ij
                                c
                              
                              ⁢
                              
                                f
                                j
                                c
                              
                            
                            +
                            
                              
                                b
                                ij
                                c
                              
                              ⁢
                              
                                e
                                j
                                c
                              
                            
                          
                          )
                        
                      
                    
                    )
                  
                
                )
              
            
          
          +
          
            
              ∑
              
                
                  (
                  
                    i
                    ,
                    j
                  
                  )
                
                ∈
                T
              
            
            ⁢
            
              
                μ
                
                  i
                  ,
                  j
                
                c
              
              ⁡
              
                (
                
                  
                    
                      (
                      
                        
                          
                            e
                            i
                            c
                          
                          ⁢
                          
                            f
                            j
                            c
                          
                        
                        -
                        
                          
                            e
                            j
                            c
                          
                          ⁢
                          
                            f
                            i
                            c
                          
                        
                      
                      )
                    
                    ⁢
                    
                      b
                      ij
                      c
                    
                  
                  +
                  
                    
                      (
                      
                        
                          
                            (
                            
                              e
                              i
                              c
                            
                            )
                          
                          2
                        
                        +
                        
                          
                            (
                            
                              f
                              i
                              c
                            
                            )
                          
                          2
                        
                        -
                        
                          
                            e
                            i
                            c
                          
                          ⁢
                          
                            e
                            j
                            c
                          
                        
                        -
                        
                          
                            f
                            i
                            c
                          
                          ⁢
                          
                            f
                            j
                            c
                          
                        
                      
                      )
                    
                    ⁢
                    
                      g
                      ij
                      c
                    
                  
                
                )
              
            
          
          +
          
            
              ∑
              
                i
                ∈
                N
              
            
            ⁢
            
              
                (
                
                  
                    θ
                    i
                    c
                  
                  -
                  
                    γ
                    i
                    c
                  
                
                )
              
              ⁢
              
                (
                
                  
                    
                      (
                      
                        e
                        i
                        c
                      
                      )
                    
                    2
                  
                  +
                  
                    
                      (
                      
                        f
                        i
                        c
                      
                      )
                    
                    2
                  
                
                )
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          subject
          ⁢
          
            
          
          ⁢
          to
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            f
            1
            c
          
          =
          0
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            (
            
              
                e
                c
              
              ,
              
                f
                c
              
            
            )
          
          ∈
          
            
              E
              c
            
            .
          
        
      
    
    
      
        (
        41
        )
      
    
  




FIG. 4 illustrates an exemplary hardware configuration of the computing system 400 that runs the method steps described in FIGS. 1-3. The hardware configuration preferably has at least one processor or central processing unit (CPU) 411. The CPUs 411 are interconnected via a system bus 412 to a random access memory (RAM) 414, read-only memory (ROM) 416, input/output (I/O) adapter 418 (for connecting peripheral devices such as disk units 421 and tape drives 440 to the bus 412), user interface adapter 422 (for connecting a keyboard 424, mouse 426, speaker 428, microphone 432, and/or other user interface device to the bus 412), a communication adapter 434 for connecting the system 400 to a data processing network, the Internet, an Intranet, a local area network (LAN), etc., and a display adapter 436 for connecting the bus 412 to a display device 438 and/or printer 439 (e.g., a digital printer of the like).
As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon. In a further embodiment, the computing system analyzes properties of the enterprise and market social networks to build features for predictive models of a propensity for a customer to buy a product, or to close a deal in a particular period of time.
Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with a system, apparatus, or device running an instruction.
A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with a system, apparatus, or device running an instruction.
Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.
Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may run entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).
Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which run via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.
The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which run on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.
The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more operable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be run substantially concurrently, or the blocks may sometimes be run in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

## Claims

1. A method for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request, the method comprising:
creating, by using a computing system including at least one memory device and at least one processor connected to the memory device, an optimization problem for calculating the amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint and the one or more customer request, the at least one contingency constraint including one or more of: a transmission line failure, a power generator failure, a transformer failure, a structure of a power distribution network, and a topology of the power distribution network, wherein said optimization problem is based on an electric optimal power flow problem according to:


min f(u0)



s.t.hc(xc,uc)=0



gc(xc,uc)≦0



|uci−u0i|≦Δuimax,iεG,c=0, . . . ,C, 



where c=0 represents an electric power system having no occurrence of contingency constraint, c=1, . . . , C, is a variable representing a contingency constraint, xc is a vector of state variables for a c-th configuration, uc is a vector of control variables, and f(u0)=ΣiεG(c0i(u0i)2+c1iu0i+c2i) is a generation cost with cost parameters c0i, c1i, c2i≧0, where G is a set of generators, and C is the number of contingency constraints, where Δuimax is a pre-determined maximal allowed variation of control variables, and hc and gc are respective operational constraints including AC power flow balance equations;
running, by using the computing system, the optimization problem in real-time; and
outputting, from the optimization problem run by the computing system, an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.

2. The method according to claim 1, wherein the step of running the optimization problem includes:
solving, by the computing system, the optimization problem without considering the at least one contingency constraint;
checking, by the computing system, whether a result of the computed optimization problem satisfies the at least one contingency constraint;
outputting, by the computing system, the result in response to determining that the result satisfies the at least one contingency constraint;
pruning, by computing system, in response to determining that the result does not satisfy the at least one contingency constraint, one or more results of the optimization problem that do not satisfy the at least one contingency constraint; and
solving, by the computing system, the optimization problem with the pruned results.

3. The method according to claim 1, wherein the step of running the optimization problem includes:
generating, by the computing system, a template to solve the optimization problem;
reformulating, by the computing system, the optimization problem based on the generated template;
forming, by the computing system, an augmented Lagrangian for the reformulated optimization problem;
initializing, by the computing system, Lagrangian multipliers and decision variables according to the at least one contingency constraint; and
solving, by the computing system, the reformulated optimization problem with the initialized Lagrangian multipliers and decision variables, based on an alternating direction method of multipliers.

4. The method according to claim 3, further comprising:
breaking the reformulated optimization problem into one or more sub-problems;
solving the one or more sub-problems with the initialized Lagrangian multipliers and decision variables, based on the formed augmented Lagrangian;
evaluating whether a solution of the one or more sub-problems meets a stopping criterion;
outputting the solution in response to determining that the solution meets the stopping criterion; and
updating the Lagrangian multipliers based on the solution, in response to determining that the solution does not meet the stopping criterion.

5. The method according to claim 1, wherein the step of running the optimization problem includes:
building a tree data structure, each node of the tree data structure describing a possible solution of the optimization problem;
computing, at each node of the built tree data structure, an upper bound and lower bound of an objective function for determining the cost for generating the electric power, the lower bound being calculated from Lagrange duality, the upper bound being calculated from an interior-point method;
evaluating, at each node of the built tree data structure, whether the computed upper bound and computed lower bound satisfy a stopping criterion;
outputting the computed upper bound and the computed lower bound in response to determining that the computed upper bound and computed lower bound satisfy the stopping criterion;
applying at least one branching procedure on the tree data structure in response to determining that the computed upper bound and computed lower bound do not satisfy the stopping criteria;
re-computing the lower bound in a region in the tree data structure branched according to the applied branching procedure;
updating the upper bound in the region in the tree data structure;
deleting nodes in the region based on the re-computed the lower bound and updated upper bound or an intersection of the branched region and an original feasible set, the original feasible set referring to possible solutions of the optimization problem satisfying the at least one contingency constraint; and
repeating the step of evaluating, the step of the outputting, the step of applying, the step of re-computing, the step of updating, and the step of deleting.

6. The method according to claim 5, wherein the stopping criterion includes one or more of:
a gap between a smallest computed lower bound and the computed upper bound is lower than a pre-determined threshold, or the tree data structure is empty.

7. The method according to claim 5, wherein the at least one branching procedure includes one or more of: ellipsoidal bisection and rectangular bisection.

8. The method according to claim 1, wherein the one or more customer request includes: a demand or load for a certain amount of the electric power.

9. A system for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request, the system comprising:
at least one memory device;
at least one processor connected to the memory device,
wherein the processor is configured to:
create an optimization problem for calculating an amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint and the one or more customer request, the at least one contingency constraint including one or more of: a transmission line failure, a power generator failure, a transformer failure, a structure of a power distribution network, and a topology of the power distribution network, wherein said optimization problem is based on an electric optimal power flow problem according to:


min f(u0)



s.t.hc(xc,uc)=0



gc(xc,uc)≦0



|uci−u0i|≦Δuimax,iεG,c=0, . . . ,C, 



where c=0 represents an electric power system having no occurrence of contingency constraint, c=1, . . . , C, is a variable representing a contingency constraint, xc is a vector of state variables for a c-th configuration, uc is a vector of control variables, and f(u0)=ΣiεG(c0i(u0i)2+c1iu0i+c2i) is a generation cost with cost parameters c0i, c1i, c2i≧0, where G is a set of generators, and C is the number of contingency constraints, where Δuimax is a pre-determined maximal allowed variation of control variables, and hc and gc are respective operational constraints including AC power flow balance equations;
run the optimization problem in real-time; and
output, from the optimization problem, an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.

10. The system according to claim 9, wherein to run the optimization problem, the processor is further configured to:
solve the optimization problem without considering the at least one contingency constraint;
check whether a result of the computed optimization problem satisfies the at least one contingency constraint;
output the result in response to determining that the result satisfies the at least one contingency constraint;
prune, in response to determining that the result does not satisfy the at least one contingency constraint, one or more results of the optimization problem that do not satisfy the at least one contingency constraint; and
solve the optimization problem with the pruned results.

11. The system according to claim 9, wherein to run the optimization problem, the processor is further configured to:
generate a template to solve the optimization problem;
reformulate the optimization problem based on the generated template;
form an augmented Lagrangian for the reformulated optimization problem;
initialize Lagrangian multipliers and decision variables according to the at least one contingency constraint; and
solve the reformulated optimization problem with the initialized Lagrangian multipliers and decision variables, based on an alternating direction method of multipliers.

12. The system according to claim 11, wherein the processor is further configured to:
break the reformulated optimization problem into one or more sub-problems;
solve the one or more sub-problems with the initialized Lagrangian multipliers and decision variables, based on the formed augmented Lagrangian;
evaluate whether a solution of the one or more sub-problems meets a stopping criterion;
outputting the solution in response to determining that the solution meets the stopping criterion; and
update the Lagrangian multipliers based on the solution, in response to determining that the solution does not meet the stopping criterion.

13. The system according to claim 9, wherein to run the optimization problem, the processor is further configured to:
build a tree data structure, each node of the tree data structure describing a possible solution of the optimization problem;

compute, at each node of the built tree data structure, an upper bound and lower bound of an objective function, the objective function determining the cost for generating the electric power, the lower bound being calculated from Lagrange duality, the upper bound being calculated from an interior-point method;
evaluate, at each node of the built tree data structure, whether the computed upper bound and computed lower bound satisfy a stopping criterion;
output the computed upper bound and the computed lower bound in response to determining that the computed upper bound and computed lower bound satisfy the stopping criterion;
apply at least one branching procedure on the tree data structure in response to determining that the computed upper bound and computed lower bound do not satisfy the stopping criteria;
re-compute the lower bound in a region in the tree data structure branched according to the applied branching procedure;
update the upper bound in the region in the tree data structure;
delete nodes in the region based on the re-computed the lower bound and updated upper bound or an intersection of the branched region and an original feasible set, the original feasible set referring to possible solutions of the optimization problem satisfying the at least one contingency constraint; and
repeat the evaluate, the output, the apply, the re-compute, the update, and the delete.

14. The system according to claim 13, wherein the stopping criterion includes one or more of:
a gap between a smallest computed lower bound and the computed upper bound is lower than a pre-determined threshold, or the tree data structure is empty.

15. The system according to claim 13, wherein the at least one branching procedure includes one or more of: ellipsoidal bisection and rectangular bisection.

16. The system according to claim 9, wherein the one or more customer request includes: a demand or load for a certain amount of the electric power.

17. A computer program product for determining an electricity dispatch plan of an electric power system with a total cost for determining an amount of an electric power to generate in an electric power system and determining a total cost for generating the amount of electric power while satisfying at least one contingency constraint and one or more customer request, the computer program product comprising a non-transitory storage medium readable by a processing circuit and storing instructions run by the processing circuit for performing a method, the method comprising:
creating an optimization problem for calculating an amount of the electric power to be generated and a total cost for generating the calculated amount of the electric power while meeting the at least one contingency constraint and the one or more customer request, the at least one contingency constraint including one or more of: a transmission line failure, a power generator failure, a transformer failure, a structure of a power distribution network, and a topology of the power distribution network, wherein said optimization problem is based on an electric optimal power flow problem according to:


min f(u0)



s.t.hc(xc,uc)=0



gc(xc,uc)≦0



|uci−u0i|≦Δuimax,iεG,c=0, . . . ,C, 



where c=0 represents an electric power system having no occurrence of contingency constraint, c=1, . . . , C, is a variable representing a contingency constraint, xc is a vector of state variables for a c-th configuration, uc is a vector of control variables, and f(u0)=ΣiεG(c0i(u0i)2+c1iu0i+c2i) is a generation cost with cost parameters c0i, c1i, c2i≧0, where G is a set of generators, and C is the number of contingency constraints, where Δuimax is a pre-determined maximal allowed variation of control variables, and hc and gc are respective operational constraints including AC power flow balance equations;
running the optimization problem in real-time; and
outputting an output specifying the calculated amount of the electric power and the total cost to generate the calculated amount of the electric power.

18. The computer program product according to claim 17, wherein the step of running the optimization problem includes:
solving the optimization problem without considering the at least one contingency constraint;
check whether a result of the computed optimization problem satisfies the at least one contingency constraint;
output the result in response to determining that the result satisfies the at least one contingency constraint;
prune, in response to determining that the result does not satisfy the at least one contingency constraint, one or more results of the optimization problem that do not satisfy the at least one contingency constraint; and
solve the optimization problem with the pruned results.

19. The computer program product according to claim 17, wherein the step of running the optimization problem includes:
generating a template to solve the optimization problem;
reformulating the optimization problem based on the generated template;
forming an augmented Lagrangian for the reformulated optimization problem;
initializing Lagrangian multipliers and decision variables according to the at least one contingency constraint; and
solving the reformulated optimization problem with the initialized Lagrangian multipliers and decision variables, based on an alternating direction method of multipliers.

20. The computer program product according to claim 19, wherein the method further comprises:
breaking the reformulated optimization problem into one or more sub-problems;
solving the one or more sub-problems with the initialized Lagrangian multipliers and decision variables, based on the formed augmented Lagrangian;
evaluating whether a solution of the one or more sub-problems meets a stopping criterion;
outputting the solution in response to determining that the solution meets the stopping criterion; and
updating the Lagrangian multipliers based on the solution, in response to determining that the solution does not meet the stopping criterion.

21. The computer program product according to claim 17, wherein the step of running the optimization problem includes:
building a tree data structure, each node of the tree data structure describing a possible solution of the optimization problem;
computing, at each node of the built tree data structure, an upper bound and lower bound of an objective function, the objective function determining the cost for generating the electric power, the lower bound being calculated from Lagrange duality, the upper bound being calculated from an interior-point method;
evaluating, at each node of the built tree data structure, whether the computed upper bound and computed lower bound satisfy a stopping criterion;
outputting the computed upper bound and the computed lower bound in response to determining that the computed upper bound and computed lower bound satisfy the stopping criterion;
applying at least one branching procedure on the tree data structure in response to determining that the computed upper bound and computed lower bound do not satisfy the stopping criteria;
re-computing the lower bound in a region in the tree data structure branched according to the applied branching procedure;
updating the upper bound in the region in the tree data structure;
deleting nodes in the region based on the re-computed the lower bound and updated upper bound or an intersection of the branched region and an original feasible set, the original feasible set referring to possible solutions of the optimization problem satisfying the at least one contingency constraint; and
repeating the step of evaluating, the step of the outputting, the step of applying, the step of re-computing, the step of updating, and the step of deleting.

22. The computer program product according to claim 21, wherein the stopping criterion includes one or more of:
a gap between a smallest computed lower bound and the computed upper bound is lower than a pre-determined threshold, or the tree data structure is empty.

23. The computer program product according to claim 21, wherein the at least one branching procedure includes one or more of: ellipsoidal bisection and rectangular bisection.

24. The computer program product according to claim 17, wherein the one or more customer request includes: a demand or load for a certain amount of the electric power.