ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming

1. Problem Statement

Two-Stage Stochastic Programming (2SP) is a fundamental framework for decision-making under uncertainty, where first-stage decisions are made before uncertainty is resolved, and second-stage (recourse) decisions are made after the realization of random variables.

• The Challenge: Solving 2SP problems is computationally demanding. The standard approach, Sample Average Approximation (SAA), leads to massive "extensive form" problems that scale linearly with the number of scenarios, often becoming intractable.
• Existing Learning-Based Solutions: Recent methods like Neur2SP use Neural Networks (NNs) as surrogates to approximate the expected recourse function. However, embedding standard NNs (with ReLU activations) into optimization models requires Mixed-Integer Programming (MIP) formulations. These MIP formulations introduce binary variables for every neuron, causing the problem size and computational complexity to grow exponentially with network depth and width, limiting scalability.
• The Gap: There is a need for a surrogate modeling approach that maintains the generality of neural networks but avoids the computational intractability of MIP embeddings, specifically for problems where the recourse function exhibits convexity.

2. Methodology: ICNN-enhanced 2SP

The authors propose ICNN-enhanced 2SP, a framework that replaces standard ReLU NNs with Input Convex Neural Networks (ICNNs) to approximate the recourse function.

Core Concept

• ICNN Architecture: Unlike standard feed-forward networks, ICNNs are architecturally constrained to ensure the output is convex with respect to the input. This is achieved by:
  • Using non-negative weights for hidden layers.
  • Employing convex, non-decreasing activation functions (e.g., ReLU).
  • Utilizing skip connections to propagate inputs directly to deeper layers.
• LP Representability: A key theoretical property of ICNNs is that their inference (finding the output for a given input) is mathematically equivalent to solving a Linear Programming (LP) problem.
• The Workflow:
  1. Data Generation: Generate training pairs $(x, Q(x))$ by solving the second-stage problem for various first-stage decisions $x$ across sampled scenarios.
  2. Surrogate Training: Train an ICNN to approximate the expected recourse function $Q(x)$. The architecture follows the Neur2SP structure:
     • Scenario Encoding: A shared network processes scenario data into a latent vector $\xi_\lambda$.
     • Decision Mapping: An ICNN $\Phi$ maps the first-stage decision $x$ and the scenario vector $\xi_\lambda$ to the expected cost.
  3. Exact Embedding: Instead of embedding the ICNN as a MIP (which requires binary variables), the trained ICNN is embedded into the 2SP reformulation as an LP constraint set.
     • The non-linear ReLU activations are transformed into linear inequalities using an epigraph representation.
     • The resulting reformulated 2SP is a pure Mixed-Integer Linear Program (MILP) (if first-stage variables are integer) or LP (if continuous), without the auxiliary binary variables required by standard NN embeddings.

3. Theoretical Foundation

The paper rigorously analyzes the convexity of the recourse function $Q(x)$ to justify the use of ICNNs:

• Continuous Recourse: If both first and second-stage variables are continuous, $Q(x)$ is proven to be convex (as the pointwise maximum of affine functions via LP duality).
• Mixed-Integer First-Stage: If first-stage variables are integer but second-stage are continuous, $Q(x)$ remains convex over the convex hull of the feasible set.
• Mixed-Integer Recourse: If second-stage variables are also integer, $Q(x)$ is generally non-convex. However, the authors argue that in many practical settings (e.g., inventory, energy), the function exhibits quasi-convexity or "piecewise convex" structures that ICNNs can approximate effectively.
• Conclusion: For a broad class of 2SP problems, the recourse function is sufficiently convex or near-convex to be accurately modeled by ICNNs, enabling exact LP-based embedding.

4. Key Contributions

1. Novel Integration: First integration of ICNNs into the 2SP paradigm to approximate the expected recourse function while preserving convexity.
2. Elimination of Integer Variables: By leveraging the LP-representability of ICNNs, the method eliminates the need for the auxiliary binary variables inherent in MIP-based NN embeddings (Neur2SP).
3. Exact Embedding: The approach provides an exact reformulation of the surrogate model within the optimization framework, avoiding approximation errors common in other surrogate methods.
4. Scalability: The method transforms the surrogate embedding from an NP-hard MIP problem into a tractable LP (or MILP with only original integer variables), significantly reducing computational complexity.

5. Experimental Results

The authors evaluated the method on three benchmark problems: Capacitated Facility Location (CFLP), Stochastic Server Location (SSLP), and Investment (INVP).

• Training Performance:
  • ICNNs required only marginally longer training times (approx. 10% overhead) compared to standard ReLU NNs due to convexity constraints.
  • Validation accuracy (MAE) was comparable to or better than standard NNs in 7 out of 10 instances, suggesting the recourse functions in these benchmarks are indeed well-approximated by convex functions.
• Solving Performance (Inference):
  • Speed: ICNN-enhanced 2SP was significantly faster than Neur2SP. Speedups ranged from 1.3x for small instances to 100x for large, complex instances (e.g., CFLP_50_50).
  • Scalability: As the number of scenarios and problem size increased, the performance gap widened. Neur2SP often hit time limits (3 hours) or failed to find high-quality solutions, while ICNN-enhanced 2SP solved instances in seconds.
  • Solution Quality: The method maintained solution quality comparable to or superior to Neur2SP and the Extensive Form (EF) baseline. In many large-scale cases, it found better solutions than EF within the time limit.
• Formulation Size: The ICNN reformulation reduced the number of auxiliary continuous variables by 50% and completely eliminated auxiliary binary variables compared to Neur2SP.

6. Significance and Implications

• Computational Efficiency: The primary contribution is solving the scalability bottleneck of learning-based 2SP. By replacing MIP embeddings with LP embeddings, the method makes it feasible to solve large-scale stochastic programs in real-time or near-real-time.
• Practical Applicability: The approach is particularly valuable for time-critical applications like power dispatch and production scheduling, where frequent re-optimization is required, and MIP-based alternatives are prohibitively expensive.
• Limitations & Future Work: The method relies on the convexity (or near-convexity) of the recourse function. It is not suitable for highly non-convex recourse problems where standard ReLU NNs are necessary. Future work may explore hybrid architectures or extensions to nonlinear convex settings.

In summary, ICNN-enhanced 2SP successfully bridges the gap between the expressivity of deep learning and the tractability of convex optimization, offering a scalable, high-fidelity alternative for solving complex stochastic programming problems.