# An Electricity Market Clearing Formulation for
Harnessing Space-Time, Load-Shifting Flexibility
from Data Centers

Weiqi Zhang‡ and Victor M. Zavala‡
‡Department of Chemical and Biological Engineering
University of Wisconsin-Madison, 1415 Engineering Dr, Madison, WI 53706, USA
Corresponding Author<EMAIL_ADDRESS>
###### Abstract

In this work, we provide a theoretical analysis of an electricity market
clearing formulation that seeks to harness spatio-temporal, load-shifting
flexibility from data centers (DaCes). Central to our study is the concept of
virtual links, which provide non-physical pathways that can be used by DaCes
to shift power loads (by shifting computing loads) across space and time. We
use virtual links to show that the clearing formulation treats DaCes as
prosumers that simultaneously request load and provide a load-shifting
flexibility service. Our analysis also reveals that DaCes are remunerated for
the provision of load shifting flexibility based on nodal price differences
(across space and time). We also show that DaCe flexibility helps relieve
space-time price volatility and show that the clearing formulation satisfies
fundamental economic properties that are expected from coordinated markets
(e.g., provides a competitive equilibrium and achieves revenue adequacy and
cost recovery). Case studies are presented to demonstrate these properties.

Keywords: market clearing; virtual links; electricity; pricing; flexibility;
space-time

##  1 Introduction

The power grid is undergoing major structural changes due to the adoption of
large amounts of renewable power. Multiple U.S. states have set ambitious
renewable portfolio standards (RPS) that dictate the required level of
renewable energy use in the near future, including California (50% by 2030
according to California Public Utilities Commission 2019), Minnesota and New
York (around 25% by 2025 and 70 % by 2030 according to National Conference of
State Legislatures 2019). A critical challenge that emerges here is the
unsteady, non-dispatchable, and spatio-temporal nature of renewable power.
Enabling high penetration of renewable power requires new sources of load-
shifting flexibility (Wierman et al. 2017). Flexibility is a key asset in
power system operations that is often harnessed from consumers via demand
response and pricing signals (Aghaei and Alizadeh 2013).

Rapid expansion of the computing industry also pose significant challenges to
the power grid. Power use from the information technology (IT) sector is
experiencing fast growth (8% in 2016 and projected at 13% in 2027) and the
dynamics and spatial distribution of data centers (DaCes) now represents a
significant demand on the grid. In addition, computing infrastructure is
undergoing structural changes; specifically, motivated by economies of scale,
large companies (e.g., Amazon, Google, Alibaba, and Tencent) are centralizing
DaCes. These DaCes form a computing infrastructure that is managed
collectively via network operation centers (NOCs). NOCs have the ability to
shift computing loads/jobs (and associated power loads) across time (via job
scheduling) and across space (via service migration). As a result, NOCs can
play an important role in providing space-time load-shifting flexibility to
the power grid. These synergies are illustrated in Figure 1.

Figure 1: Interactions between the computing and power infrastructures.

These trends have motivated research into market mechanisms that harness
space-time flexiblity from DaCes. Recent work by Wierman and co-workers has
identified various forms of DaCe flexibility that can be of practical use such
as load shifting, load shedding, and geographical load balancing (Wierman et
al. 2017). The work in Ghatikar et al. (2012) reviews how operations of DaCes
can provide demand response services. The work in Rao et al. (2010) analyzes
how NOCs may be incentivized to exploit price differences across electricity
markets. The work in Tran et al. (2015) sets up a Stackelberg game to simulate
optimal load-shifting strategies that DaCes might follow to real-time pricing
signals. For temporal flexibility. The work in Liu et al. (2013) uses a
stochastic optimization framework to study how DCs can predict coincidental
peak-pricing and avoid high cost caused by peak hours using temporal workload
shifting. Research has also focused on harnessing DaCe flexibility for the
specific purpose of exploiting the availability of renewable power (e.g., as a
way to decarbonize operations and mitigate variability). For example, Kim et
al. (2017) shows that optimal placement and participation of DaCes in power
grid markets (as dispatchable loads) leads to important reductions in power
spillage and cost and to a better utilization of wind generation (thus
enabling higher adoption levels).

Modeling DaCe flexibility is challenging due to the complicated nature of
their workloads (Wierman et al. 2017). Specifically, DaCes need to process
complex mixtures of flexible and inflexible loads that vary significantly over
time. Work by Liu et al. (2014) has shown that load-shifting in DaCes can be
seen as a form of large-scale storage but also note that incentivizing the
provision of DaCe flexibility in power markets is difficult. It is also
important to recognize that different DaCes possess different types and
degrees of spatial flexibility; for instance, some DaCes might only possess
local flexibility, while others might be equipped with geographical
flexibility. Similarly, some DaCes have different levels of temporal
flexibility, which is dictated by the nature of their workloads (e.g., job
duration).

DaCes demand responses have been studied using various game-theoretic modeling
frameworks. For instance, Zhou et al. (2018) and Sun et al. (2016) study how
to incentivize spatial and temporal flexibility participation from the DaCe
side using online auctioning. A Nash bargaining framework has been employed to
study the design incentive mechanisms between data centers and load-serving
entities (Cao et al. 2018) and between data centers and tenants in order to
encourage the utilization of flexibility (Guo et al. 2018). These studies have
shown that the amount of flexibility that data centers are willing to offer
is, in fact, highly dependent on electricity prices. However, the decision-
making process of DaCes is not properly taken into account in existing
electricity market designs; as such, electricity prices are limited in their
ability to incentivize the provision of flexibility.

Power grids in the U.S. are operated using a coordinated market design where
an independent system operator (ISO) collects bid information from power
consumers and suppliers and uses this information to solve a market clearing
problem (an optimization problem). The solution of this problems seeks to
determine power allocations and locational marginal prices (LMPs) that
maximize the social surplus (the collective profit of all players) subject to
myriad constraints of the underlying physical assets (e.g., transmission,
capacity). Clearing mechanisms in current use are largely based on the
pioneering work of Hogan (Hogan 1992, Hogan et al. 1996), which establishes
revenue adequacy for transmission congestion payments and uses duality theory
to determine proper remuneration mechanisms to participants using clearing
prices.

Various market clearing formulations have been proposed to capture different
characteristics of specific types of assets. For instance, the work by Carrion
and Arroyo (2006) proposes a clearing problem to capture time-dependent
limitations (start-up costs and ramping constraints) in thermal units. Recent
work also proposes formulations to capture operational logic of combined-cycle
power plants. The formulation proposed in Bouffard et al. (2005) aims to
incorporate generation uncertainty directly in the clearing procedure. Along
the same lines, the works in Pritchard et al. (2010), Zavala et al. (2017)
propose stochastic clearing formulations to analyze whether LMPs properly
reflect uncertainty of power generation, while maintaining key economic
properties in the face of such uncertainty (e.g., revenue adequacy and cost
recovery). The work in Gribik et al. (2011) proposed a pricing methodology
that captures the cost of using an off-line resource to meet operational
constraints.

Zhang et al. (2020) have recently proposed a market clearing formulation that
captures space-time load-shifting flexibility of DaCes. This flexibility is
captured in the market clearing process using a load disaggregation procedure
that can be represented using virtual links. Virtual links are non-physical
pathways that can be used by the ISO to shift power loads in space (i.e., by
sending a computing load to another geographical location) and time (i.e., by
delaying a computing load). This paradigm is compatible with existing market
clearing procedures and reveals that virtual links form an additional
infrastructure layer (similar to that overseen by NOCs) that complements the
transmission network. In this work, we provide an in-depth theoretical
analysis of market clearing formulations with virtual links. This reveals
mechanisms under which DaCes should be remunerated for their flexibility and
reveals information that DaCes should share with the ISO in the bidding
process. This also shows that DaCes act as prosumers that simultaneously pay
for requested load and that are paid for their flexibility service (there is
an incentive to offer flexibility in order to decrease total cost). Our
analysis also shows that virtual links provide a convenient mathematical
construct to establish fundamental market properties; specifically, we show
that a market that harnesses space-time load-shifting flexibility increases
the social surplus, achieves revenue adequacy, achieves cost recovery, and
mitigates space-time volatility of LMPs. The framework is applied to case
studies to illustrate the theoretical results and practical impact.

The paper is structured as follows; Section 2 presents basic market clearing
formulations that are used to introduce notation and concepts. Specifically,
we consider a formulation that uses load disaggregation to capture DaCe
flexibility and provide an equivalent representation that uses virtual links.
Section 3 presents a general market formulation that captures space-time
virtual links along with its properties. Section 4 presents cases studies to
illustrate the developments. Section 5 closes with remarks on future
directions.

##  2 Basic Market Formulations

The market clearing formulations under study incorporate several new elements
that are not standard in the power systems literature. As such, we introduce
the reader to these new concepts by exploring a family of formulations of
increasing complexity. This will also allows us to introduce basic
terminology, notation, and to highlight key concepts that motivate our work.
The market setting studied is for an energy-only setting, similar to those
studied in recent market design work by Pritchard et al. (2010), Kazempour et
al. (2018), Zakeri et al. (2019), and Zavala et al. (2017).

###  2.1 Basic Notation and Terminology

We begin our discussion by introducing basic notation for a static network
(there is no time associated with it). The market considers a set of suppliers
(owners of power plants) $\mathcal{S}$ and consumers (owners of DaCes)
$\mathcal{D}$ connected to a transmission network comprised of geographical
nodes $\mathcal{N}$ and transmission lines $\mathcal{L}$ (owned by
transmission service providers).

Each supplier $i\in\mathcal{S}$ is connected to the power grid at node
$n(i)\in\mathcal{N}$. The supplier bids into the market by offering power at
bid price $\alpha_{i}^{p}\in\mathbb{R}_{+}$ and offers available capacity
$\bar{p}_{i}\in[0,\infty)$. We define
$\mathcal{S}_{n}:=\\{i\in\mathcal{S}\,|\,n(i)=n\\}\subseteq\mathcal{S}$ (set
of suppliers connected to node $n$). The cleared allocation for supplier
$i\in\mathcal{S}$ (load injected) are denoted as $p_{i}$ and must satisfy
$p_{i}\in[0,\bar{p}_{i}]$. We use $p$ to denote the collection of all cleared
allocations.

A consumer $j\in\mathcal{D}$ bids into the market by requesting power at bid
price $\alpha_{j}^{d}\in\mathbb{R}_{+}$ and requests a maximum capacity
$\bar{d}_{j}\in[0,\infty)$. We define
$\mathcal{D}_{n}:=\\{j\in\mathcal{D}\,|\,n(j)=n\\}\subseteq\mathcal{D}$ (set
of consumers connected to node $n$). For simplicity, we assume that there is
only one consumer at a given node ($\mathcal{D}_{n}$ are singletons). The
cleared allocation for consumer $j\in\mathcal{D}$ (load withdrawn) is denoted
as $d_{j}$ and must satisfy $d_{j}\in[0,\bar{d}_{j}]$. We use $d$ to denote
the collection of all cleared allocations. A standard (inflexible) consumer
requests that the cleared load $d_{j}$ is delivered at a single node
$n(j)\in\mathcal{N}$. A flexible consumer (a DaCe owner), on the other hand,
offers the possibility that the cleared load $d_{j}$ is delivered at a set of
possible nodes $\mathcal{N}_{d}\subseteq{N}$; in other words, the cleared load
$d_{j}$ can be disaggregated and individual portions are delivered at
different nodes. We will see that this load disaggregation scheme can be seen
as a spatial, load-shifting mechanism that can be modeled using virtual links.
For simplicity, we will not make a distinction between DaCe owners and
inflexible consumers. This is because an inflexible consumer can be modeled as
a flexible consumer with $\mathcal{N}_{d}=\\{n(j)\\}$ (it offers one node
option for the load to be delivered).

Each transmission owner has a line $l\in\mathcal{L}$ defined by its sending
node $\mathrm{snd}(l)\in\mathcal{N}$ and receiving node
$\mathrm{rec}(l)\in\mathcal{N}$. The definitions of $\mathrm{snd}(l)$ and
$\mathrm{rec}(l)$ are interchangeable because power can flow in either
direction. The sending and receiving nodes of a link are also known as its
supporting nodes. For each node $n\in\mathcal{N}$, we define its set of
receiving lines
$\mathcal{L}_{n}^{\textrm{rec}}:=\\{l\in\mathcal{L}\,|\,n=\textrm{rec}(l)\\}\subseteq\mathcal{L}$
and its set of sending lines
$\mathcal{L}_{n}^{\textrm{snd}}:=\\{l\in\mathcal{L}\,|\,n=\textrm{snd}(l)\\}\subseteq\mathcal{L}$.
Each line offers a bid price $\alpha^{f}_{l}\in\mathcal{R}_{+}$ and capacity
$\bar{f}_{l}\in[0,\infty)$. Each cleared flow $f_{l}$ must satisfy the bounds
$f_{l}\in[-\bar{f}_{l},\bar{f}_{l}]$ and the collection $f$ must obey the
direct-current (DC) power flow equations:

$f_{l}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),$ (2.1)

where $B_{l}\in\mathbb{R}_{+}$ is the line susceptance and
$\theta_{n}\in\mathbb{R}$ is the phase angle at node $n\in\mathcal{N}$. The DC
power flow model is a linear model and requires small phase angle differences
across transmission lines
$\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}\in[-\Delta\bar{\theta^{\prime}}_{l},\Delta\bar{\theta^{\prime}}_{l}]$.
The limits on phase angle differences and the capacity constraints for flows
can be captured as:

$-\Delta\bar{\theta}_{l}\leq\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}\leq\Delta\bar{\theta}_{l}$
(2.2)

where
$\Delta\bar{\theta}_{l}:=\min\\{\bar{f}_{l}/B_{l},\Delta\bar{\theta^{\prime}}_{l}\\}$.

We use $\pi_{n}\in\mathbb{R}_{+}$ to represent the cleared price at node
$n\in\mathcal{N}$. The collection of cleared prices is denoted as $\pi$; these
are also known as nodal prices or LMPs and are used to charge/remunerate
market players. We observe that, in a typical market, suppliers and
transmission owners offer a service to the grid, while inflexible consumers
request a service from the grid. This distinction is important because we will
see that flexible consumers (DaCes) act as prosumers that simultaneously
request a service (request load) and offer a service (flexibility for load to
be delivered at different locations); as such, a well-designed market should
properly remunerate the provision of flexibility by DaCes.

###  2.2 Basic Formulation with Inflexible Consumers

We begin our discussion by studying a clearing formulation with inflexible
consumers:

$\displaystyle\underset{d,p,f,\theta}{\text{max}}$
$\displaystyle\sum_{j\in\mathcal{D}}\alpha_{j}^{d}d_{j}-\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}-\sum_{l\in\mathcal{L}}\alpha_{l}^{f}|f_{l}|$
(2.3a) s.t.
$\displaystyle\sum_{l\in\mathcal{L}_{n}^{\textrm{rec}}}f_{l}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{l\in\mathcal{L}_{n}^{\textrm{snd}}}f_{l}+\sum_{j\in\mathcal{D}_{n}}d_{j},\quad(\pi_{n})\quad
n\in\mathcal{N}$ (2.3b) $\displaystyle
f_{l}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.3c) $\displaystyle
d\in\mathcal{C}_{d}\,,\,p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}.$
(2.3d)

Here, we define the feasible capacity sets
$\mathcal{C}_{d}:=\\{d\,|\,d_{j}\in[0,\bar{d}_{j}]\,\,\forall\,\,j\in\mathcal{D}\\}$,
$\mathcal{C}_{p}:=\\{p\,|\,p_{i}\in[0,\bar{p}_{i}]\,\,\forall\,\,i\in\mathcal{S}\\}$
and
$\mathcal{C}_{\theta}:=\\{\theta\,|\,\theta_{\textrm{rec}(l)}-\theta_{\textrm{snd}(l)}\in[-\Delta\bar{\theta}_{l},\Delta\bar{\theta}_{l}]\,\,\forall\,\,l\in\mathcal{L}\\}$.
The objective function (2.3a) is known as the social surplus or total welfare,
which captures the value of demand served (to be maximized) and the cost of
supply and transmission cost services (to be minimized). The transmission cost
is typically not included in the market clearing literature; this cost is
included here to highlight an important analogy between transmission costs and
load-shifting costs for DaCes (to be discussed later). Specifically, we will
see that load-shifting creates an alternative, non-physical infrastructure
network that is analogous to the transmission network. Constraint (2.3b) is
the power balance constraint at each node $n$ (Kirchoff’s current law).

The solution of the market clearing problem gives the primal allocations
$(p,d,f)$ and the dual allocations $\pi$. The dual allocations are the dual
variables associated with the power balance constraints (2.3b). We will see
that these can be used locational marginal prices (LMPs) that clear the
market. We use $(p,d,f,\pi)$ to denote the primal-dual allocation obtained
from the solution of the clearing formulation.

The social surplus (2.3a) is a non-smooth function because of the presence of
absolute value terms. As is standard practice Bertsimas and Tsitsiklis (1997),
this can be reformulated as a standard linear program by decomposing each line
$l$ into directed edges $l^{+}=(\textrm{snd}(l),\textrm{rec}(l))$,
$l^{-}=(\textrm{rec}(l),\textrm{snd}(l))$ and replace the terms in (2.3) as
$f_{l}\leftarrow f_{l^{+}}-f_{l^{-}}$, $|f_{l}|\leftarrow
f_{l^{+}}+f_{l^{-}}$, and $f_{l^{+}}\geq 0,f_{l^{-}}\geq 0$. We use
$\mathcal{K}$ to represent the set of directed edges that results from this
decomposition. Each edge $k\in\mathcal{K}$ resulted from line
$l(k)\in\mathcal{L}$ inherits the susceptance $B_{k}:=B_{l(k)}$, bid price
$\alpha_{k}^{f}:=\alpha_{l(k)}^{f}$, and capacity
$\Delta\bar{\theta}_{k}:=\Delta\bar{\theta}_{l(k)}$. We define the profit term
for each directed edge in a similar way:

$\phi^{f}_{k}(\pi_{\textrm{rec}(k)},\pi_{\textrm{snd}(k)},f_{k}):=(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k}$
(2.4)

Using these definitions, the transmission cost can be expressed as:

$\sum_{l\in\mathcal{L}}\alpha_{l}^{f}|f_{l}|=\sum_{l\in\mathcal{L}}\alpha_{l}^{f}(f_{l^{+}}+f_{l^{-}})=\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k},$
(2.5)

and the net flows entering a node $n$ can be expressed as:

$\begin{split}\sum_{l\in\mathcal{L}^{\textrm{rec}}_{n}}f_{l}-\sum_{l\in\mathcal{L}^{\textrm{snd}}_{n}}f_{l}&=\sum_{l\in\mathcal{L}^{\textrm{rec}}_{n}}(f_{l^{+}}-f_{l^{-}})-\sum_{l\in\mathcal{L}^{\textrm{snd}}_{n}}(f_{l^{+}}-f_{l^{-}})\\\
&=\left(\sum_{l\in\mathcal{L}^{\textrm{rec}}_{n}}f_{l^{+}}+\sum_{l\in\mathcal{L}^{\textrm{snd}}_{n}}f_{l^{-}}\right)-\left(\sum_{l\in\mathcal{L}^{\textrm{rec}}_{n}}f_{l^{-}}+\sum_{l\in\mathcal{L}^{\textrm{snd}}_{n}}f_{l^{+}}\right)\\\
&=\sum_{k\in\mathcal{K}^{\textrm{rec}}_{n}}f_{k}-\sum_{l\in\mathcal{K}^{\textrm{snd}}_{n}}f_{k}.\end{split}$
(2.6)

This leads to the (equivalent) clearing problem:

$\displaystyle\underset{d,p,f,\theta}{\text{min}}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\sum_{j\in\mathcal{D}}\alpha_{j}^{d}d_{j}$
(2.7a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}+\sum_{j\in\mathcal{D}_{n}}d_{j},\quad(\pi_{n})\quad
n\in\mathcal{N}$ (2.7b) $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.7c) $\displaystyle
d\in\mathcal{C}_{d}\,,\,p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}$
(2.7d)

In this formulation, we minimize the negative surplus (as opposed to maximize
the surplus); this equivalent representation will facilitate the analysis.

A well-designed market clearing formulation must satisfy the following
economic properties:

  * •

Competitive Equilibrium: The clearing formulation must deliver allocations and
prices that represent a competitive equilibrium. Specifically, the market must
deliver allocations that balance supply and demand and that maximize the
collective profit for all players. This property also ensures that the ISO
does not interfere with the competitive nature of the market players.

  * •

Revenue Adequacy: The clearing formulation delivers allocations and prices
such that the total amount of money paid by service requesters (consumers)
covers the total amount paid to all service providers (suppliers and
transmission). This also ensures that the ISO does not have financial gain.

  * •

Cost Recovery: The clearing formulation delivers allocations and prices such
that no cleared player incurs a financial loss (it recovers its operating
cost).

Although not necessarily a fundamental property, it is often desired that
prices delivered by the market are consistent with bid prices provided by
market players (e.g., prices are bounded by bid prices provided by players).
We will see that this property is intimately related to cost recovery;
specifically, for a service provider to not incur a financial loss, its
cleared price must be higher than its bid price (its marginal cost); for a
consumer, the cleared price must be lower than its bid price. We thus see that
prices must satisfy some inherent bounding properties in order for cost
recovery to occur.

Figure 2: Standard market clearing mechanism with inflexible loads.

We now show that the market clearing formulation satisfies the stated
properties; our discussion here will be informal and is intended to introduce
the general logic behind the analysis of clearing formulations (we will follow
a similar logic in studying more complex formulations).

We first need to define the mechanism that will be used to charge/remunerate
players and we then need to verify that such mechanism is compatible with the
clearing formulation. We consider that each supplier $i$ is remunerated with
price $\pi_{n(i)}$ for each unit of power cleared (injected) and each consumer
$j$ pays $\pi_{n(j)}$ for each unit of power cleared (withdrawn). Each
transmission provider $l$ is remunerated using the unit price
$|\pi_{\textrm{rec}(l)}-\pi_{\textrm{snd}(l)}|$, which is the price difference
between the supporting nodes. The profit functions for supplier
$i\in\mathcal{S}$, consumer $j\in\mathcal{D}$, and transmission provider
$l\in\mathcal{L}$ are thus:

$\displaystyle\phi^{p}_{i}(\pi_{n(i)},p_{i}):=(\pi_{n(i)}-\alpha^{p}_{i})p_{i}$
(2.8a)
$\displaystyle\phi^{d}_{j}(\pi_{n(j)},d_{j}):=(\alpha^{d}_{j}-\pi_{n(j)})d_{j}$
(2.8b)
$\displaystyle\phi^{f}_{l}(\pi_{\textrm{rec}(l)},\pi_{\textrm{snd}(l)},f_{l}):=(|\pi_{\textrm{rec}(l)}-\pi_{\textrm{snd}(l)}|-\alpha^{f}_{l})|f_{l}|$
(2.8c)

When convenient, we use the short-hand notation $\phi^{p}_{i},\phi^{d}_{j}$,
and $\phi^{f}_{l}$. We proceed by defining the (partial) Lagrange function of
the clearing formulation (2.7):

$\displaystyle L(\pi,d,p,f)$ $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\sum_{j\in\mathcal{D}}\alpha^{d}_{j}d_{j}-\sum_{n\in\mathcal{N}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-\sum_{j\in\mathcal{D}_{n}}d_{j}\right)$
(2.9) $\displaystyle=$
$\displaystyle-\sum_{j\in\mathcal{D}}(\alpha^{d}_{j}-\pi_{n(j)})d_{j}-\sum_{i\in\mathcal{S}}(\pi_{n(i)}-\alpha_{i}^{p})p_{i}-\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k}$
$\displaystyle=$
$\displaystyle-\sum_{j\in\mathcal{D}}\phi^{d}_{j}-\sum_{i\in\mathcal{S}}\phi^{p}_{i}-\sum_{k\in\mathcal{K}}\phi^{f}_{k},$

and the Lagrange dual function:

$\mathcal{D}(\pi):=\min_{d\in\mathcal{C}_{d},p\in\mathcal{C}_{p},f\in\mathcal{F}}L(\pi,d,p,f).$
(2.10)

where
$\mathcal{F}:=\\{f\,|\,\exists\,\theta\in\mathcal{C}_{\theta}\,\text{s.t.}\,f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)})\,\forall\,l\in\mathcal{L}\\}$
denotes the set of flows that satisfies constraints (2.7c). These definitions
allow us to formulate the Lagrangian dual problem:

$\max_{\pi}\,\mathcal{D}(\pi).$ (2.11)

Throughout our study we assume that strong duality holds for all proposed
market clearing formulations. For the setting discussed here, this guarantees
that an optimal solution of the clearing problem (2.7)) can also be found by
solving the corresponding Lagrangian dual problem (2.11).

We now proceed to show that the solution of the clearing formulation
constitutes a competitive equilibrium. By definition, the solution satisfies
the nodal balance constraints (2.7b). Furthermore, given a set of prices
$\pi$, the Lagrange dual function (2.10) can be decomposed into the
independent optimization problems
$\max_{d_{j}\in[0,\bar{d}_{j}]}\,\phi^{d}_{j}$ for each consumer $j$,
$\max_{p_{i}\in[0,\bar{p}_{i}]}\,\phi^{p}_{i}$ for each supplier $i$, and
$\max_{f\in\mathcal{F}}\sum_{k\in\mathcal{K}}\phi^{f}_{k}$ for the
transmission providers. Thus, the clearing formulation finds prices that
maximize the profit function for each player. From strong duality we have that
a solution of the Lagrangian dual problem also solves the clearing problem and
thus satisfies the power balance constraints (supply equals demand at each
node).

To establish revenue adequacy, we need to show that the total revenue
collected from consumers matches the total revenue allocated to service
providers:

$\sum_{j\in\mathcal{D}}\pi_{n}(j)d_{j}=\sum_{i\in\mathcal{S}}\pi_{n(i)}p_{i}+\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)})f_{k}.$
(2.12)

From the power balance constraints (2.7b) we have that:

$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-\sum_{j\in\mathcal{D}_{n}}d_{j}=0.$
(2.13)

This implies that,

$\displaystyle\sum_{n\in\mathcal{N}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-\sum_{j\in\mathcal{D}_{n}}d_{j}\right)=0.$
(2.14)

This expression can be written in the following equivalent form:

$\displaystyle\sum_{j\in\mathcal{D}}\pi_{n(j)}d_{j}$
$\displaystyle=\sum_{i\in\mathcal{S}}\pi_{n(i)}p_{i}+\sum_{n\in\mathcal{N}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}\right)$
$\displaystyle=\sum_{i\in\mathcal{S}}\pi_{n(i)}p_{i}+\sum_{k\in\mathcal{K}}\left(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}\right)f_{k},$
(2.15)

which establishes revenue adequacy.

We now establish cost recovery; in establishing a competitive equilibrium, we
argue that the Lagrangian dual problem (2.10) maximizes the profit function
for each individual player. Furthermore, since $(p,d,f,\theta)=(0,0,0,0)$ is a
feasible (trivial) solution we have that, at the optimal allocation, the
profit function for each player must be non-negative and thus
$\phi^{p}_{i},\phi^{d}_{j},\phi^{f}_{l}\geq 0$.

To see how cost recovery leads to price-boundedness, define the set of cleared
suppliers $\mathcal{S}^{*}:=\\{i\in\mathcal{S}\,|\,p_{i}>0\\}$ and the set of
cleared consumers $\mathcal{D}^{*}:=\\{j\in\mathcal{D}\,|\,d_{j}>0\\}$. From
the argument behind cost recovery we have
$\phi^{p}_{i}(\pi_{n(i)},p_{i})=(\pi_{n(i)}-\alpha^{p}_{i})p_{i}\geq 0$ and
$\phi^{d}_{j}(\pi_{n(j)},d_{j})=(\alpha^{d}_{j}-\pi_{n(j)})d_{j}\geq 0$. For
$i\in\mathcal{S}^{*}$, we have $p_{i}>0$ and thus
$\pi_{n(i)}\geq\alpha^{p}_{i}$. Similarly, for $j\in\mathcal{D}^{*}$, we have
$d_{j}>0$ and thus $\pi_{n(j)}\leq\alpha^{d}_{j}$.

It is often observed that increasing transmission capacity of a line has the
effect of reducing the price difference between the connected nodes; in other
words, transmission capacity reduces the spatial variability of prices. In the
limit when there is enough transmission capacity and the network is well-
connected, power should be allowed to move freely in the network (there is no
market friction) and all nodal prices should collapse to a single value. On
the other hand, when there is not enough transmission capacity and/or the
network is not well-connected, there will be large differences between nodal
prices. Understanding the effect of transmission capacity on prices will
become relevant for the formulations studied in this paper; specifically, we
will see that virtual links form an alternative infrastructure network that
can help overcome limitations of the transmission network.

To gain some intuition into how transmission capacity reduces spatial
volatility, here we present a simple analysis in the absence of DC constraints
(2.7c); in such a case, the clearing formulation reduces to:

$\displaystyle\underset{d,p,f}{\text{min}}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\sum_{j\in\mathcal{D}}\alpha_{j}^{d}d_{j}$
(2.16a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}+\sum_{j\in\mathcal{D}_{n}}d_{j},\quad(\pi_{n})\quad
n\in\mathcal{N}$ (2.16b) $\displaystyle
d\in\mathcal{C}_{d}\,,\,p\in\mathcal{C}_{p}\,,\,f\in\mathcal{C}_{f}$ (2.16c)

where $\mathcal{C}_{f}=\\{f|f_{k}\in[0,\bar{f}_{k}]\\}$ and
$\bar{f}_{k}=B_{k}\bar{\theta}_{k}$. Consider now a couple of instances for
the clearing formulation (2.16) with line capacities $\bar{f}_{k}$ and
$\bar{f}^{\prime}_{k}$ satisfying $\bar{f}_{k}<\bar{f}^{\prime}_{k}$ for some
$k\in\mathcal{K}$. Let $\pi^{*},\pi^{\prime*}$ be the optimal prices for the
corresponding instances; we would like to show that the prices satisfy:

$\pi^{\prime*}_{\textrm{rec}(k)}-\pi^{\prime*}_{\textrm{snd}(k)}\leq\pi^{*}_{\textrm{rec}(k)}-\pi^{*}_{\textrm{snd}(k)}.$
(2.17)

The Lagrange function of (2.16) has the same form as that of (2.9). The
Lagrange dual function is:

$\mathcal{D}(\pi)=\min_{d\in\mathcal{C}_{d},p\in\mathcal{C}_{p},f\in\mathcal{C}_{f}}L(\pi,d,p,f).$
(2.18)

For fixed prices $\pi$, the Lagrange function is separable and be decomposed
into the individual profit-maximization subproblems:

$\displaystyle\max_{d}\quad$ $\displaystyle(\alpha^{d}_{j}-\pi_{n(j)})d_{j}$
(2.19a) s.t. $\displaystyle 0\leq d_{n}\leq\bar{d}_{j}$ (2.19b)
$\displaystyle\max_{p_{i}}\quad$
$\displaystyle(\pi_{n(j)}-\alpha^{p}_{i})p_{i}$ (2.20a) s.t. $\displaystyle
0\leq p_{i}\leq\bar{p}_{i}$ (2.20b) $\displaystyle\max_{f}\quad$
$\displaystyle\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k}.$
(2.21)

These subproblems have explicit solutions and this allows us to write the
Lagrangian dual function as:

$\mathcal{D}(\pi)=-\sum_{j\in\mathcal{D}}|\alpha^{d}_{j}-\pi_{n(j)}|_{+}\bar{d}_{j}-\sum_{i\in\mathcal{S}}|\pi_{n(i)}-\alpha_{i}^{p}|_{+}\bar{p}_{i}-\sum_{k\in\mathcal{K}}|\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k}|_{+}\bar{f}_{k}$
(2.22)

where $|\cdot|_{+}=\max\\{\cdot,0\\}$. The Lagrangian dual problem is:

$\max_{\pi}\,\mathcal{D}(\pi).$ (2.23)

Defining $\mathcal{D}^{\prime}(\pi)$ as the Lagrangian dual function for the
problem with expanded capacity $\bar{f}^{\prime}_{k}$; we have that
$h^{\prime}(\pi)\leq\mathcal{D}(\pi)$ for any $\pi$ due to the larger feasible
region of the inner problem. Now let $(d^{*},p^{*},f^{*},\pi^{*})$ be an
optimal solution for $\max_{\pi}\mathcal{D}(\pi)$, and define
$\Delta_{k}(\pi):=\pi_{\textrm{rec}(v)}-\pi_{\textrm{snd}(v)}-\alpha^{f}_{k}$.
We consider a couple of cases; for the first case, assume
$\Delta_{k}(\pi^{*})\leq 0$, we thus have
$\mathcal{D}^{\prime}(\pi^{*})=\mathcal{D}(\pi^{*})$ and thus the optimal
prices remain the same; for the second case, assume $\Delta_{k}(\pi^{*})>0$
and let $\pi$ be arbitrary prices such that
$\Delta_{k}(\pi)>\Delta_{k}(\pi^{*})>0$. We now observe that $\pi$ cannot be
optimal; from the setup above we have that:

$\displaystyle\mathcal{D}(\pi)-\mathcal{D}^{\prime}(\pi)=\Delta_{k}(\pi)(\bar{f}^{\prime}_{k}-\bar{f}_{k})$
(2.24a)
$\displaystyle\mathcal{D}(\pi^{*})-\mathcal{D}^{\prime}(\pi^{*})=\Delta_{k}(\pi^{*})(\bar{f}^{\prime}_{k}-\bar{f}_{k}),$
(2.24b)

this implies that:

$\displaystyle\mathcal{D}^{\prime}(\pi)-\mathcal{D}^{\prime}(\pi^{*})=\mathcal{D}(\pi)-\mathcal{D}(\pi^{*})+(\bar{f}^{\prime}_{k}-\bar{f}_{k})(\Delta_{k}(\pi^{*})-\Delta_{k}(\pi))<0,$
(2.25)

which holds because $\Delta_{k}(\pi^{*})-\Delta_{k}(\pi)<0$ and
$\mathcal{D}(\pi)\leq\mathcal{D}(\pi^{*})$ (by optimality of $\pi^{*}$).

This simple analysis provides some intuition into how the addition of
transmission flexibility can help mitigate nodal price differences. We will
see later that a similar behavior can be obtained by incorporating spatial
load-shifting flexibility provided by DaCes. Moreover, we will see that
temporal load-shifting flexibility can be used to mitigate temporal price
differences.

###  2.3 Basic Formulation with Flexible Consumers

We now expand the previous clearing formulation by incorporating flexible
consumers; specifically, we consider flexible consumers that offer load-
shifting flexibility by exploiting the availability of multiple DaCes placed
at different nodes. For simplicity in the presentation, here we consider a
single flexible consumer. Suppose that this consumer submits a bid for
requested load $\bar{d}$ with bid price $\alpha^{d}$; the requested load can
be served/delivered at a set of nodes $\mathcal{N}_{d}\subseteq\mathcal{N}$.
Each node $n\in\mathcal{N}_{d}$ receives a partial load $d_{n}\geq 0$; the
total load served to the consumer is $\sum_{n\in\mathcal{N}_{d}}d_{n}$ and
satisfies $\sum_{n\in\mathcal{N}_{d}}d_{n}\leq\bar{d}$ (total load served
cannot exceed the requested load). The clearing problem is:

$\displaystyle\underset{d,p,f,\theta}{\text{min}}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\alpha^{d}\sum_{n\in\mathcal{N}_{d}}d_{n}$
(2.26a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}+d_{n}\quad(\pi_{n}),\quad
n\in\mathcal{N}_{d}$ (2.26b)
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}\quad(\pi_{n}),\quad
n\in\mathcal{N}\backslash\mathcal{N}_{d}$ (2.26c) $\displaystyle
0\leq\sum_{n\in\mathcal{N}_{d}}d_{n}\leq\bar{d}$ (2.26d) $\displaystyle
d_{n}\geq 0,\quad n\in\mathcal{N}_{d}$ (2.26e) $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.26f) $\displaystyle
p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}$ (2.26g)

From the structure of the surplus function we see that the formulation aims to
maximize the total load delivered to the flexible consumer. From the power
balances, we see that nodes offered by the flexible consumer
($\mathcal{N}_{d}$) can receive load, while those not offered
($\mathcal{N}\setminus\mathcal{N}_{d}$) cannot. The profit function for the
flexible consumer is defined as
$\phi^{d}(\pi,d):=\sum_{n\in\mathcal{N}_{d}}(\alpha^{d}-\pi_{n})d_{n}$. This
indicates that the consumer is charged for power based on the prices of all
the nodes offered. This remuneration mechanism is fundamentally different from
that of an inflexible consumer (which is charged based on the price at a
single node). As such, when a consumer offers load to be delivered at multiple
nodes, it is expected that the ISO can exploit this flexibility to maximize
the consumer profit (if this is not the case, there is no incentive for the
consumer to offer flexibility).

We now establish the fundamental market properties for (2.26) to highlight
differences with the previous market setting. The partial Lagrange function
is:

$\displaystyle L(\pi,d,p,f)$ $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\alpha^{d}\sum_{n\in\mathcal{N}_{d}}d_{n}-\sum_{n\in\mathcal{N}\backslash\mathcal{N}_{d}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}-\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}\right)$
(2.27)
$\displaystyle\qquad-\sum_{n\in\mathcal{N}_{d}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}-\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-d_{n}\right)$
$\displaystyle=$
$\displaystyle-\sum_{j\in\mathcal{N}_{d}}(\alpha^{d}-\pi_{n(j)})d_{j}-\sum_{i\in\mathcal{S}}(\pi_{n(i)}-\alpha_{i}^{p})p_{i}-\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k},$

and the Lagrangian dual problem is:

$\displaystyle\max_{\pi}\,\mathcal{D}(\pi):=\quad$
$\displaystyle\min_{d,p,f,\theta}\quad$ $\displaystyle L(\pi,d,p,f)$ (2.28a)
s.t. $\displaystyle 0\leq\sum_{j\in\mathcal{N}_{d}}d_{j}\leq\bar{d}$ (2.28b)
$\displaystyle d_{n}\geq 0,\quad n\in\mathcal{N}_{d}$ (2.28c) $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.28d) $\displaystyle
p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}$ (2.28e)

The Lagrange dual function $\mathcal{D}(\pi)$ can be decomposed to individual
profit maximization problems:

$\displaystyle\max_{d}\quad$
$\displaystyle\sum_{j\in\mathcal{N}_{d}}(\alpha^{d}-\pi_{n(j)})d_{j}$ (2.29a)
s.t. $\displaystyle 0\leq\sum_{j\in\mathcal{N}_{d}}d_{j}\leq\bar{d}$ (2.29b)
$\displaystyle d_{n}\geq 0,\quad n\in\mathcal{N}_{d}$ (2.29c)
$\displaystyle\max_{p_{i}}\quad$
$\displaystyle(\pi_{n(j)}-\alpha^{p}_{i})p_{i}$ (2.30a) s.t. $\displaystyle
0\leq p_{i}\leq\bar{p}$ (2.30b)
$\displaystyle\max_{f,\theta\in\mathcal{C}_{\theta}}\quad$
$\displaystyle\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k}$
(2.31a) s.t. $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.31b)

It is straightforward to show that the profit maximization problems for
suppliers (2.30) and transmission providers (2.31) are the same as those of
the base formulation with inflexible consumers (under DC constraints). The
main difference that arises here lies in the profit maximization problem for
the consumer (2.29); the structure of this problem confirms that the flexible
consumer should be charged based on the nodal prices and the corresponding
components of the disaggregated load; moreover, the total load served should
not exceed the requested capacity.

We now establish the properties for the market clearing formulation; the logic
is similar as that followed before but we highlight some basic differences
that arise from the provision of flexibility. Market clearance is guaranteed
by satisfaction of the power balance constraints (2.26b), (2.26c).
Furthermore, (2.29)-(2.31) show that the formulation (2.26) delivers an
optimal price and allocation that maximize profit for the flexible consumer,
each of the suppliers, and the transmission network. From the balance
constraints (2.26b), (2.26c) we have:

$0=\sum_{n\in\mathcal{N}}\pi_{n}\left(\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-\sum_{j\in\mathcal{D}_{n}}d_{j}\right)$
(2.32)

Basic manipulations reveal that this expression implies revenue adequacy.

To establish cost recovery, we note again that $(p,d,f,\theta)=(0,0,0,0)$ is a
feasible solution and thus the profit function of all players is non-negative.
Non-negative profits implies that
$\phi^{p}_{i}(\pi_{n(i)},p_{i})=(\pi_{n(i)}-\alpha^{p}_{i})p_{i}\geq 0$ and
$\phi^{d}(\pi,d)=\sum_{j\in\mathcal{N}_{d}}(\alpha^{d}-\pi_{n(j)})d_{j}\geq
0$. If supplier $i$ satisfies $p_{i}>0$, then $\pi_{n(i)}\geq\alpha^{p}_{i}$.
To establish upper bounds, suppose by contradiction that there exists
$n\in\mathcal{N}_{d}$ such that $\alpha^{d}-\pi_{n}<0$ and $d_{n}>0$; then,
$d$ is not optimal ($d$ does not attain the maximum profit for the flexible
consumer); we can construct $d^{\prime}$ by letting
$d^{\prime}_{n^{\prime}}=d_{n^{\prime}}$ for
$n^{\prime}\in\mathcal{D}\backslash\\{j\\}$ and $d^{\prime}_{n}=0$. We thus
have that $d^{\prime}$ satisfies all constraints and gives a higher profit; as
such, $d_{n}>0$ implies $\pi_{n}\leq\alpha^{d}$. We thus see that the
introduction of flexibility affects price boundedness; specifically, for
markets with inflexible loads, a nodal price can only be upper bounded by the
bid price of the load connected to it. This is not the case for markets with
flexible loads; specifically, the price for any node in $\mathcal{N}_{d}$ can
be bounded by the load bid price $\alpha^{d}$. Therefore, the key insight here
is that load-shifting flexibility provides a new mechanism for the ISO to
control price behavior.

Figure 3: Disaggregation model (left) and equivalent representation using
virtual links (right).

###  2.4 Basic Formulation with Virtual Links

We have seen that there natural incentive for flexible consumers to offer
alternative nodes to the ISO in order to access alternative nodal prices.
However, the market clearing formulation previously explored does not provide
intuition on how DaCe flexibility is remunerated. To address this issue, we
propose a mathematically-equivalent formulation that treats DaCes as prosumers
that simultaneously request power and offer load-shifting flexibility. To do
this, we introduce the notion of virtual links; specifically, as shown in
Figure 3, load disaggregation can be seen as a non-physical transport (shift)
of load from a reference node to a set of alternate nodes.

Suppose the flexible consumer submits a bid for requested load $\bar{d}$ at a
hub (reference) node $n_{h}\in\mathcal{N}$ with bid price $\alpha^{d}$ and
offers at set of alternate nodes $\mathcal{N}_{d}\subseteq\mathcal{N}$ such
that $n_{h}\in\mathcal{N}_{d}$. We use $\delta_{n_{h},n}\in\mathbb{R}_{+}$ to
denote the amount of load that is shifted from the hub node $n_{h}$ to the
alternate node $n\in\mathcal{N}_{d}$; we refer to the load-shifting pathway as
a virtual link. This leads to the following clearing formulation:

$\displaystyle\underset{d,p,f,\theta,\delta}{\text{min}}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\alpha^{d}d$
(2.33a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}+\begin{cases}d-\sum_{j\in\mathcal{N}_{d}}\delta_{n_{h},j},\quad
n=n_{h}\\\ \delta_{n_{h},n},\quad n\in\mathcal{N}_{d}\backslash\\{n_{h}\\}\\\
0,\quad n\in\mathcal{N}\backslash\mathcal{N}_{d}\end{cases}\quad(\pi_{n})$
(2.33b) $\displaystyle 0\leq d\leq\bar{d}$ (2.33c)
$\displaystyle\delta_{n}\geq 0,\quad n\in\mathcal{N}_{d}$ (2.33d)
$\displaystyle d-\sum_{n\in\mathcal{N}_{d}}\delta_{n_{h},n}\geq 0$ (2.33e)
$\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.33f) $\displaystyle
p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}$ (2.33g)

It is not difficult to observe that formulations (2.26) and (2.33) are
equivalent. Specifically, there exists a bijection between $d_{n}$ in (2.26)
and $(d,\delta_{n_{h},n})$ in (2.33) such that each pair satisfies:

$\displaystyle d_{n_{h}}=d-\sum_{n\in\mathcal{N}_{d}}\delta_{n_{h},n}$
$\displaystyle d_{n}=\delta_{n_{h},n},\quad
n\in\mathcal{N}_{d}\backslash\\{n_{h}\\}.$

A feasible solution $(d,p,f,\theta,\delta)$ of (2.33) implies existence of a
feasible solution $(d,p,f,\theta)$ for (2.26) with the same value of
$(f,\theta,p)$ (and viceversa). In addition, both solutions attain the same
optimal objective value. The partial Lagrange function for (2.33) is:

$\displaystyle L(d,p,\theta,\delta)$ $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}-\alpha^{d}d-\pi_{n_{h}}\Big{(}\sum_{k\in\mathcal{K}_{n_{h}}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n_{h}}}p_{i}-\sum_{k\in\mathcal{K}_{n_{h}}^{\textrm{snd}}}f_{k}-d+\sum_{n\in\mathcal{N}_{d}}\delta_{n_{h},n}\Big{)}$
(2.34)
$\displaystyle\quad-\sum_{n\in\mathcal{N}_{d}\setminus\\{n_{d}\\}}\pi_{n}\Big{(}\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}-\delta_{n_{h},n}\Big{)}$
$\displaystyle\quad-\sum_{n\in\mathcal{N}\setminus\mathcal{N}_{d}\setminus\\{n_{d}\\}}\pi_{n}\Big{(}\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}\Big{)}$
$\displaystyle=$
$\displaystyle(\pi_{n_{h}}-\alpha^{d})d-\sum_{n\in\mathcal{N}_{d}}(\pi_{n_{h}}-\pi_{n})\delta_{n_{h},n}-\sum_{i\in\mathcal{S}}(\pi_{i}-\alpha_{i}^{p})p_{i}-\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k)}-\pi_{\textrm{snd}(k)}-\alpha^{f}_{k})f_{k},$

and the Lagrangian dual problem is:

$\displaystyle\max_{\pi}\quad$ $\displaystyle\min_{d,p,f,\theta}\quad$
$\displaystyle L(\pi,d,p,\theta)$ (2.35a) s.t. $\displaystyle 0\leq
d\leq\bar{d}$ (2.35b) $\displaystyle\delta_{n_{h},n}\geq 0,\quad
n\in\mathcal{N}_{d}$ (2.35c) $\displaystyle
d-\sum_{n\in\mathcal{N}_{d}}\delta_{n_{h},n}\geq 0$ (2.35d) $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.35e) $\displaystyle
p\in\mathcal{C}_{p}\,,\,\theta\in\mathcal{C}_{\theta}$ (2.35f)

The Lagrange function (2.34) reveals that virtual links are a service offered
by the consumer. The market remunerates the consumer for the provision of this
service via the profit
$\sum_{n\in\mathcal{N}_{d}}(\pi_{n_{h}}-\pi_{n})\delta_{n_{h},n}$. This
highlights that load-shifting is incentivized whenever there is a nodal price
$\pi_{n}$ that is lower than the price at the hub node $\pi_{n_{h}}$. This is
analogous to how transmission is remunerated (based on nodal price
differences). The market also charges the consumer via the the profit
$(\alpha^{d}-\pi_{n_{h}})d$; consequently, the flexible consumer acts as a
prosumer and has total profit:

$(\alpha^{d}-\pi_{n_{h}})d+\sum_{n\in\mathcal{N}_{d}}(\pi_{n_{h}}-\pi_{n})\delta_{n_{h},n}=(\alpha^{d}-\pi_{n_{h}})(d-\sum_{n\in\mathcal{N}_{d}}\delta_{n_{h},n})+\sum_{n\in\mathcal{N}_{d}}(\alpha^{d}-\pi_{n})\delta_{n_{h},n}$
(2.36)

This is the same profit function shown in (2.27), where the profit is
determined by the difference between the bid price and the price at the nodes
where the loads are shifted to (this further reinforces the equivalence
between the load disaggregation formulation and the formulation with virtual
links). The load disaggregation formulation shows the total remuneration for
DaCes, while the formulation with virtual links reveals how the market
remunerates the provision of load-shifting services. We observe that all
market and price properties established for the load disaggregation model hold
for the virtual link model (since the models are equivalent); as such, these
are not established again.

###  2.5 Basic Formulation with General Virtual Links (Spatial)

We now generalize the concept of virtual links as a means to offer spatial
load-shifting flexibility services; this will reveal strong connections
between the non-physical network formed by virtual links and the physical
transmission network. Specifically, we will see that virtual links form an
additional infrastructure layer that is not restricted by DC power flow laws.

We let $\mathcal{V}$ be the set of all virtual links; each virtual link
$v\in\mathcal{V}$ has an associated bid price
$\alpha^{\delta}_{v}\in\mathbb{R}_{+}$ and capacity
$\bar{\delta}_{v}\in[0,\infty)$. The cleared load shifts (virtual flows) are
defined as $\delta_{v}\in\mathbb{R}_{+}$ and are subject to capacity
constraints $\delta_{v}\in[0,\bar{\delta}_{v}]$. We define
$\mathcal{V}_{n}^{\textrm{snd}}:=\\{v\in\mathcal{V}\,|\,\textrm{snd}(v)=n\\}\subseteq\mathcal{V}$,
$\mathcal{V}_{n}^{\textrm{rec}}:=\\{v\in\mathcal{V}\,|\,\textrm{rec}(v)=n\\}\subseteq\mathcal{V}$
to be the set of sending and receiving virtual links at node $n$. Each
flexible consumer $j\in\mathcal{D}$ is associated with a set of virtual links
$\mathcal{V}_{j}\subseteq\mathcal{V}$. For each $v\in\mathcal{V}_{j}$,
$\textrm{snd}(v)=n_{h}(j)$ since each consumer can only bid flexibility going
from its hub node to other alternative nodes. We note that the bid price of
the virtual link can represent cost of shifting load (e.g., opportunity cost
of migrating a computing load). This can also help capture the fact that
shifts to certain nodes can be more expensive (e.g., due to distance or to
capture preferred locations by the market players). The shift cost is
analogous to the service cost of power transmission.

In a base setting with inflexible consumers, the load cleared (withdrawn) at a
node $n$ is $\hat{d}_{n}=\sum_{j\in\mathcal{D}_{n}}d_{j}$. This does not hold
if we consider flexible consumers, as a requested load at a given node might
be withdrawn at another node. We thus have that the load withdrawn at node $n$
is:

$\displaystyle\hat{d}_{n}=\sum_{j\in\mathcal{D}_{n}}d_{j}+\sum_{v\in\mathcal{V}^{in}_{n}}\delta_{v}-\sum_{v\in\mathcal{V}^{out}_{n}}\delta_{v}.$
(2.37)

As load shifting is introduced to the market clearing, the clearing process
needs to ensure that a certain DaCe does not absorb a load that exceeds its
available computing capacity. Moreover, the clearing process needs to ensure
that a certain DaCe does not shift load that exceeds how much it actually
possesses. This logic can be captured using the computing capacity
constraints:

$0\leq\sum_{j\in\mathcal{D}_{n}}d_{j}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n}}\delta_{v}\leq\bar{d}^{\max}_{n},\quad
n\in\mathcal{N}$ (2.38)

where $\bar{d}_{n}^{\textrm{max}}$ denotes the capacity of the DaCe located at
$n$.

The market clearing problem with spatial virtual links is:

$\displaystyle\underset{d,p,f,\theta,\delta}{\text{min}}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{i}^{p}p_{i}+\sum_{k\in\mathcal{K}}\alpha_{k}^{f}f_{k}+\sum_{v\in\mathcal{V}}\alpha^{\delta}_{v}\delta_{v}-\sum_{j\in\mathcal{D}}\alpha_{j}^{d}d_{j}$
(2.39a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k}+\sum_{i\in\mathcal{S}_{n}}p_{i}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n}}\delta_{v}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k}+\sum_{j\in\mathcal{D}_{n}}d_{j}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n}}\delta_{v},\,(\pi_{n})\,n\in\mathcal{N}$
(2.39b) $\displaystyle
f_{l^{+}}-f_{l^{-}}=B_{l}(\theta_{\textrm{snd}(l)}-\theta_{\textrm{rec}(l)}),\quad
l\in\mathcal{L}$ (2.39c) $\displaystyle
0\leq\sum_{j\in\mathcal{D}_{n}}d_{j}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n}}\delta_{v}\leq\bar{d}^{\max}_{n},\,(\omega^{l}_{n},\omega^{u}_{n})\quad
n\in\mathcal{N}$ (2.39d) $\displaystyle
d\in\mathcal{C}_{d},\,p\in\mathcal{C}_{p},\,\theta\in\mathcal{C}_{\theta},\,\delta\in\mathcal{C}_{\delta}$
(2.39e)

where the set
$\mathcal{C}_{\delta}:=\\{\delta\,|\,\delta_{v}\in[0,\bar{\delta}_{v}]\,\,\forall\,\,v\in\mathcal{V}\\}$
captures the capacity constraints for virtual links. Comparing this
formulation with the previous formulation (2.33), we observe that the social
surplus (2.39a) now captures the operational cost of virtual links; moreover,
the balance constraints (2.39b) now include spatial virtual shifts. The dual
variables associated with the computing capacity constraints (2.39d) are
denoted $\omega^{l}_{n}$ and $\omega^{u}_{n}$, respectively. Note that the
operational cost of virtual links resembles that of operational costs of
physical transmission and, as the name suggest, these capture costs associated
with load shifting (e.g., data transfer costs). In this market, each consumer
$j\in\mathcal{D}$ is charged with the electricity price at the hub node and
also remunerated by the shifting service provided through virtual links. As
shown in Section 2.4, the market pays off virtual links by the price
difference between the sending and receiving nodes.

###  2.6 Basic Formulation with General Virtual Links (Temporal)

The concept of virtual links naturally arises from the ability of DaCes to
offer geographical load-shifting flexibility; however, this concept can also
be used to capture temporal flexibility. This is key because DaCes are also
able to schedule tasks over time in a way that they find most
efficient/profitable. The key is to capture temporal shifting flexibility by
using virtual links considering a time horizon as a linear network (with nodes
defining time locations). We thus have that virtual links transport load from
a given time location to another time location in the future.

To see how to incorporate temporal virtual links in the clearing model, we
consider a time horizon given by the time nodes
$\mathcal{T}=\\{t_{1},t_{2},...,t_{T}\\}$. For simplicity, we consider a
network with a single spatial node (no transmission network is present in this
setting). For each time node $t\in\mathcal{T}$, the DaCe bids a price
$\alpha^{d}_{t}$ and a capacity $\bar{d}_{t}$ that represents the amount of
load requested. Similarly, we consider a supplier that bids a price
$\alpha^{p}_{t}$ and a capacity $\bar{p}_{t}$ at time $t\in\mathcal{T}$. The
clearing formulation will find optimal levels for load satisfaction $d_{t}$
and generation $p_{t}$ for each time $t\in\mathcal{T}$.

Each virtual link $v\in\mathcal{V}$ branches from a time node $t$ to a later
time node $t^{\prime}$. The virtual link bids into the market at a price
$\alpha^{\delta}_{v}$ and capacity $\mathcal{\delta}_{t}$. The load at each
time $t\in\mathcal{T}$ is associated with a set of virtual links
$\mathcal{V}_{t}\subseteq\mathcal{V}$. For each $v\in\mathcal{V}_{t}$, we have
$\textrm{snd}(v)=t$ (since each consumer can only bid flexibility going from
the current time to a later time). The market clearing process will find the
optimal time shift flows $\delta_{v}$ for each $v\in\mathcal{V}$. A
distinguishing feature of temporal virtual links (compared to spatial virtual
links) is that they are naturally unidirectional. The temporal model needs to
establish balance constraints for each time node. The load cleared/withdrawn
at $t$ is:

$\displaystyle\hat{d}_{t}=d_{t}+\sum_{v\in\mathcal{V}^{in}_{t}}\delta_{v}-\sum_{v\in\mathcal{V}^{out}_{t}}\delta_{v}.$
(2.40)

Interestingly, we note that this power balance is similar to that of an energy
storage system. This indicates that storage systems act as
transporters/carriers of load and thus can be remunerated as flexibility
providers. This also highlights that virtual links provide a mechanism to
remunerate technologies that can provide load-shifting flexibility (e.g.,
buildings, manufacturing, batteries).

The clearing formulation for this setting is:

$\displaystyle\underset{d,p,\delta}{\text{min}}$
$\displaystyle\sum_{t\in\mathcal{T}}\alpha_{t}^{p}p_{t}+\sum_{v\in\mathcal{V}}\alpha^{\delta}_{v}\delta_{v}-\sum_{j\in\mathcal{D}}\alpha_{j}^{d}d_{j}$
(2.41a) s.t. $\displaystyle
p_{t}=d_{t}+\sum_{v\in\mathcal{V}^{in}_{t}}\delta_{v}-\sum_{v\in\mathcal{V}^{out}_{t}}\delta_{v},\quad
t\in\mathcal{T}$ (2.41b) $\displaystyle 0\leq
d_{t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{t}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{t}}\delta_{v}\leq\bar{d}^{\max}_{t},\,(\omega^{l}_{t},\omega^{u}_{t})\quad
t\in\mathcal{T}$ (2.41c) $\displaystyle 0\leq p_{t}\leq\bar{p}_{t},\quad
t\in\mathcal{T}$ (2.41d) $\displaystyle 0\leq d_{t}\leq\bar{d}_{t},\quad
t\in\mathcal{T}$ (2.41e) $\displaystyle
0\leq\delta_{v}\leq\bar{\delta}_{v},\quad v\in\mathcal{V}$ (2.41f)

The load at each time $t$ is charged at the corresponding cleared price and
also remunerated by the shifting service provided through virtual links; the
consumer flexibility is remunerated based on the price difference between the
sending and receiving times. In other words, a load shift will occur provided
there is a price difference. We can see that the temporal formulation is
directly analogous to the spatial formulation; as such, we can use virtual
links to unify space-time shifting.

Figure 4: Illustration of space-time load shifting using virtual links.

##  3 Market Formulation with Space-Time Virtual Links

In this section, we establish properties for a general clearing framework with
space-time virtual links (3.42). This formulation unifies all the formulations
that we have previously discussed. We will show that this clearing formulation
satisfies revenue adequacy, cost recovery, and provides a competitive
equilibrium. Moreover, we explore the effect of consumer flexibility on space-
time price behavior; specifically, we will show that virtual links mitigate
volatility.

Central to our results is the observation that virtual links can be used to
treat space and time load-shifting flexibility in a unified manner, as shown
in Figure 4. In this illustration, the spatial nodes of the network are
extended into a time dimension using a set of time nodes, thus becoming a
space-time network (a graph). Each time slice of the space-time graph
represents the state of the network at the corresponding time. This space-time
network representation is analogous to those used in dynamic network flow
models.

Consider a space-time clearing setting with spatial nodes $\mathcal{N}$ and
temporal nodes $\mathcal{T}$. A node in this space-time graph is defined as
the pair $(n,t)\in\mathcal{N}\times\mathcal{T}$ (we refer to $(n,t)$ as a
space-time node). Participation of suppliers, consumers and transmission
services is extended to include a time dimension. Specifically, participants
bid prices $\alpha^{p}_{i,t}$, $\alpha^{d}_{j,t}$, $\alpha^{f}_{k,t}$ and
capacities $\bar{p}_{i,t}$, $\bar{d}_{j,t}$,$\bar{f}_{k,t}$ at each time
$t\in\mathcal{T}$ (bids are a function of time). The cleared allocations
$d_{j,t}$, $p_{i,t}$, $f_{k,t}$ and $\theta_{k,t}$ are also indexed in time.

Virtual links connect space-time nodes; each $v\in\mathcal{V}$ is associated
with a sending space-time node
$\text{snd}(v)=(n_{\text{snd}(v)},t_{\text{snd}(v)})$ and a receiving space-
time node $\text{rec}(v)=(n_{\text{rec}(v)},t_{\text{rec}(v)})$. We define
$\mathcal{V}_{n,t}^{\textrm{snd}}:=\\{v\in\mathcal{V}\,|\,\textrm{snd}(v)=(n,t)\\}\subseteq\mathcal{V}$,
$\mathcal{V}_{n,t}^{\textrm{rec}}:=\\{v\in\mathcal{V}\,|\,\textrm{rec}(v)=(n,t)\\}\subseteq\mathcal{V}$
to be the set of sending and receiving virtual links at space-time node
$(n,t)$. This setting captures the special case in which $v$ is a spatial
virtual link if it connects nodes at different locations but same time
($n_{\text{snd}(v)}\neq
n_{\text{rec}(v)},t_{\text{snd}(v)}=t_{\text{rec}(v)}$). Similarly, the
setting captures the special case in which $v$ is a temporal virtual link if
it connects nodes at different times but at the same location
($t_{\text{snd}(v)}\neq
t_{\text{rec}(v)},n_{\text{snd}(v)}=n_{\text{rec}(v)}$). The load
$j\in\mathcal{D}$ at each space-time node $(n(j),t(j))$ is associated with a
set of virtual links $\mathcal{V}_{j}$ and we have
$\mathcal{V}=\bigcup_{j\in\mathcal{D}}\mathcal{V}_{j}$.

Figure 5: Market clearing mechanism with flexible loads using space-time
virtual links.

The clearing formulation with space-time virtual links is:

$\displaystyle\underset{d,p,f,\theta,\delta}{\text{min}}$
$\displaystyle\sum_{t\in\mathcal{T}}\Big{(}\sum_{i\in\mathcal{S}}\alpha_{i,t}^{p}p_{i,t}+\sum_{k\in\mathcal{K}}\alpha^{f}_{k,t}f_{k,t}-\sum_{j\in\mathcal{D}}\alpha_{j,t}^{d}d_{j,t}\Big{)}+\sum_{v\in\mathcal{V}}\alpha^{\delta}_{v}\delta_{v}$
(3.42a) s.t.
$\displaystyle\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k,t}+\sum_{i\in\mathcal{S}_{n}}p_{i,t}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}=\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k,t}+\sum_{j\in\mathcal{D}_{n}}d_{j,t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v},\quad(\pi_{n,t})\quad
n\in\mathcal{N},t\in\mathcal{T}$ (3.42b) $\displaystyle
f_{l^{+},t}-f_{l^{-},t}=B_{l}(\theta_{\textrm{snd}(l),t}-\theta_{\textrm{rec}(l),t}),\quad
l\in\mathcal{L},t\in\mathcal{T}$ (3.42c) $\displaystyle
0\leq\sum_{j\in\mathcal{D}_{n}}d_{j,t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}\leq\bar{d}^{\max}_{n,t},\quad(\omega^{l}_{n,t},\omega^{u}_{n,t})\quad
n\in\mathcal{N},t\in\mathcal{T}$ (3.42d)
$\displaystyle(d,p,\theta,\delta)\in\mathcal{C}$ (3.42e)

where
$\mathcal{C}:=\mathcal{C}^{d}\times\mathcal{C}^{p}\times\mathcal{C}^{\theta}\times\mathcal{C}^{\delta}$
captures the capacity constraints for all variables:

$\displaystyle\mathcal{C}_{d}:=\\{d\,|\,d_{j,t}\in[0,\bar{d}_{j,t}]\,\,\forall\,\,j\in\mathcal{D},\,t\in\mathcal{T}\\}$
(3.43a)
$\displaystyle\mathcal{C}_{p}:=\\{p\,|\,p_{i,t}\in[0,\bar{p}_{i,t}]\,\,\forall\,\,i\in\mathcal{S},\,t\in\mathcal{T}\\}$
(3.43b)
$\displaystyle\mathcal{C}_{\theta}:=\\{\theta\,|\,\theta_{\textrm{rec}(k),t}-\theta_{\textrm{snd}(k),t}\in[-\Delta\bar{\theta}_{k,t},\Delta\bar{\theta}_{k,t}]\,\,\forall\,\,k\in\mathcal{K},t\in\mathcal{T}\\}$
(3.43c)
$\displaystyle\mathcal{C}_{\delta}:=\\{\delta\,|\,\delta_{v}\in[0,\bar{\delta}_{v}]\,\,\forall\,\,v\in\mathcal{V}\\}$
(3.43d)

The social surplus (3.42a) captures the entire time horizon. Constraints
(3.42b) are nodal balances for each space-time node (we denote the duals of
these constraints as $\pi_{n,t}$). Constraints (3.42c) are DC power flows for
all times. Constraints (3.42d) are computing capacity constraints for DaCes at
space-time node $(n,t)$. The duals associated with these constraints are
denoted $\omega^{l}_{n,t}\in\mathbb{R}_{+}$ and
$\omega^{u}_{n,t}\in\mathbb{R}_{+}$. The market clearing setting is
illustrated in Figure 5.

###  3.1 Market Properties

To establish market properties for (3.42), we formulate the partial Lagrange
function of (3.42):

$\displaystyle L(d,p,f,\theta,\delta,\pi,\omega)$ $\displaystyle=$
$\displaystyle\sum_{t\in\mathcal{T}}\Big{(}\sum_{i\in\mathcal{S}}\alpha_{i,t}^{p}p_{i,t}+\sum_{k\in\mathcal{K}}\alpha^{f}_{l,t}f_{l,t}-\sum_{j\in\mathcal{D}}\alpha_{j,t}^{d}d_{j,t}\Big{)}+\sum_{v\in\mathcal{V}}\alpha^{\delta}_{v}\delta_{v}$
(3.44)
$\displaystyle-\sum_{t\in\mathcal{T}}\sum_{n\in\mathcal{N}}\pi_{n,t}\Big{(}\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k,t}+\sum_{i\in\mathcal{S}_{n}}p_{i,t}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k,t}-\sum_{j\in\mathcal{D}_{n}}d_{j,t}-\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}\Big{)}$
$\displaystyle+\sum_{n\in\mathcal{N},t\in\mathcal{T}}\omega^{u}_{n,t}\Big{(}\sum_{j\in\mathcal{D}_{n}}d_{j,t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}-\bar{d}^{\max}_{n,t}\Big{)}$
$\displaystyle-\sum_{n\in\mathcal{N},t\in\mathcal{T}}\omega^{l}_{n,t}\Big{(}\sum_{j\in\mathcal{D}_{n}}d_{j,t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}\Big{)}$
$\displaystyle=$
$\displaystyle-\sum_{j\in\mathcal{D},t\in\mathcal{T}}\phi_{j,t}^{d}(\hat{\pi}_{n(j),t},\alpha_{j,t}^{d},d_{j})-\sum_{v\in\mathcal{V}}\phi_{v}^{\delta}(\hat{\pi}_{\textrm{rec}(v)},\hat{\pi}_{\textrm{snd}(v)},\alpha_{v}^{\delta},\delta_{v})$
$\displaystyle-\sum_{k\in\mathcal{K},t\in\mathcal{T}}\phi_{k,t}^{f}(\pi_{\textrm{rec}(k),t},\pi_{\textrm{snd}(k),t},\alpha^{f}_{k,t},f_{k,t})-\sum_{i\in\mathcal{S},t\in\mathcal{T}}\phi_{i,t}^{p}(\pi_{n(i),t},\alpha_{i,t}^{p},p_{i})$

where we define $\omega_{n,t}:=\omega^{u}_{n,t}-\omega^{l}_{n,t}$ and
$\hat{\pi}_{n,t}:=\pi_{n,t}+\omega_{n,t}$. The profits for demands, virtual
links, suppliers, and transmission links are (see Figure 6):

$\displaystyle\phi_{j,t}^{d}(\hat{\pi}_{n(j),t},\alpha_{j,t}^{d},d_{j})$
$\displaystyle:=(\alpha_{j,t}^{d}-\hat{\pi}_{n(j),t})d_{j,t}$ (3.45a)
$\displaystyle\phi_{v}^{\delta}(\hat{\pi}_{\textrm{rec}(v)},\hat{\pi}_{\textrm{snd}(v)},\alpha_{v}^{\delta},\delta_{v})$
$\displaystyle:=(\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha^{\delta}_{v})\delta_{v}$
(3.45b) $\displaystyle\phi_{i,t}^{p}(\pi_{n(i),t},\alpha_{i,t}^{p},p_{i,t})$
$\displaystyle:=(\pi_{n(i),t}-\alpha_{i,t}^{p})p_{i,t}$ (3.45c)
$\displaystyle\phi_{k,t}^{f}(\pi_{\textrm{rec}(k),t},\pi_{\textrm{snd}(k),t},\alpha^{f}_{k,t},f_{k,t})$
$\displaystyle:=(\pi_{\textrm{rec}(k),t}-\pi_{\textrm{snd}(k),t}-\alpha^{f}_{k,t})f_{k,t}$
(3.45d)

We can thus see that the Lagrange function (3.44) is the negative sum of
profit functions for all participants with price adjustment for DaCes due to
the capacity constraints (3.42d). The presence of capacity constraints for
DaCes introduces technical difficulties in the analysis (as they couple
demands and virtual links). To see this, we note that the total profit for the
DaCes is:

$\displaystyle\sum_{t\in\mathcal{T}}\left(\sum_{j\in\mathcal{D}}(\alpha_{j,t}^{d}-\hat{\pi}_{n(j),t})d_{j,t}\right)+\sum_{v\in\mathcal{V}}(\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha^{\delta}_{v})\delta_{v}$
(3.46) $\displaystyle=$
$\displaystyle\sum_{j\in\mathcal{D},t\in\mathcal{T}}\alpha^{d}_{j,t}-\sum_{v\in\mathcal{V}}\alpha^{\delta}_{v}\delta_{v}-\sum_{n\in\mathcal{N},t\in\mathcal{T}}\hat{\pi}_{n,t}\left(\sum_{j\in\mathcal{D}_{n}}d_{j,t}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}-\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}\right).$

The profit functions for the DaCes use $\hat{\pi}=\pi+\omega$ as prices
(instead of the LMPs $\pi$). The dual variable $\omega$ adjusts the incentive
for load-shifting to prevent shifting that exceeds computing capacity bounds
or available loads to shift. Specifically, if $\omega_{\textrm{snd}(v)}>0$,
the upper bound of $\hat{d}_{\textrm{snd}(v)}$ is active (meaning that local
loads are reaching their upper limit at $\textrm{snd}(v)$); thus,
$\omega_{\textrm{snd}(v)}$ provides incentive to shift. If
$\omega_{\textrm{snd}(v)}<0$, the local loads are exactly zero, and
$\omega_{\textrm{snd}(v)}$ eliminates the incentive to shift. Similarly, if
$\omega_{\textrm{rec}(v)}>0$, the upper bound of $\hat{d}_{\textrm{rec}(v)}$
is active, meaning that local loads reach the maximum at the receiving node;
thus, $\omega_{\textrm{snd}(v)}$ eliminates the incentives to shift. If
$\omega_{\textrm{rec}(v)}<0$, the local loads are zero at the receiving node,
and $\omega_{\textrm{rec}(v)}$ provide incentives for shifting. An alternative
way of interpreting $\omega$ is as an internal price factor for DaCes;
specifically, $\omega$ is the demand-supply relationship of loads within the
DaCe network. If loads are not desired at a space-time node, then $\omega>0$
(the load will be pushed away from the node and therefore is not as valuable);
if loads are desired at a space-time node, $\omega<0$ (the load will be
attracted to the node and therefore it is valuable).

Figure 6: Payment, remuneration, and profit of market players.

Since we assume that strong duality holds, an optimal solution of (3.42) can
be obtained by solving the Lagrangian dual problem:

$\underset{\pi,\omega}{\text{max}}\underset{(d,p,\theta,\delta)\in\mathcal{C},f\in\mathcal{F}}{\text{min}}\,L(d,p,f,\theta,\delta,\pi,\omega)$
(3.47)

where $\mathcal{F}$ captures the DC power flow constraints (3.42c). For fixed
duals $\pi,\omega$, the Lagrange function can be decomposed into the
individual profit maximization problems:

$\displaystyle\underset{p_{i,t}\in[0,\bar{p}_{i,t}]}{\text{max}}\phi_{i,t}^{p}(\pi_{n(i),t},\alpha_{i,t}^{p},p_{i,t})$
(3.48a)
$\displaystyle\underset{d_{j,t}\in[0,\bar{d}_{j,t}]}{\text{max}}\phi_{j,t}^{d}(\hat{\pi}_{n(j),t},\alpha_{j,t}^{d},d_{j,t})$
(3.48b)
$\displaystyle\underset{\delta_{v}\in[0,\bar{\delta}_{v}]}{\text{max}}\phi_{v}^{\delta}(\hat{\pi}_{\textrm{rec}(v)},\hat{\pi}_{\textrm{snd}(v)},\alpha_{v}^{\delta},\delta_{v})$
(3.48c)
$\displaystyle\underset{\theta_{t}\in\mathcal{C}_{\theta_{t}},f_{k,t}\in\mathcal{F}_{t}}{\text{max}}\sum_{k\in\mathcal{K}}\phi_{k,t}^{f}(\pi_{\textrm{rec}(k),t},\pi_{\textrm{snd}(k),t},\alpha^{f}_{k,t},f_{k,t})$
(3.48d)

We now proceed to establish fundamental properties for the clearing
formulation.

######  Theorem 3.1.

The clearing formulation (3.42) provides an allocation and prices that
represent a competitive equilibrium.

###### Proof.

The market is cleared by construction, because the balance constraints (3.42b)
are satisfied at any solution. Furthermore, (3.48) shows that the market
clearing formulation (3.42) delivers an optimal price and allocation that
maximize the profit for all players. $\Box$ ∎

######  Theorem 3.2.

The clearing formulation (3.42) delivers an allocation and prices that satisfy
revenue adequacy.

###### Proof.

The following power balance holds at each space-time node:

$\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k,t}+\sum_{i\in\mathcal{S}_{n}}p_{i,t}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k,t}-\sum_{j\in\mathcal{D}_{n}}d_{j,t}-\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}=0$

Multiplying both sides by the corresponding space-time nodal price and summing
over all space-time nodes, we obtain:

$\sum_{n\in\mathcal{N},t\in\mathcal{T}}\pi_{n,t}\Big{(}\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k,t}+\sum_{i\in\mathcal{S}_{n}}p_{i,t}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k,t}-\sum_{j\in\mathcal{D}_{n}}d_{j,t}-\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}\Big{)}=0.$

This can be rewritten as:

$\displaystyle\sum_{j\in\mathcal{D},t\in\mathcal{T}}\pi_{n(j),t}d_{j,t}$
$\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{S},t\in\mathcal{T}}\pi_{n(i),t}p_{i,t}+\sum_{n\in\mathcal{N},t\in\mathcal{T}}\pi_{n,t}\Big{(}\sum_{k\in\mathcal{K}_{n}^{\textrm{rec}}}f_{k,t}+\sum_{v\in\mathcal{V}^{\textrm{snd}}_{n,t}}\delta_{v}-\sum_{k\in\mathcal{K}_{n}^{\textrm{snd}}}f_{k,t}-\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}}\delta_{v}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{S},t\in\mathcal{T}}\pi_{n(i),t}p_{i,t}+\sum_{k\in\mathcal{K},t\in\mathcal{T}}(\pi_{\textrm{rec}(k),t}-\pi_{\textrm{snd}(k),t})f_{k,t}+\sum_{v\in\mathcal{V}}(\pi_{\textrm{snd}(v)}-\pi_{\textrm{rec}(v)})\delta_{v}$

The summation on the left-hand side represents the total payment by all loads,
while the summations on the right-hand side represent the revenue for
suppliers, transmission service provides, and virtual links (service
providers), respectively. This establishes revenue adequacy. $\Box$ ∎

######  Theorem 3.3.

The clearing formulation (3.42) delivers an allocation and prices that
guarantee cost recovery for all players.

###### Proof.

Consider the allocation $(p^{*},d^{*},f^{*},\delta_{v}^{*})$ and duals
$(\pi^{*},\omega^{*})$; we need to show that

$\displaystyle\phi_{i,t}^{p}(\pi^{*}_{n(i),t},\alpha_{i,t}^{p},p^{*}_{i,t})\geq
0$ (3.49a)
$\displaystyle\phi_{j,t}^{d}(\hat{\pi}^{*}_{n(j),t},\alpha_{j,t}^{d},d^{*}_{j})\geq
0$ (3.49b)
$\displaystyle\phi_{v}^{\delta}(\hat{\pi}^{*}_{\textrm{rec}(v)},\hat{\pi}^{*}_{\textrm{snd}(v)},\alpha_{v}^{\delta},\delta^{*}_{v})\geq
0$ (3.49c)
$\displaystyle\sum_{k\in\mathcal{K}}\phi_{k,t}^{f}(\pi^{*}_{\textrm{rec}(k),t},\pi^{*}_{\textrm{snd}(k),t},\alpha^{f}_{k,t},f^{*}_{k,t})\geq
0.$ (3.49d)

For the inner problem of (3.47), $(p,d,f,\theta,\delta)=(0,0,0,0,0)$ is a
feasible point (for any $(\pi,\omega)$). For fixed $(\pi,\omega)$, the inner
problem is equivalent to maximizing individual profit functions in (3.48);
therefore, (3.49) hold. $\Box$ ∎

One can easily show that increasing load-shifting flexibility leads to a
higher total social surplus. The intuition is that, with more flexibility is
offered by DaCes, the ISO has more options to match demand and supplies across
space-time. We use the notation $\mathcal{M}(\mathcal{V},\bar{\delta})$ to
represent the market clearing problem (3.42) in parametric form; the problem
is a function of the set of virtual links $\mathcal{V}$ and virtual link
capacities $\bar{\delta}$. We denote the corresponding optimal social surplus
value as $\phi(\mathcal{V},\bar{\delta})$. The following result formalizes
this observation.

######  Theorem 3.4.

The social surplus satisfies
$\phi(\mathcal{V},\bar{\delta})\geq\phi(\mathcal{V}^{+},\bar{\delta}^{+})$ if
$\mathcal{V}\subseteq\mathcal{V}^{+}$ and
$\bar{\delta}_{v}\leq\bar{\delta}^{+}_{v}$ for all $v\in\mathcal{V}$.

###### Proof.

Let $(d,p,f,\theta,\delta)$ be a feasible solution of
$\mathcal{M}(\mathcal{V},\bar{\delta})$; the nodal balance constraints, and
capacity constraints for $d,p,\theta$ remain unchanged for
$\mathcal{M}(\mathcal{V}^{+},\bar{\delta}^{+})$ and therefore are satisfied by
$(d,p,f,\theta,\delta)$. The solution $\delta_{v}$ satisfies the virtual link
capacity constraints of $\mathcal{M}(\mathcal{V}^{+},\bar{\delta}^{+})$
because $v\in\mathcal{V}\subseteq\mathcal{V}_{+}$, and
$0\leq\delta_{v}\leq\bar{\delta}_{v}\leq\bar{\delta}^{+}_{v}$. Therefore,
$(d,p,f,\theta,\delta)$ is feasible for
$\mathcal{M}(\mathcal{V}^{+},\bar{\delta}^{+})$ and
$\phi(\mathcal{V^{+}},\bar{\delta}^{+})\leq\phi(\mathcal{V},\bar{\delta})$.
$\Box$ ∎

###  3.2 Pricing Properties

We now investigate how virtual links affect price behavior. We begin by
showing that the nodal prices are bounded by the bid prices of cleared
players. We denote $(p^{*},d^{*},f^{*},\theta^{*},\delta^{*})$ and
$(\pi^{*},\omega^{*})$ as the optimal primal-dual allocation. At each space-
time node, we define the set of cleared suppliers
$\mathcal{S}_{n,t}^{*}:=\\{i\in\mathcal{S}_{n}\,|\,p^{*}_{i,t}>0\\}$, and
loads $\mathcal{D}_{n,t}^{*}:=\\{j\in\mathcal{D}_{n}\,|\,d^{*}_{j,t}>0\\}$.

######  Theorem 3.5.

If $\mathcal{S}_{n,t}^{*}$ and $\mathcal{D}_{n,t}^{*}$ are non-empty for
$(n,t)\in\mathcal{N}\times\mathcal{T}$, the optimal prices satisfy:

$\max_{i\in\mathcal{S}_{n,t}^{*}}\alpha_{i,t}^{p}\leq\pi^{*}_{n,t}\leq\min_{j\in\mathcal{D}_{n,t}^{*}}(\alpha_{j,t}^{d}-\omega^{*}_{n(j),t})$
(3.50)

###### Proof.

From Theorem 3.3 we have that:
$\phi_{j,t}^{d}(\pi_{j(n),t}^{*},\alpha_{j,t}^{d},d_{j,t}^{*})\geq
0,\,\phi_{i,t}^{p}(\pi_{i(n),t}^{*},\alpha_{i,t}^{p},p_{i,t}^{*})\geq 0$ holds
for any $j\in\mathcal{D}_{n,t},i\in\mathcal{S}_{n,t}$; consequently,

$\displaystyle(\alpha_{j,t}^{d}-\hat{\pi}^{*}_{n(j),t})d^{*}_{j,t}$
$\displaystyle\geq 0$
$\displaystyle(\pi^{*}_{n(i),t}-\alpha_{i,t}^{p})p^{*}_{i,t}$
$\displaystyle\geq 0.$

For any $j\in\mathcal{D}_{n,t}^{*}$ we have that $d^{*}_{j,t}>0$; we thus have
$\alpha_{j,t}^{d}-\omega^{*}_{n(j),t}\geq\pi^{*}_{n,t}$. Similarly,
$\pi^{*}_{n,t}\geq\alpha_{i,t}^{p}$ for any $i\in\mathcal{S}_{n,t}^{*}$ and
thus:

$\max_{i\in\mathcal{S}_{n}^{*}}\alpha_{i,t}^{p}\leq\pi^{*}_{n,t}\leq\min_{j\in\mathcal{D}_{n}^{*}}(\alpha_{j,t}^{d}-\omega^{*}_{n(j),t})$

∎

This result shows that cleared suppliers and consumers define the bounds for
the LMP values. On the load side, we see that the price bound is on the
adjusted price (effect of the shifting capacity constrains). If
$\omega^{*}_{n(j),t}>0$ we have that the load is not desired at the node and
therefore its value $\alpha_{j,t}^{d}-\omega^{*}_{n(j),t}$ is decreased; if
$\omega^{*}_{n(j),t}<0$ we have that the load is desired at the node and
therefore its value $\alpha_{j,t}^{d}-\omega^{*}_{n(j),t}$ is increased. If
the net dual If the computing capacity constraints are not active, the LMPs
are bounded by the load bid prices.

From cost recovery for virtual links, we have
$(\hat{\pi}_{\textrm{snd}(v)}^{*}-\hat{\pi}_{\textrm{rec}(v)}^{*}-\alpha^{\delta}_{v})\delta_{v}^{*}\geq
0$ and thus:

$\delta_{v}^{*}>0\;\;\Rightarrow\;\;\hat{\pi}_{\textrm{snd}(v)}^{*}-\hat{\pi}_{\textrm{rec}(v)}^{*}\geq\alpha^{\delta}_{v}.$
(3.51)

This indicates that a virtual link is used only if the price difference
between the receiving node and sending node is high enough to overcome its
load-shifting cost (bid price). On the other hand, if the price difference is
lower than the bid price, the virtual link will not be used. In short, the
virtual link bid price (shifting cost) defines the minimum incentive to
activate virtual links.

We have shown that each virtual link $v\in\mathcal{V}$ solves the problem

$\displaystyle\underset{\delta_{v}\in[0,\bar{\delta}_{v}]}{\text{max}}\phi_{v}^{\delta}(\pi_{\textrm{rec}(v)},\pi_{\textrm{snd}(v)},\alpha^{\delta}_{v},\delta_{v}).$
(3.52)

The optimal solution of this problem satisfies:

$\displaystyle\hat{\pi}_{\textrm{snd}(v)}^{*}-\hat{\pi}_{\textrm{rec}(v)}^{*}>\alpha^{\delta}_{v}\quad\Rightarrow\quad\delta_{v}^{*}=\bar{\delta}_{v}$
(3.53a)
$\displaystyle\delta_{v}^{*}\in(0,\bar{\delta}_{v})\quad\Rightarrow\quad\hat{\pi}_{\textrm{snd}(v)}^{*}-\hat{\pi}_{\textrm{rec}(v)}^{*}=\alpha^{\delta}_{v}$
(3.53b)

These results are analogous to congestion (friction) behavior observed in
physical transmission networks. Specifically, the price difference between the
supporting nodes of a virtual link equals the shifting cost when the virtual
flow has not hit is capacity bound; this implies that, when the shift cost is
zero, the prices of the supporting nodes will be the same (this helps
homogenize LMPs). On the other hand, when the virtual flow hits it capacity
limit, the price difference is bounded by the shift cost; since the shift cost
is non-negative, we can see that price at the receiving node will be less than
(or equal) that of the sending node. In other words, the receiving node cannot
be higher (otherwise there is no incentive to shift load).

A key difference between virtual flows and physical flows is that the former
are not subject to any DC network constraints; as such, the only source of
congestion for the virtual links is their capacity constraint. Note also that
virtual flows can travel in space-time; while physical flows can only travel
in space; as such, virtual flows can be used to mitigate space-time price
variability.

We note that DaCes receive the adjusted prices $\pi+\omega$ (due to the
presence of computing capacity constraints); the duals $\omega$ thus play a
key role that we now explain. Because
$\omega_{n,t}^{u}\cdot\omega_{n,t}^{l}=0$ for any space-time node $n,t$ (they
are complementary), we have the following interpretation for possible values
of $\omega$:

  * •

$\omega_{n,t}=0$: $\omega^{u}_{n,t}=0$ and $\omega^{l}_{n,t}=0$. The incentive
for submitting or shifting a load into space-time node $(n,t)$ is dependent on
the LMPs $\pi$ alone.

  * •

$\omega_{n,t}>0$: $\omega^{u}_{n,t}>0$ and $\omega^{l}_{n,t}=0$. The upper
bound is active, which means the computing resource is scarce at $(n,t)$.
Loads submitted at and shifted into $(n,t)$ will compete for this scarce
computing resource. On the other hand, virtual links flowing outward are
incentivized to shift more load.

  * •

$\omega_{n,t}<0$: $\omega^{u}_{n,t}=0$ and $\omega^{l}_{n,t}<0$. The lower
bound is active, which means no loads are physically cleared at $(n,t)$. The
DaCe thus have a higher incentive to submit loads at $(n,t)$, and virtual
links have a higher incentive to shift loads into $(n,t)$. On the other hand,
virtual links shifting out will compete for loads to shift.

We now explore the effect of increasing DaCe flexibility on the clearing
outcomes. For simplicity, we write the Lagrangian dual problem as:

$\underset{\pi,\omega}{\text{max}}\quad\mathcal{D}(\pi,\omega),$ (3.54)

where:

$\mathcal{D}(\pi,\omega):=\underset{(d,p,\theta,\delta)\in\mathcal{C},f\in\mathcal{F}}{\text{min}}\,L(d,p,f,\theta,\delta,\pi,\omega)$
(3.55)

To establish properties that describe the impact of adding virtual link
capacity on the prices, we inspect what happens to the solution of the
clearing problem if we increase the capacity of one virtual link
$v\in\mathcal{V}$ by some amount $\epsilon>0$. The capacity of $v$ is
expressed as $\bar{\delta}_{v}=\bar{\delta}_{v}^{0}+\epsilon$, where
$\bar{\delta}_{v}^{0}$ is the original (base) capacity. We denote the
Lagrangian dual problem with capacity
$\bar{\delta}_{v}=\bar{\delta}_{v}^{0}+\epsilon$ as:

$\max_{\pi,\omega}\mathcal{D}^{\epsilon}(\pi,\omega).$ (3.56)

We refer to this problem as $\mathcal{M}(\epsilon)$ and denote a primal-dual
solution as
$(p^{*\epsilon},d^{*\epsilon},f^{*\epsilon},\theta^{*\epsilon},\delta^{*\epsilon},\pi^{*\epsilon},\omega^{*\epsilon})$.
Note that
$(p^{*0},d^{*0},f^{*0},\theta^{*0},\delta^{*0},\pi^{*0},\omega^{*0})$ is an
optimal solution of the base problem $\mathcal{M}(0)$.

We proceed to analyze the effect of incorporating additional flexibility of
DaCes. We begin with the case of adding capacity to a virtual link that is not
congested. Intuitively, adding capacity to such a link should not benefit the
DaCe. Our analysis shows that the unit profit for the shift (price difference
between its supporting nodes minus its shift cost) does not change. The
following result establishes this property.

######  Theorem 3.6.

If $\delta^{*0}_{v}<\bar{\delta}_{v}^{0}$ then, for any $\epsilon>0$, we have
that:

$\displaystyle\hat{\pi}^{*\epsilon}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}=\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}.$
(3.57)

###### Proof.

Proof: If $\delta^{*0}_{v}<\bar{\delta}^{0}_{v}$, then
$\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)}\leq\alpha^{\delta}_{v}$,
and thus:

$\phi_{v}^{\delta*0}=(\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)}-\alpha^{\delta}_{v})\delta^{*0}_{v}=0.$

This means
$\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})=\mathcal{D}^{0}(\pi^{*0},\omega^{*0})$
since all other profit values remain unchanged, which implies that
$(p^{*0},d^{*0},\delta^{*0},f^{*0},\theta^{*0})$ also solves of
$\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})$. We now look at an arbitrary
$(\pi,\omega)\neq(\pi^{*0},\omega^{*0})$. By optimality of $\mathcal{M}(0)$,
we have that
$\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})=\mathcal{D}^{0}(\pi^{*0},\omega^{*0})\geq\mathcal{D}^{0}(\pi,\omega)$.
For any $(\pi,\omega)$, any feasible point of $\mathcal{D}^{0}(\pi,\omega)$ is
feasible for $\mathcal{D}^{\epsilon}(\pi,\omega)$. This implies
$\mathcal{D}^{\epsilon}(\pi,\omega)\leq\mathcal{D}^{0}(\pi,\omega)\leq\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})$;
thus, $(p^{*0},d^{*0},f^{*0},\theta^{*0},\delta^{*0},\pi^{*0},\omega^{*0})$
solves $\mathcal{M}(\epsilon)$. This implies that (3.57) holds. $\Box$ ∎

We now focus on the more interesting case of adding capacity to a congested
virtual link. Specifically, we show that the unit profit decreases with
capacity.

######  Theorem 3.7.

If $\delta^{*0}_{v}=\bar{\delta}^{0}_{v}$ then, for any $\epsilon>0$, we have
that:

$\hat{\pi}^{*\epsilon}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}\leq\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}.$
(3.58)

Furthermore, for any $\epsilon_{2}>\epsilon_{1}>0$,

$\hat{\pi}^{*\epsilon_{2}}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon_{2}}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}\leq\hat{\pi}^{*\epsilon_{1}}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon_{1}}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}$
(3.59)

###### Proof.

Proof: If (3.58) holds, then (3.59) holds by setting
$\bar{\delta}_{v}=\bar{\delta}^{0}_{v}+\epsilon_{1}$ as the base case, and
setting $\epsilon=\epsilon_{2}-\epsilon_{1}$. We now prove (3.58); let
$\Delta^{*}_{v}:=\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)}-\alpha^{\delta}_{v}>0$
be the unit profit of virtual link $v$ in the base solution. Assume that
$(\pi,\omega)$ satisfies $\Delta_{v}(\hat{\pi})>\Delta^{*}_{v}$, where
$\Delta_{v}(\hat{\pi}):=\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha^{\delta}_{v}$
is the unit profit of $v$ at price $\hat{\pi}$. We show that $(\pi,\omega)$ is
not optimal. By optimality of $\mathcal{M}(0)$,
$\mathcal{D}^{0}(\pi^{*0},\omega^{*0})\geq\mathcal{D}^{0}(\pi,\omega)$ for any
$(\pi,\omega)$. At $(\pi^{*0},\omega^{*0})$,
$\delta_{v}^{*0}=\bar{\delta}_{v}^{0}+\epsilon$ since $\Delta_{v}^{*}>0$, and
the optimal values of all other profit terms remain unchanged. Thus,

$\mathcal{D}^{0}(\pi^{*0},\omega^{*0})-\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})=\Delta_{v}^{*}(\bar{\delta}^{0}_{v}+\epsilon)-\Delta_{v}^{*}\bar{\delta}^{0}_{v}=\Delta_{v}^{*}\epsilon$

The same reasoning holds for $(\pi,\omega)$ that satisfies
$\Delta_{v}(\hat{\pi})>0$; we have:

$\mathcal{D}^{0}(\pi,\omega)-\mathcal{D}^{\epsilon}(\pi,\omega)=\Delta_{v}(\hat{\pi})\epsilon,$

then we have:

$\displaystyle\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0})-\mathcal{D}^{\epsilon}(\pi,\omega)$
$\displaystyle=$
$\displaystyle(\mathcal{D}^{0}(\pi,\omega)-\mathcal{D}^{\epsilon}(\pi,\omega))-(\mathcal{D}^{0}(\pi^{*0},\omega^{*0})-\mathcal{D}^{\epsilon}(\pi^{*0},\omega^{*0}))+(\mathcal{D}^{0}(\pi^{*0},\omega^{*0})-\mathcal{D}^{0}(\pi,\omega))$
$\displaystyle=$
$\displaystyle\Delta_{v}(\hat{\pi})\epsilon-\Delta_{v}^{*}\epsilon+\mathcal{D}^{0}(\pi^{*0},\omega^{*0})-\mathcal{D}^{0}(\pi,\omega)$
$\displaystyle=$
$\displaystyle(\Delta_{v}(\hat{\pi})-\Delta_{v}^{*})\epsilon+\mathcal{D}^{0}(\pi^{*0},\omega^{*0})-\mathcal{D}^{0}(\pi,\omega)$
$\displaystyle>$ $\displaystyle 0$

where the last inequality holds because
$\Delta_{v}(\hat{\pi})>\Delta_{v}^{*}$,
$\mathcal{D}^{0}(\pi^{*0},\omega^{*0})\geq\mathcal{D}^{0}(\pi,\omega)$, and
$(\pi^{*0},\omega^{*0})$ solves $\mathcal{M}(0)$. Since this holds for
arbitrary $(\pi,\omega)$ such that $\Delta_{v}(\hat{\pi})>\Delta_{v}^{*}$, we
conclude that:

$\hat{\pi}^{*\epsilon}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon}_{\textrm{rec}(v)}\leq\hat{\pi}^{*0}_{\textrm{snd}(v)}-\hat{\pi}^{*0}_{\textrm{rec}(v)},$

which implies (3.58). $\Box$

∎

Theorem 3.7 indicates that increasing virtual link capacity has the effect of
reducing the price difference between space-time nodes that support the
virtual links. We note, however, that the ability of virtual links to reduce
price volatility might be affected by computing capacity constraints (as the
duals $\omega$ might distort the prices in a manner that is difficult to
predict). Moreover, we note that Theorem 3.7 does not guarantee convergence of
the price difference to a specific value. To address these issues, we now
proceed to show that, when the capacity of a virtual link is sufficiently
large, the price difference between the supporting nodes is bounded by the
link shift cost. As such, the price difference can be made arbitrarily small
as the shift cost is made arbitrarily small. In order to study this
convergence behavior, we apply subgradient analysis to problem (3.47). A brief
review of subgradient analysis and nonsmooth optimization is provided in the
Appendix A.

We recall that minimizing the Lagrange function with respect to allocation
variables is equivalent to individual profit maximization; we exploit this
property to write out the optimal profit of each player as a function of
$(\pi,\omega)$:

$\displaystyle\phi_{j,t}^{d*}(\hat{\pi}_{n(j),t})$
$\displaystyle=\text{max}\\{(\alpha_{j,t}^{d}-\hat{\pi}_{n(j),t})\bar{d}_{j,t},0\\}=|\alpha_{j,t}^{d}-\hat{\pi}_{n(j),t}|_{+}\bar{d}_{j,t}$
(3.60a) $\displaystyle\phi_{i,t}^{p*}(\pi_{n(i),t})$
$\displaystyle=\text{max}\\{(\pi_{n(i),t}-\alpha_{i,t}^{p})\bar{p}_{i,t},0\\}=|\pi_{n(i),t}-\alpha_{i,t}^{p}|_{+}\bar{p}_{i,t}$
(3.60b)
$\displaystyle\phi_{v}^{\delta*}(\hat{\pi}_{\textrm{snd}(v)},\hat{\pi}_{\textrm{rec}(v)})$
$\displaystyle=\text{max}\\{(\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta})\bar{\delta}_{v},0\\}=|\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}|_{+}\bar{\delta}_{v}$
(3.60c) $\displaystyle\phi_{t}^{f*}(\pi)$
$\displaystyle=\text{max}_{f_{t}\in\mathcal{F}_{t}}\sum_{k\in\mathcal{K}}(\pi_{\textrm{rec}(k),t}-\pi_{\textrm{snd}(k),t}-\alpha^{f}_{k,t})f_{k,t}$
(3.60d)

where $|\cdot|_{+}:=\max\\{\cdot,0\\}$. The Lagrangian dual function is thus:

$\displaystyle\mathcal{D}(\pi,\omega)=-\sum_{t\in\mathcal{T}}\Big{(}\sum_{j\in\mathcal{D}}\phi_{j,t}^{d*}+\sum_{i\in\mathcal{S}}\phi_{i,t}^{p*}+\phi^{f*}_{t}\Big{)}-\sum_{v\in\mathcal{V}}\phi_{v}^{\delta*}.$
(3.61)

Using linearity of subdifferential operator, we calculate the subgradient of
this function with respect to each element of an arbitrary price $\pi$ as
follows:

$\partial_{\pi_{n,t}}\mathcal{D}=-\left(\sum_{j\in\mathcal{D}_{n}}\partial_{\pi_{n,t}}\phi_{j,t}^{d*}+\sum_{i\in\mathcal{S}_{n}}\partial_{\pi_{n,t}}\phi_{i,t}^{p*}+\sum_{v\in\mathcal{V}^{\textrm{rec}}_{n,t}\cup\mathcal{V}^{\textrm{snd}}_{n,t}}\partial_{\pi_{n,t}}\phi_{v}^{\delta*}+\partial_{\pi_{n,t}}\phi_{t}^{f*}\right).$

Here, $+$ denotes the Minkowski sum and the individual subgradient terms are:

$\partial_{\pi_{n(i),t}}\phi_{i,t}^{p*}=\begin{cases}\\{0\\},\hat{\pi}_{n(i)}<\alpha_{i}^{p}\\\
\\{\bar{p}_{i}\\},\hat{\pi}_{n(i)}>\alpha_{i}^{p}\\\
[0,\bar{p}_{i}],\hat{\pi}_{n(i)}=\alpha_{i}^{p}\end{cases}$

$\partial_{\pi_{n(j),t}}\phi_{j,t}^{d*}=\begin{cases}\\{-\bar{d}_{j}\\},\pi_{n(j)}<\alpha_{j}^{d}\\\
\\{0\\},\pi_{n(j)}>\alpha_{j}^{d}\\\
[-\bar{d}_{j},0],\pi_{n(j)}=\alpha_{j}^{d}\end{cases}$

$\partial_{\pi_{\textrm{rec}(v)}}\phi_{v}^{\delta*}=\begin{cases}\\{0\\},\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}<0\\\
\\{-\bar{\delta}_{v}\\},\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}>0\\\
[-\bar{\delta}_{v},0],\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}=0\end{cases}$

$\partial_{\pi_{\textrm{snd}(v)}}\phi_{v}^{\delta*}=\begin{cases}\\{0\\},\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}<0\\\
\\{\bar{\delta}_{v}\\},\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}>0\\\
[0,\bar{\delta}_{v}],\,\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}-\alpha_{v}^{\delta}=0\end{cases}$

It is difficult (if not impossible) to derive an analytic form for
$\partial_{\pi_{n,t}}\phi_{t}^{f*}$ (due to the presence of DC constraints).
For the following analysis, however, we only need to assume that
$\partial_{\pi_{n,t}}\phi_{t}^{f*}$ is bounded. We now show the effect of
increasing virtual shift capacity; in short, the virtual link capacity has a
critical point beyond which the difference of $\pi+\omega$ between the
connected space-time nodes will be bounded by its bid price. Once the virtual
link capacity reaches this critical point, additional capacity will not be
used by the market.

######  Theorem 3.8.

Assume $\partial_{\pi_{n,t}}\phi_{t}^{f*}$ is bounded for any $\pi$; then, for
any $v\in\mathcal{V}$, $\exists\;M_{v}>0$ such that, if $\epsilon>M_{v}$:

$\hat{\pi}^{*\epsilon}_{\textrm{snd}(v)}-\hat{\pi}^{*\epsilon}_{\textrm{rec}(v)}\leq\alpha^{\delta}_{v}$

###### Proof.

Proof: Consider an arbitrary virtual link $v$, the optimality conditions
require that:

$\displaystyle 0$
$\displaystyle\in\partial_{\pi_{\textrm{snd}(v)}}\mathcal{D}^{\epsilon}(\pi^{*\epsilon},\omega^{*\epsilon})$
$\displaystyle 0$
$\displaystyle\in\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon}(\pi^{*\epsilon},\omega^{*\epsilon})$

Each term in the subgradient is an interval of possibly zero length. When the
capacity of $v$ increases, all terms remain constant except for the
subgradient terms $\partial_{\pi_{\textrm{snd}(v)}}\phi_{v}^{\delta*}$ and
$\partial_{\pi_{\textrm{rec}(v)}}\phi_{v}^{\delta*}$. This allows us to write
the sum of all other terms as constant intervals, which we denote
$[a^{-},a^{+}]$ for $\partial_{\pi_{\textrm{snd}(v)}}\mathcal{D}^{\epsilon}$
and $[b^{-},b^{+}]$ for
$\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon}$, respectively. Then
the subgradients can be expressed as

$\partial_{\pi_{\textrm{snd}(v)}}\mathcal{D}^{\epsilon}=-\left([a^{-},a^{+}]+\partial_{\pi_{\textrm{snd}(v)}}\phi_{v}^{\delta*}\right)$
$\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon}=-\left([b^{-},b^{+}]+\partial_{\pi_{\textrm{rec}(v)}}\phi_{v}^{\delta*}\right)$

Let
$M_{v}=\text{max}\\{-a^{-}-\bar{\delta}_{v}^{0},b^{+}-\bar{\delta}_{v}^{0},0\\}$
and suppose $\epsilon>M_{v}$. Given arbitrary duals $(\pi,\omega)$ that
satisfy
$\hat{\pi}_{\textrm{snd}(v)}-\hat{\pi}_{\textrm{rec}(v)}>\alpha_{v}^{\delta}$,
we show that $\pi$ does not satisfy the optimality condition for
$\mathcal{M}(\epsilon)$ if $\epsilon>M_{v}$. If
$\pi_{\textrm{snd}(v)}+\omega_{\textrm{snd}(v)}-\pi_{\textrm{rec}(v)}-\omega_{\textrm{rec}(v)}-\alpha_{v}^{\delta}>0$,
then the subgradients at the supporting nodes become:

$\displaystyle\partial_{\pi_{\textrm{snd}(v)}}\mathcal{D}^{\epsilon}\subseteq[-a^{+}-\bar{\delta}_{v}^{0}-\epsilon,-a^{-}-\bar{\delta}_{v}^{0}-\epsilon]$
$\displaystyle\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon}\subseteq[-b^{+}+\bar{\delta}_{v}^{0}+\epsilon,-b^{-}+\bar{\delta}_{v}^{0}+\epsilon]$

By definition of $M_{v}$, we have:

$\displaystyle-a^{-}-\bar{\delta}_{v}^{0}-\epsilon<-a^{-}-\bar{\delta}_{v}^{0}+a^{-}+\bar{\delta}_{v}^{0}=0$
$\displaystyle-b^{+}+\bar{\delta}_{v}^{0}+\epsilon>-b^{+}+\bar{\delta}_{v}^{0}+b^{+}-\bar{\delta}^{0}_{v}=0$

This means that the lower bound of
$\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon}$ is strictly positive,
and the upper bound of $\partial_{\pi_{\textrm{snd}(v)}}g$ is strictly
negative. Therefore,
$0\notin\partial_{\pi_{\textrm{rec}(v)}}\mathcal{D}^{\epsilon},0\notin\partial_{\pi_{\textrm{snd}(v)}}g$,
which implies $(\pi,\omega)$ is not optimal. $\Box$ ∎

Theorem 3.8 shows that the price difference is eventually bounded by the shift
cost in the limit of high virtual link capacity. This result is key, as it
shows that virtual links can help homogenize prices (by controlling price
differences). It is important to highlight that the price differences
exploited by virtual links traverse space and time and thus spatial and
temporal price variability can be mitigated. The ability to control price
differences across space and time is a key benefit over power transmission
(which only exploits spatial price differences). Moreover, one could argue
that it is easier to expand virtual link capacity (by installing more DaCes)
than it is to install more transmission lines.

A rigorous proof of price convergence is established here for the market
clearing formulation (3.42), which is quite general but also does not account
for other features encountered in practice (e.g., ramping constraints and AC
power flows). A rigorous analysis of more sophisticated formulations is
challenging and is left as a topic of future work. However, we have observed
empirically that similar properties are observed in more complex formulations
(in the next section we illustrate how temporal virtual links mitigate price
volatility introduced by ramping constraints).

##  4 Computational Studies

In this section we present case studies to demonstrate the various benefits of
using the virtual link paradigm for capturing DaCe flexibility. All our models
were implemented in JuMP Dunning et al. (2017) and were solved using Gurobi
Gurobi Optimization (2019). We first analyze a small-scale model to illustrate
the key results and then analyze a large-scale model to show that the results
and insights are scalable. All scripts needed to reproduce the results can be
found in https://github.com/zavalab/JuliaBox/tree/master/VirtualLinks.

Figure 7: Scheme for 7-bus system (small generators co-located with DaCes not
shown).

###  4.1 7-Bus Spatial System

We consider a 7-bus system at a fixed time, sketched in Figure 7. Four DaCes,
owned and operated by a single market player, are distributed at nodes
$\\{2,3,6,7\\}$. Their bid prices and capacities are
$\\{10,10,15,15\\}\,\$/\textrm{MWh}$ and $\\{13,17,17,13\\}\,\textrm{MWh}$,
respectively. Each DaCe has a computing capacity of $20\,\textrm{MWh}$ and is
co-located with a small and expensive generator with bid price
$\alpha^{p}=3\,\$/\textrm{MWh}$ and capacity $5\,\textrm{MWh}$. In addition,
nodes 2 and 4 are connected to a large generator with bid price
$\alpha^{p}=1\,\$/\textrm{MWh}$ and capacity $20\,\textrm{MWh}$. The
transmission network topology is highlighted using solid lines in Figure 7.
Each line has a capacity of $10\,\textrm{MWh}$ and a bid cost
$0.1\,\$/\textrm{MWh}$.

We considered three scenarios with different virtual link capacity levels. The
results are summarized in Table 1. Scenario 1 represents the base case in
which no virtual links are used. Scenario 2 accounts for virtual links $(1,7)$
and $(7,1)$, both with capacity $5\,\textrm{MWh}$ and bid cost
$0.3\,\$/\textrm{MWh}$. Scenario 3 is a replicate of scenario 2, except the
capacity is set as $10\,\textrm{MWh}$. Scenario 4, on top of virtual links in
scenario 2, includes additional virtual links $(1,3)$ and $(3,1)$, both with
capacity $5\,\textrm{MWh}$ and bid cost $0.3\,\$/\textrm{MWh}$. Scenario 5 is
a replicate of scenario 4, except the capacity is set as $10\,\textrm{MWh}$.
Scenario 6 is a replicate of scenario 5, except that the computing capacity
for each DaCe is increased from $20\,\textrm{MWh}$ to $25\,\textrm{MWh}$.
Scenario 7 is a replicate of scenario 6, except that the bid costs of all
virtual links are reduced to 0.

Table 1: Results for 7-bus system. Symbol $\phi$ denotes the social surplus. The surplus and dual variables are in units of USD ($). Scenario | $\phi$ | $[\pi_{1},\pi_{2},\pi_{3}]$ | $\pi_{4}$ | $[\pi_{5},\pi_{6},\pi_{7}]$ | $[\omega_{2},\omega_{3},\omega_{6},\omega_{7}]$ |  $\sum d_{j}$ (MWh)
---|---|---|---|---|---|---
1 | 522 | $[3,1,2]$ | 1 | $[14.9,15,15]$ | $[0,0,0,0]$ | 50
2 | 577.36 | $[5,1,3]$ | 2.9 | $[14.87,15,14.93]$ | $[0,0,0,0]$ | 55
3 | 605.533 | $[10,1,5.5]$ | 1 | $[10.233,10.367,10.3]$ | $[0,0,0,0]$ | 56
4 | 582.467 | $[3,2.4,2.7]$ | 2.6 | $[14.867,15,14.933]$ | $[0,0,0,0]$ | 55
5 | 618.133 | $[10,1,5.5]$ | 5.4 | $[10.233,10.367,10.3]$ | $[0,4.2,0,0]$ | 57.5
6 | 639.133 | $[3.3,2.7,3]$ | 2.9 | $[3.533,3.667,3.6]$ | $[0,0,0,0]$ | 60
7 | 644.533 | $[3,1,3]$ | 1 | $[2.933,3.067,3]$ | $[0,0,0,0]$ | 60
Table 2: DaCe load payments and revenues for different players (in $) Scenario | Total Load Payments | Transmission | Suppliers | Virtual Links | Total Revenue
---|---|---|---|---|---
1 | 373 | 180 | 193 | 0 | 373
2 | 490.13 | 181.8 | 258.67 | 49.67 | 490.13
3 | 493.63 | 273.8 | 216.83 | 3 | 493.63
4 | 459.03 | 133.8 | 264.67 | 60.57 | 459.03
5 | 508.63 | 185.8 | 306.33 | 16.5 | 508.63
6 | 203.03 | 17.8 | 179.83 | 5.4 | 203.03
7 | 181.13 | 80.8 | 100.33 | 0 | 181.13
Table 3: Profit for market players (in $, S# denotes supplier at node #) Scenario | DaCe Load | Virtual Links | Transmission | S2 | S4
---|---|---|---|---|---
1 | 50 | 0 | 175 | 0 | 0
2 | 55 | 48.17 | 176.77 | 0 | 38
3 | 56 | 0 | 268.33 | 0 | 0
4 | 55 | 58.17 | 128.67 | 28 | 32
4 | 57.5 | 0 | 180.33 | 0 | 88
4 | 60 | 0 | 12.33 | 34 | 38
5 | 60 | 0 | 75.33 | 0 | 0

Results for price behavior are summarized in Table 1. Here, $\phi$ represents
the social surplus in units of USD ($). In the base case, the LMPs show
clustered patterns, where nodes in the same cycle share similar prices. We
also observe a large price difference between nodes in the separate cycles. In
scenarios 2 and 3, the virtual link connects across the two cycles (via node 1
and node 7) to exploit the price difference in between. We see that the price
gap between node 1 and node 7 is reduced to $0.3\,\$/\textrm{MWh}$ in scenario
3, exactly the bid price of the virtual link, as predicted by the pricing
properties. We also run scenario 3 with $\bar{\delta}=1000\,\textrm{MWh}$,
which gives back the same primal and dual optimal solutions except for the
price at node 4 due to degeneracy. We note that the LMP at node 3 also
approaches the LMPs of the other cycle even though there is no virtual link
connected at node 3 yet. Similarly, the LMPs of nodes 5 and 6 come down to
around $10\,\$/\textrm{MWh}$ with node 7 without virtual links directed
connected. Because of the DC power flow constraints, the addition of virtual
links alter the LMPs of not just the connected nodes, but also neighboring
nodes in the same cluster. The values of $\omega$ for scenarios 1 and 2 are
zero, meaning that computing capacity constraints are inactive. Scenario 5
shows a case where the addition of a virtual link within cluster $\\{1,2,3\\}$
does not change the prices (compared with scenario 3), even if the price
difference between the connected nodes is much higher than the bid cost. The
reason is that computing capacity constraint is active at the destination node
of the newly added virtual link (node 3) , as shown by the nonzero value of
$\omega_{3}$. However, if the computing capacity constraints are not binding
(as in scenarios 6 and 7), the price difference within the cluster
$\\{1,2,3\\}$ becomes much smaller. In scenario 6, the price gaps across
virtual links ($|\pi_{1}-\pi_{3}|$ and $|\pi_{1}-\pi_{7}|$) are exactly the
bid cost of the virtual links, meaning that the price gaps converge to the
best case. As an extreme case, scenario 7 shows that the prices
$[\pi_{1},\pi_{3},\pi_{7}]$ become homogeneous when the bid costs are zero.
These results are consistent with the pricing properties established and show
how virtual links provide a mechanism to help mitigate spatial variability of
prices.

Table 2 summarizes results for load payments and revenues. These results
verify that revenue adequacy holds for our proposed market clearing
formulation. Table 3 summarizes results for profits for different market
stakeholders. The results verify that the clearing formulation satisfies cost
recovery in all scenarios. Furthermore, we notice that virtual link profits
are strictly positive and comparable to profits of load clearing in scenarios
2 and 4, but zero otherwise. This shows that virtual links provide an extra
revenue stream when price volatility is high (there exist large price
differences to exploit). Another interesting observation from scenarios 2 and
4 is that, when the amount of total cleared load is the same, more flexibility
leads to lower load payments and higher virtual link revenue because the extra
flexibility from a new virtual link provides more ways to clear the DaCe
loads. This is not necessarily true when the total amount of cleared loads is
different, though, because clearing more load might need to use more expensive
power suppliers from the grid. When too much flexibility is provided, however,
DaCes could benefit from a lower price, as shown by scenarios 6 and 7 in Table
2, but will lose the virtual link revenue streams (because of low price
volatility).

Figure 8: Scheme for 4-time system.

###  4.2 1-Bus Temporal System

We now consider a single DaCe co-located with one generator over a time
horizon of 4 points. The setup is a modification of the temporal case shown in
Zhang et al. (2020). The system is sketched in Figure 8. At each time
interval, the DaCe can receive loads shifted from the previous time interval
and delay loads to some later time interval, thus providing temporal
flexibility (similar to that of a storage system). As boundary conditions, the
DaCe does not receive loads at $t=t_{1}$, and does not delay loads at $t=4$.
The load capacity and bid costs of loads and supplies change with time. The
system thus has $T=4$ time nodes and we consider 4 virtual links
$\mathcal{V}:=\\{(1,2),(1,3),(1,4),(3,4)\\}$. The supplier capacities are set
to $\bar{p}=\\{50,50,50,50\\}$, load capacities to
$\bar{d}=\\{70,25,70,40\\}$, supplier bidding costs to
$\alpha^{p}=\\{10,20,10,15\\}$, and load bidding prices to
$\alpha^{d}=\\{30,60,40,50\\}$. We fix the bidding cost for virtual links as
$\alpha^{\delta}=\\{3,3,3,3\\}$. To create extreme temporal prices differences
(often seen in real systems), we also incorporate a set of ramp limit
constraints $|p_{t+1}-p_{t}|\leq 15$.

Table 4: Results for one-bus network with temporal shifting flexibility.  Scenario |  $\bar{\delta}$ (MWh) |  $\phi$ ($) |  $\pi$ ($/MWh) |  $d$ (MWh) |  $p$ (MWh) |  $\delta$ (MWh)
---|---|---|---|---|---|---
1 | [0,0,0,0] | 4400 | [30,-30,40,15] | [40,25,40,40] | [40,25,40,40] | [0,0,0,0]
2 | [8,0,0,0] | 4856 | [30,-30,40,15] | [56,25,48,40] | [48,33,48,40] | [8,0,0,0]
3 | [10,0,0,0] | 4970 | [30,20,40,15] | [60,25,50,40] | [50,35,50,40] | [10,0,0,0]
4 | [21,0,0,0] | 5040 | [23,20,40,15] | [70,25,50,40] | [50,45,50,40] | [20,0,0,0]
5 | [21,20,0,0] | 5040 | [23,20,40,15] | [70,25,50,40] | [50,45,50,40] | [20,0,0,0]
6 | [11,0,11,0] | 5090 | [23,20,40,20] | [70,25,50,40] | [50,35,50,50] | [10,0,10,0]
7 | [11,0,11,10] | 5197 | [30,20,40,27] | [61,25,60,40] | [50,36,50,50] | [11,0,0,10]
8 | [11,0,11,20] | 5197 | [30,20,40,37] | [61,25,60,40] | [50,36,50,50] | [11,0,0,10]
9 | [21,0,11,20] | 5260 | [23,20,40,37] | [70,25,60,40] | [50,45,50,50] | [20,0,0,10]
Table 5: Total payments and revenue for market players (in units of $). Scenario | Load Payments | Suppliers | Virtual Links | Total Revenue
---|---|---|---|---
1 | 2650 | 2650 | 0 | 2650
2 | 3450 | 2970 | 480 | 3450
3 | 4900 | 4800 | 100 | 4900
4 | 4710 | 4650 | 60 | 4710
5 | 4710 | 4650 | 60 | 4710
6 | 4910 | 4850 | 60 | 4910
7 | 5810 | 5570 | 240 | 5810
8 | 6210 | 6070 | 140 | 6210
9 | 5990 | 5900 | 90 | 5990
Table 6: DaCe loads and virtual link and supplier profits (in units of $). Scenario | Loads Profit | Virtual Links Profit | Suppliers Profit
---|---|---|---
1 | 3650 | 0 | 750
2 | 3650 | 456 | 750
3 | 2400 | 70 | 2500
4 | 2890 | 0 | 2150
5 | 2890 | 0 | 2150
6 | 2690 | 0 | 2400
7 | 1920 | 177 | 3100
8 | 1520 | 77 | 3600
9 | 2010 | 0 | 3250

Nine scenarios with different temporal shifting capacities are presented in
Table 4. The results are analogous to those observed in the spatial 7-bus case
and highlights how virtual links facilitate treating space and time dimensions
in a unified manner. Specifically, the social surplus and the total amount of
delivered loads increase with increasing shifting capacity. Price variability
also becomes smaller with increasing shifting capacity. In the limit of high
shifting capacity, prices converge and the differences between time nodes are
bounded by the shifting cost, similar to the results of scenario 3 in the
7-bus system. Note that scenarios 1 and 2 has a negative LMP caused by the
ramping limit, which is relieved by virtual links in other scenarios. Another
interesting observation arises from scenarios 1 to 3, where a virtual link
between $t_{1}$ and $t_{2}$ increases the amount of load cleared at $t_{3}$.
These results show how temporal flexibility is able to relieve ramping
constraints (analogous to how spatial flexibility relieves network
transmission constraints). However, because temporal shifts only move in the
direction of increasing time, their effects on price gaps are also
unidirectional. Specifically, temporal shifts can only exploit lower prices in
later times; for instance, scenarios 4 and 5 show that adding virtual link
$(1,3)$ does not change the solution since the price at node 2 is higher than
that at node 3.

Table 5 summarizes the payment and revenue results for the temporal case. We
observe that revenue adequacy is satisfied for all scenarios. Table 6
summarizes the profit results for the temporal case. We observe that the
clearing formulation satisfies cost recovery, since no participant incurs a
negative profit in all scenarios. Furthermore, similar to the spatial system,
the revenues and profits generated via virtual links become larger when there
is more price volatility in the system.

###  4.3 Space-Time IEEE-30 Bus System

We now consider a modified version of the IEEE 30-bus system. The network
topology is presented in Figure 9. Each square node is connected to a load
with varying demand capacity in time. The loads bid with the same price (200
$/MWh) and different capacity levels. A total of six of these loads are DaCes
owned by the same entity, distributed at 6 different nodes as shown in Figure
9. We run the space-time market clearing model over $T=24$ hours. Virtual
links are assigned as follows: a virtual link is assigned from one DaCes at
one time, either to itself at a later time, or to another DaCe at the same
time or a later time. Each virtual link has a bid price of
$0\,\$/\textrm{MWh}$ and capacity of $20\,\textrm{MWh}$. The two suppliers are
designated with a fixed cost and capacity over the time horizon.

Figure 9: Scheme of IEEE 30-bus system. Squared nodes are connected to a load.
Dashed curves are virtual links (not all virtual links are shown for clarity).

The LMPs of the 30-bus system over the time horizon are plotted in Figure 10.
We observe that virtual links are able to drastically reduce both spatial and
temporal price volatility. Specifically, with no virtual links, we can observe
prices reaching 200 $/MWh in 8 out of 24 time intervals, and negative prices
at 4 time intervals. Table 7 provide summarizing statistics for LMPs for both
cases. The range, standard deviation and average deviation are all much
smaller for the case with virtual links than the case with no virtual links.
In addition, the case of no virtual links has a mean value that is much higher
than its median value, meaning that the LMP distribution is positively skewed
when there are no virtual links. The price convergence behavior can also be
observed from the LMP distribution shown in Figure 11. With virtual links, the
LMPs become have less spread and exhibit a higher frequency at around 50
$/MWh, compared to the case with no virtual links.

(a) No virtual links

(b) With virtual links

Figure 10: Price trajectories of all buses over time. Dashed lines denote nodes with DaCes. Figure 11: Space-time LMPs distribution.  Table 7: Summarizing statistics for LMPs of IEEE 30-bus case study (in units of $/MWh). LMP Statistics | No virtual links | With virtual links
---|---|---
Mean | 56.6 | 43.77
Median | 44.21 | 44.22
Maximum | 200.0 | 55.95
Minimum | -5.85 | 18.42
Standard Deviation | 31.36 | 5.29
Average Deviation | 21.3 | 2.32

##  5 Conclusions and Future Work

We have presented a market clearing formulation to capture space-time, load-
shifting flexibility provided by data centers. Load-shifting flexibility is
captured using the concept of virtual links, which are non-physical pathways
that can transfer power geographically and over time. We show that the
proposed market clearing formulation satisfying fundamental properties (it
provides a competitive equilibrium and satisfies revenue adequacy and cost
recovery). Our analysis reveals that DaCes act as prosumers that are
remunerated for their provision of flexibility; this remuneration is analogous
to that of transmission service providers (based on nodal price differences)
but is unique in that it can traverse space-time. Moreover, we show that load-
shifting flexibility can help mitigate space-time price volatility;
specifically, we show that prices can be made homogeneous as we increase
flexibility. This new feature can be achieved because virtual links provide
alternative pathways that can help relieve physical transmission congestion.
We present case studies that illustrate these effects. As part of future work,
we are interested in understanding how data center flexibility could be used
to mitigate risk and maximize reliability. To do so, it is necessary to
develop stochastic market clearing formulations. Moreover, we are interested
in understand the effect of load-shifting flexibility on AC power flow systems
and in understanding strategic bidding by DaCes that help exploit space-time
price differences.

## Acknowledgments

We acknowledge support from the U.S. National Science Foundation under award
1832208.

## References

  * Aghaei and Alizadeh (2013) Jamshid Aghaei and Mohammad-Iman Alizadeh.  Demand response in smart electricity grids equipped with renewable energy sources: A review.  _Renewable and Sustainable Energy Reviews_ , 18:64–72, 2013\.
  * Bagirov et al. (2014) Adil Bagirov, Napsu Karmitsa, and Marko M Mäkelä.  _Introduction to Nonsmooth Optimization: theory, practice and software_.  Springer, 2014.
  * Bertsimas and Tsitsiklis (1997) Dimitris Bertsimas and John N Tsitsiklis.  _Introduction to linear optimization_.  Athena Scientific Belmont, MA, 1997.
  * Bouffard et al. (2005) François Bouffard, Francisco D Galiana, and Antonio J Conejo.  Market-clearing with stochastic security-part i: formulation.  _IEEE Trans. Power Syst._ , 20(4):1818–1826, 2005\.
  * Cao et al. (2018) Xuanyu Cao, Junshan Zhang, and H. Vincent Poor.  Data center demand response with on-site renewable generation: A bargaining approach.  _IEEE/ACM Transactions on Networking_ , 26(6):2707–2720, 2018.
  * Carrion and Arroyo (2006) M. Carrion and J.M. Arroyo.  A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem.  _IEEE Transactions on Power Systems_ , 21(3):1371–1378, 2006.
  * Commission (2019) California Public Utilities Commission.  California renewables portfolio standard.  https://www.cpuc.ca.gov/renewables/, 2019.  Accessed 2019-07-01.
  * Dunning et al. (2017) Iain Dunning, Joey Huchette, and Miles Lubin.  Jump: A modeling language for mathematical optimization.  _SIAM Review_ , 59(2):295–320, 2017.
  * Ghatikar et al. (2012) Girish Ghatikar, Venkata Ganti, Nance Matson, and Mary Ann Piette.  Demand response opportunities and enabling technologies for data centers: Findings from field studies, 2012.
  * Gribik et al. (2011) Paul R. Gribik, Dhiman Chatterjee, Nivad Navid, and Li Zhang.  Dealing with uncertainty in dispatching and pricing in power markets.  _2011 IEEE Power and Energy Society General Meeting_ , 2011.
  * Guo et al. (2018) Yuanxiong Guo, Hongning Li, and Miao Pan.  Colocation data center demand response using nash bargaining theory.  _IEEE Transactions on Smart Grid_ , 9(5):4017–4026, 2018.
  * Gurobi Optimization (2019) LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2019.  URL http://www.gurobi.com.
  * Hogan (1992) William W. Hogan.  Contract networks for electric power transmission.  _Journal of Regulatory Economics_ , 4(3):211–242, Sep 1992.
  * Hogan et al. (1996) W.W. Hogan, E.G. Read, and B.J. Ring.  Using mathematical programming for electricity spot pricing.  _International Transactions in Operational Research_ , 3(3‐4):209–221, 1996.
  * Kazempour et al. (2018) Jalal Kazempour, Pierre Pinson, and Benjamin F Hobbs.  A stochastic market design with revenue adequacy and cost recovery by scenario: Benefits and costs.  _IEEE Transactions on Power Systems_ , 33(4):3531–3545, 2018.
  * Kim et al. (2017) Kibaek Kim, Fan Yang, Victor M. Zavala, and Andrew A. Chien.  Data centers as dispatchable loads to harness stranded power.  _IEEE Transactions on Sustainable Energy_ , 8(1):208–218, 2017.
  * Liu et al. (2013) Zhenhua Liu, Adam Wierman, Yuan Chen, Benjamin Razon, and Niangjun Chen.  Data center demand response: Avoiding the coincident peak via workload shifting and local generation.  _Performance Evaluation_ , 70(10):770 – 791, 2013\.  Proceedings of IFIP Performance 2013 Conference.
  * Liu et al. (2014) Zhenhua Liu, Iris Liu, Steven Low, and Adam Wierman.  Pricing data center demand response.  _ACM SIGMETRICS Performance Evaluation Review_ , 42(1):111–123, 2014.
  * of State Legislatures (2019) National Conference of State Legislatures.  State renewable portfolio standards and goals.  http://www.ncsl.org/research/energy/renewable-portfolio-standards.aspx, 2019\.  Accessed 2019-07-01.
  * Pritchard et al. (2010) Geoffrey Pritchard, Golbon Zakeri, and Andrew Philpott.  A single-settlement, energy-only electric power market for unpredictable and intermittent participants.  _Operations Research_ , 58(4-part-2):1210–1219, 2010.
  * Rao et al. (2010) Lei Rao, Xue Liu, Le Xie, and Wenyu Liu.  Minimizing electricity cost: Optimization of distributed internet data centers in a multi-electricity-market environment.  _2010 Proceedings IEEE INFOCOM_ , 2010.
  * Sun et al. (2016) Qihang Sun, Shaolei Ren, Chuan Wu, and Zongpeng Li.  An online incentive mechanism for emergency demand response in geo-distributed colocation data centers.  In _Proceedings of the Seventh International Conference on Future Energy Systems_ , pages 3:1–3:13, New York, NY, USA, 2016. ACM.
  * Tran et al. (2015) Nguyen H. Tran, Dai H. Tran, Shaolei Ren, Zhu Han, Eui-Nam Huh, and Choong Seon Hong.  How geo-distributed data centers do demand response: A game-theoretic approach.  _IEEE Transactions on Smart Grid_ , page 1, 2015.
  * Wierman et al. (2017) Adam Wierman, Zhenhua Liu, Iris Liu, and Hamed Mohsenian-Rad.  Opportunities and challenges for data center demand response.  _IEEE Transactions on Smart Grid_ , 9:4017–4026, 2017.
  * Zakeri et al. (2019) Golbon Zakeri, Geoffrey Pritchard, Mette Bjorndal, and Endre Bjorndal.  Pricing wind: a revenue adequate, cost recovering uniform price auction for electricity markets with intermittent generation.  _INFORMS Journal on Optimization_ , 1(1):35–48, 2019.
  * Zavala et al. (2017) Victor M. Zavala, Kibaek Kim, Mihai Anitescu, and John Birge.  A stochastic electricity market clearing formulation with consistent pricing properties.  _Operations Research_ , 65(3):557–576, 2017.
  * Zhang et al. (2020) Weiqi Zhang, Line A Roald, Andrew A Chien, John R Birge, and Victor M Zavala.  Flexibility from networks of data centers: A market clearing formulation with virtual links.  _Electric Power Systems Research_ , 189:106723, 2020.
  * Zhou et al. (2018) Ruiting Zhou, Zongpeng Li, and Chuan Wu.  An online emergency demand response mechanism for cloud computing.  _ACM Trans. Model. Perform. Eval. Comput. Syst._ , 3(1):5:1–5:25, February 2018.

##  Appendix A Review on Non-Smooth Analysis

In this section we review tools of nonsmooth analysis that we use to establish
price bounding properties. This discussion is based on Bagirov et al. (2014).

###  A.1 Definitions

We consider a function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ that is convex
but not necessarily differentiable. A vector $g\in\mathbb{R}^{n}$ is a
subgradient of $f$ at point $x\in\mathbb{R}^{n}$ if for any
$y\in\mathbb{R}^{n}$

$f(y)\geq f(x)+g^{T}(y-x).$ (A.62)

The right hand side of (A.62) is a globally valid lower bound function for $f$
that attains the exact function value at point $x$. The subdifferential
$\partial f(x)$ of $f$ at $x$ is defined as the set of all subgradients at
$x$:

$\partial f(x)=\\{g\,|\,f(y)\geq
f(x)+g^{T}(y-x)\,\forall\,y\in\mathbb{R}^{n}\\}.$ (A.63)

In general, since convexity implies local Lipschitz continuity, $\partial
f(x)$ is a nonempty, convex and compact set. As a special case, if $f$ is
continuously differentiable at $x$, then the gradient $\nabla f(x)$ is defined
at $x$ and the subdifferential becomes a singleton:

$\partial f(x)=\\{\nabla f(x)\\}.$ (A.64)

###  A.2 Subgradient Calculus

We now summarize a set of basic rules for subgradient calculus. If
$f(x)=\sum_{i=1}^{n}\alpha_{i}f_{i}(x)$, where $\alpha_{i}\geq 0$ and $f_{i}$
is convex. Then the subdifferential of $f$ is

$\partial f(x)=\sum_{i=1}^{n}\alpha_{i}\partial f_{i}(x)$ (A.65)

where the $+$ operator is the Minkowski sum operator for sets:

$A+B=\\{a+b\,|\,a\in A,b\in B\\}$ (A.66)

In our analysis we frequently encounter functions of the following form:

$f(x)=\max_{i\in\\{1,2,...n\\}}\\{f_{i}(x)\\}$ (A.67)

where each $f_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is convex. The
subdifferential of $f$ is

$\partial f(x)=\text{conv}\bigcup_{i\in I(x)}\partial f_{i}(x)$ (A.68)

where $\text{conv}(\cdot)$ is the convex hull operator and
$I(x):=\\{i\,|\,f_{i}(x)=f(x)\\}$ denotes the set of active functions. When
$f_{i}$’s are differentiable, we have

$\partial f(x)=\text{conv}\\{\nabla f_{i}(x)\,|\,i\in I(x)\\}$ (A.69)

Note that all the subgradient calculus rules reviewed above reduce to
multivariate calculus if $f$ is continuously differentiable at $x$ (all
$\partial f_{i}$ can be replaced by $\nabla f_{i}(x)$).

###  A.3 Optimality Conditions

For convex $f$, $x^{*}$ is a global minimizer of $f$ if and only if
$0\in\partial f(x^{*})$. For the case in which $f$ is continuously
differentiable at $x^{*}$, the optimality conditions reduce to $\nabla
f(x^{*})=0$, which are necessary and sufficient optimality conditions for
convex minimization problems.