(373ag) An Enhanced Column and Constraint Generation Method for Adaptive Robust Optimization with Non-Convex Subproblems

We propose an enhanced column and constraint generation (CCG) method for two-stage adaptive robust optimization (ARO) problems. The proposed method is computationally more efficient than the traditional one and has new capabilities to handle nonlinear programming (NLP) subproblems. We illustrate the characteristics and performance of the enhanced CCG method using the optimal scheduling/contracting problem of a virtual power plant (VPP) (Lima et al., 2015; Lima et al., 2018). In this problem, wind power production and electricity prices in the pool market are considered uncertain.

Bertsimas et al. (2013) and Zeng and Zhao (2013) pioneered the development of a CCG method suitable for two-stage adaptive robust optimization. This CCG method plays an important role in the solution of ARO problems due to its capability to handle the two-level structure of ARO problems. Its main characteristic is the addition of primal variables and constraints from the subproblem to the master problem at each iteration, instead of adding an optimality cut.

In Bertsimas et al. (2013), the authors have derived an ARO formulation and applied the CCG method to solve it. However, they have mainly focused on the unit commitment problem and its solutions. Zeng and Zhao (2013) described formally the main characteristics of the CCG method for ARO. These authors demonstrated that the primal variables and constraints added to the master problem in the CCG method are as tight as Benders-based optimality cuts added to the master problem. Besides, they show that the computational performance of the CCG method is superior to an approach with optimality cuts.

We propose an enhanced CCG method with two phases: phase I and II. In phase I, the objective is to improve the upper bound (considering an ARO maximization problem) of the optimal objective function by obtaining feasible solutions from the subproblem; whereas, in phase II, the objective is to improve the lower bound of the optimal objective function. The enhanced CCG method moves from phase I to phase II, and it can return to phase I from phase II. The move from phase I to phase II is triggered by a new bound that is calculated from information of the subproblem. The enhanced CCG method uses this two-phase approach for ARO problems with mixed integer linear programming (MILP) or NLP subproblems.

In ARO formulations, MILP subproblems arise if discrete uncertainty sets are used to characterize the uncertain parameters, whereas NLP subproblems arise from using continuous uncertainty sets.

We address the VPP problem using an ARO formulation with two alternative descriptions of the uncertainty sets: discrete and continuous. For the VPP problem, we select a specific case study that leads the CCG method to perform a significant number of iterations to converge. For both types of subproblems, this behavior is used to explain the characteristics of the upper bound, the lower bound, and the new bound of the enhanced CCG method.

The results show that for MILP subproblems the computational performance of the enhanced CCG method is superior to that of the CCG method. For NLP subproblems, we provide the relationship between the quality of the bounds obtained and the budget of time given to the solution of the subproblems.

We perform a thorough comparison between the scheduling and market involvement of the VPP results obtained with the two alternative uncertainty sets. In addition, we analyze the corresponding results in terms of worse output of the uncertainty parameters for both types of uncertainty sets. We conclude with a risk management analysis made using a verification step of a Monte Carlo Sample Average Approximation methodology.

References

Bertsimas D., Litvinov E., Sun X.A., Zhao J., Zheng T., 2013. Adaptive Robust Optimization for the Security Constrained Unit Commitment Problem. IEEE Transactions on Power Systems 28 (1), 52–63.

Lima R.M., Conejo A.J., Langodan S., Hoteit I., Knio O.M., 2018. Risk-averse formulations and methods for a virtual power plant. Computers & Operations Research 96, 350 – 373.

Lima, R. M., Novais, A. Q., Conejo, A. J., 2015. Weekly self-scheduling, forward contracting, and pool involvement for an electricity producer. An adaptive robust optimization approach. European Journal of Operational Research 240 (2), 457–475.

Zeng B., Zhao L., 2013. Solving two-stage robust optimization problems using a column- and-constraint generation method. Operations Research Letters 41 (5), 457–461.