Alternating Mixed-Integer Programming and Neural Network Training for Approximating Stochastic Two-Stage Problems

Jan Kronqvist, Boda Li, Jan Rolfes, Shudian Zhao

Abstract

Two-stage stochastic programs (2SPs) are essential for decision-making under uncertainty, yet they become computationally intractable when the second stage involves discrete variables. Traditional deterministic equivalent models scale poorly as the number of scenarios increases. This paper discusses a novel approach that approximates the expected value of the second-stage problem using a neural network (NN). By encoding the NN into the first-stage mixed-integer linear program (MILP) and utilizing an alternating algorithm that iteratively refines the NN's accuracy around the optimal solution, the researchers demonstrate significant improvements in both computational efficiency and solution quality in power system applications.

Introduction

In many infrastructure and economic systems, decisions must be made in two distinct phases: a "here-and-now" decision (Stage 1) followed by a "wait-and-see" recourse decision (Stage 2) after uncertain parameters—such as weather or market prices—are revealed. When Stage 2 includes discrete decisions (e.g., unit commitment in power grids), the resulting 2SP is NP-complete.

The standard approach to solving these problems involves creating a deterministic equivalent, which replicates the second-stage constraints for every possible scenario. However, as the scenario count grows to capture the true distribution of uncertainty, the resulting MILP becomes too large for modern solvers. This research proposes a surrogate-based optimization method that replaces the expensive second-stage expectation with a neural network approximation, specifically focusing on an iterative "alternating" training strategy to ensure local accuracy near the optimal operating point.

Methodology

Neural Network Encoding

The researchers utilize a neural network with Rectified Linear Unit (ReLU) activation functions to approximate the second-stage cost function. Because ReLU functions are piecewise linear, the entire NN can be mathematically encoded into a MILP using "Big-M" constraints. This allows a standard solver, such as Gurobi, to optimize the first-stage variables while treating the NN as a functional component of the objective landscape.

The Alternating Algorithm (MIP-NN 2SP)

The core innovation of this work is the MIP-NN 2SP algorithm, which moves away from static training. Instead of training the NN once on a broad, uniform dataset, the algorithm employs an iterative loop:

  1. Solve: The first-stage MILP is solved using the current NN approximation to find a candidate optimal decision.
  2. Sample: New data points are generated by sampling the second-stage costs specifically in the neighborhood of the current candidate decision.
  3. Retrain: The NN is updated with this targeted data, improving its fidelity in the most relevant regions of the search space.
  4. Repeat: The process continues until the first-stage decisions stabilize.

This "active learning" approach addresses the "boundary problem," where optimization solutions often lie at the edges of the feasible region—areas where standard neural networks typically struggle with accuracy if trained on uniform distributions.

Case Study: Power System Operations

The methodology was validated using a power systems scheduling case study based on the MATPOWER "case5.m" 5-bus instance. The model incorporated real-world uncertainty using:

  • Market Data: Price data from the Pecan Street "miso" dataset.
  • Renewables/Demand: Data from the California ISO for four seasons in 2022.
  • Scenarios: 400 distinct scenarios for renewable energy production to simulate high-dimensional uncertainty.

Results and Discussion

The alternating method was compared against a baseline approach that used the same volume of data but sampled it uniformly across the entire decision space.

Accuracy and Cost Efficiency

In the "Summer" scenario, the baseline method exhibited a significant $80,000 gap** between the cost predicted by the NN and the actual expected cost. The proposed alternating method virtually eliminated this gap, providing a much more reliable surrogate. Consequently, by identifying a more precise operating point for conventional generators, the alternating algorithm achieved approximately **$20,000 in operational savings compared to the baseline.

Computational Performance

The NN-encoded MILP proved highly efficient, solving in approximately 5 seconds on a standard laptop. Furthermore, the generation of training data for the retraining steps is highly parallelizable, making the total runtime suitable for day-ahead scheduling environments where decisions must be finalized within tight windows.

Conclusion

By bridging the gap between mixed-integer programming and deep learning, the alternating MIP-NN approach provides a scalable path for solving complex stochastic problems. The iterative refinement of the neural surrogate ensures that the model is most accurate where it matters most: near the optimal solution. Future research will focus on scaling this approach to larger grid systems and extending the framework to handle the non-linearities inherent in AC Optimal Power Flow (ACOPF) models.

Summary updated

BibTeX
@inproceedings{kronqvist2023alternating,
  author = {Jan Kronqvist and Boda Li and Jan Rolfes and Shudian Zhao},
  title = {{Alternating Mixed-Integer Programming and Neural Network Training for Approximating Stochastic Two-Stage Problems}},
  booktitle = {Lod},
  year = {2023},
  doi = {10.1007/978-3-031-53966-4\_10},
}
Figure