Abstract—Most Independent System Operators (ISOs) adopt the Bid Cost Minimization (BCM) to select offers and their respective generation levels while minimizing the total bid cost. It was shown that the customer payment costs that result from selected offers can differ significantly from the customer payments resulting from the Payment Cost Minimization (PCM), under which payment costs are minimized directly. In order to solve the PCM in the dual space, the Lagrangian relaxation and surrogate optimization approach is frequently used. When standard optimization methods, such as branch-and-cut, become ineffective due to the large size of a problem, the Lagrangian relaxation and surrogate optimization approach provides a good feasible solution within a reasonable CPU time. The convergence of the standard Lagrangian relaxation and surrogate subgradient approach depends on the optimal dual value, which is usually unknown. Furthermore, when using the surrogate subgradient approach, the upper bound property is lost, so additional conditions are needed to ensure convergence. The main goal of this paper is to develop a convergent variation of the surrogate subgradient method without invoking the optimal dual value, and show the relevance and effectiveness of the new method for solving large constrained optimization problems, such as the PCM.
URRENTLY, most ISOs in the United States adopt the bid cost minimization (BCM) settlement mechanism for minimizing total offer costs. In this setup, customer payment costs, which are determined by a mechanism that assigns uniform market clearing prices (MCPs), are different from the minimized offer costs. An alternative method to determine customer payment costs is to minimize them directly; the payment cost minimization (PCM) mechanism accomplishes this task. Despite the fact that the direct minimization of payment costs arguably results in lower customer payment costs than those obtained by the minimization of offer costs, the question of the whether the payment Cost Minimization (PCM) mechanism is beneficial for power markets still remains open. There have been several attempts to compare bid- versus payment- cost minimization mechanisms (e.g., , ). The purpose of this paper, however, is not to discuss advantages and disadvantages of the PCM mechanism compared to the existing settlement mechanisms, but rather to develop a new convergent surrogate subgradient method for solving mixed-integer problems (MIPs), prove its convergence without invoking the optimal dual value and apply this approach to solving the PCM problem in the dual space.
The branch-and-cut method has been of big interest for solving integer programming problems. In the branch-and-cut approach the valid cuts are added to obtain the convex hull of feasible solution after relaxing the integrality constraints. Branching is then frequently used to decompose the problem. However, the efficiency of solving...