Systems and methods for solving large scale stochastic unit commitment problems

• US 10,417,571 B2
• Filed: 05/11/2015
• Issued: 09/17/2019
• Est. Priority Date: 03/07/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kalagnanam, Jayant R., Koc, Ali
• Primary Examiner(s): Chang, Li Wu
• Application Number:
  US14/708,814
• Publication Number:
  US 20150242757A1
• Time in Patent Office: 1,590 Days
• Field of Search: None
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management

Abstract

The present disclosure relates generally to computational solution algorithms (and associated systems and methods) applied to a stochastic unit commitment problem. In one example, the computational solution algorithms (and associated systems and methods) may be applied to the energy industry.

Claims

1. A computer-system for operating a plurality of power generators, the system comprising one or more processor units configured for:

iteratively generating in a sequential manner a plurality of candidate columns by operating on a restricted master linear problem and a corresponding dual problem each of the candidate columns comprising a schedule for a respective power generator; and

solving, using plural processing units, in parallel for at least two of the candidate columns, a pricing problem, wherein a framework generating a branch-and-bound tree is run to generate column and cuts at every node of the tree in parallel using said plural processing units;

wherein the generation of the candidate columns includes;

maintaining a list of k best lower bounds and corresponding dual solutions;

as the column generation proceeds, checking a lower bound at each iteration and, if the checked lower bound is larger than at least one of the lower bounds in the list, inserting the checked lower bound into an appropriate position in the list;

at each iteration of the candidate column generation using a weighted dual solution to solve the pricing problem,

determining a schedule and generation amounts for the plurality of power generators in a pre-defined time horizon based on solving the pricing problem for each of a plurality of power generators; and

generating power at times specified by said schedule and according to said generation amounts at the plurality of power generators in the pre-defined time horizon.

2. The system of claim 1,

wherein the restricted master linear problem comprises:

min c′

λ

s.t. A′

λ

≥

b;

θ

*

eλ

=1;

α

*

λ

≥

0;

wherein the corresponding dual problem comprises;

max α

s.t. θ

(A′

−

b)+α

≤

c′

;

λ

*

θ

≥

0;

wherein the pricing problem comprises;

3. The system of claim 1, wherein the stochastic unit commitment problem relates to energy.

4. The system of claim 1, wherein the steps are carried out in the order recited.

6. The system of claim 1, wherein:

to solve the pricing problem, at each iteration, the candidate column generation using a weighted dual solution θ

, wherein θ

=wθ

*+w₁θ

₁+ . . . +w_kwθ

_k, w≥

0,i=1, . . . , k, w+Σ

_{i=1, . . . , k}w_i=1, and wherein θ

₁, . . . , θ

_k corresponds to the dual solutions that are in the list.

5. An article of manufacture, comprising:

at least one non-transitory computer usable medium having a computer readable program code logic tangibly embodied therein to execute at least one machine instruction in a processing unit of a computer system for operating a plurality of generators, said computer readable program code logic, when executing on one or more processing units, performing the following steps;

iteratively generating in a sequential manner a plurality of candidate columns by operating on a restricted master linear problem and a corresponding dual problem, each of the candidate columns comprising a schedule for a respective power generator; and

solving, using plural processing units, in parallel for at least two of the candidate columns, a pricing problem, wherein a framework generating a branch-and-bound tree is run to generate column and cuts at every node of the tree in parallel using said plural processing units,

wherein the generation of the candidate columns includes;

maintaining a list of k best lower bounds and corresponding dual solutions;

as the column generation proceeds, checking a lower bound at each iteration and, if the checked lower bound is larger than at least one of the lower bounds in the list, inserting the checked lower bound into an appropriate position in the list;

at each iteration of the candidate column generation using a weighted dual solution to solve the pricing problem,

determining schedule and generation amounts for the plurality of power generators in a pre-defined time horizon based on solving the pricing problem for each of a plurality of power generators; and

generating power at times specified by said schedule and according to said generation amounts at the plurality of power generators in the pre-defined time horizon.

7. The article of manufacture of claim 5, wherein:

to solve the pricing problem, at each iteration, the candidate column generation using a weighted dual solution θ

, wherein θ

=wθ

*+w₁θ

₁+ . . . +w_kwθ

_k, w≥

0,i=1, . . . , k, w+Σ

_{i=1, . . . , k}w_i=1, and wherein θ

₁, . . . , θ

_k corresponds to the dual solutions that are in the list.