11institutetext: Institute of Biomedical Engineering, University of Oxford
22institutetext: Nuffield Department of Women’s and Reproductive Health,
University of Oxford

# Dual Conditioned Diffusion Models for Out-Of-Distribution Detection:
Application to Fetal Ultrasound Videos

Divyanshu Mishra 11 He Zhao 11 Pramit Saha 11 Aris T. Papageorghiou 22
J.Alison Noble 11

###### Abstract

Out-of-distribution (OOD) detection is essential to improve the reliability of
machine learning models by detecting samples that do not belong to the
training distribution. Detecting OOD samples effectively in certain tasks can
pose a challenge because of the substantial heterogeneity within the in-
distribution (ID), and the high structural similarity between ID and OOD
classes. For instance, when detecting heart views in fetal ultrasound videos
there is a high structural similarity between the heart and other anatomies
such as the abdomen, and large in-distribution variance as a heart has 5
distinct views and structural variations within each view. To detect OOD
samples in this context, the resulting model should generalise to the intra-
anatomy variations while rejecting similar OOD samples. In this paper, we
introduce dual-conditioned diffusion models (DCDM) where we condition the
model on in-distribution class information and latent features of the input
image for reconstruction-based OOD detection. This constrains the generative
manifold of the model to generate images structurally and semantically similar
to those within the in-distribution. The proposed model outperforms reference
methods with a 12% improvement in accuracy, 22% higher precision, and an 8%
better F1 score.

##  1 Introduction

Existing out-of-distribution (OOD) detection methods work well when the in-
distribution (ID) classes have low heterogeneity (low variance) but fail when
in-distribution classes have high heterogeneity [23] or high spatial
similarity between ID and OOD classes [9]. Fetal ultrasound (US) anatomy
detection is one such application where both the challenges co-exist.

In this paper, we propose a Dual-Conditioned Diffusion Model (DCDM) to detect
OOD samples when in-distribution data has high variance and test the
performance by detecting heart views in fetal US videos as an example
application. Specifically, an Ultrasound (US) typically comprises 13 anatomies
and their views. However,analysis models are usually developed for anatomy-
specific tasks. Hence, to separate heart views from other 12 anatomies (head,
abdomen, femur etc) we develop an OOD detection algorithm. Our in-distribution
data comprises five structurally different heart views captured across
different cardiac cycles of a beating heart during obstetric US scanning. We
develop a diffusion-based model for reconstruction-based OOD detection, which
extends [14] with a novel dual conditioning mechanism that alleviates the
influence of high inter- and intra-class variation within different classes by
leveraging in-distribution class conditioning (IDCC) and latent image feature
conditioning (LIFC). These conditioning mechanisms allow our model to generate
images similar to the input image for in-distribution data. The primary
contributions of our paper are summarized as follows: 1) We introduce a novel
conditioned diffusion model for OOD detection and demonstrate that the dual
conditioning mechanism is effective in tackling challenging scenarios where
in-distribution data comprises multiple heterogeneous classes and there is a
high spatial similarity between ID and OOD classes. 2) Two original conditions
are proposed for the diffusion model, which are in-distribution class
conditioning (IDCC) and latent image feature conditioning (LIFC). IDCC is
proposed to handle high inter-class variance within in-distribution classes
and high spatial similarity between ID and OOD classes. LIFC is introduced to
counter the intra-class variance within each class. 3) We demonstrate in our
experiments that DCDM can detect and separate heart views from other anatomies
in fetal ultrasound videos without needing any labelled data for OOD classes.
Extensive experiments and ablations demonstrate superior performance over
existing OOD detection methods. Our approach is not fetal ultrasound specific
and could be applied to other OOD applications.

##  2 Related Work

OOD detection [31] involves identifying samples that do not belong to the
training distribution. Such models can be categorized into: (a) unsupervised
OOD detection [23] and (b) supervised OOD detection. [34, 5, 11]. Unsupervised
OOD detection methods can again be divided into two main categories: (i)
likelihood-based approaches [12, 21, 30], and (ii) reconstruction-based [3,
33, 25]. Likelihood-based approaches suffer from several issues, including
assigning higher likelihood to OOD samples [19, 4], susceptibility to
adversarial attacks [8], and calibration issues [28]. Current reconstruction-
based approaches are sensitive to dimensions of the bottleneck layer and
require rigorous tuning specific to the dataset and task [10]. Additionally,
models trained using a generator-discriminator architecture and optimizing
adversarial losses can be highly unstable and challenging to train [1, 2].
Finally, reconstruction-based methods often rely on highly compressed latent
representations, which can lead to loss of important low-level detail. This
can be problematic when discriminating between classes with high spatial
similarity. Recently, diffusion models have been introduced to address these
limitations on tasks such as image synthesis [6], and OOD detection [10].

Denoising Diffusion Probabilistic Models (DDPMs) [14] are generative models
that work by gradually adding noise to an input image through a forward
diffusion process followed by gradually removing noise using a trained neural
network in the backward diffusion process [32]. To guide the generative
process of a diffusion model (DM), previous work [18, 24, 22] condition the
DDPMs on task-specific conditioning. In image-to-image translation tasks like
super-resolution, colourization, etc., previous papers [24] condition the
model by concatenating a resized or grayscale version of the input image to
the noised image. This concatenation is unsuitable for reconstruction-based
OOD detection as the model will generate similar images for ID and OOD
samples. In the context of OOD detection using DMs, previous works [10] have
trained unconditional DDPMs and, during inference, sampled using a Pseudo
Linear Multi Step (PLMS) [16] sampler for varying noise levels. However, their
approach generates 5500 samples to detect OOD samples for each input image
which is time-consuming and impractical for settings where shorter inference
times are needed. AnoDDPM [29] utilises simplex noise rather than Gaussian
noise to corrupt the image (t=250 rather than t=1000) for anomaly detection.
However, this approach requires data specific tuning,and is outperformed by
[10].

Figure 1: DCDM architecture where $\boldsymbol{(a)}$ the input image $x_{0}$
is mapped to the latent vector $z_{0}$ using a pretrained encoder
$\mathcal{E}$ and forward diffusion is applied, $\boldsymbol{(b)}$ the
backward diffusion process denoises the latent vector $z_{t}$ and the final
denoised latent vector $z_{0}$ is mapped to pixel space by the decoder
$\mathcal{D}$ $\boldsymbol{(c)}$ the dual-conditioning mechanism. We obtain
${f_{img}}$ by passing the input image $x_{0}$ through the encoder
$\mathcal{E}$. ${f_{cls}}$ is obtained using the true label during training or
predicted class label during testing.

##  3 Methods

###  3.1 Dual Conditioned Diffusion Models

Diffusion models are generative models that rely on two Markov processes known
as forward and backward diffusion [14]. To improve efficiency during training
and inference, forward and backward diffusion is applied to the latent space
[22]. Autoencoder (AE = $\mathcal{E}$ \+ $\mathcal{D}$) is pretrained
separately on ID heart data and can successfully reconstruct the input heart
images (SSIM=0.956). The latent variable ${z_{0}}$ is obtained by passing an
input image ${x_{0}}$ through a pretrained encoder $\mathcal{E}$. Given the
latent vector ${z_{0}}$ and a fixed variance schedule [14]
$\\{\beta_{t}\in(0,1)\\}_{t=1}^{T}$, the forward diffusion process, defined by
Eqn. 1, gradually adds Gaussian noise to ${z_{0}}$ to give a noised latent
vector ${z_{t}}$ where ${\alpha_{t}=1-\beta_{t}}$ and
$\bar{\alpha}_{t}=\prod_{i=1}^{t}\alpha_{i}$:

$q(\boldsymbol{z}_{t}|\boldsymbol{z}_{0})=\mathcal{N}(\boldsymbol{z}_{t};\sqrt{\bar{\alpha}_{t}}\boldsymbol{z}_{0},(1-\bar{\alpha}_{t})\mathbf{I})$
(1)

In backward diffusion, we aim to reverse the forward diffusion process and
predict $z_{t-1}$ given $z_{t}$. To predict (${z}_{t-1}|{z}_{t}$),we train a
denoising U-Net [14] denoted as
$\boldsymbol{\epsilon}_{\theta}\left(z_{t},t,d_{0}\right)$ that takes the
current timestep $t$, noised latent vector $z_{t}$ and the dual conditioning
embedding vector $d_{0}$ as input and predicts the noise at timestep $t$ as
shown in Eqn. 2.

${\boldsymbol{z}_{t-1}=\mathcal{N}(\boldsymbol{z}_{t-1};\frac{1}{\sqrt{\alpha_{t}}}\Big{(}\boldsymbol{z}_{t}-\frac{1-\alpha_{t}}{\sqrt{1-\bar{\alpha}_{t}}}\boldsymbol{\epsilon}_{\theta}(\boldsymbol{z}_{t},t,d_{0})\Big{)},{(1-\bar{\alpha}_{t})\mathbf{I}})}$
(2)

The dual embedding vector $d_{0}$ is obtained by combining IDCC (${f_{cls}}$)
and LIFC (${f_{img}}$) vectors, which we explain in Section 3.2. The output
${z_{t-1}}$ is again input to ${\epsilon_{\theta}}$. This process is repeated
until $z_{0}$ is obtained.

The final model optimisation objective is given by Eqn. 3 where $\epsilon$ is
the original noise added during the forward diffusion process.

$\mathcal{L}_{DCDM}:=\mathbb{E}_{\mathcal{E}(x),\epsilon\sim\mathcal{N}(0,1),t}\left[\left\|\epsilon-\epsilon_{\theta}\left(z_{t},t,d_{0}\right)\right\|_{2}^{2}\right]$
(3)

Once we obtain $z_{0}$ from the backward diffusion process, it is passed on to
the decoder $\mathcal{D}$ and mapped back to the pixel space to give generated
image $x^{\prime}_{0}$.

###  3.2 Dual Conditioning Mechanism

Image features and in-distribution class information are utilised in our
proposed dual conditioning mechanism. This guides the DCDM to generate images
that are spatially and semantically similar to the input image for in-
distribution samples and dissimilar for OOD samples.

Latent Image Feature Conditioning (LIFC): The image conditioning dictates the
desired appearance of generated images in terms of shape and texture. In our
model, we use the features extracted by a pretrained encoder for conditioning.
Empirically, we use the same encoder $\mathcal{E}$ as our feature extractor to
obtain latent feature vector $z_{0}$ as shown in Fig. 1. Specifically, the
input image of dimension $224\times 224\times 3$ is passed through the encoder
$\mathcal{E}$ and a feature map with the size of $7\times 7\times 128$ is
obtained which is followed by global average pooling (GAP) resulting in a
feature vector ($f_{img}$) with dimension 128.

In-Distribution Class Conditioning (IDCC): Given an in-distribution dataset
comprising $n$ heterogeneous classes, conditioning the model only on image-
level features is insufficient. Therefore we introduce an in-distribution
class conditioning (IDCC) that informs the DCDM of the class of the input
image and enables it to generate samples belonging to the same class for ID. A
label encoder generates a unique class conditional embedding ($f_{cls}$) of
dimension 128 for each class label. The class label is assigned based on the
ground truth label during the training phase and to the classifier’s
prediction during inference, as depicted in Fig. 1. In practice, we train a
CNN classifier, freeze its weight and use it as our in-distribution classifier
(CFR), as discussed in section 3.3.

Cross Attention Guidance: To integrate the dual-conditioning guidance into the
diffusion model, we use a cross-attention [27] mechanism inside the denoising
U-Net rather than just concatenation [24] as it is more effective [13, 20, 17]
and allows condition diffusion models on various input modalities [22]. Our
LIFC and IDCC are first concatenated to give a feature vector with a dimension
of 256. This acts as a side input to each UNet block. The features from the
UNet block and the conditional features are fused by cross-attention and serve
as input to the following UNet block as shown in Fig. 1.For more
details,regarding cross-attention block refer to Rombach _et al_ [22].

###  3.3 In-Distribution Classifier

The in-distribution classifier (CFR) serves two main functions. First, it
provides labels for the class conditioning during inference; second, it is
utilized as a feature extractor for calculating the OOD score.

Inference Class Guidance. IDCC requires in-distribution class information to
generate the class conditional embedding. However, class information is only
available during training. To obtain class information during inference, we
separately train a ConvNext CNN based classifier (accuracy = 88%) on the in-
distribution data and use its predictions as the class information. During
inference, the input image $x_{0}$ is passed through the classifier, and the
predicted label is used to generate the class embedding by feeding to the
label encoder as shown in Fig. 1. Moreover, as the classifier is only trained
on in-distribution data, it classifies an OOD sample to an in-distribution
class. The classifier’s prediction is utilised by the DCDM and it tries to
generate an image belonging to in-distribution class for the OOD samples. This
reduces the structural and semantic similarity between the input and the
generated image, as demonstrated by our qualitative results (Fig. 2).

Feature-Based OOD Detection To evaluate the performance of the DCDM, the
cosine similarity between features of the input image $x_{0}$ and the
generated image $x^{\prime}_{0}$ from the in-distribution classifier is
calculated and is referred as an OOD score where $f_{0}$ and $f^{\prime}_{0}$
are the features of $x_{0}$ and $x^{\prime}_{0}$, respectively:

$\text{OOD~{}score}=~{}\\\ sim(f_{0},f^{\prime}_{0})~{}=\dfrac{f_{0}\cdot
f^{\prime}_{0}}{\left\|f_{0}\right\|_{2}\left\|f^{\prime}_{0}\right\|_{2}},$
(4)

An input image $x_{0}$ is classified as in-distribution (ID) or OOD based on
Eqn. 5 where $\tau$ is a pre-defined threshold and $y_{pred}$ is the
prediction of our feature-based OOD detection algorithm.

$y_{pred}=\begin{cases}0(ID)&if\hskip 2.84526pt\text{OOD~{}score}>\tau\\\
1~{}\text{(OOD)}&otherwise\end{cases}$ (5)

##  4 Experiments and Results

####  4.0.1 Dataset and Implementation

For our experiments, we utilized a fetal ultrasound dataset of 359 subject
videos that were collected as part of the PULSE project [7]. The in-
distribution dataset consisted of 5 standard heart views (3VT, 3VV, LVOT,
RVOT, and 4CH), while the out-of-distribution dataset comprised of three non-
heart anatomies - fetal head, abdomen, and femur. The original images were of
size $1008\times 784$ pixels and were resized to $224\times 224$ pixels.

To train the models, we randomly sampled 5000 fetal heart images and used 500
images for evaluating image generation performance. To test the performance of
our final model and compare it with other methods, we used an held-out dataset
of 7471 images, comprising 4309 images of different heart views and 3162
images (about 1000 for each anatomy) of out-of-distribution classes. Further
details about the dataset are given in Supp. Fig. 2 and 3.

All models were trained using PyTorch version 1.12 with a Tesla V100 32 GB
GPU. During training, we used T=1000 for noising the input image and a
linearly increasing noise schedule that varied from 0.0015 to 0.0195. To
generate samples from our trained model, we used DDIM [26] sampling with
T=100. All baseline models were trained and evaluated using the original
implementation.

###  4.1 Results

We evaluated the performance of the dual-conditioned diffusion models (DCDMs)
for OOD detection by comparing them with two current state-of-the-art
unsupervised reconstruction-based approaches and one likelihood-based
approach. The first baseline is Deep-MCDD [15], a likelihood-based OOD
detection method that proposes a Gaussian discriminant-based objective to
learn class conditional distributions. The second baseline is ALOCC [23] a
GAN-based model that uses the confidence of the discriminator on reconstructed
samples to detect OOD samples. The third baseline is the method of Graham _et
al._ [10], where they use DDPM [14] to generate multiple images at varying
noise levels for each input. They then compute the MSE and LPIPS metrics for
each image compared to the input, convert them to Z-scores, and finally
average them to obtain the OOD score.

Quantitative Results The performance of the DCDM, along with comparisons with
the other approaches, are shown in Table 1. The GAN-based method ALOCC [23]
has the lowest AUC of 57.22%, which is improved to 63.86% by the method of
Graham _et al._ and further improved to 64.58% by likelihood-based Deep-MCDD.
DCDM outperforms all the reference methods by 20%, 14% and 13%, respectively
and has an AUC of 77.60%. High precision is essential for OOD detection as
this can reduce false positives and increase trust in the model. DCDM exhibits
a precision that is 22% higher than the reference methods while still having
an 8% improvement in F1-Score.

Qualitative Results Qualitative results are shown in Fig. 2. Visual
comparisons show ALOCC generates images structurally similar to input images
for in-distribution and OOD samples. This makes it harder for the ALOCC model
to detect OOD samples. The model of Graham  _et al._ generates any random
heart view for a given image as a DDPM is unconditional, and our in-
distribution data contains multiple heart views. For example, given a 4CH view
as input, the model generates an entirely different heart view. However,
unlike ALOCC, the Graham  _et al._ model generates heart views for OOD
samples, improving OOD detection performance. DCDM generates images with high
spatial similarity to the input image and belonging to the same heart view for
ID samples while structurally diverse heart views for OOD samples. In Fig 2
(c) for OOD sample, even-though the confidence is high (0.68), the gap between
ID and OOD classes is wide enough to separate the two.Additional qualitative
results can be observed in Supp. Fig. 4.

Table 1: Quantitative comparison of our model (DCDM) with reference methods

Method | AUC(%) | F1-Score(%) | Accuracy(%) | Precision(%)
---|---|---|---|---
Deep-MCDD [15] | 64.58 | 66.23 | 60.41 | 51.82
ALOCC [23] | 57.22 | 59.34 | 52.28 | 45.63
Graham et al. [10] | 63.86 | 63.55 | 60.15 | 50.89
DCDM(Ours) | 77.60 | 74.29 | 77.95 | 73.34

Figure 2: Qualitative comparison of our method with $\boldsymbol{(a)}$ ALOCC
generates similar images to the input for ID and OOD samples
$\boldsymbol{(b)}$ Graham _et al._ generates any random heart view for a given
input image $\boldsymbol{(c)}$ Our model generates images that are similar to
the input image for ID and dissimilar for OOD samples. Classes predicted by
CFR and the OOD score ($\tau$ = 0.73) are mentioned in brackets.

###  4.2 Ablation Study

Ablation experiments were performed to study the impact of various
conditioning mechanisms on the model performance both qualitatively and
quantitatively. When analyzed quantitatively, as shown in Table 2, the
unconditional model has the lowest AUC of 69.61%. Incorporating the IDCC
guidance or LIFC separately, improves performance with an AUC of 75.27% and
77.40%, respectively. The best results are achieved when both mechanisms are
used (DCDM), resulting in an 11% improvement in the AUC score relative to the
unconditional model. Although there is a small margin of performance
improvement between the combined model (DCDM) and the LIFC model in terms of
AUC, the precision improves by 3%, demonstrating the combined model is more
precise and hence the best model for OOD detection.

As shown in Fig. 3, the unconditional diffusion model generates a random heart
view for a given input for both in-distribution and OOD samples. The IDCC
guides the model to generate a heart view according to the in-distribution
classifier (CFR) prediction which leads to the generation of similar samples
for in-distribution input while dissimilar samples for OOD input. On the other
hand, LIFC generates an image with similar spatial information. However, heart
views are still generated for OOD samples as the model was only trained on
them. When dual-conditioning (DC) is used, the model generates images that are
closer aligned to the input image for in-distribution input and high-fidelity
heart views for OOD than those generated by a model conditioned on either IDCC
or LIFC alone. Supp. Fig. 1 presents further qualitative ablations.

Table 2: Ablation study of different conditioning mechanisms of DCDM.

Method | Accuracy (%) | Precision (%) | AUC (%)
---|---|---|---
Unconditional | 68.16 | 58.44 | 69.61
In-Distribution Class Conditioning | 74.39 | 66.12 | 75.27
Latent Image Feature Conditioning | 77.02 | 70.02 | 77.40
Dual Conditioning | 77.95 | 73.34 | 77.60

Figure 3: Qualitative ablation study showing the effect of (a) IDCC, (b) LIFC
and, (c) DC on generative results of DM. Brackets in IDCC, DC show labels
predicted by CFR.

##  5 Conclusion

We introduce novel dual-conditioned diffusion model for OOD detection in fetal
ultrasound videos and demonstrate how the proposed dual-conditioning
mechanisms can manipulate the generative space of a diffusion model.
Specifically, we show how our dual-conditioning mechanism can tackle scenarios
where the in-distribution data has high inter- (using IDCC) and intra- (using
LIFC) class variations and guide a diffusion model to generate similar images
to the input for in-distribution input and dissimilar images for OOD input
images. Our approach does not require labelled data for OOD classes and is
especially applicable to challenging scenarios where the in-distribution data
comprises more than one class and there is high similarity between the in-
distribution and OOD classes.

##  6 Acknowledgement

This work was supported in part by the InnoHK-funded Hong Kong Centre for
Cerebro-cardiovascular Health Engineering (COCHE) Project 2.1 (Cardiovascular
risks in early life and fetal echocardiography), the UK EPSRC (Engineering and
Physical Research Council) Programme Grant EP/T028572/1 (VisualAI), and a UK
EPSRC Doctoral Training Partnership award.

## References

  * [1] Arjovsky, M., Bottou, L.: Towards principled methods for training generative adversarial networks. arXiv preprint arXiv:1701.04862 (2017)
  * [2] Bau, D., Zhu, J.Y., Wulff, J., Peebles, W., Strobelt, H., Zhou, B., Torralba, A.: Seeing what a gan cannot generate. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4502–4511 (2019)
  * [3] Chen, X., Konukoglu, E.: Unsupervised detection of lesions in brain mri using constrained adversarial auto-encoders. arXiv preprint arXiv:1806.04972 (2018)
  * [4] Choi, H., Jang, E., Alemi, A.A.: Waic, but why? generative ensembles for robust anomaly detection. arXiv preprint arXiv:1810.01392 (2018)
  * [5] DeVries, T., Taylor, G.W.: Learning confidence for out-of-distribution detection in neural networks. arXiv preprint arXiv:1802.04865 (2018)
  * [6] Dhariwal, P., Nichol, A.: Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems 34, 8780–8794 (2021)
  * [7] Drukker, L., Sharma, H., Droste, R., Alsharid, M., Chatelain, P., Noble, J.A., Papageorghiou, A.T.: Transforming obstetric ultrasound into data science using eye tracking, voice recording, transducer motion and ultrasound video. Scientific Reports 11(1), 14109 (2021)
  * [8] Fort, S.: Adversarial vulnerability of powerful near out-of-distribution detection. arXiv preprint arXiv:2201.07012 (2022)
  * [9] Fort, S., Ren, J., Lakshminarayanan, B.: Exploring the limits of out-of-distribution detection. Advances in Neural Information Processing Systems 34, 7068–7081 (2021)
  * [10] Graham, M.S., Pinaya, W.H., Tudosiu, P.D., Nachev, P., Ourselin, S., Cardoso, M.J.: Denoising diffusion models for out-of-distribution detection. arXiv preprint arXiv:2211.07740 (2022)
  * [11] Guénais, T., Vamvourellis, D., Yacoby, Y., Doshi-Velez, F., Pan, W.: Bacoun: Bayesian classifers with out-of-distribution uncertainty. arXiv preprint arXiv:2007.06096 (2020)
  * [12] Hendrycks, D., Gimpel, K.: A baseline for detecting misclassified and out-of-distribution examples in neural networks. arXiv preprint arXiv:1610.02136 (2016)
  * [13] Hertz, A., Mokady, R., Tenenbaum, J., Aberman, K., Pritch, Y., Cohen-Or, D.: Prompt-to-prompt image editing with cross attention control. arXiv preprint arXiv:2208.01626 (2022)
  * [14] Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems 33, 6840–6851 (2020)
  * [15] Lee, D., Yu, S., Yu, H.: Multi-class data description for out-of-distribution detection. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1362–1370 (2020)
  * [16] Liu, L., Ren, Y., Lin, Z., Zhao, Z.: Pseudo numerical methods for diffusion models on manifolds. arXiv preprint arXiv:2202.09778 (2022)
  * [17] Margatina, K., Baziotis, C., Potamianos, A.: Attention-based conditioning methods for external knowledge integration. arXiv preprint arXiv:1906.03674 (2019)
  * [18] Meng, C., He, Y., Song, Y., Song, J., Wu, J., Zhu, J.Y., Ermon, S.: Sdedit: Guided image synthesis and editing with stochastic differential equations. In: International Conference on Learning Representations (2021)
  * [19] Nalisnick, E., Matsukawa, A., Teh, Y.W., Gorur, D., Lakshminarayanan, B.: Do deep generative models know what they don’t know? arXiv preprint arXiv:1810.09136 (2018)
  * [20] Rebain, D., Matthews, M.J., Yi, K.M., Sharma, G., Lagun, D., Tagliasacchi, A.: Attention beats concatenation for conditioning neural fields. arXiv preprint arXiv:2209.10684 (2022)
  * [21] Ren, J., Liu, P.J., Fertig, E., Snoek, J., Poplin, R., Depristo, M., Dillon, J., Lakshminarayanan, B.: Likelihood ratios for out-of-distribution detection. Advances in neural information processing systems 32 (2019)
  * [22] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 10684–10695 (2022)
  * [23] Sabokrou, M., Khalooei, M., Fathy, M., Adeli, E.: Adversarially learned one-class classifier for novelty detection. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 3379–3388 (2018)
  * [24] Saharia, C., Chan, W., Chang, H., Lee, C., Ho, J., Salimans, T., Fleet, D., Norouzi, M.: Palette: Image-to-image diffusion models. In: ACM SIGGRAPH 2022 Conference Proceedings. pp. 1–10 (2022)
  * [25] Schlegl, T., Seeböck, P., Waldstein, S.M., Schmidt-Erfurth, U., Langs, G.: Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In: Information Processing in Medical Imaging: 25th International Conference, IPMI 2017, Boone, NC, USA, June 25-30, 2017, Proceedings. pp. 146–157. Springer (2017)
  * [26] Song, J., Meng, C., Ermon, S.: Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502 (2020)
  * [27] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)
  * [28] Wald, Y., Feder, A., Greenfeld, D., Shalit, U.: On calibration and out-of-domain generalization. Advances in neural information processing systems 34, 2215–2227 (2021)
  * [29] Wyatt, J., Leach, A., Schmon, S.M., Willcocks, C.G.: Anoddpm: Anomaly detection with denoising diffusion probabilistic models using simplex noise. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 650–656 (2022)
  * [30] Xu, H., Chen, W., Zhao, N., Li, Z., Bu, J., Li, Z., Liu, Y., Zhao, Y., Pei, D., Feng, Y., et al.: Unsupervised anomaly detection via variational auto-encoder for seasonal kpis in web applications. In: Proceedings of the 2018 world wide web conference. pp. 187–196 (2018)
  * [31] Yang, J., Zhou, K., Li, Y., Liu, Z.: Generalized out-of-distribution detection: A survey. arXiv preprint arXiv:2110.11334 (2021)
  * [32] Yang, L., Zhang, Z., Song, Y., Hong, S., Xu, R., Zhao, Y., Shao, Y., Zhang, W., Cui, B., Yang, M.H.: Diffusion models: A comprehensive survey of methods and applications. arXiv preprint arXiv:2209.00796 (2022)
  * [33] Zhou, Y.: Rethinking reconstruction autoencoder-based out-of-distribution detection. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7379–7387 (2022)
  * [34] Zhou, Z., Guo, L.Z., Cheng, Z., Li, Y.F., Pu, S.: Step: Out-of-distribution detection in the presence of limited in-distribution labeled data. Advances in Neural Information Processing Systems 34, 29168–29180 (2021)


# Accelerating L-shaped Two-stage Stochastic SCUC with Learning Integrated
Benders Decomposition

Fouad Hasan, Student Member, IEEE, Amin Kargarian, Senior Member, IEEE This
work was supported by the National Science Foundation under Grant
ECCS-1944752Fouad hasan and A. Kargarian are with the Department of Electrical
and Computer Engineering, Louisiana State University, Baton Rouge, LA 70803
USA (e-mail<EMAIL_ADDRESS>kargarian@lsu.edu).

(June 2023 2021)

###### Abstract

Benders decomposition is widely used to solve large mixed-integer problems.
This paper takes advantage of machine learning and proposes enhanced variants
of Benders decomposition for solving two-stage stochastic security-constrained
unit commitment (SCUC). The problem is decomposed into a master problem and
subproblems corresponding to a load scenario. The goal is to reduce the
computational costs and memory usage of Benders decomposition by creating
tighter cuts and reducing the size of the master problem. Three approaches are
proposed, namely regression Benders, classification Benders, and regression-
classification Benders. A regressor reads load profile scenarios and predicts
subproblem objective function proxy variables to form tighter cuts for the
master problem. A criterion is defined to measure the level of usefulness of
cuts with respect to their contribution to lower bound improvement. Useful
cuts that contain the necessary information to form the feasible region are
identified with and without a classification learner. Useful cuts are
iteratively added to the master problem, and non-useful cuts are discarded to
reduce the computational burden of each Benders iteration. Simulation studies
on multiple test systems show the effectiveness of the proposed learning-aided
Benders decomposition for solving two-stage SCUC as compared to conventional
multi-cut Benders decomposition.

###### Index Terms:

Stochastic unit commitment, Benders decomposition, useful cuts, machine
learning.

##  I Introduction

###  I-A Background and Motivation

Security-constrained unit commitment (SCUC) is a complex optimization problem
solved daily to determine the optimal schedule of generating units [1]. SCUC
is a mixed-integer program (MIP) that involves a mix of continuous and integer
decision variables. The challenge with mixed integer problems is that the
inclusion of integer variables often makes the problem NP-hard. SCUC becomes
even more complex under input parameter (e.g., demand) uncertainty [2, 3, 4]
To counterbalance uncertainty in power system operation, SCUC is often
formulated as a stochastic MIP problem, known as an L-shaped optimization
problem[5]. An L-shaped problem is formulated as two-stage stochastic
optimization. This formulation involves here-and-now and wait-and-see decision
variables. It is a two-stage optimization problem with a single integer
recourse decision in the second stage. The name L-shaped comes from the shape
of the SCUC feasible region when represented graphically. This type of problem
is commonly encountered in decision-making under uncertainty, where a
decision-maker may face different scenarios or outcomes with associated
probabilities. Due to the block structure, the L-shaped two-stage stochastic
program is an effective method for SCUC [6]. L-shaped optimization problems
can be solved using specialized techniques such as Benders decomposition (BD).
Although Benders decomposition solves L-shaped problems, it suffers from
exponential worst-case computational complexity. This is due, in part, to the
large number of successively added cuts over iterations, which causes the size
of Benders’ master problem to grow excessively. Moreover, the master problem
takes over 90% of the time required to implement Benders decomposition [7].
Also, as noted in [8], not every extreme point in the feasible region of
subproblems contributes equally to limiting the optimal solution to the master
problem. This implies that a significant number of Benders cuts may not be
tight enough at the final optimal solution. Consequently, these non-useful
Benders cuts can make solving large-scale integer programs challenging.

Various mathematical and heuristic approaches have been presented in the
literature to enhance Benders decomposition performance. This study aims to
accelerate the convergence of Benders decomposition by taking advantage of
machine learning techniques.

###  I-B Literature Review

It has been more than 50 years since the development of the Benders
decomposition algorithm by J. Bender (1962) [9]. The algorithm is designed to
address complicating variables that, when temporarily fixed, simplify the
problem significantly. It distributes the computational load between a master
problem and a subproblem (SP). Benders decomposition has proven successful in
various fields, including planning and scheduling, healthcare, transportation,
telecommunications, energy and resource management, and chemical process
design [6]. The primary application of Benders decomposition is initially
focused on solving MIP problems. Once integer variables are fixed, the problem
is converted into a continuous linear program, which can develop cuts using
standard duality theory. Many enhancements have been made to extend Benders’
applicability to a wider range of problems. As a result, Benders decomposition
has been widely used to solve linear, nonlinear, integer, stochastic, multi-
stage, and bilevel optimization problems [10]. The traditional implementation
of Benders decomposition can be computationally expensive, time-consuming, and
memory-intensive, with problems such as poor feasibility and optimality cuts,
ineffective early iterations, and the zigzagging behavior of primal solutions
[7]. Researchers have explored various strategies to speed up the convergence
and reduce the number of iterations and time spent on each iteration. The
master problem is usually solved using branch-and-bound, with the simplex
approach used to solve the subproblem. However, a significant number of cuts
generated do not contribute to convergence, leading to memory occupation [8].
To address this problem, improvement criteria are proposed to ensure that new
and useful cuts are included in the master problem [11]. Additionally,
researchers have observed several orders of improvement when using constraint
programming to solve the master problem [12]. Column generation has been
introduced to handle specific structures more effectively and achieve tighter
constraints at the root node of the branch-and-bound tree [13, 14]. For large
subproblems, decomposition, parallelization, and column generation have been
used to reduce overall solution time. By adding valid inequalities to the
master, one can significantly reduce the number of generated cuts and solution
time [15]. Moreover, clustering subproblems can decrease the number of
iterations [16]. Recently, researchers have been exploring the use of machine
learning (ML) to alleviate the computational complexity of complex problems
[17, 18]. ML-based algorithms can be categorized into three types: end-to-end
learning (with label), unsupervised/reinforcement learning (no ground truth),
and algorithm-specific hybrid learning, which leverages the specific structure
of the target problem to accelerate the optimization process. For instance, a
support vector machine is used in [19] to construct a cut classifier that
identifies valuable cuts in each Benders iteration, thus reducing the size of
the master problem and shortening the solution time. Another strategy is to
use the Lagrange multipliers of the Benders subproblem to aggregate the
optimality cuts [20]. In [21], a cut regressor and a cut classifier are used,
and five features are designed to characterize the generated cuts [22].
Solving two-stage stochastic SCUC with Benders decomposition is still
computationally challenging and needs further investigation. Also, despite
machine learning advantages, the literature lack ML-based Benders approaches
to accelerate two-stage stochastic SCUC.

###  I-C Contribution

This paper presents combined machine learning and model-based variants of
Benders decomposition for solving two-stage stochastic SCUC. The proposed
approaches form tighter cuts and a truncated, less computationally expensive
Benders master problem. A regressor is trained to predict proxy variables
corresponding to subproblems and create a tighter master problem feasible
region. After carrying out each Benders iteration, useful cuts are identified
using a criterion and a classification learner. A truncated master problem is
created by adding useful cuts to the model and discarding non-useful cuts.
Combining the regressor and classifier reduces the computational cost and
memory usage of the Benders decomposition for solving two-stage stochastic
SCUC. The Benders iterative loop inherently ensures the feasibility and
optimality of results. The three enhanced Benders approaches are tested on
various test systems, and the results are analyzed.

###  I-D Paper Organization

The rest of the paper is structured as follows. The problem formulation is
given in Section II. The proposed enhanced Benders approaches are presented in
Section III. The numerical simulations are discussed in Section IV, and
concluding remarks are provided in Section V.

##  II TWO-STAGE STOCHASTIC UNIT COMMITMENT

The considered problem is a two-stage stochastic unit commitment with respect
to demand uncertainty. Benders decomposition is used to solve the problem.

###  II-A Problem Formulation

The problem is formulated in (1), which includes two sets of variables
pertaining to here-and-now decisions and wait-and-see decisions [23]. On/off
status of units are here-and-now variables, and generation dispatches are
wait-and-see variables. The first term of (1a) is the first-stage startup and
shutdown costs, and the second is the second-stage generation dispatch costs.
The first stage constraints are (1b) – (1i), which are scenario-independent
unit commitment constraints. The second-stage scenario-dependent operational
constraints are formulated in (1j)–(1n). N-1 security constraints are included
in the model with index c.

$\min\sum_{t}\sum_{g}(SU_{g}y_{gt}+SD_{g}z_{gt})+\sum_{\omega}\pi_{\omega}\sum_{t}\sum_{g}f(p_{gt\omega})$
(1a)

s.t.

$y_{gt}-z_{gt}=u_{gt}-u_{g(t-1)}\ \ \forall g,\forall t$ (1b)
$y_{gt}+z_{gt}\leq 1\ \ \forall g,\forall t$ (1c)
$\sum_{t=1}^{UT_{g}}(1-u_{gt})=0\ \ \forall g$ (1d)
$\sum_{\tau=t}^{t+T_{g}^{on}-1}u_{g\tau}\geq T_{g}^{on}y_{gt}\ \ \forall
g,t=UT_{g}+1,UT_{g}+2,...T-T_{g}^{on}+1$ (1e)
$\sum_{\tau=t}^{T}(u_{g\tau}-y_{gt})\geq 0\ \ \forall g,t=T-T_{g}^{on}+2,...T$
(1f)

$\sum_{t=1}^{DT_{g}}u_{gt}=0\ \ \forall g$ (1g)
$\sum_{\tau=t}^{t+T_{g}^{off}-1}(1-u_{g\tau})\geq T_{g}^{off}z_{gt}\ \ \forall
g,t=DT_{g}+1,DT_{g}+2,...T-T_{g}^{off}+1$ (1h)
$\sum_{\tau=t}^{T}(1-u_{g\tau}-z_{gt})\geq 0\ \ \forall
g,t=T-T_{g}^{off}+2,...T$ (1i)

{

$p_{g}^{min}u_{gt}\leq p_{gt\omega c}\leq p_{g}^{max}u_{gt}\ \ \forall
g,\forall t$ (1j) $p_{gt\omega c}-p_{g(t-1)\omega c}\leq
RU_{g}(1-y_{gt})+P_{g}^{min}y_{gt}\ \ \forall g,\forall t$ (1k)
$p_{g(t-1)\omega c}-p_{gt\omega c}\leq RD_{g}(1-z_{gt})+P_{g}^{min}z_{gt}\ \
\forall g,\forall t$ (1l) $\sum_{g}p_{gt\omega c}=D_{t}\ \ \forall t$ (1m)
$-PL^{max}\leq SF_{c}P_{t\omega c}^{inj}\leq PL^{max}\ \ \forall t$ (1n)

}

$\forall\omega\in\Omega,\forall c$

###  II-B Benders Decomposition

The computational complexity of mixed-integer program (1) increases with the
increasing size of the network, number of demand scenarios, and number of
contingencies. Benders decomposition is suitable for solving MIP problems with
a block structure over contingencies and uncertainty scenarios [6]. We use a
multi-cut variant of Benders decomposition that converges faster than the
classical single-cut approach [20, 24]. The multi-cut technique decomposes a
problem into multiple subproblems and generates multiple cuts in each
iteration. This multi-cut generation improves convergence performance [25].
Problem (1) is decomposed into a master problem and n subproblems. The master
problem (MP) at iteration k is formulated in (2a)-(2c).

$\min_{x}\sum_{t}\sum_{g}(SU_{g}y_{gt}+SD_{g}z_{gt})+\sum_{\omega}\alpha_{\omega}$
(2a)

s.t.

$(1b)-(1i)$ (2b) $\cup_{i=1}^{i=k-2}h_{\beta}^{n}(u_{gt},\alpha_{\omega})$
(2c) $h_{\beta}^{k-1}(u_{gt},\alpha_{\omega}):\alpha_{\omega}\geq
J_{SP,\omega}^{k-1}+\sum_{t}\sum_{g}\lambda_{gt\omega}^{k-1}(u_{gt}-u_{gt}^{k-1})\
\ \forall\omega$ (2d) $\alpha_{\omega}\geq\alpha_{\omega}^{min}\ \
\forall\omega$ (2e) $x\in\\{u_{gt},y_{gt},z_{gt},\alpha_{\omega}\\}$

The objective function (2a) consists of startup and shutdown costs and a term
as a proxy for the subproblems’ objective function. Equation (2c) is the
accumulation of all cuts generated up to iteration k-2, (2d) denotes Benders
cuts generated at iteration k-1, and (2e) defines the bound on proxy variables
where $\alpha_{\omega}^{min}$ is set as a large negative constant.

Benders subproblem $\omega$ ($SP_{\omega}$) is formulated in (3a)- (3e). To
gain extra computational efficiency, we use an always-feasible subproblem
model [26]. This model includes non-negative slack variables $\nu$ and
$\gamma$ to prevent ($SP_{\omega}$) infeasibility. Auxiliary variables $\nu$
and $\gamma$ relax generation capacity constraints.

$\min_{x}\sum_{t}\sum_{g}\sum_{\omega}(\pi_{\omega}f(p_{gt\omega})+\nu_{(}gt\omega))+\sum_{t}\sum_{\omega}\gamma_{t\omega}$
(3a)

s.t.

$u_{gt}=u_{gt}^{*}$ (3b)

{

$(1j)-(1n)$ (3c) $p_{g}^{min}u_{gt}\leq p_{gt\omega c}\leq
p_{g}^{max}u_{gt}+\nu_{(gt\omega)}+\gamma_{t\omega}\ \ \forall g,\forall t$
(3d) $\nu_{(gt\omega)}\geq 0,\gamma_{t\omega}\geq 0$ (3e)

}

$x\in\\{p_{gt\omega c},\nu_{(gt\omega)},\gamma_{t\omega}\\}$

The objective function (3a) consists of generation costs and constraint
violation penalty modeled by $\nu_{gtw}$ and $\gamma_{tw}$. Constraint (3b)
sets the first stage decisions, i.e., generator unit status, as fixed values
received from the master problem. Inequalities (3e) set bound on auxiliary
variables. The MP and SPs are solved iteratively until convergence tolerance
$\varepsilon$ is smaller than a predetermined threshold.

$\epsilon=\frac{UB-LB}{abs(LB)}$ (4)

where

$LB=J_{MP},\ \ UB=J_{SP}+J_{MP}-\sum_{\omega}\alpha_{\omega}$

The two-stage stochastic SCUC with multi-cut Benders is summarized in
Algorithm I.

##  III PROPOSED LEARNING ASSISTED BENDERS DECOMPOSITION

While multi-cut Benders outperforms single-cut Benders in terms of convergence
performance, its memory usage and computational overhead still need
enhancement. We present three learning-aided approaches to reduce the
computational costs of multi-cut Benders decomposition for solving two-stage
stochastic SCUC. We mainly focus on the master problem, which has higher
computational costs than subproblems.

###  III-A Regression-assisted Benders (R-Benders)

The first proposed approach uses a combination of a regressor and cut
filtering. The regressor forms a tighter bound for the master problem at the
root node starting from k=1. We predict the optimal subproblem proxy variables
$\alpha_{\omega}^{*}$, i.e., $\alpha_{\omega}$ upon the convergence of
Algorithm I. Knowing $\alpha_{\omega}^{*}$, or even a good approximation,
makes inequalities (2c), (2d), and (2e) tighter and the lower bound LB closer
to the optimal subproblem cost. The cut filtering approach identifies and
drops non-useful cuts during each subsequent Benders iteration to reduce the
size of the master problem. Non-useful cuts are cuts with no impact on the
master problem feasible region.

####  III-A1 SP Objective Proxy Prediction

In the multi-cut Benders formulation (2), $\alpha_{\omega}$ is a variable and
$\alpha_{\omega}^{min}$ is a bound where $\alpha_{\omega}$ $\geq$
$\alpha_{\omega}^{min}$ constitutes a master problem constraint. The value of
$\alpha_{\omega}$ increases after each iteration and reaches its optimal value
$\alpha_{\omega}^{*}$ upon convergence. The value of $\alpha_{\omega}^{min}$
can be selected by analyzing the physical and economic aspects of the SCUC
problem. Setting a suitable $\alpha_{\omega}^{min}$ reduces the search space
and enhances Benders convergence performance. An ideal case is to set
$\alpha_{\omega}^{min}$ corresponding to each subproblem $\omega$ as the
optimal value of $\alpha_{\omega}$ instead of using a large negative value.
Fig. 1 shows the advantage of using optimal $\alpha_{\omega}^{*}$. The master
problem objective reaches its optimal value in the very initial iterations. We
use machine learning to predict $\alpha_{\omega}^{*}$ for each subproblem
$\omega$ by reading power demand before implementing multi-cut Benders
Algorithm I.

Figure 1: Benders convergence using $\alpha_{\omega}^{*}$ $\forall$ $\omega$
in inequality (2b).

####  III-A2 Training Dataset Preparation

Electricity demand scenarios are input to two-stage SCUC. We have observed
that $\alpha_{\omega}^{*}$ are correlated with system demand. We use demand
information as the input to a supervised learning model whose output is
$\alpha_{\omega}^{*}$. To account for potential system operation scenarios in
the training phase, we generate a set of daily load profile samples$D^{s}$
$\in\mathbb{R}^{s\times 1}$ according to (5). To follow the concept of demand
uncertainty modeling in the two-stage SCUC problem, each $D^{s}$ contains n
demand profile scenarios generated by (6).

$D^{s}=D_{base}[\eta_{s}^{L}+\eta_{s}(\eta_{s}^{U}-\eta_{s}^{L})]\ \ \forall
s$ (5)
$D^{s}_{\omega}=D^{s}[\eta_{\omega}^{L}+\eta_{\omega}(\eta_{\omega}^{U}-\eta_{\omega}^{L})]\
\ \forall\omega,\forall s$ (6)

where $D_{\omega}^{s}\in\mathbb{R}^{s\times 1}$, and $\eta_{s}\\{\cdot\\}$ and
$\eta_{\omega}\\{\cdot\\}$ follows a uniform distribution between 0 and 1.
Indices for samples and subsamples are denoted by $s$ and $\omega$. Two stages
of randomness are carried out to consider a range of realistic operational
conditions. The load point is shifted using the random parameter
$\eta_{s}\\{\cdot\\}$ to model its daily and seasonal volatility within the
range [$\eta_{s}^{U}$, $\eta_{s}^{L}$]. $\eta_{s}^{U}$ and $\eta_{s}^{L}$ can
be determined by historical data and load growth projection or to the point
when any further increase or decrease renders unit commitment infeasible. The
uncertainty in subsamples is modeled using the random parameter
$\eta_{\omega}\\{\cdot\\}$ within a specified range [$\eta_{\omega}^{U}$,
$\eta_{\omega}^{L}$]. Subsamples model the hourly load randomness by
multiplying $D^{s}$ by random parameters and creating $D_{\omega}^{s}$. Fig. 2
illustrates the load scenario generation.

Figure 2: Demand scenario generation.

For a given system, Algorithm I is executed for each demand profile sample
$D^{s}$. Optimal values of proxy variables upon Benders convergence are
labeled as $\alpha^{s*}$ and stored. Expressions (7) and (8) are,
respectively, the input and target of the supervised learning model.

$Input\ \ sample:D^{s}=[D_{1}^{s},D_{2}^{s},D_{3}^{s},...,D_{n}^{s}]^{T}\ \
\forall s$ (7)

$Target\ \
sample:\alpha^{s*}=[\alpha_{1}^{s*},\alpha_{2}^{s*},\alpha_{3}^{s*},...,\alpha_{n}^{s*}]^{T}\
\ \forall s$ (8)

####  III-A3 Supervised Learning Strategy

We use neural networks (NN), an efficient tool to capture the complexity and
nonlinearity of a function by utilizing various activation functions. The
regressor uses a fully connected NN with mini-batch gradient descent and
Rectified Linear Units (ReLU) activation functions for hidden layers. The loss
function is the mean squared error (MSE).

$MSE=\frac{\sum_{n}(x_{n}-\hat{x_{n}})^{2}}{n}$ (9)

The Adam optimizer determines optimal weights and trains the learning model.
Various batch sizes, epochs, and layer counts are tested to determine the best
architecture. A single hidden layer is selected to have a minimalistic model.
Table I shows the architecture and hyperparameters used in this study.
Although more sophisticated structures may improve the results, we obtained
promising outcomes with this minimalistic architecture. Fig. 3 illustrates a
conceptual schematic of the learner model.

TABLE I: Hyperparameters of The Learner NN regressor |  Hidden layer=1, Batch size=300 500 |  Activation = ReLU, Loss function = MSE Optimizer = Adam
---|---|---
Figure 3: NN regressor reads demand profiles and predicts proxy variables
$\alpha$.

####  III-A4 Data Scaling

Data normalization and standardization are crucial before training a learner.
The data samples are normalized by (10). This process enhances prediction
accuracy and numerical stability.

$x_{normalized}=\frac{x_{n}-x_{min}}{x_{max}-x_{min}}$ (10)

####  III-A5 Useful Cut Identification

The master problem still retains all cuts generated after carrying out each
Benders iteration. As a result, the master problem size grows at every
iteration, calling for a considerable computational memory requirement. In
most cases, a subset of Benders cuts generated at each iteration contains the
necessary information to build the feasible search space of the master
problem. Currently, a lack of practical and systematic approach exists for
classifying useful and non-useful cuts for large-scale problems [10]. Several
features are suggested in [19, 21], such as cut violation, cut depth, cut
order, and cut producing scenario, to identify approximately useful cuts.

Our idea of useful cut identification is based on Fig. 4, which shows an
example of the master problem objective value (or lower bound) improvement
with cumulatively added cuts. It can be observed that all cuts are not equally
contributing to the lower bound and optimality gap improvement. Several cuts
provide a positive increase in the lower bound. Such cuts can be classified as
useful cuts. Other cuts do not contribute to the lower bound improvement and
can be classified as non-useful. Our observation and experiment show that the
numerical difference between cut values $\psi{(u_{gt}^{k})}$ and proxy values
$\alpha^{k}_{\omega}$ can be used for useful cut identification. If an
inequality constraint is satisfied as equality upon solving optimization, it
is typically referred to as a binding or strictly useful constraint. Thus, if
$\alpha^{k}_{\omega}$ \- $\psi{(u_{gt}^{k})}$ = 0, the cut is useful.

Figure 4: Benders lower bound improvement with cuts added cumulatively; a case
of IEEE 118-bus system.

However, many other cuts that are not satisfied as equality may also contain
the necessary information to form the master problem feasible region. Such
cuts should also be considered useful. As an inequality constraint approaches
equality, its importance in forming a feasible region is expected to increase.
Consider a demand profile sample $D^{s}$. To capture all cuts that contain
necessary information at each iteration k, we label cuts as "useful" if the
difference between $\alpha^{k}_{\omega}$ and $\psi{(u_{gt}^{k})}$ is less than
a threshold $\delta$, which is selected through experimental observation. We
have tested various cases and observed that $\delta$ within the range
$[0.1,100]$ works well for the studied cases. Once all cuts are generated at
iteration $k-1$, we add them to MP and solve the updated MP at iteration k to
obtain $u_{gt}^{k}$ and $\alpha^{k}_{\omega}$. We check (11) to identify
useful cuts generated at iteration k-1. Cuts that satisfy (11) contain
necessary information and are useful. We repeat this process at each iteration
$k$ to detect useful cuts generated at iteration $k-1$. Non-useful cuts are
dropped from MP before moving to iteration $k+1$.

$h_{\beta}^{k-1}(u_{gt},\alpha_{\omega})^{\phi}:|\alpha_{\omega}^{k}-\psi(u_{gt}^{k})|\leq\delta$
(11)

where $\psi{(u_{gt}^{k})}$ is the numerical value of the right-hand side of
(2d).

$\psi(u_{gt}^{k})=J_{SP,\omega}^{k-1}+\sum_{t}\sum_{g}\lambda_{gt\omega}^{k-1}(u_{gt}-u_{gt}^{k-1})$

Figure 5: R-Benders flowchart.

####  III-A6 Avoiding Information Loss

Selecting a small $\delta$ results in labeling fewer cuts as useful. A large
$\delta$ yields keeping more cuts in the master problem, and thus less
computational cost reduction is gained. Depending on the value of
hyperparameter $\delta$, we have observed cases with no cut labeled as useful
at a few iterations. Retaining at least one cut from each iteration is
crucial; otherwise, the proposed R-Benders may not converge due to loss of
information from that particular iteration. To prevent this, we keep several
cuts generated from high-load scenarios at each iteration, most of which may
already be on the useful cut list. The number of retained cuts is determined
through experimentation.

####  III-A7 R-Benders MP Formulation

The R-Benders master problem at iteration k is as follows:

$\min_{x}\sum_{t}\sum_{g}(SU_{g}y_{gt}+SD_{g}z_{gt})+\sum_{\omega}\alpha_{\omega}$
(12a)

s.t.

$(1b)-(1i)$ (12b)
$\cup_{i=1}^{i=k-2}h_{\beta}^{n}(u_{gt},\alpha_{\omega})^{\psi}$ (12c)
$h_{\beta}^{k-1}(u_{gt},\alpha_{\omega}):\alpha_{\omega}\geq
J_{SP,\omega}^{k-1}+\sum_{t}\sum_{g}\lambda_{gt\omega}^{k-1}(u_{gt}-u_{gt}^{k-1})\
\ \forall\omega$ (12d) $\alpha_{\omega}\geq\alpha_{\eta}\alpha_{\omega}^{min}\
\ \forall\omega$ (12e) $x\in\\{u_{gt},y_{gt},z_{gt},\alpha_{\omega}\\}$

where (12c) denotes the list of all useful cuts detected until iteration
$k-2$. (12d) includes all cuts generated at iteration $k-1$. The value of
$\alpha_{\omega}$ successively progresses to reach the optimal value. To
maintain the quality of the lower bound solution, we should ensure
$\alpha_{\omega}$$\geq$$\alpha_{\omega}^{*}$. Given the possibility of machine
learning error, the regressor predictions $\alpha_{\omega}^{*}$ are reduced by
a factor $\alpha_{\eta}$ and $\alpha_{\omega}$$\geq$$\alpha_{\omega}^{*}$ is
replaced with $\alpha_{\omega}$$\geq$$\alpha_{\eta}$$\alpha_{\omega}^{*}$. The
reduction factor $\alpha_{\eta}$ is determined by analyzing the regressor
prediction error. The R-Benders approach is summarized in Algorithm II and
Fig. 5. Although a classification learning model can be trained to identify
useful cuts (as in the C-Bender approach presented in Section III.B), the
R-Benders approach does not use any classifier with the cost of filtering cuts
with one iteration delay. The only learning model in R-Benders is a regressor
to predict $\alpha_{\omega}^{*}$.

###  III-B Classification-based Cut Identification (C-Benders)

We use a supervised classification learner to identify useful cuts before
solving the master problem at each iteration k, instead of using criterion
(11). Fig. 6 conceptualizes the proposed C-Benders where dotted lines denote
non-useful cuts and solid lines denote useful cuts. The input to the
classifier is cuts generated at iteration k, and its output is cut labels.
Only useful cuts are kept; the rest are omitted from the master problem
feasible region. A neural network is trained with a suitable loss function,
such as F-score. The model architecture and hyperparameters are given in Table
I.

Figure 6: Useful cut identification with a classifier.

To prepare a training dataset, all cuts must be labeled as useful or non-
useful. We implement Benders for each demand profile sample and collect all
cuts upon convergence. We restart the Benders only to solve the master problem
while ignoring subproblems as we have already stored cuts. At each iteration
k, we add to the master problem one of the stored cuts and measure its
contribution to lower bound improvement. We repeat this procedure by
cumulatively adding cuts one after another to label all cuts of iteration k
depending on their contribution to the lower bound improvement. We repeat this
process for all Benders iterations. One alternative is to form the master
problem with all cuts first and then remove cuts one by one to observe their
impact on the lower bound. Generating a labeled dataset for C-Benders is
computationally expensive, particularly for multi-cut Benders decomposition.
The number of Benders iterations is relatively high for the SCUC problem with
intertemporal constraints, leading to a multiplicatively larger number of cuts
that should be individually checked. The number of cuts generated at each
iteration depends on the number of demand scenarios. This is another factor
that increases the computational cost of cut labeling. For instance, consider
solving the 118-bus system with a 4-hour commitment horizon and a load profile
sample with 40 stochastic scenarios. This case takes 289 iterations to
converge with a less than 1% gap. The total number of cuts generated for each
sample is 40×289 =11,560. To determine the label of each cut, we must solve
the master problem 11,560 times. Generating the training dataset for C-Benders
is computationally expensive, while R-Benders does not need such dataset
generation. However, C-Benders provides more accurate cut labels than
R-Benders, which estimates labels using (11). Fig. 7 shows the C-Benders
flowchart. The master problem is formulated in (12a)-(12d), and (2e). Filtered
cuts in (12c) are identified using the classifier. The training process is
offline and needs to be performed only once. The overall accuracy of the
learning-aided cut classification is slightly better than the non-learning cut
classification of R-Benders.

Figure 7: C-Benders flowchart.

###  III-C Combined Classifier-Regressor Benders (CR-Benders)

This approach (Fig. 8) is a combination of C-Benders and R-Benders. CR-Benders
uses a regressor to predict subproblem proxy variables $\alpha_{\omega}^{*}$
and a classifier for cut filtering before starting each iteration k. This
approach is C-Benders equipped with $\alpha_{\omega}^{*}$ prediction
capability.

Figure 8: CR-Benders flowchart.

###  III-D Subproblem Acceleration

Two non-binding constraint removal strategies can be used to accelerate
subproblem solutions, particularly for large SCUC problems. In the first
learning-aided strategy, two classifiers can be trained to identify inactive
(aka non-binding) network and generation ramp constraints at each Benders
iteration and remove them from the model [27]. Another more straightforward
yet less efficient strategy is to solve a relaxed subproblem without network
constraints. The relaxed subproblem solution and shift factors are used to
check network constraints. The violated constraints are added to the relaxed
subproblem, which is repeated until all network constraints are satisfied
[28]. These two strategies reduce computation time and memory usage. We have
used the second strategy.

##  IV NUMERICAL RESULT

The effectiveness of the proposed algorithms is evaluated in comparison to
conventional multi-cut Benders decomposition. The YALMIP toolbox and CPLEX are
used to implement Benders [29], and PyTorch is used to construct neural
network models. Simulations are conducted on a computer with an Intel(R)
Xeon(R) 2.10 GHz CPU and 512 GB of RAM.

###  IV-A Test Systems and Data Preparation

Three test systems with various scheduling horizons are used, including the
IEEE 24-bus, 118-bus, and 1354-bus systems [30]. The 24-bus system includes
ten generators and 34 transmission lines. The 118-bus system consists of 54
generators and 186 lines. The 1354-bus system has 270 generators and 1991
branches. Each case includes 40 equiprobable load profile scenarios. Table II
shows the range of load perturbation with respect to base case demand values
to incorporate daily and hourly load uncertainty. The convergence tolerance is
set to 1% for all cases.

TABLE II: Parameter Range for Demand Dataset Generation System |  Load |
---|---|---
|  [$\eta_{s}^{L}$, $\eta_{s}^{U}$] |  [$\eta_{\omega}^{L}$, $\eta_{\omega}^{U}$]
24-bus |  70%-130% |  95%-105%
118-bus |  70%-130% |  95%-105%
1354-bus |  70%-110% |  95%-105%

###  IV-B Useful Cut Statistics

Table III shows the average number of total cuts and useful cuts for different
systems where $h$ stands for horizons. To determine the usefulness of a cut,
we have calculated the contribution of each cut to improving the objective
value of the master problem. A cut is useful if it results in a non-zero
increase in the objective value. The percentage of the number of useful cuts
to total cuts reduces as the size of the system and the number of scheduling
horizons increase. For instance, for the IEEE 118-bus system with three time
periods, only 13% of cuts are labeled as useful, and the rest of 87% are non-
useful. Filtering non-useful cuts reduces the computational burden of the
master problem significantly.

TABLE III: Comparison of Total Cuts and Useful Cuts Test case |  Average number of total cuts |  Average number of useful cuts |  % of useful cuts
---|---|---|---
24-bus,1h |  224 |  103 |  46%
24-bus,12h |  1872 |  220 |  12%
118-bus,1h |  308 |  109 |  35%
118-bus,3h |  2280 |  288 |  13%
1354-bus,2h |  5520 |  795 |  15%

###  IV-C Master Problem Runtime and Solution Quality

Table IV reports the average solver time of the master problem and the
percentage of time improvement obtained by the three proposed approaches as
compared to the conventional multi-cut Benders. During each iteration of the
proposed approaches, we tackle a significantly smaller problem, resulting in
considerable time savings. All three proposed approaches outperform
conventional Benders. The time saving becomes more significant as the size of
the optimization model increases. For instance, R-Benders reduces the master
problem solution time from 236 seconds to 30 for the 118-bus system, an 87%
improvement. The time-saving of CR-Benders is more than R-Benders and
C-Benders.

TABLE IV: Average Solver Time (and Improvement Percentage) Comparison in Seconds System |  Benders |  R-Benders |  C-Benders |  CR-Benders
---|---|---|---|---
24-bus,1h |  2.1 |  1.4 (33%) |  0.73 (65%) |  0.66 (69%)
24-bus,12h |  37.7 |  32.9 (13%) |  9.7 (74%) |  9.4 (75%)
118-bus,1h |  2.8 |  2.6 (7%) |  2.5 (11%) |  2.5 (11%)
118-bus,3h |  236 |  30 (87%) |  57 (76%) |  24 (90%)
1354-bus,2h |  110 |  74 (33%) |  65 (41%) |  62 (44%)

The average number of Benders iterations is shown in Fig. 9. The three
proposed approaches, particularly C-Benders and CR-Benders, take roughly the
same number of iterations as conventional Benders decomposition. A comparison
of the solution time and the number of iterations, as well as the number of
useful cuts from Table III, show that R-Benders, C-Benders, and CR-Benders can
capture the necessary information to build a computationally less expensive
master problem.

Figure 9: Average number of iterations.

We use a CostGap index to assess the solution quality. The CostGap index
measures the difference between the objective values generated by the proposed
approaches $f^{p}$ and the conventional Benders $f^{B}D$.

$CostGap\%=\frac{|f^{P}-f^{BD}|}{f_{BD}}\times 100$ (13)

Table V presents the average CostGap index for all cases. The average cost gap
for all test cases is negligible. For instance, the gap is less than 0.02% for
the 118-bus system with a 3-hour horizon. We have observed several cases for
which the proposed approaches obtain even a better solution than the
conventional Benders. This is due to a warm start with stronger cuts in the
first iteration.

TABLE V: Costgap Index (%) System |  R-Benders |  C-Benders |  CR-Benders
---|---|---|---
24-bus,1h |  0 |  0.13 |  0.07
24-bus,12h |  0.05 |  0.8 |  0.03
118-bus,1h |  0.6 |  0.01 |  0.01
118-bus,3h |  0 |  0.02 |  0.02
1354-bus,2h |  0.04 |  0.05 |  0

###  IV-D Memory Usage

Figure 10: Memory usage comparison. A) 24-bus (1h), b) 24-bus (12h), c)
118-bus (1h), d) 118-bus (3h), and e) 1354-bus (2h).

The memory usage of the proposed approach is compared with the conventional
Benders. The memory occupied to form the constraint set from Benders cuts is
illustrated in Fig. 10. The memory requirement reduces significantly by
filtering out non-useful cuts from the model. For example, Fig. 10.d shows
that for the 118-bus system with 3h horizon, the memory usage of CR-Benders is
87.5% less than that of the conventional Benders decomposition. Fig. 11
demonstrates the number of cuts added to the master problem per iteration. The
slope of the increment for the conventional Benders is steeper than that of
RC-Benders.

Figure 11: Cumulative increment of the number of cuts for IEEE 118-bus 3h
case.

###  IV-E Non-convergent case analysis

In specific situations, the conventional Benders decomposition (BD) technique
struggles to achieve convergence within the allocated timeframe, even in the
presence of an optimal solution. Through our experiments, we have demonstrated
that the utilization of a predicted subproblem proxy can effectively address
these scenarios and enhance the duality gap. We focused on two particular
scenarios involving a 118-bus system and a 3-hour horizon, where the original
MCBD approach failed to converge within 400 iterations. By employing the
R-benders method, we observed an average convergence within 59 iterations for
these same scenarios. It is evident that the incorporation of the proxy value
yields superior performance.

##  V CONCLUSION

The proposed algorithms aim to reduce the computational costs of two-stage
SCUC using machine learning-based warm-start and cut filtering. The proposed
algorithms provide guaranteed feasible and near-optimal solutions.
Conventional Benders decomposition suffers from slow convergence and might not
reach an optimal point within a specified time. Not all cuts generated through
Benders iterations contain useful information to form the feasible region of
the master problem. Removing non-useful cuts and forming stronger cuts enhance
Benders decomposition performance. We trained a regressor to predict
subproblem objective proxy variables for the master problem. The predicted
values form the first set of cuts in the first Benders iteration. After
solving the first iteration and onward, cuts are filtered by comparing the
numerical value of cuts and the numerical value of proxy variables obtained
from that particular iteration. A classifier is trained to identify useful
cuts automatically after each Benders iteration. The proposed approaches are
applicable to many MIP problems. Simulation results on various test systems
show CR-Benders outperform R-Benders and C-Benders in terms of solution time
and memory saving. On average, CR-Benders leads to 58% time saving and 77%
memory saving, which is higher than the other two approaches. While C-Benders
and CR-Benders work better than R-Benders, they need a computationally
expensive dataset generation for classification learning training. This
procedure is, however, offline and needs to be implemented once.

## References

  * [1] A. J. Conejo, L. Baringo, A. J. Conejo, and L. Baringo, “Unit commitment and economic dispatch,” Power System Operations, pp. 197–232, 2018.
  * [2] T. Yang, D. Wu, Y. Sun, and J. Lian, “Minimum-time consensus-based approach for power system applications,” IEEE Transactions on Industrial Electronics, vol. 63, no. 2, pp. 1318–1328, 2016.
  * [3] Y. Du, Y. Li, C. Duan, H. B. Gooi, and L. Jiang, “Adjustable uncertainty set constrained unit commitment with operation risk reduced through demand response,” IEEE Transactions on Industrial Informatics, vol. 17, no. 2, pp. 1154–1165, 2021.
  * [4] W. Zhang, C. Shao, B. Hu, J. Zhou, M. Cao, K. Xie, P. Siano, and W. Li, “Proactive security-constrained unit commitment against typhoon disasters: An approximate dynamic programming approach,” IEEE Transactions on Industrial Informatics, vol. 19, no. 5, pp. 7076–7087, 2023.
  * [5] C. C. Carøe and J. Tind, “L-shaped decomposition of two-stage stochastic programs with integer recourse,” Mathematical Programming, vol. 83, pp. 451–464, 1998.
  * [6] A. J. Conejo, E. Castillo, R. Mínguez, and R. García-Bertrand, “Decomposition in linear programming: complicating variables,” Decomposition Techniques in Mathematical Programming: Engineering and Science Applications, pp. 107–139, 2006.
  * [7] T. L. Magnanti and R. T. Wong, “Accelerating benders decomposition: Algorithmic enhancement and model selection criteria,” Operations research, vol. 29, no. 3, pp. 464–484, 1981.
  * [8] M. Minoux, Mathematical programming: theory and algorithms.  John Wiley & Sons, 1986.
  * [9] J. BnnoBRs, “Partitioning procedures for solving mixed-variables programming problems ‘,” Numerische mathematik, vol. 4, no. 1, pp. 238–252, 1962\.
  * [10] R. Rahmaniani, T. G. Crainic, M. Gendreau, and W. Rei, “The benders decomposition algorithm: A literature review,” European Journal of Operational Research, vol. 259, no. 3, pp. 801–817, 2017.
  * [11] K. Holmberg, “On the convergence of cross decomposition,” Mathematical Programming, vol. 47, pp. 269–296, 1990.
  * [12] A. I. Corréa, A. Langevin, and L.-M. Rousseau, “Scheduling and routing of automated guided vehicles: A hybrid approach,” Computers & operations research, vol. 34, no. 6, pp. 1688–1707, 2007.
  * [13] J.-F. Cordeau, G. Stojković, F. Soumis, and J. Desrosiers, “Benders decomposition for simultaneous aircraft routing and crew scheduling,” Transportation science, vol. 35, no. 4, pp. 375–388, 2001.
  * [14] M. I. Restrepo Ruiz, Grammar-Based Decomposition Methods for Multi-Activity Tour Scheduling.  PhD thesis, École Polytechnique de Montréal, 2015.
  * [15] J. Naoum-Sawaya and S. Elhedhli, “A nested benders decomposition approach for telecommunication network planning,” Naval Research Logistics (NRL), vol. 57, no. 6, pp. 519–539, 2010.
  * [16] K. Brandes, Implementierung und analyse verschiedener strategien zur aggregation und disaggregation von multi-cuts im benders dekompositionsverfahren.  PhD thesis, Master’s thesis, Universität Paderborn, North Rhine-Westphalia, Germany, 2011.
  * [17] A. Paulus, M. Rolínek, V. Musil, B. Amos, and G. Martius, “Comboptnet: Fit the right np-hard problem by learning integer programming constraints,” in International Conference on Machine Learning, pp. 8443–8453, PMLR, 2021\.
  * [18] M. Mohammadi and A. Mohammadi, “Empowering distributed solutions in renewable energy systems and grid optimization,” arXiv preprint arXiv:2310.15468, 2023.
  * [19] H. Jia and S. Shen, “Benders cut classification via support vector machines for solving two-stage stochastic programs,” INFORMS Journal on Optimization, vol. 3, no. 3, pp. 278–297, 2021.
  * [20] B. Vandenbussche, S. Delikaraoglou, I. Blanco, and G. Hug, “Data-driven adaptive benders decomposition for the stochastic unit commitment problem,” arXiv preprint arXiv:1912.01039, 2019.
  * [21] M. Lee, N. Ma, G. Yu, and H. Dai, “Accelerating generalized benders decomposition for wireless resource allocation,” IEEE Transactions on Wireless Communications, vol. 20, no. 2, pp. 1233–1247, 2020.
  * [22] A. Ruszczyński, “Decomposition methods,” Handbooks in operations research and management science, vol. 10, pp. 141–211, 2003.
  * [23] A. J. Conejo and L. Baringo, Power system operations, vol. 11.  Springer, 2018.
  * [24] J. R. Birge and F. V. Louveaux, “A multicut algorithm for two-stage stochastic linear programs,” European Journal of Operational Research, vol. 34, no. 3, pp. 384–392, 1988.
  * [25] L. Su, L. Tang, and I. E. Grossmann, “Computational strategies for improved minlp algorithms,” Computers & Chemical Engineering, vol. 75, pp. 40–48, 2015.
  * [26] A. Nasri, S. J. Kazempour, A. J. Conejo, and M. Ghandhari, “Network-constrained ac unit commitment under uncertainty: A benders’ decomposition approach,” IEEE transactions on power systems, vol. 31, no. 1, pp. 412–422, 2015.
  * [27] F. Hasan and A. Kargarian, “Topology-aware learning assisted branch and ramp constraints screening for dynamic economic dispatch,” IEEE Transactions on Power Systems, vol. 37, no. 5, pp. 3495–3505, 2022.
  * [28] D. A. Tejada-Arango, P. Sánchez-Martın, and A. Ramos, “Security constrained unit commitment using line outage distribution factors,” IEEE Transactions on power systems, vol. 33, no. 1, pp. 329–337, 2017.
  * [29] J. Lofberg, “Yalmip: A toolbox for modeling and optimization in matlab,” in 2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508), pp. 284–289, IEEE, 2004.
  * [30] S. Babaeinejadsarookolaee, A. Birchfield, R. D. Christie, C. Coffrin, C. DeMarco, R. Diao, M. Ferris, S. Fliscounakis, S. Greene, R. Huang, et al., “The power grid library for benchmarking ac optimal power flow algorithms,” arXiv preprint arXiv:1908.02788, 2019.