#  *○ COSMic: A Coherence-Aware Generation Metric for Image Descriptions

Mert İnan
University of Pittsburgh
<EMAIL_ADDRESS>& Piyush Sharma
Google Research
<EMAIL_ADDRESS>& Baber Khalid
Rutgers University
<EMAIL_ADDRESS>Radu Soricut
Google Research
<EMAIL_ADDRESS>& Matthew Stone
Rutgers University
<EMAIL_ADDRESS>& Malihe Alikhani
University of Pittsburgh
<EMAIL_ADDRESS>
###### Abstract

Developers of text generation models rely on automated evaluation metrics as a
stand-in for slow and expensive manual evaluations. However, image captioning
metrics have struggled to give accurate learned estimates of the semantic and
pragmatic success of output text. We address this weakness by introducing the
first discourse-aware learned generation metric for evaluating image
descriptions. Our approach is inspired by computational theories of discourse
for capturing information goals using coherence. We present a dataset of
image–description pairs annotated with coherence relations. We then train a
coherence-aware metric on a subset of the Conceptual Captions dataset and
measure its effectiveness—its ability to predict human ratings of output
captions—on a test set composed of out-of-domain images. We demonstrate a
higher Kendall Correlation Coefficient for our proposed metric with the human
judgments for the results of a number of state-of-the-art coherence-aware
caption generation models when compared to several other metrics including
recently proposed learned metrics such as BLEURT and BERTScore.

##  1 Introduction

---
Caption | Coh. |  CIDEr | COSMic
Model |  first flower of the year | Story | 0.000 | 0.653
Human |  close-up of pink flowers | Visible
Figure 1:  A comparison of the scores for a generated (Model) caption that has
a different coherence relation than the reference (Human) caption. “Coh.”
represents the coherence labels for generated and reference captions. Our
coherence-aware metric COSMic is aware of the different information goals for
these captions, and assigns a more adequate score when comparing the Model
caption against the Human caption. In this case where a caption that does not
just describe the image but elaborates on it, our metric recognizes that the
model output is potentially successful (Photo credit: Moorthy Gounder)

An investigation of the descriptions used with images on the web shows that
image descriptions can have different functions and goals Kruk et al. (2019a);
Alikhani et al. (2020). For instance, captions may describe visible entities,
activities and relationships, provide background information that goes beyond
what’s visible, or report the writer’s own subjective reactions to what’s
displayed. By drawing on such diverse examples, image captioning models can
learn the different inferential links between text and images and use that
information at generation time to produce descriptions that can fulfill
different discourse goals and inject the desired context into their output
Papineni et al. (2002); Lin (2004); Denkowski and Lavie (2014); Anderson et
al. (2016a).

So far, however, efforts to develop such expressive captioning models have
been hindered by the lack of automatic metrics that can evaluate their output
with respect to their information goals in context. Previous approaches to
automatic caption evaluation have mostly focused on n-gram measures of
similarity to reference output Vedantam et al. (2014); such surface-level
models fail to deal with the lexical and syntactic diversity of image
descriptions. More recent approaches more closely approximate semantic
similarity using word embedding-based techniques. These models show robust
performance and achieve a higher correlation with human judgments than that of
previous metrics. Nevertheless, they too fail to generalize to the different
kinds of content that successful descriptions may exhibit across different
goals and contexts. That is, they cannot distinguish reasonable descriptions
that happen to differ from reference output in their goals and perspective,
from problematic descriptions that hallucinate inappropriate content or
context.

To bridge this gap, we present a coherence-aware embedding-based generation
metric that learns to respect diverse discourse goals without penalizing
captions that are purposefully generated to fulfill different purposes or
communicate background information. Figure 1 demonstrates this capability by
presenting an example image and captions with different coherence labels
together with their scores.

Our approach to modeling discourse goals is based on the framework of
discourse coherence theory Hobbs (1985), which characterizes the inferences
that give discourse units a coherent joint interpretation using a constrained
inventory of coherence relations. In particular, we use the taxonomy for
image–text coherence developed by Alikhani et al. (2020), which for example
includes Visible, Story and Subjective relations between the text and the
image. A description and an image stand in a Visible relation if the text
includes information that is recognizably depicted in the image. Subjective
captions react to the content of the image and Story captions provide a free-
standing description of the circumstances depicted in the image similar to the
Narration relation in text. Our metric is learned in part from a new dataset
of 4000 images with descriptions labeled with different coherence labels in
this taxonomy.

In inaugurating the study of coherence-aware generation metrics, we make the
following specific contributions. In Section 3 we present two different,
annotated datasets for training and testing a coherence-aware metric. We
present a model to score a generated caption given the image, reference
caption, and the discourse goals of both these captions (Section 4). We
compare this metric to previous ones using a common methodology, ranking the
performance of several different caption generation systems on out-of-domain
images—relying on a new benchmark out-of-domain test set, which we publish,
providing reference captions for a subset of OpenImages Kuznetsova et al.
(2020b). Our experiments demonstrate that among all these metrics, our
proposed metric has the highest correlation with human judgments.

##  2 Related work

There are diverse ways of characterizing the contributions of text and
imagery. Gao et al. (2015) investigate the genre of image captions and Huang
and Kovashka (2016) study the persuasive implicit relationships between text
and images. Kruk et al. (2019b) study the emotional links between text and
images. Otto et al. (2019) present an annotated dataset of text and imagery
that compares the information load in text and images. However, we build on
works that study information-level inferences between discourse units in
different modalities such as comic book panels McCloud (1993), movie plots
Cumming et al. (2017), and diagrammatic elements Hiippala et al. (2021). In
particular, we use Alikhani et al. (2020)’s relations that characterize
inferences between text and images.

Coherence-aware models have benefited several NLP tasks such as gesture
interpretation Lascarides and Stone (2009); Pustejovsky and Krishnaswamy
(2020), text summarization Xu et al. (2019), machine comprehension Gao et al.
(2020). The majority of these works use Rhetorical Structure Theory (RST) Mann
and Thompson (1987) and Penn Discourse TreeBank (PDTB) Prasad et al. (2008b)
datasets to learn and predict these relations between two adjacent text spans.
In this line of work, we are the first to present a coherence-aware generation
metric.

|  |  |
---|---|---|---
Facade of a glass building. |  A pink flower bush in a garden. |  The underside of the Arc de Triomphe. |  Close-up of a fly sitting on a daisy.
|  |  |
Man sitting by his artwork looking at a large statue of a man on a horse in a royal courtyard. |  Woman with an umbrella reading a book sitting in the grass in front of a city skyline. |  Cowboy on a horse and cowboy on the ground working together to lasso a calf in a pen. |  Black and white artwork painted on a blue wall.
Figure 2: Examples of the ground truth captions that we collected for the COIN
dataset. (Photo credits from left to right, top to bottom: Sharron Mollerus,
Northfielder, George M. Groutas, davebloggs007, Tim Adams, Brisbane City
Council, Colin Brown, Guilhem Vellut)

The most widely used automatic evaluation metrics are ngram-based, which
compute the exact number of ngram matches between reference and generated text
Cui et al. (2018). Examples of such metrics that are commonly used for
evaluating the output of captioning, translation and summarization models are
BLEU Papineni et al. (2002), ROUGE Lin (2004), and CIDEr Vedantam et al.
(2015), . The major problem of the n-gram similarity metrics is that they give
no credit to synonym matches of reference n-grams, even if those words are
common and used appropriately in the generated text. Embedding-based metrics
such as BLEURT Sellam et al. (2020) and BERTScore Zhang et al. (2020) designed
to address this limitation are closer to human ratings. BLEURT is a data-
intensive training scheme that is based on BERT Devlin et al. (2019) fine-
tuned on human ratings of generated text. BERTScore, however, computes the
similarity score as the average of cosine similarities between predicted
tokens and their top matching reference tokens. These metrics however, do not
respect the information goal and the purpose for which the model has generated
the text. We address this problem by introducing the first coherence-aware
generation metric. Similar to SPICE Anderson et al. (2016b) and VIFIDEL
Madhyastha et al. (2019) we use the information encoded in images. We further
propose the addition of coherence relations that facilitate learning with
fewer samples by a multimodal metric using pre-trained BERT and ViLBERT.

Figure 3:  An illustration of different flavors of COSMic that outputs a score
for the generated caption given the image, reference caption, and the
coherence-labels for both the captions. (a) COSMic Vanilla uses only global
textual and visual features, while (b) COSMic ViLBERT uses combined visio-
linguistic features with both local and global focus. This model takes into
account the information goals (determined by coherence-labels) for both the
captions when comparing the generated caption to the reference for evaluation.

##  3 Data Collection

We collect two datasets: human judgments for image captions that are generated
by coherence-aware captioning systems using Conceptual Captions dataset; and
ground-truth labels for the Open Images dataset. With Conceptual Captions
corpora we fine-tune ViLBERT with ratings and show that addition of coherence
relations can make automated scoring closer to human scoring. We use
OpenImages corpora to reinforce that multimodality and coherence relations
have significant contributions to scoring out-of-domain datasets, as well.

#### Protocol

We hired two expert linguists for data annotation and designed an annotation
website to facilitate the annotation procedure. They are native English
speakers who identify themselves as of White and Latino ethnicity. The code
111https://github.com/Merterm/COSMic of the annotation website, and the
details of the protocol is publicly available. The study has been approved by
our institution’s human subject board.

#### Conceptual Captions Score Annotation

We have collected ratings on the quality of different image descriptions with
coherence labels for a subset of 1000 images from the Conceptual Captions (CC)
training dataset Ng et al. (2020). With this paper, we are publishing this
dataset as a benchmark for evaluation metrics that are coherence-aware. The
set-up of the data collection is as follows: CC images are input into a
caption-generation model created by Alikhani et al. (2020). This model
generates coherence-aware descriptions for input images in 4 different
coherence classes of Meta, Visible, Subjective, Story. These 4,000
image/caption pairs are then presented to human annotators who are asked to
select the correct coherence label for each pair:

  * •

Meta: the caption talks about when, where, and how the picture is taken. Meta-
talk in Schiffrin (1980)

  * •

Visible: the caption is true just by looking at the picture. Restatement
relation in Prasad et al. (2008a).

  * •

Subjective: the captions is the matter of opinion. Evaluation relation in
Hobbs (1985).

  * •

Story: text and image work like story and illustration. Occasion relation in
Hobbs (1985).

After the annotator selects a specific coherence label from the above, we ask
them to rate the quality of the captions, given the label, on a scale of 1 to
5. We use these annotations as training data for our coherence-aware
captioning metric, COSMic. We call this data we annotated RaCCoon (Ratings for
Conceptual Caption).

To calculate the Cohen’s $\kappa$ agreement measure, we selected 150 images
randomly and assigned them to two annotators. The Kappa coefficient is
$\kappa=0.89$ which indicates a substantial agreement Viera and Garrett (2005)

#### OpenImages Ground Truth Captions

To create an out of domain test set we asked our annotators to write Visible
captions for 1,000 images222The same subset, named T2, was used for the
CVPR-2019 Workshop on Conceptual Captions, www.conceptualcaptions.com. from
the OpenImages dataset Kuznetsova et al. (2020a). We call this dataset COIN
(Corpus of OpenImages with Natural descriptions). A sample of these ground
truth captions written by our expert linguists are presented in Figure 2. We
use this dataset to test COSMic and other learned metrics in Section 5 and
present our benchmark results in Table 1.

##  4 Method

The goal of a coherence-aware image captioning metric is to predict a score
for the generated caption given the image, reference caption, and coherence
relations of one generated caption and one reference caption. This metric
function $M$ can be formalized as predicting a score $s$ as follows:

$s=M(I,g,r,g_{c},r_{c};\theta)$ (1)

where the metric is defined by parameters $\theta$, and where the model inputs
are defined as $I$ being the image being captioned, $g$ and $r$ the generated
and reference captions, respectively. $g_{c}$ and $r_{c}$ are the coherence
relations for $g$, $r$ respectively.

We now describe the architecture of our coherence-aware image captioning
metric, COSMic (COherence-Sensitive Metric of image captions). It has two
flavors — a ViLBERT-based model pre-trained on large multimodal data, and a
baseline Vanilla version, as illustrated in Figure 3. Both are trained on
RaCCoon training data (Section 3) with normalized human annotated rating to
obtain the model’s target score.

###  4.1 COSMic ViLBERT

ViLBERT Lu et al. (2019) is a multimodal feature learning model pre-trained on
3.3 million Conceptual Captions image and captions data. It is trained for
masked multi-modal learning and multi-modal alignment prediction and
demonstrates strong performance on several downstream multimodal tasks such as
VQA, VCR, grounding, and image retrieval. For this reason we use a pre-trained
ViLBERT to embed our multimodal inputs shown in Equation 1 with changes to
incorporate both the captions and coherence relations.

For input image ($I$), we use the same process as ViLBERT. We use a Faster
R-CNN Ren et al. (2016) model pre-trained on Visual Genome Krishna et al.
(2016) to detect objects regions and extract features. The sequence of these
image features is denoted as $I^{\prime}$ with 100 bounding box features where
each element is $R^{2048}$. Similar to ViLBERT, we use the special token [IMG]
to denote the beginning of the bounding box features list.

For input captions ($g$, $r$) and coherence labels ($g_{c}$, $g_{r}$), the
sequence begins with the special token [CLS] followed by input text
embeddings. Each of our text inputs are tokenized and embedded using ViLBERT’s
input text pre-processing and denoted as $g^{\prime}$, $r^{\prime}$,
$g_{c}^{\prime}$, $g_{r}^{\prime}$ for $g$, $r$, $g_{c}$ and $g_{r}$
respectively. Note that the coherence labels are processed as text inputs such
as _“Visible”_ and _“Story”_ which allows the model to use its pre-trained
representations of these concepts. Each of these input sequences are separated
by the special token [SEP] to form our input sequence.

Hence, our input to ViLBERT is of form:

$v=$ ([IMG], $I^{\prime}$, [CLS], $r^{\prime}$, [SEP], $g^{\prime}$, [SEP],
$r_{c}^{\prime}$, [SEP], $g_{c}^{\prime}$)

We use a linear layer with sigmoid activation on ViLBERT’s output text logits
to compute COSMic’s output metric score ($s$).

$s=\text{Linear}(\text{ViLBERT}(v))$ (2)

During training, we fine-tune ViLBERT and the output linear layer in an end-
to-end fashion by minimizing the Mean-Squared error between the output score,
$s$ and the corresponding reference score, $y$, on the RaCCoon dataset.

###  4.2 COSMic Vanilla

The COSMic ViLBERT approach above takes advantage of multimodal pre-training
on the Conceptual Captions dataset to embed the image and text inputs. As a
simpler baseline, we now present COSMic Vanilla which independently embeds the
input image and text to be later combined for score computation with no end-
to-end training.

To extract image features, we use a ResNet50v2 He et al. (2015) model pre-
trained on ImageNet Deng et al. (2009) and linearly transform the global image
representation to 512-dimensional space.

$e_{I}=\text{Linear}_{1}(\text{AveragePool}(\text{ResNet}(I)))$ (3)

In our textual feature extraction module, we embed $g$ and $r$ independently
with a pre-trained BERT-Large-512 model. We use the _[CLS]_ token embedding as
1024 dimensional caption-level representation in each case and transform them
to 512-dimensional space.

$\displaystyle e_{g}$
$\displaystyle=\text{Linear}_{2}(\text{BERT}_{\text{CLS}}(g))$ (4)
$\displaystyle e_{r}$
$\displaystyle=\text{Linear}_{2}(\text{BERT}_{\text{CLS}}(r))$

In our coherence label embedding module, $g_{c}$ and $r_{c}$ are each
represented as one-hot vectors such that the dimensions correspond to labels
Meta, Visible, Subjective and Story. Each is embedded into a 512-dimensional
space.

$\displaystyle e_{g_{c}}$ $\displaystyle=\text{Linear}_{3}(g_{c})$ (5)
$\displaystyle e_{r_{c}}$ $\displaystyle=\text{Linear}_{3}(r_{c})$

We thus obtain the 5 vectors (each $R^{512}$), representing one of the inputs
of Equation 1. We concatenate and use a feed-forward network with
progressively smaller hidden layers of sizes $[512,256,128,64,32,16,8]$, each
with ReLU Agarap (2018) activation. The output score, $s$, is computed by a
final linear layer on top of the above network.

$\displaystyle e$
$\displaystyle=\text{concat}([e_{I},e_{g},e_{r},e_{g_{c}},e_{r_{c}}]))$ (6)
$\displaystyle s$ $\displaystyle=\text{Linear}_{4}(\text{MLP}_{1}(e))$

where $e\in R^{2560}$ and $s\in R$.

To understand the role of each component of this implementation, we further
deconstruct each module in ablation experiments described in Table 2.

System | Avg. Hum. Rating | Metrics
---|---|---
Model |  Coh. Label | B1 | B2 | M | RL | C | S | BR |  BS-F |  COSMic Vanilla |  COSMic ViLBERT |  COSMic Vanilla+ |  COSMic ViLBERT+
BUTD |  Visible | 2.191 | .163 | .077 | .049 | .160 | .092 | .030 | -.877 | .863 | .706 | .796 | .522 | .641
Base |  Visible | 3.532 | .050 | .025 | .019 | .066 | .020 | .002 | -1.114 | .862 | .696 | .777 | .516 | .614
Meta | 3.213 | .041 | .000 | .012 | .063 | .012 | .000 | -1.059 | .863 | .548 | .727 | .505 | .602
Subj. | 2.830 | .033 | .012 | .011 | .057 | .017 | .000 | -1.197 | .849 | .323 | .421 | .358 | .403
Story | 2.915 | .029 | .000 | .017 | .058 | .013 | .000 | -1.304 | .842 | .533 | .629 | .482 | .527
Lite |  Visible | 3.298 | .028 | .011 | .013 | .053 | .011 | .000 | -1.101 | .863 | .684 | .784 | .515 | .604
Meta | 2.830 | .026 | .010 | .008 | .055 | .015 | .000 | -1.084 | .859 | .548 | .748 | .511 | .565
Subj. | 2.298 | .039 | .012 | .019 | .066 | .024 | .003 | -1.217 | .849 | .364 | .451 | .379 | .419
Story | 2.426 | .036 | .000 | .018 | .062 | .021 | .000 | -1.362 | .842 | .568 | .666 | .499 | .519
Kendall’s Correlation ($\tau$) | 1.000 | .071 | .154 | .036 | -.036 | -.571 | -.052 | .286 | .445 | .571 | .546 | .667 | .764
Table 1:  System-level scores for 9 different image captioning systems as
evaluated by human annotators and various captioning metrics. Bottom-Up Top-
Down (BUTD) is trained on COCO, while others are trained on the Conceptual
Captions (CC) dataset. The evaluation however is conducted on COIN dataset,
which is out-of-domain for both COCO and CC. This domain shift causes the
n-gram based metrics (e.g. BLEU, ROUGE, CIDEr) to assign very low scores to
otherwise correct captions (See Table 4). Whereas embedding based metrics
(e.g. BLEURT, BERTScore and COSMic) do not suffer from this limitation. Since
all metrics have different scales, instead of absolute scores, we use Kendall
Rank Correlation to measure agreement with human scores. Model names are
abbreviated as follows: B1: Bleu1, B2: Bleu2, M: METEOR, RL: ROUGEL, C: CIDEr,
S: SPICE, BR: BLEURT, BS-F: BERTScore F1. COSMic models with ’+’ denote
application of data augmentation to remove training data bias. More metrics
and detailed results can be found on the code repository.

###  4.3 Coherence-aware Captioning Systems

In order to experiment with COSMic, we generate our own captions. In this
section we describe the coherence-aware captioning systems used to generate
these image captions for the training and testing of COSMic.

For our base captioning system, we use the state-of-the-art coherence-aware
captioning system introduced by Alikhani et al. (2020). It uses a Transformer-
based Vaswani et al. (2017) encoder-decoder architecture where the encoder
inputs are (1) global image features, (2) image labels, and (3) coherence
label. The coherence-label also serves as the first input token for the
decoder which generates the output captions. We set the coherence label to the
groundtruth relation at training time, and the desired relation at inference
time. We use the Conceptual Captions dataset Sharma et al. (2018) with
machine-generated coherence labels for training this captioning system. To
obtain the coherence labels above, we closely follow Alikhani et al. (2020) to
train a coherence classifier on the Clue dataset Alikhani et al. (2020) that
provides around 4K human annotated (image, caption, relation) triplets. We
present two caption-generation systems in this section.

#### Base-systems family

A family of 4 captioning systems is created by setting the coherence-label to
Meta, Visible, Subjective or Story in the base captioning model described
above. These are considered different captioning systems because the
information content and discourse goals, as controlled by the coherence label,
are different.

#### Lite-systems family

We remove the global image features from the base model’s input to obtain a
smaller, light-weight (lite) model. Similar to the base model, we obtain a
family of 4 captioning systems by changing the coherence-label.

In Section 5, we study the order in which several image captioning metrics
rank these 8 systems. The goal is to identify the metric that agrees the most
with the groundtruth rankings based on human assessments.

###  4.4 COCO-trained Captioning System

COSMic’s training data, RaCCoon, is based on Conceptual Captions and it is
coherence-aware. To test the model’s generalization capability, we use a
captioning system trained on MS COCO Chen et al. (2015). Since COSMic expects
an input coherence label, and COCO captions are Visible style by design, we
set the label to Visible. Specifically, we use the Bottom-Up Top-Down (BUTD)
Attention model Anderson et al. (2018). This helps study how well COSMic
generalizes to other captioning datasets and coherence-agnostic captioning
systems.

##  5 Experiments

Here, we describe the experimental setup to compare COSMic with other metrics.
As outlined in Section 3 and 4, we use the RaCCoon data to train our models,
and COIN to test COSMic and other metrics. We have several baseline metrics
that we compare to, which can be found on Table 1.

###  5.1 Model Training Setup

We implement COSMic—as described in Section 4—with PyTorch Paszke et al.
(2019) and train on a GTX1080 GPU. We pre-compute
BERT333https://github.com/google-research/bert and
ResNet444https://www.tensorflow.org/api_docs/python/tf/keras/applications/ResNet50V2
features using their TensorFlow Abadi et al. (2015) implementations. We use
the public ViLBERT555https://github.com/facebookresearch/vilbert-multi-task
implementation. We use a batch size of 4, and a learning rate of $2\times
10^{-6}$ for fine-tuning ViLBERT and use RAdam optimizer and stop the training
when the validation score does not change for 3 epochs. For COSMic Vanilla, we
train with a batch-size of 10, Adam optimizer Kingma and Ba (2017) with a base
learning rate of $10^{-3}$ that decays by a factor of $10^{-2}$ every 10
epochs. We observe that the Vanilla converges in approximately 100 epochs and
ViLBERT converges in 9 epochs. ViLBERT has 250 million parameters. COSMic
Vanilla includes 3,062,913 trainable parameters. Pre-trained BERT-Large and
ResNet50V2 have an additional 350 million parameters. The setup for coherence-
aware captioning models to obtain machine-generated captions for our study is
the same as Alikhani et al. (2020).

###  5.2 Baseline Captioning Metrics

To benchmark COSMic, we compare it with other learned metrics. In this section
we describe these various metrics traditionally used for measuring image
captioning systems. None of these metrics were designed to support the
coherence relations of the reference or generated captions. These serve as
baselines for COSMic.

#### N-gram based

The most popular image captioning metrics are based on precision and recall of
n-grams from generated and reference captions. We compare with Bleu1, Bleu2,
Bleu3, Bleu4 Guo and Hu (2019), ROUGEL Lin (2004), CIDEr Vedantam et al.
(2015), and SPICE Anderson et al. (2016b). We compute these using their
popular open-source implementation666https://github.com/tylin/coco-caption.

#### BLEURT

We use a pre-trained BLEURT model777https://github.com/google-research/bleurt
as a baseline for our work. Unlike N-gram based approaches, BLEURT uses BERT-
based word embeddings which are robust to variations in surface word
realizations between the reference and generated captions. We do not do any
fine-tuning for this baseline.

#### BERTScore

BERTScore888https://github.com/Tiiiger/bert_score uses a pre-trained BERT
model to embed the reference and generated captions. Text-level similarity
scores are then computed by matching the tokens’ output embeddings.

Please note that for both BERT-based baselines above (BLEURT, BERTScore), we
use the BERT-Large-512 size model.

|  |  |  |
---|---|---|---|---
Reference |  two men in scrubs performing surgery. |  mountains in front of a clear blue sky. |  large brick building next to a green lawn and big trees. |  a foggy forest.
Generated |  surgeons operating on a patient. |  mountain range as seen from the trail. |  the front of the house. |  light shining through the trees.
Figure 4:  Illustration of COIN reference captions and corresponding outputs
of the Base-Visible model. Though the generated captions are correct, an
n-gram based metric such as CIDEr assigns them a very low score due to the
variations in surface word realizations. See Table 1 for average scores over
the test set. (Photo credits, from left to right: U.S. Army Africa, Gabriel,
Fr James Bradley, Rosmarie Voegtli)

###  5.3 COIN-based Evaluation Setup

We use each baseline metric and COSMic to score the 8 different image
captioning systems described in Section 4 on the same set of test images with
reference captions. Note that the range and scale of each metric is different,
however they are all monotonously increasing functions of model quality. So in
our study, we do not analyze the absolute score assigned by these metrics, but
only their ranks. We also ask human annotators to rank these 8 captioning
systems on the same set of test images. The ranks assigned by a higher
performing metric will align better with the ranks from human annotators.

Since the captioning systems above are trained on Conceptual Captions or COCO,
we use image/caption pairs from COIN for an out-of-domain evaluation. A subset
of 50 random images is used to rank the captioning systems as described above,
resulting in 400 machine-generated captions total for the 8 captioning
systems. These were then evaluated by human annotators using the process
described in Section 3. The human-scored system level performance for each
captioning system on this test set is reported in Table 1 in “Average Human
Rating”.

We measure the alignment between metric-assigned and human-assigned scores
using the Kendall Kendall (1938) correlation coefficient. In order to
calculate the score, we first aggregate all the sample scores and average
them. Then we calculate the Kendall tau score using the SciPy 1.7.1
implementation. The score is calculated between two vectors, first of which is
the average human ratings for 8 models and the second being the investigated
metric scores for 8 models in the following order:$[$BaseVisible, BaseMeta,
BaseSubjective, BaseStory, LiteVisible, LiteMeta, LiteSubjective,
Lite${}_{Story}]$. Due to the small sample size, Kendall correlation is the
most suitable correlation measure.

A key measure of the success of an automatic evaluation metric is whether it
makes the same decision about which system is better in a head-to-head
evaluation as we would get from a human-subjects evaluation. If each system is
evaluated based on its average score, then success comes when the average
computed metric correlates closely with the average human-ranking. In
particular, we measure the alignment between metric assigned and human
assigned scores using the Kendall score, following the work of Sellam et al.
(2020).

##  6 Results

Table 1 presents the results of the COIN-based study. The last row reports the
Kendall correlation coefficient between the scores assigned by the metric and
humans.

All N-gram based metrics, such as BLEU and CIDEr, fail to adapt to the out-of-
domain ground-truth captions from COIN. This results in a relatively flat
distribution of system-level scores concentrated close to 0, and hence low
correlation coefficients. CIDEr has a highly negative Kendall’s $\tau$, which
denotes a strong negative association with human judgements. This is partly
due to low ($\sim$0.01) and hence noisy CIDEr scores. (Figure 4 provides
example cases that illustrate this argument.)

Embedding-based methods, BLEURT and BERTScore, do not suffer from this
limitation resulting in more meaningful scoring of systems and hence higher
correlation with human scores. However, by design, both these metrics are
agnostic to coherence-labels and the input image. COSMic, which is coherence-
aware, obtains the highest correlation with human scores. COSMic ViLBERT has
the highest Kendall’s correlation among all of our models. COSMic Vanilla
performs the second best among our models and it performs better than the rest
of the models in terms of Kendall’s correlation.

#### Data Augmentation

The raw RaCCoon training data has a coherence-level bias as demonstrated by
the average COSMic score for each class — Visible (0.622), Meta (0.459),
Subjective (0.236) and Story (0.397). This reflects the human annotators’ bias
towards liking Visible captions the most, and Subjective captions the least,
which is expected. However, training COSMic on this data injects the same
coherence-bias into the model which is undesirable. As presented in Table 1,
both flavors of COSMic (without the ‘+’) assign high scores to Visible
captioning systems.

To mitigate this issue, we algorithmically augment the training data to bring
the average scores for each coherence class to comparable values. We achieve
this by pairing images with random captions from the coherence class and
assigning them a score of 0. This is a valid training sample because the
randomly sampled caption does not describe the said image and serves as a
negative sample. With these operations, the class bias is significantly
reduced — Visible (0.459), Meta (0.439), Subjective (0.328) and Story (0.425).
The COSMic columns in Table 1 with ‘+’ denote that this data augmentation
approach improves ranking of captioning systems leading to better alignment
with human judgements.

#### Ablation Study

Table 2 reports the performance of COSMic Vanilla without coherence-labels
and/or the image as model inputs. We find that removal of image features
affects COSMic’s performance, showing the important contribution of images.
The performance deteriorates significantly when the coherence-labels are
removed from the model ("No $r_{c},g_{c}$" column in Table 2). This
demonstrates that COSMic successfully integrates coherence-relations in the
caption scoring process.

System | COSMic |
---|---|---
Model |  Coh. Label | Full | No $I$ | No $c$ | No $I$ & $c$
Base |  Visible | .516 | .447 | .434 | .442
Meta | .505 | .439 | .442 | .453
Subj. | .356 | .347 | .438 | .453
Story | .505 | .433 | .436 | .445
Lite |  Visible | .515 | .444 | .434 | .433
Meta | .511 | .434 | .447 | .464
Subj. | .379 | .367 | .440 | .459
Story | .499 | .440 | .433 | .442
Kendall’s Corr. ($\tau$) | .667 | .546 | -.222 | -.415
Table 2: Ablation experiment results. "No $I$" represents "COSMic Vanilla
without image features", "No $r_{c},g_{c}$" represents "COSMic Vanilla without
coherence label embeddings", finally "No $I$ & No $r_{c},g_{c}$" represents
"COSMic Vanilla without coherence label embeddings and without image
features".

##  7 Conclusion

Our work is the first step towards designing generation metrics that respect
the information goal of the generated text. We observe that a small set of
examples annotated with coherence relations can provide what is needed for
learning a discourse-aware generation metric. Our findings have implications
for designing context-aware multimodal metrics with criteria that are closer
to human ratings for evaluating machine-generated multimodal content.

We have called attention to the challenge of learning robust generation
metrics that can evaluate the output of the generation models considering the
information goals. Our findings suggest that fine-tuning ViLBERT—originally
trained with millions of images—with a smaller sample of coherence relations
and expert-annotated scoring, automated metrics can score generated captions
closer to a human rating. The presented dataset provides the opportunity for
future research in the area of image description generation, designing
discourse-aware metrics, and multimodal content evaluation. We hope that
coherence-aware text generation metrics could be used for learning better
generation models (such as abstractive summarization or story generation) and
could be deployed directly in machine learning pipelines to help in optimizing
hyper-parameters. Ultimately, it is intended to have a generalizable model
that can use a labeling mechanism—not restricted to coherence labels— to
improve applicability of generation metrics in different tasks.

##  8 Ethics

This paper describes a research prototype. We do not work with sensitive or
personal data. Our protocol was approved by our ethics board. Human subjects
participated voluntarily, undertook minimal risk, and were compensated fairly
for their time. The dataset we produced is fully anonymized. Subjects
consented to the distribution of their data as part of their participation in
the research. Technologists should think carefully before deploying our ideas
in production. Our work depends on pretrained models such as word and image
embeddings. These models are known to reproduce and even magnify societal bias
present in training data. Moreover, like many ML NLP methods, our methods are
likely to perform better for content that is better represented in training,
leading to further bias against marginalized groups. We can hope that general
methods to mitigate harms from ML bias can address these issues.

A distinctive complication of our work is the fact that many image–text
presentations involve writers expressing subjective opinions. By its nature,
our evaluation metric assesses such subjective texts based on averages and
trends across many users, which may be problematic. Although such judgments
are ultimately matters of personal taste, they are nevertheless often grounds
by which hierarchies of differences are culturally encoded and enforced. Thus,
a deployed subjective-caption generation system could well be unfair to users,
especially if those users are not confident in their own taste or critical
towards the system’s responses. Our evaluation metric is not sensitive to such
harms.

## Acknowledgements

The authors affiliated with Rutgers University were partly supported by NSF
Award CCF-19349243. Thanks to Pitt Cyber for supporting this project and the
authors from the University of Pittsburgh. We also acknowledge the Center for
Research Computing at the University of Pittsburgh for providing the required
computational resources for carrying out experiments at the University of
Pittsburgh.

## References

  * Abadi et al. (2015) Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015.  TensorFlow: Large-scale machine learning on heterogeneous systems.  Software available from tensorflow.org.
  * Agarap (2018) Abien Fred Agarap. 2018.  Deep learning using rectified linear units (relu).  _CoRR_ , abs/1803.08375.
  * Alikhani et al. (2020) Malihe Alikhani, Piyush Sharma, Shengjie Li, Radu Soricut, and Matthew Stone. 2020\.  Cross-modal coherence modeling for caption generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6525–6535, Online. Association for Computational Linguistics.
  * Anderson et al. (2016a) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016a.  SPICE: semantic propositional image caption evaluation.  _CoRR_ , abs/1607.08822.
  * Anderson et al. (2016b) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016b.  Spice: Semantic propositional image caption evaluation.  In _European Conference on Computer Vision_ , pages 382–398. Springer.
  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Chen et al. (2015) Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollar, and C. Lawrence Zitnick. 2015.  Microsoft coco captions: Data collection and evaluation server.
  * Cui et al. (2018) Yin Cui, Guandao Yang, Andreas Veit, Xun Huang, and Serge Belongie. 2018.  Learning to evaluate image captioning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5804–5812.
  * Cumming et al. (2017) Samuel Cumming, Gabriel Greenberg, and Rory Kelly. 2017.  Conventions of viewpoint coherence in film.  _Philosophers’ Imprint_ , 17(1):1–29.
  * Deng et al. (2009) J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. 2009.  ImageNet: A Large-Scale Hierarchical Image Database.  In _CVPR09_.
  * Denkowski and Lavie (2014) Michael Denkowski and Alon Lavie. 2014.  Meteor universal: Language specific translation evaluation for any target language.  In _Proceedings of the EACL 2014 Workshop on Statistical Machine Translation_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Gao et al. (2015) Haoyuan Gao, Junhua Mao, Jie Zhou, Zhiheng Huang, Lei Wang, and Wei Xu. 2015.  Are you talking to a machine? dataset and methods for multilingual image question.  In _Advances in Neural Information Processing Systems_ , pages 2296–2304.
  * Gao et al. (2020) Yifan Gao, Chien-Sheng Wu, Jingjing Li, Shafiq Joty, Steven C.H. Hoi, Caiming Xiong, Irwin King, and Michael Lyu. 2020.  Discern: Discourse-aware entailment reasoning network for conversational machine reading.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2439–2449, Online. Association for Computational Linguistics.
  * Guo and Hu (2019) Yinuo Guo and Junfeng Hu. 2019.  Meteor++ 2.0: Adopt syntactic level paraphrase knowledge into machine translation evaluation.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 501–506, Florence, Italy. Association for Computational Linguistics.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2015.  Deep residual learning for image recognition.  _CoRR_ , abs/1512.03385.
  * Hiippala et al. (2021) Tuomo Hiippala, Malihe Alikhani, Jonas Haverinen, Timo Kalliokoski, Evanfiya Logacheva, Serafina Orekhova, Aino Tuomainen, Matthew Stone, and John A. Bateman. 2021.  AI2D-RST: a multimodal corpus of 1000 primary school science diagrams.  _Lang. Resour. Evaluation_ , 55(3):661–688.
  * Hobbs (1985) Jerry R. Hobbs. 1985.  On the coherence and structure of discourse.
  * Huang and Kovashka (2016) Xinyue Huang and Adriana Kovashka. 2016.  Inferring visual persuasion via body language, setting, and deep features.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , pages 73–79.
  * Kendall (1938) M. G. Kendall. 1938.  A new measure of rank correlation.  _Biometrika_ , 30(1/2):81–93.
  * Kingma and Ba (2017) Diederik P. Kingma and Jimmy Ba. 2017.  Adam: A method for stochastic optimization.
  * Krishna et al. (2016) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, Michael Bernstein, and Li Fei-Fei. 2016.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.
  * Kruk et al. (2019a) Julia Kruk, Jonah Lubin, Karan Sikka, Xiao Lin, Dan Jurafsky, and Ajay Divakaran. 2019a.  Integrating text and image: Determining multimodal document intent in Instagram posts.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4622–4632, Hong Kong, China. Association for Computational Linguistics.
  * Kruk et al. (2019b) Julia Kruk, Jonah Lubin, Karan Sikka, Xiao Lin, Dan Jurafsky, and Ajay Divakaran. 2019b.  Integrating text and image: Determining multimodal document intent in instagram posts.  _arXiv preprint arXiv:1904.09073_.
  * Kuznetsova et al. (2020a) Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, and et al. 2020a.  The open images dataset v4.  _International Journal of Computer Vision_ , 128(7):1956–1981.
  * Kuznetsova et al. (2020b) Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, et al. 2020b.  The open images dataset v4.  _International Journal of Computer Vision_ , pages 1–26.
  * Lascarides and Stone (2009) Alex Lascarides and Matthew Stone. 2009.  A formal semantic analysis of gesture.  _Journal of Semantics_ , 26(4):393–449.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Lu et al. (2019) Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. 2019.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Madhyastha et al. (2019) Pranava Madhyastha, Josiah Wang, and Lucia Specia. 2019.  VIFIDEL: Evaluating the visual fidelity of image descriptions.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6539–6550, Florence, Italy. Association for Computational Linguistics.
  * Mann and Thompson (1987) William C Mann and Sandra A Thompson. 1987.  _Rhetorical structure theory: A theory of text organization_.  University of Southern California, Information Sciences Institute Los Angeles.
  * McCloud (1993) Scott McCloud. 1993.  _Understanding comics: The invisible art_.  William Morrow.
  * Ng et al. (2020) Edwin G. Ng, Bo Pang, Piyush Sharma, and Radu Soricut. 2020.  Understanding guided image captioning performance across domains.  _arXiv preprint arXiv:2012.02339_.
  * Otto et al. (2019) Christian Otto, Matthias Springstein, Avishek Anand, and Ralph Ewerth. 2019.  Understanding, categorizing and predicting semantic image-text relations.  In _Proceedings of the 2019 on International Conference on Multimedia Retrieval_ , pages 168–176. ACM.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  pages 311–318.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc.
  * Prasad et al. (2008a) Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Miltsakaki, Livio Robaldo, Aravind Joshi, and Bonnie Webber. 2008a.  The Penn Discourse TreeBank 2.0. In _Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC’08)_ , Marrakech, Morocco. European Language Resources Association (ELRA).
  * Prasad et al. (2008b) Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Miltsakaki, Livio Robaldo, Aravind K Joshi, and Bonnie L Webber. 2008b.  The Penn discourse treebank 2.0.  In _LREC_. Citeseer.
  * Pustejovsky and Krishnaswamy (2020) J Pustejovsky and N Krishnaswamy. 2020.  Situated meaning in multimodal dialogue: human-robot and human-computer interactions.
  * Ren et al. (2016) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. 2016.  Faster r-cnn: Towards real-time object detection with region proposal networks.
  * Schiffrin (1980) Deborah Schiffrin. 1980.  Meta-talk: Organizational and evaluative brackets in discourse.  _Sociological Inquiry_ , 50(3-4):199–236.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020.  BLEURT: Learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7881–7892, Online. Association for Computational Linguistics.
  * Sharma et al. (2018) Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. 2018.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2556–2565, Melbourne, Australia. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30, pages 5998–6008. Curran Associates, Inc.
  * Vedantam et al. (2015) Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. 2015.  CIDEr: Consensus-based image description evaluation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4566–4575.
  * Vedantam et al. (2014) Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh. 2014.  Cider: Consensus-based image description evaluation.  _CoRR_ , abs/1411.5726.
  * Viera and Garrett (2005) Anthony Viera and Joanne Garrett. 2005.  Understanding interobserver agreement: The kappa statistic.  _Family medicine_ , 37:360–3.
  * Xu et al. (2019) Jiacheng Xu, Zhe Gan, Yu Cheng, and Jingjing Liu. 2019.  Discourse-aware neural extractive text summarization.  _arXiv preprint arXiv:1910.14142_.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_.


# Modeling Gas Flow Directions as State Variables: Does it Provide More
Flexibility to Power Systems?

Junesoo Shin∗ Yannick Werner∗† and Jalal Kazempour∗
∗ Department of Wind and Energy Systems,
Technical University of Denmark, Kgs. Lyngby, Denmark
† Department of Industrial Economics and Technology Management,
Norwegian University of Science and Technology, Trondheim, Norway
<EMAIL_ADDRESS>$\\{$yanwe<EMAIL_ADDRESS>
###### Abstract

As a common practice, the direction of natural gas flow in every pipeline is
determined ex-ante for simplification purposes, and treated as a given
parameter within the scheduling problem. However, in integrated gas and
electric power networks with a large share of intermittent renewable power
supply, it is no longer straightforward to optimally predetermine the gas flow
directions. A wrong predetermination of gas flow directions may result in
feasible but not necessarily optimal schedules. We propose a mixed-integer
linear optimization model to determine the optimal gas flow directions while
scheduling the system. This unlocks additional flexibility to power systems,
provided that a tight coordination between power and gas systems exists. The
increased flexibility, although it comes at the cost of increased
computational complexity, is quantified by comparing the total operational
cost of the entire system with bidirectional gas flows as opposed to
unidirectional gas flows. We numerically show that modeling gas flow
directions as state variables may bring added value not only in the meshed but
also in the radial gas networks.
Keywords: Integrated energy systems, optimal gas flow directions, flexibility,
linepack, mixed-integer linear program.

##  1 Introduction

###  1.1 Motivation and aim

The increasing share of intermittent renewable power supply increases the need
for operational flexibility in electric power systems. Natural gas-fired power
plants are generally able to provide flexibility by quickly adjusting their
power output in order to cope with fluctuations in the renewable power supply
[1]. This, however, leads to fluctuations in the natural gas demand and might
even trigger a change of the flow direction in certain gas pipelines. If this
change contradicts the predetermined flow direction, the operational space of
natural gas-fired power plants will be shrunk. In this case, more expensive
flexibility options have to be utilized, leading to an increase of total
operational cost of the system.

Pursuing modeling simplicity, it is currently a common practice to assume that
flow directions in natural gas pipelines can be determined ex-ante based on
historical observations and expert judgement, no matter what the schedule of
gas-fired power plants is [2]. This predetermined flow direction is then
treated as a fixed parameter within the scheduling problem. This assumption is
more frequently taken in gas networks with a radial topology, as it is the
case in Denmark, compared to meshed gas networks, which is the case in Belgium
[3]. Nonetheless, it has been argued that flow directions even in meshed
networks can be predetermined in a straightforward manner, e.g., by using a
simplified model neglecting the gas flow dynamics in pipelines [4].

This practice is, however, being challenged, as the uncertainty induced by
renewable power supply propagates from the power system to the natural gas
network via coupling components at the interface of the two systems, in
particular natural gas-fired power plants. As a consequence, natural gas
demands and eventually optimal flow quantities in pipelines and even flow
directions become uncertain [5]. One may hypothesize this uncertainty will be
even more magnified in systems with significant stochastic renewable gas
injection.

This paper argues that in order to unlock the full flexibility potential that
the natural gas network can provide to the power system, not only the
schedules and flow quantities but also the gas flow directions should be
optimally determined. This calls for a change in the current practice that
predetermines the gas flow directions. We find out that even in radial gas
networks it might no longer be straightforward to optimally predetermine the
flow directions, in particular in cases that natural gas suppliers are located
far away from each other throughout the network.

Hereafter, by unidirectional we refer to those models with predetermined gas
flow directions, while by bidirectional we refer to models where the gas flow
direction in every pipeline is optimally determined along with schedules and
flow quantities.

###  1.2 State of the art

Table 1: State of the art

Reference | Convexification method | Model |  | Bidirectional
---
gas flow modeling
| Linepack
---
modeling
[6] | Convex relaxation | SDP | Yes | No
[7] | Convex relaxation | MISOCP | Yes | No
[8] | Convex relaxation | MISOCP | No | Yes
[9] | Convex relaxation | MISOCP | Yes | Yes
[10], [4] | Piecewise linear approximation | MILP | Yes | No
[11] | Piecewise linear approximation | MILP | Yes | Yes
[12] | Outer linear approximation | MILP | Yes | Yes
This paper |  | Outer linear approximation
---
(tighter constraints)
MILP | Yes | Yes

The current literature proposes a broad range of operational models for
integrated power and natural gas systems, mainly built upon convexified gas
flow equations, while taking into account the bidirectionality of gas flows
and linepack (stored gas in the pipelines). Table 1 provides an overview. The
interested reader is referred to [13] for a more comprehensive survey.
Reference [6] proposes a semidefinite programming (SDP) approach, where a
tractable and tight convex relaxation is explored using many small matrices
with lifting variables. However, for dense gas networks, it becomes
challenging to solve the resulting model due to large matrices. In addition,
[7], [8], and [9] use a second-order cone (SOC) relaxation to convexify the
gas flow equations, while proposing solutions to tighten the relaxation.
Reference [7] proposes an iterative algorithm based on sequential cone
programming to obtain a reliable solution to the original problem. Similarly,
[8] develops an iterative algorithm that is tightening the bounds of the
McCormick envelops used to convexify the bilinear terms that are necessary to
convexify the gas flow equations when accounting for linepack. Reference [9]
investigates both linepack modeling and bidirectionality, while proposing a
mixed-integer linear program (MILP) as well as a mixed-integer second-order
cone program (MISOCP). To convexify bilinear terms, a McCormick relaxation is
used. References [4], [10], and [11] propose piecewise linear approximation
methods to convexify the gas flow equations. In detail, [4] proposes a two-
stage model, where the flow direction of the passive pipelines is determined
and then a non-linear program is solved. In addition, [10] develops an
extended incremental method including a finitely bounded variable. Reference
[11] uses an incremental formulation of the piecewise linear approximation, as
originally suggested by [14]. Finally, [12] exploits an outer linear
approximation of the gas flow equations, while exploring sequential and
stochastic coupling of power and gas systems. Due to its simplicity and
computational advantages compared to other approaches presented here, we use
an outer linear approximation based on a Taylor-series expansion. For that, we
use a set of predefined fixed pressure points to approximate non-convex gas
flow dynamics.

###  1.3 Contributions

We quantify the increased flexibility potential that the natural gas system
provides to the power system by including the gas flow directions as state
variables in the scheduling problem. We consider a co-optimization problem for
the integrated power and gas system, accounting for linepack in the natural
gas pipelines. After some reformulations to achieve convexity, we compare two
cases: The first case includes only nodal pressures and pipeline flows as
state variables and assumes predetermined gas flows (unidirectional). In the
second case, the flow directions are included as state variables in the
optimization model (bidirectional). This brings an extra degree of freedom to
the system operator but at the potential expense of increased computational
complexity due to the inclusion of binary variables for representing the flow
directions. Using a stylized case study, we provide an in-depth analysis of
natural gas flow quantities, directions, and linepack utiliziation in both
cases considering a meshed as well as a radial gas network. We show that
including gas flow directions as state variables may provide substantial
flexibility to the power system and foster the utilization of linepack,
leading to a decrease in total operational cost of the integrated system.
Methodologically, we contribute to the literature by improving the currently
prevalent linear approximation of the non-linear and non-convex Weymouth
equation that governs the gas flow dynamics by further tightening the feasible
region of the approximation. This ensures that the optimal flow directions
obtained with the convexified model remain the same when recalculating them
based on the optimal pressures using the original Weymouth equation.

###  1.4 Paper organization

The remainder of this paper is organized as follows. Section 2 introduces
optimization models for the operation of integrated power and gas system with
unidirectional and bidirectional flows. Section 3 proposes a tightened version
of the outer linear approximation of the non-convex gas flow equations for
both unidirectional and bidirectional cases. Section 4 presents a detailed
analysis of both models applied to a stylized case study, considering both
meshed and radial gas network topologies. Section 5 concludes. Finally,
Appendices A-C provide further modeling details.

##  2 Formulation

###  2.1 General model

Aiming at harnessing further flexibility from the gas network by modeling flow
directions as state variables, we consider an integrated power and natural gas
system given perfect and instantaneous information exchange. Although such a
fully coordinated system does not represent the current status of real-world
system operation, it provides an ideal benchmark to evaluate the maximum
flexibility potential in the coordinated system when accounting for
bidirectionality of gas flows. We consider a deterministic model with a
single-point forecast and inelastic demand profiles while optimally
determining dispatch schedules of power generators and gas suppliers in the
day-ahead time stage. A compact form of the co-optimization model is given
below:

$\displaystyle\underset{\textbf{x},\textbf{y}}{\operatorname{Minimize}}\quad$
$\displaystyle Cost^{\text{power}}(\mathbf{x})+Cost^{\text{gas}}(\mathbf{y})$
(1a) $\displaystyle\mathbf{g}^{\text{power}}(\mathbf{x})\leq 0$ (1b)
$\displaystyle\mathbf{h}^{\text{power}}(\mathbf{x})=0$ (1c)
$\displaystyle\mathbf{g}^{\text{gas}}(\mathbf{y})\leq 0$ (1d)
$\displaystyle\mathbf{h}^{\text{gas}}(\mathbf{y})=0$ (1e)
$\displaystyle\mathbf{e}^{\text{power}}(\mathbf{x})+\mathbf{f}^{\text{gas}}(\mathbf{y})=0.$
(1f)

The objective function (1a) minimizes the total operational cost of the
integrated power and gas system. The capacity, flow, and nodal balance
constraints for power and gas systems are represented as (1b)-(1f), where (1f)
links the power and gas systems together. The power and gas system variables
are represented by vectors $\mathbf{x}$ and $\mathbf{y}$, respectively.
Throughout this paper, upper-case letters denote parameters whereas variables
are represented by lower-case letters.

Since the focus of this work lies on the difference between unidirectional and
bidirectional gas flow models, we present the objective function (1a) as well
as the power system constraints (1b)-(1c), which are shared in both models, in
Appendix A and Appendix B, respectively. Section 2.2 describes those gas
network constraints which are common in both unidirectional and bidirectional
models. Finally, we provide a detailed description of the gas flow constraints
(1d)-(1e) as well as linking constraints (1f) accounting for unidirectional
and bidirectional flows in Section 2.3 and Section 2.4, respectively.

###  2.2 Common gas system constraints

Let $m,u\in\mathcal{N}$, $k\in\mathcal{K}$, and $t\in\mathcal{T}$ denote the
set of gas network nodes, gas suppliers, and time periods, respectively. Each
gas pipeline connects two nodes of the network, such that
$(m,u)\in\mathcal{Z}$ denotes the set of all pipelines in the network. In
order to properly model technical limits of the gas network, the following set
of constraints is enforced:

$\displaystyle 0\leq g_{k,t}\leq G^{\text{max}}_{k},\hskip 5.69054pt\forall
k,t$ (2a) $\displaystyle\mathit{PR}^{\text{min}}_{m}\leq
pr_{m,t}\leq\mathit{PR}^{\text{max}}_{m},\hskip 5.69054pt\forall m,t$ (2b)
$\displaystyle pr_{u,t}\leq\Gamma_{m,u}pr_{m,t},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (2c)

Constraints (2a) limit the schedule $g_{k,t}$ of gas supply unit $k$ in time
period $t$ to its maximum capacity $G^{\text{max}}_{k}$. Constraints (2b)
enforce the nodal pressures $pr_{m,t}$ at node $m$ in time period $t$ to lie
within the technical limits $\mathit{PR}^{\text{min}}_{m}$ and
$\mathit{PR}^{\text{max}}_{m}$. We use a simplified representation of
compressors (2c) in pipeline $(m,u)\in\mathcal{Z}$, where we assume a constant
compression ratio $\Gamma_{m,u}>1$ for pipelines that host compressors and
$\Gamma_{m,u}=1$ otherwise. Furthermore, any form of energy demand from the
compressor is neglected.

###  2.3 Unidirectional gas flow constraints

The steady-state gas flow $q_{m,u,t}$ in pipeline $(m,u)$ and time period $t$
is determined by the Weymouth equation as

$\displaystyle q_{m,u,t}^{2}=K^{2}_{m,u}(pr^{2}_{m,t}-pr^{2}_{u,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t,$ (3a)

where $K_{m,u}$ denotes the natural gas flow constant of pipeline $(m,u)$,
capturing the technical characteristics of the pipeline. In the unidirectional
model, we assume that the flow direction is predetermined and fixed to flow
from node $m$ to node $u$ in all time periods, which is enforced by

$\displaystyle q_{m,u,t}\geq 0\hskip 5.69054pt\forall(m,u)\in\mathcal{Z},t,$
(4a) In addition, we enforce $\displaystyle
q_{m,u,t}=\frac{q_{m,u,t}^{\text{in }}+q_{m,u,t}^{\text{out}}}{2},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (4b)

which relates the gas flow within a pipeline to the average of its gas inflow
$q_{m,u,t}^{\text{in}}$ and outflow $q_{m,u,t}^{\text{out}}$.

Due to the slow transients of natural gas flows in pipelines, a time delay
between gas inflow and outflow exists, which behaves like an intertemporal
storage. This storage can be described by the following set of constraints:

$\displaystyle h_{m,u,t}=S_{m,u}\frac{pr_{m,t}+pr_{u,t}}{2},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (5a) $\displaystyle
h_{m,u,t}=h_{m,u,(t-1)}+q_{m,u,t}^{\text{in }}-q_{m,u,t}^{\text{out
}},\forall(m,u)\in\mathcal{Z},t$ (5b) $\displaystyle H_{m,u}^{0}\leq
h_{m,u,t},\hskip 5.69054pt\forall(m,u)\in\mathcal{Z},t=|\mathcal{T}|.$ (5c)

Constraints (5a) relate the linepack mass $h_{m,u,t}$ in the pipeline $(m,u)$
and time period $t$ to the average pressure difference of the connected nodes
and the pipeline’s specific linepack constant $S_{m,u}$, which, again,
captures the technical characteristics of the pipeline. The intertemporal
energy balance is defined by (5b), where the initial linepack mass $h_{m,u,0}$
is fixed to a given level $H_{m,u}^{0}$, by setting $h_{m,u,0}=H_{m,u}^{0}$.
Constraints (5c) ensure that a depletion of natural gas in the pipelines at
the end of the planning horizon, i.e., $t=|\mathcal{T}|$, is avoided by lower
bounding the linepack mass to the initial level.

As linking constraints in the form of (1f), the nodal balance for every gas
node $m$ is enforced by

$\displaystyle\sum_{k\in\mathcal{A}_{m}^{\rm{K}}}g_{k,t}-\sum_{i\in\mathcal{A}_{m}^{\rm{G}}}\eta_{i}p_{i,t}-\sum_{u:(m,u)\in\mathcal{Z}}\left(q_{m,u,t}^{\text{in}}-q_{m,u,t}^{\text{out}}\right)\hskip
14.22636pt=\sum_{d\in\mathcal{A}^{\rm{DG}}_{m}}D_{d,t}^{\mathrm{G}},\hskip
5.69054pt\forall m,t.$ (6)

where $\mathcal{A}_{m}^{\rm{K}}$, $\mathcal{A}_{m}^{\rm{G}}$, and
$\mathcal{A}^{\rm{DG}}_{m}$ describe the sets of gas supply units, gas-fired
power plants (GFPPs), and gas loads in node $m$, respectively. We consider the
gas supply schedule $g_{k,t}$ and power production schedule $p_{i,t}$ by GFFP
$i$ to be variable, while we assume that the gas demand $D_{d,t}^{\mathrm{G}}$
of every gas demand $d$ is fixed. The power conversion factor of GFPPs,
$\eta_{i}$, links the power and gas system operation by relating the gas
demand of GFFP $i$ to its power production.

The unidirectional gas flow constraints constitute a linear problem without
binary variables. In the following section, we show how this model can be
extended to account for bidirectional flows, resulting in a mixed-integer
linear program.

###  2.4 Bidirectional gas flow constraints

In order to account for bidirectional flows, the unidirectional Weymouth
equation (3a) is replaced by

$\displaystyle
q_{m,u,t}|q_{m,u,t}|=K^{2}_{m,u}(pr^{2}_{m,t}-pr^{2}_{u,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t,$ (7a)

which allows the gas flow $q_{m,u,t}$ to be either positive, or zero, or
negative, depending on the sign of the pressure difference
$(pr^{2}_{m}-pr^{2}_{u})$ at the adjacent nodes.

Similarly, constraints (4) are replaced by the following set of constraints:

$\displaystyle q_{m,u,t}=q^{+}_{m,u,t}-q^{-}_{m,u,t},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (8a) $\displaystyle 0\leq
q_{m,u,t}^{+}\leq My_{m,u,t},\hskip 5.69054pt\forall(m,u)\in\mathcal{Z},t$
(8b) $\displaystyle 0\leq q_{m,u,t}^{-}\leq M\left(1-y_{m,u,t}\right),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (8c) $\displaystyle
q_{m,u,t}^{+}=\frac{q_{m,u,t}^{\text{in }}+q_{m,u,t}^{\text{out }}}{2},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (8d) $\displaystyle
q_{m,u,t}^{-}=\frac{q_{u,m,t}^{\text{in }}+q_{u,m,t}^{\text{out }}}{2},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (8e) $\displaystyle q_{m,u,t}\geq
0,\hskip 5.69054pt\forall\\{(m,u)\in\mathcal{Z}|\Gamma_{m,u}\neq 1\\},t$ (8f)
$\displaystyle y_{m,u,t}\in\\{0,1\\},\forall(m,u)\in\mathcal{Z},t.$ (8g)

The gas flow $q_{m,u,t}$ is described in (8a) by two non-negative variables
$q_{m,u,t}^{+}$ and $q_{m,u,t}^{-}$ that represent flow directions from node
$m$ to $u$ and node $u$ to $m$, respectively. Using binary variable
$y_{m,u,t}$, (8b) and (8c) enforce that the gas can only flow in one direction
in each pipeline and time period using the big-M method. The value of constant
$M$ is chosen to be sufficiently high to not additionally constrain the amount
of natural gas flows, but not too high to avoid causing numerical problems.
Constraints (8d) and (8e) relate the flow in a pipeline to the average of in-
and outflow. In pipelines that host compressors, the flow direction is not
governed by the Weymouth equation, since the gas flows from a node with lower
pressure to a node with higher pressure. Hence, (8f) ensures that the flow in
these pipelines is unidirectional. Constraints (8g) introduce binary
variables.

Accounting for bidirectional flows in pipelines, the linepack constraints (5b)
have to be adjusted as

$\displaystyle h_{m,u,t}=h_{m,u,(t-1)}+q_{m,u,t}^{\text{in
}}-q_{m,u,t}^{\text{out
}}+q_{u,m,t}^{\text{in}}-q_{u,m,t}^{\text{out}},\forall(m,u)\in\mathcal{Z},t.$
(9)

Similarly, the nodal gas balance constraints (6) are rewritten as

$\displaystyle\sum_{k\in\mathcal{A}_{m}^{\rm{K}}}g_{k,t}-\sum_{i\in\mathcal{A}_{m}^{\rm{G}}}\eta_{i}p_{i,t}-\sum_{u:(m,u)\in\mathcal{Z}}\Big{(}q_{m,u,t}^{\text{in}}-q_{m,u,t}^{\text{out}}\hskip
14.22636pt+q_{u,m,t}^{\text{in}}-q_{u,m,t}^{\text{out}}\Big{)}=\sum_{d\in\mathcal{A}^{\rm{DG}}_{m}}D_{d,t}^{\mathrm{G}},\hskip
5.69054pt\forall m,t.$ (10)

Note that both unidirectional and bidirectional gas flow models are non-convex
due to the Weymouth equation (3a) and (7a). Hence, we adopt a convex linear
approximation of the Weymouth equation in the next section. Furthermore, we
improve the approximation that is currently prevalent in the literature [12,
15] by showing how it can be further tightened to account for some of the
underlying gas flow physics.

##  3 Tighter approximation

Figure 1: Outer linear approximation of the Weymouth equation.

In Appendix C, Weymouth equation is convexified using a Taylor series
approximation and relaxation. This outer approximation method violates some of
the underlying physics of gas flows. The main issues are two-fold:

  * •

The linear approximations extend to the green areas by crossing the y-axis as
shown in Fig. 1. The points in the green area treat gas flows from nodes with
lower pressure to higher pressure as feasible, since the sign of
$pr^{2}_{m}-pr^{2}_{u}$ is flipped.

  * •

The relaxation includes points on the y-axis and x-axis. Apart from the
origin, points on the y-axis have gas flows when there is no pressure
difference in the adjacent nodes. Similarly, points on the x-axis have no gas
flow when there is pressure difference in the adjacent nodes.

Since determining the optimal gas flow directions is critical to our model, we
resolve the above approximation issues by introducing the following additional
constraints that further tighten the feasible space.

$\displaystyle pr_{m,t}\geq pr_{u,t},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (11a) $\displaystyle 0\leq
q_{m,u,t}\leq M(pr_{m,t}-pr_{u,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (11b)

Constraints (11a) enforce gas flow from nodes with higher pressure to lower
pressure in the unidirectional model. To prevent gas flow in the pipelines
with zero pressure difference between the adjacent nodes, (11b) is introduced.
However, the extent to which one value can be considered larger than the other
is arbitrary, allowing the gas flow with very small pressure difference to be
feasible. The same issue exists for very small gas flow while having a large
difference in the pressures in the adjacent nodes. These issues are inherent
to any convex relaxation technique and are therefore not further addressed in
this paper.

Constraints (11a) are adjusted to account for bidirectional flows in pipelines
as

$\displaystyle(pr_{m,t}-pr_{u,t})y_{m,u,t}\geq 0,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (12a)
$\displaystyle(pr_{u,t}-pr_{m,t})(1-y_{m,u,t})\geq 0,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (12b)

However, (12a) and (12b) are non-linear due to the product of continuous
variables $pr_{m,t}$ and binary variables $y_{m,u,t}$. We use a binary
expansion method, that exactly reformulates the above non-linear expressions
as linear expressions, as given in (13). For the implementation of the binary
expansion method, two non-negative auxiliary variables $\phi_{m,t}$ and
$\phi_{u,t}$ are introduced, where $\phi_{m,t}=pr_{m,t}y_{m,u,t}$ and
$\phi_{u,t}=pr_{u,t}y_{m,u,t}$.

$\displaystyle\phi_{m,t}-\phi_{u,t}\geq 0,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (13a) $\displaystyle
pr_{u,t}-pr_{m,t}-\phi_{u,t}+\phi_{m,t}\geq 0,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (13b) $\displaystyle-
y_{m,u,t}M\leq\phi_{m,t}\leq y_{m,u,t}M,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (13c)
$\displaystyle-(1-y_{m,u,t})M\leq\phi_{m,t}-pr_{m,t}\leq(1-y_{m,u,t})M,$
$\displaystyle\hskip 14.22636pt\hskip 5.69054pt\forall(m,u)\in\mathcal{Z},t$
(13d) $\displaystyle-y_{m,u,t}M\leq\phi_{u,t}\leq y_{m,u,t}M,\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (13e)
$\displaystyle-(1-y_{m,u,t})M\leq\phi_{u,t}-pr_{u,t}\leq(1-y_{m,u,t})M,$
$\displaystyle\hskip 14.22636pt\hskip 5.69054pt\forall(m,u)\in\mathcal{Z},t.$
(13f)

Constraints (11b) are adjusted as (14a) and (14b) to account for bidirectional
gas flow.

$\displaystyle 0\leq q_{m,u,t}^{+}\leq M(pr_{m,t}-pr_{u,t})y_{m,u,t},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (14a) $\displaystyle 0\leq
q_{m,u,t}^{-}\leq M(pr_{u,t}-pr_{m,t})(1-y_{m,u,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (14b)

Dealing with the same non-linearity issue, the auxiliary variables
$\phi_{m,t}$ and $\phi_{u,t}$ are introduced to linearize (14a) and (14b) to
(15a) and (15b).

$\displaystyle 0\leq q_{m,u,t}^{+}\leq M(\phi_{m,t}-\phi_{u,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (15a) $\displaystyle 0\leq
q_{m,u,t}^{-}\leq M(pr_{u,t}-pr_{m,t}-\phi_{u,t}+\phi_{m,t}),\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (15b)

Table 2 summarizes the structure of optimization problems for both
approximated unidirectional and bidirectional gas flow models.

Table 2: Summary of approximated gas flow models.

| Optimization problem | The set of variables
---|---|---
| Unidirectional
---
(Linear program)
| Objective function: (18)
---
Power system constraints: (19)
Gas system constraints:
(2), (4b), (5), (6), (11), (21)
| $\Theta_{\mathrm{Unidirectional}}=$
---
$\\{p_{i,t},w_{j,t},g_{k,t},\theta_{n,t},f_{n,r,t},$
$h_{m,u,t},$,
$pr_{m,t},q_{m,u,t},q_{m,u,t}^{\mathrm{in}},q_{m,u,t}^{\mathrm{out}}\\}$
| Bidirectional
---
(Mixed-integer
linear program)
| Objective function: (18)
---
Power system constraints: (19)
Gas system constraints:
(2), (5a), (5c), (8), (9), (10),
(13), (15), (22)
| $\Theta_{\mathrm{Bidirectional}}=$
---
$\\{\Theta_{\mathrm{Unidirectional}},q_{m,u,t}^{+},q_{m,u,t}^{-},$
$q_{u,m,t}^{\text{in }}q_{u,m,t}^{\text{out
}},y_{m,u,t},\phi_{m,t},\phi_{u,t}\\}$

##  4 Case study

The case study is a stylized $24$-node IEEE reliability test power system,
connected to a $12$-node natural gas system that is composed of $12$ power
generators ($5$ non-GFPPs and $7$ GFPPs), $2$ wind farms, $3$ gas supply
units, $17$ electricity loads, and $4$ gas loads. The online appendix for the
original case study with network topology is available at [12]. For all cases,
the total installed wind power capacity was chosen to equal $40$% of the
hourly average electricity demand. The models are solved using Lenovo SD$530$
with two Intel Xeon Gold $6226$R processors ($2.90$ GHz, $16$ core per CPU),
and $378$ GB RAM in Julia using JuMP and Gurobi solver package $9.1.0$. Due to
computational complexities when solving the mixed-inter linear program that
describes the bidirectional gas flow model, the time horizon was split into
two parts: hours $1$ to $12$ and hours $13$ to $24$. To avoid a depletion of
natural gas in the pipelines, the linepack mass at hour $12$ is used as the
initial line pack mass of hour $13$.

Figure 2: Gas flows for unidirectional and bidirectional models in the
pipelines ($m4-m5$), ($m6-m8$), and ($m10-m11$). If the pipeline ($m4-m5$) is
present, it represents the meshed gas network, whereas if the pipeline
($m4-m5$) is removed, it represents the radial gas network.

To study the benefit of modeling bidirectional gas flows as opposed to
unidirectional gas flows in both radial and meshed systems, the gas system
network in the case study is slightly adjusted. Fig. 2 shows the gas network
diagram, including nodes $m1$ to $m12$, gas supply units GS$1$ to GS$3$, gas
loads GD$1$ to GD$3$, and GFPPs G$1$, G$2$, G$5$, etc. The dotted pipeline
between nodes $4$ and $5$ in the meshed network is removed in the radial
network topology. Note that the gas suppliers are located at different ends of
the network that are topologically far away from each other.

We observed that the unidirectional gas flow model can be solved within
seconds for both meshed and radial systems, whereas the bidirectional gas flow
model was solved in $2.6$ hours for the meshed system, and in less than two
minutes for the radial system. All input data and codes used in this paper are
publicly available in the online companion [16].

###  4.1 Model comparison

For the bidirectional gas flow model, we observe that a change in the flow
directions happens most frequently in the pipelines ($m4-m5$), ($m6-m8$), and
($m10-m11$), which are connected to nodes with gas loads and GFPPs. The gas
flow in these pipelines is shown in the attached plots in Fig. 2. It can be
further noticed, that the change of flow direction happens not only in the
meshed but also in the radial system. Moreover, the changes in flow directions
mostly occur in the later half of the day when the demands for electricity and
gas are higher. This is accompanied by a higher amount of gas that is
transported through the pipelines, indicating an increase of the utilization
of comparatively cheap GFPPs. In fact, in the meshed system, the total power
production by GFFPs as a share of total electricity demand increases from
$13.0$% in the unidirectional case to $16.7$% in the bidirectional case.
Consequently, allowing for bidirectional flows in the gas systems increases
the flexibility in the power system. This leads to an operational cost saving
of $2.1$% in the meshed system and $1.2$% in the radial system. The next
section describes the difference in gas flows and power production schedule of
GFPPs between the unidirectional and bidirectional models in detail for a
selected hour and pipeline.

###  4.2 Consequences of the non-optimal gas flow direction

To closely examine the reason for the reduced operational cost in the
bidirectional gas flow model, we zoom into hour $15$ in the meshed system.
Fig. 3 focuses on the pipeline from node $m6$ to $m8$, and depicts the
percentage change in gas flows and gas load at hour $15$ with respect to the
previous hour. In contrast to the pipeline flows, the percentage change in the
production of GFPPs G$10$ and G$11$ is computed with respect to their
installed capacity.

(a) Unidirectional gas flow model

(b) Bidirectional gas flow model

Figure 3: Close case study of nodes m$8$ and m$6$ showing the percentage
changes in gas flows, gas consumption, and production levels in hour $15$ with
respect to hour $14$. The percentage change in the production of GFPPs is
computed with respect to their installed capacity. The gas inflow into node
$6$ from $8$ in plot (3(b)) is not represented as a percentage, because the
inflow at hour $14$ is zero.

In hour 15, the electricity consumption increases by $15.8$% with respect to
the previous hour. The cheapest available power generator to meet the
increased demand is GFFP G$10$. In the unidirectional gas flow model, the
predetermined gas flow direction from node $6$ to $8$ restricts the amount of
natural gas available for the operation of G$10$. As a consequence, G$10$ is
only able to ramp up $31$% of its capacity in the unidirectional gas flow
model compared to $97$% in the bidirectional case. Hence, more expensive
generators have to be dispatched in the unidirectional gas flow model,
resulting in a higher total operational cost. Note that neither ramping nor
unit commitment constraints have been included in the model, which might
impose additional technical constraints on the operational flexibility of
GFPPs.

###  4.3 Linepack flexibility

Linepack provides additional operational flexibility to the power system based
on the temporal separation of gas inflows and outflows of pipelines due to
slow flow transients. Fig. 4 shows the total charge and discharge in two
pipelines ($m6-m8$) and ($m10-m11$). We select these two pipelines, since we
observe frequent changes of flow direction in such pipelines. A sample of
these changes has already been illustrated and discussed in Fig. 3 for the
case of meshed network. We observe that the magnitude of total charge and
discharge in the bidirectional gas flow model is comparatively higher than
that in the unidirectional gas flow model. This is not necessarily the case
for each individual pipeline, but in overall, the bidirectional model charges
and discharges more than the unidirectional model. This indicates that the
optimal determination of gas flow directions by treating them as state
variables optimizes the charging and discharging capabilities in the
pipelines, increasing the overall flexibility potential of linepack. Apart
from decreasing the total operational cost of the integrated system, we
hypotesize that the increased utilization of linepack may flatten the nodal
gas prices, since cheaper gas sources can be utilized more efficiently.

(a) Unidirectional, ($m6-m8$)

(b) Bidirectional, ($m6-m8$)

(c) Unidirectional, ($m10-m11$)

(d) Bidirectional, ($m10-m11$)

Figure 4: Linepack mass in pipelines ($m6-m8$) and ($m10-m11$) for
unidirectional and bidirectional gas flow models.

###  4.4 Approximation error

In order to validate our results, we look at the difference in the
approximation error for bidirectional and unidirectional gas flow models. The
approximation error $\Delta_{m,u,t}$ is calculated as the normalized absolute
difference of the optimal natural gas flows of the convexified problem and the
flows obtained when using the original Weymouth equation (7a) based on
pressures. The superscript * indicates optimal values obtained from the
models.

$\displaystyle\Delta_{m,u,t}=\frac{|q_{m,u,t}^{*2}-K_{m,u}^{2}(pr_{m,t}^{*2}-pr_{u,t}^{*2})|}{K_{m,u}^{2}(pr_{m,t}^{*2}-pr_{u,t}^{*2})},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (16)

Fig. 5 shows the difference in the normalized approximation error in
percentage. The blue scale indicates to what extent the bidirectional gas flow
model accurately approximates the Weymouth equation in comparison to the
unidirectional model, and vice versa for the red scale. We observe large
differences for individual pipelines and time periods. To quantify the overall
difference between both models, we use the normalized root mean square error
as

$\displaystyle\Xi=\left[\frac{1}{|\mathcal{T}|\cdot|\mathcal{Z}|}\sum_{t\in\mathcal{T}}\sum_{(m,u)\in\mathcal{Z}}\Delta_{m,u,t}^{2}\right]^{\frac{1}{2}}.$
(17)

where $|\mathcal{T}|$ and $|\mathcal{Z}|$ are the number of time periods and
pipelines, respectively. In our case study, $|\mathcal{T}|=24$ and
$|\mathcal{Z}|=12$. This error is $0.640$ and $0.636$ for the bidirectional
and unidirectional models, respectively, implying that the overall error in
both models induced by the approximation of the Weymouth equation is roughly
the same. We also notice that the approximation accuracy is highly dependent
on the number and choice of fixed pressure points used for the Taylor-series
expansion of the Weymouth equation.

Figure 5: Difference in relative errors between left-hand side and right-hand
side of Weymouth equation. The blue (red) colors indicate a higher (lower)
approximation error in the unidirectional compared to the bidirectional gas
flow model.

Improving the tightness of the approximation is critical to get meaningful
flow levels and validity of the model. For this paper, we solely present the
comparison between the errors computed. We find out that the bidirectional
model does neither improve nor worsen the overall approximation of the
Weymouth equation, compared to the unidirectional model.

##  5 Conclusion and future work

We provided a detailed analysis of the increased flexibility that the natural
gas system provides to the power system when gas flow directions are
considered as state variables in the co-optimization problem. This increased
flexibility was quantified in terms of the reduced operational cost of the
integrated system, by comparing the optimal cost achieved in models with
unidirectional and bidirectional gas flows. Using a stylized case study, we
found out that modeling gas flows as state variables reduces the operational
cost not only in meshed but also in radial networks. The latter particularly
happens in a radial network where natural gas sources are located far away
from each other in the network.

Given a set of predefined fixed pressure points, we convexified gas flow
equations using a Taylor-series expansion. It is worth mentioning that this
approximation is usually not tight at optimum, and therefore it may result in
schedules which are not necessarily feasible in terms of gas flow dynamics.
Consequently, the approximation may overestimate the flexibility that does not
exist in the real-time operation. To avoid it, we improved the currently
prevalent approximation by tightening the resulting feasible region, ensuring
correct flow directions which are consistent with the original non-convex
Weymouth equation. Furthermore, we quantified the error of approximation by
comparing the convexified and the original Weymouth equations. We found out
that the overall errors including all pipelines and time periods in the
unidirectional and bidirectional models are in the same order of magnitude.
There could be, however, large differences when it comes to individual
pipelines and time periods.

As potential directions for the future work, the impact of the approximation
error and its relation to the flexibility potential should be further
analyzed. One may also conduct a fairness analysis, exploring how the
approximation error impacts every individual in terms of the associated
operational cost (or profit in a market context). In parallel, an improvement
in convexification methods is necessary. Possible approaches and directions
have been extensively explored in other research fields, e.g., for the
alternating current (AC) power flow problem [17, 18]. The outer approximation
method based on the Taylor-series expansion can be further improved by
investigating how to more efficiently select the fixed pressure points as the
input data. Furthermore, alternative approaches, e.g., based on machine
learning [19], can be explored to reduce the computational time of the
resulting MILP in the bidirectional model, by predicting the inactive
constraints and/or the value of binary variables associated with the flow
directions at the optimal point.

This paper exploited a simplified model for the representation of compressors,
while discarding other critical gas network components such as valves. This
simplification certainly affects the flexibility potential to be unlocked by
introducing the gas flow directions as state variables. It is of interest to
leverage more detailed operational models for compressors and valves [20]. The
future work should also model potential sources of uncertainty, e.g.,
renewable power supply, and explores how uncertainty is being propagated from
power to natural gas system, depending on the topology of both networks and
their interconnection. Recall that the proposed model is a co-optimization,
which provides an ideal benchmark. However, power and gas systems are not
necessarily being operated by the same entities in the real world. Therefore,
the future work should explore how the maximum flexibility potential can be
efficiently unlocked in practice [21]. Finally, it is of importance to focus
on the transition towards the large deployment of distributed energy
resources, in particular electrolyzers and fuel cells, and their associated
impacts on the operation of integrated system.

## Appendices

###  5.1 Objective function (1a)

The objective function minimizes the total operational cost of the integrated
system, including the cost of non-GFPPs as well as gas suppliers:

$\displaystyle\underset{\mathrm{\Theta}}{\operatorname{Minimize}}\quad\sum_{t\in\mathcal{T}}\Big{(}\sum_{i\in\mathcal{C}}C_{i}^{\rm{E}}p_{i,t}+\sum_{k\in\mathcal{K}}C_{k}^{\rm{G}}g_{k,t}\Big{)},$
(18)

where $p_{i,t}$ and $g_{k,t}$ denote the schedules of power generator $i$ and
gas supplier $k$ in time period $t$, with associated production and supply
costs $C_{i}^{\rm{E}}$ and $C_{k}^{\rm{G}}$, respectively. Furthermore,
$\mathcal{C}$ denotes the set of non-GFPPs. Recall that $\mathcal{K}$ is the
set of gas suppliers. The set of primal variables is
$\Theta_{\mathrm{Unidirectional}}$ in the unidirectional gas flow model and
$\Theta_{\mathrm{Bidirectional}}$ in the bidirectional case, as already
defined in Table 2.

###  5.2 Power system constraints (1b) and (1c)

Let $(n,r)\in\mathcal{L}$ denote the set of power system lines. Using
linearized lossless power flow equations, we enforce power system constraints
by

$\displaystyle 0\leq p_{i,t}\leq P^{\text{max}}_{i},\hskip 5.69054pt\forall
i,t$ (19a) $\displaystyle 0\leq w_{j,t}\leq W_{j,t},\hskip 5.69054pt\forall
j,t$ (19b) $\displaystyle f_{n,r,t}=B_{n,r}(\theta_{n,t}-\theta_{r,t}),\hskip
5.69054pt\forall(n,r)\in\mathcal{L},t$ (19c)
$\displaystyle-F^{\text{max}}_{n,r}\leq f_{n,r,t}\leq
F^{\text{max}}_{n,r},\hskip 5.69054pt\forall(n,r)\in\mathcal{L},t$ (19d)
$\displaystyle-\pi\leq\theta_{n,t}\leq\pi,\hskip 5.69054pt\forall n,t$ (19e)
$\displaystyle\theta_{n,t}=0,\hskip 5.69054pt\forall n:ref,t$ (19f)
$\displaystyle\sum_{i\in\mathcal{A}^{\rm{I}}_{n}}p_{i,t}+\sum_{j\in\mathcal{A}^{\rm{J}}_{n}}w_{j,t}-\sum_{(n,r)\in\mathcal{L}}f_{n,r,t}=\sum_{l\in\mathcal{A}^{\rm{DE}}_{n}}D^{\mathrm{E}}_{l,t},\hskip
5.69054pt\forall n,t.$ (19g)

Constraints (19a) limit the power production schedule $p_{i,t}$ of generator
$i$ in time period $t$ to its installed capacity $P^{\text{max}}_{i}$. The
production schedule of wind farm $j$ in time period $t$, denoted by $w_{j,t}$,
is restricted in (19b) by its single-point deterministic forecast $W_{j,t}$.
Constraints (19c) compute the power flow $f_{n,r,t}$ across the line
connecting nodes $n$ and $r$ in time period $t$ as the product of the line
susceptance $B_{n,r}$ and the difference of the nodal voltage angles
$\theta_{n,t}$ and $\theta_{r,t}$. Constraints (19d) enforce transmission
capacity constraints, where $F^{\text{max}}_{n,r}$ is the capacity of line
connecting nodes $n$ and $r$. Constraints (19e) limit nodal voltage angles,
whereas (19f) fixes the voltage angle at the reference node to zero. The power
balance in every node $n$ is enforced by (19g), ensuring that the power demand
$D^{\mathrm{E}}_{l,t}$ of all loads $l$ located at node $n$ is fully met in
each time period $t$. The set of power generators, wind farms, and electricity
loads in node $n$ is denoted by $\mathcal{A}^{\rm{I}}_{n}$,
$\mathcal{A}^{\rm{J}}_{n}$, and $\mathcal{A}^{\rm{DE}}_{n}$, respectively.

###  5.3 Linear approximation of Weymouth equation

To convexify the non-convex Weymouth equation (3a) and (7a), it has to be
first relaxed and divided into two parts to represent each gas flow direction:

$\displaystyle q_{m,u,t}\leq K_{m,u}\sqrt{pr^{2}_{m,t}-pr^{2}_{u,t}},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t$ (20a) $\displaystyle q_{u,m,t}\leq
K_{m,u}\sqrt{pr^{2}_{u,t}-pr^{2}_{m,t}},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},t.$ (20b)

Afterwards, a Taylor series approximation is performed around a set of given
fixed pressure points $(PR_{m,v},PR_{u,v})$ to approximate the non-convex
equations (20) [15, 12]. The tightness of this approximation can be controlled
by the number of pressure points $v$ at the cost of increasing computational
complexity.

Since the flow directions are predetermined in the unidirectional gas flow
model, we only need to consider the flow (20a), which is approximated by

$\displaystyle
q_{m,u,t}\leq\frac{K_{m,u}PR_{m,v}}{\sqrt{PR^{2}_{m,v}-PR^{2}_{u,v}}}pr_{m,t}-\frac{K_{m,u}PR_{u,v}}{\sqrt{PR^{2}_{m,v}-PR^{2}_{u,v}}}pr_{u,t},\hskip
5.69054pt\forall(m,u)\in\mathcal{Z},v,t.$ (21)

In the bidirectional gas flow model, the flow directions are endogenously
determined in the co-optimization model. Thus, we approximate (20a) and (20b)
by properly accounting for the flow direction as

$\displaystyle
q_{m,u,t}^{+}\leq\frac{K_{m,u}PR_{m,v}}{\sqrt{PR^{2}_{m,v}-PR^{2}_{u,v}}}pr_{m,t}-\frac{K_{m,u}PR_{u,v}}{\sqrt{PR^{2}_{m,v}-PR^{2}_{u,v}}}pr_{u,t}\hskip
5.69054pt+M\left(1-y_{m,u,t}\right),\hskip
5.69054pt\forall\\{(m,u)\in\mathcal{Z}|m>u\\},v,t$ (22a) $\displaystyle
q_{m,u,t}^{-}\leq\frac{K_{m,u}PR_{u,v}}{\sqrt{PR^{2}_{u,v}-PR^{2}_{m,v}}}pr_{u,t}-\frac{K_{m,u}PR_{m,v}}{\sqrt{PR^{2}_{u,v}-PR^{2}_{m,v}}}pr_{m,t}\hskip
5.69054pt+My_{m,u,t},\hskip
5.69054pt\forall\\{(m,u)\in\mathcal{Z}|m<u\\},v,t.$ (22b)

The terms including the binary variables $M(1-y_{m,u,t})$ and $My_{m,u,t}$
ensure that when either $q_{m,u,t}^{+}$ or $q_{m,u,t}^{-}$ takes a zero value,
the corresponding constraint (22a) or (22b) is inactive.

## References

  * [1] J. Gil, A. Caballero and A.. Conejo  “Power cycling: CCGTs: The critical link between the electricity and natural gas markets”  In _IEEE Power and Energy Magazine_ 12.6, 2014, pp. 40–48
  * [2] Olivier Massol and Albert Banal-Estañol  “Market power and spatial arbitrage between interconnected gas hubs”  In _The Energy Journal_ 39 International Association for Energy Economics, 2018, pp. 67–95  DOI: 10.5547/01956574.39.SI2.omas
  * [3] European Network of Transmission System Operators for Gas (ENTSOG)  “European network of transmission system operators for gas – Transparency platform”  URL: https://transparency.entsog.eu/#/map
  * [4] Jorge Munoz, Jimenez-Redondo Noemi, Perez-Ruiz Juan and Barquin Julian  “Natural gas network modeling for power systems reliability studies”  In _IEEE Bologna Power Tech Conference_ , 2003, pp. 1–8
  * [5] Nico Keyaerts, Erik Delarue, Yannick Rombauts and William D’haeseleer  “Impact of unpredictable renewables on gas-balancing design in Europe”  In _Applied Energy_ 119, 2014, pp. 266–277
  * [6] Saeed D. and Mohammad E. Khodayar  “Coordinated operation of electricity and natural gas systems: A convex relaxation approach”  In _IEEE Transactions on Smart Grid_ 10.3, 2019
  * [7] Yubin He et al.  “Decentralized optimization of multi-area electricity-natural gas flows based on cone reformulation”  In _IEEE Transactions on Power Systems_ 33.4 Institute of ElectricalElectronics Engineers Inc., 2018, pp. 4531–4542  DOI: 10.1109/TPWRS.2017.2788052
  * [8] Sheng Chen, Antonio J. Conejo, Ramteen Sioshansi and Zhinong Wei  “Unit commitment with an enhanced natural gas-flow model”  In _IEEE Transactions on Power Systems_ 34.5, 2019, pp. 3729–3738
  * [9] Anna Schwele, Christos Ordoudis, Jalal Kazempour and Pierre Pinson  “Coordination of power and natural gas systems: Convexification approaches for linepack modeling”  In _IEEE Milan Power Tech Conference_ , 2019, pp. 1–6
  * [10] Mathias Sirvent, Nikolaos Kanelakis, Björn Geißler and Pandelis Biskas  “Linearized model for optimization of coupled electricity and natural gas systems”  In _Journal of Modern Power Systems and Clean Energy_ 5.3, 2017
  * [11] Carlos M. Correa-Posada and Pedro Sanchez-Martin  “Integrated power and natural gas model for energy adequacy in short-term operation”  In _IEEE Transactions on Power Systems_ 30.6, 2015  DOI: 10.1109/TPWRS.2014.2372013
  * [12] Christos Ordoudis, Pierre Pinson and Juan M. Morales  “An integrated market for electricity and natural gas systems with stochastic power producers”  In _European Journal of Operational Research_ 272.2 Elsevier B.V., 2019, pp. 642–654  DOI: 10.1016/j.ejor.2018.06.036
  * [13] Enrica Raheli, Qiuwei Wu, Menglin Zhang and Changyun Wen  “Optimal coordinated operation of integrated natural gas and electric power systems: A review of modeling and solution methods”  In _Renewable and Sustainable Energy Reviews_ 145.111134 Elsevier Ltd, 2021  DOI: 10.1016/j.rser.2021.111134
  * [14] Carlos M Correa-Posada and Pedro Sánchez-Martín  “Gas network optimization: A comparison of piecewise linear models”, 2014, pp. 1–24  URL: http://www.optimization-online.org/DB_FILE/2014/10/4580.pdf
  * [15] Asgeir Tomasgard, Frode Rømo, Marte Fodstad and Kjetil Midthun  “Optimization models for the natural gas value chain”  In _Geometric Modelling, Numerical Simulation, and Optimization_ , 2007, pp. 521–558  DOI: 10.1007/978-3-540-68783-2–“˙˝16
  * [16] Junesoo Shin, Yannick Werner and Jalal Kazempour  “Modeling gas flow directions as state variables: Does it provide more flexibility to power systems?”, 2022  DOI: 10.5281/zenodo.5546581
  * [17] Andreas Venzke, Spyros Chatzivasileiadis and Daniel K. Molzahn  “Inexact convex relaxations for AC optimal power flow: Towards AC feasibility”  In _Electric Power Systems Research_ 187.106480 Elsevier Ltd, 2020  DOI: 10.1016/j.epsr.2020.106480
  * [18] K. Baker  “Emulating AC OPF solvers for obtaining sub-second feasible, near-optimal solutions”  URL: https://arxiv.org/abs/2012.10031
  * [19] Dimitris Bertsimas and Bartolomeo Stellato  “Online mixed-integer optimization in milliseconds” to be published  In _INFORMS Journal on Computing_ , 2022
  * [20] M. Sidhant et al.  “Optimal compression in natural gas networks: A geometric programming approach”  In _IEEE Transactions on Control of Network Systems_ 2.1, 2015, pp. 47–56
  * [21] G. Byeon and P. Van Hentenryck  “Unit commitment with gas network awareness”  In _IEEE Transactions on Power Systems_ 35.2, 2020, pp. 1327–1339