# A Note on Approximating Weighted Nash Social Welfare with Additive
Valuations

Yuda Feng
Department of Computer
Science and Technology,
Harbin Institute of Technology,
Harbin, Heilongjiang, China.
<EMAIL_ADDRESS>YF is an incoming PhD student at Nanjing University,
and his work was a part of his undergraduate dissertation supervised by SL.
Shi Li
Department of Computer
Science and Technology,
Nanjing University,
Nanjing, Jiangsu, China.
<EMAIL_ADDRESS>The work of SL was supported by the State Key Laboratory for
Novel Software Technology, and the New Cornerstone Science Laboratory.

###### Abstract

We give the first $O(1)$-approximation for the weighted Nash Social Welfare
problem with additive valuations. The approximation ratio we obtain is
$e^{1/e}+\epsilon\approx 1.445+\epsilon$, which matches the best known
approximation ratio for the unweighted case [3].

Both our algorithm and analysis are simple. We solve a natural configuration
LP for the problem, and obtain the allocation of items to agents using a
randomized version of the Shmoys-Tardos rounding algorithm developed for
unrelated machine scheduling problems [30]. In the analysis, we show that the
approximation ratio of the algorithm is at most the worst gap between the Nash
social welfare of the optimum allocation and that of an EF1 allocation, for an
unweighted Nash Social Welfare instance with identical additive valuations.
This was shown to be at most $e^{1/e}\approx 1.445$ by Barman et al. [3],
leading to our approximation ratio.

##  1 Introduction

In the weighted (or asymmetric) Nash Social Welfare problem with additive
valuations, we are given a set ${\mathcal{A}}$ of $n$ agents, and a set
${\mathcal{G}}$ of $m$ indivisible items. Every agent $i\in{\mathcal{A}}$ has
a weight $w_{i}\geq 0$ such that $\sum_{i\in{\mathcal{A}}}w_{i}=1$. There is a
value $v_{ij}\in{\mathbb{R}}_{\geq 0}$ for every $i\in{\mathcal{A}}$ and
$j\in{\mathcal{G}}$. The goal of the problem is to find an allocation
$\sigma:{\mathcal{G}}\to{\mathcal{A}}$ of items to agents so as to maximize
the following weighted Nash social welfare of $\sigma$:

$\displaystyle\prod_{i\in{\mathcal{A}}}\left(\sum_{j\in\sigma^{-1}(i)}v_{ij}\right)^{w_{i}}.$

In the case where all $w_{i}$’s are equal to $\frac{1}{n}$, we call the
problem the unweighted (or symmetric) Nash Social Welfare problem.

Allocating resources in a fair and efficient manner among multiple agents is a
fundamental problem in computer science, game theory, and economics, with
applications across diverse domains [19, 33, 4, 28, 25, 2, 29, 5]. The
weighted Nash social welfare function is a notable objective that balances
efficiency and fairness. The unweighted (or symmetric) objective was
independently proposed by different communities [26, 20, 32], and later the
study has been extended to the weighted case [16, 18]. Since then it has been
used in a wide range of applications, including bargaining theory [21, 7, 31],
water allocation [17, 10], and climate agreements [34].

The unweighted Nash Social Welfare problem with additive valuations is proved
to be NP-hard by Nguyen et al. [27], and APX-hard by Lee [22]. Later the
hardness of approximation was improved to $\sqrt{8/7}\approx 1.069$ by Garg et
al. [12], via a reduction from Max-E3-Lin-2.

On the positive side, Cole and Gkatzelis [9] gave a $(2e^{1/e}+\epsilon\approx
2.889+\epsilon)$-approximation using a market equilibrium with some spending
restrictions. The ratio was improved by Cole et al. [8] to $2$ using a tight
analysis, and by Anari et al. [1] to $e$ via a connection of the problem to
real stable polynomials. Both papers formulated some convex program (CP)
relaxations for the problem. In particular, [8] showed that the optimum
solution to their CP corresponds to the spending-restricted market equilibrium
defined in [9]. The state-of-the-art result for the problem is a combinatorial
$(e^{1/e}+\epsilon\approx 1.45+\epsilon)$-approximation algorithm due to
Barman et al.[3]. They showed that when all the valuations of agents are
identical, any allocation that is envy-free up to one item (EF1) is
$e^{1/e}$-approximate. Their approximation result then follows from a
connection between the non-identical and identical valuation settings they
established.

All the results discussed above are for the unweighted case. For the weighted
case with agent weights $w\in[0,1]^{\mathcal{A}},|w|_{1}=1$, Brown et al. [6]
presented a $5\cdot\exp(2\cdot
D_{\text{KL}}\Big{(}w||\frac{\vec{1}}{n})\Big{)}=5\cdot\exp(2\log
n+2\sum_{i\in{\mathcal{A}}}w_{i}\log w_{i})$ approximation algorithm, where
$D_{\text{KL}}$ denotes the KL divergence of two distributions. This is the
first work that studies the weighted version for the additive valuation case.
Prior to this work, there is an
$O(nw_{\max})=O(n\max_{i\in{\mathcal{A}}}w_{i})$-approximation for the more
general submodular valuation case [13], which we discuss soon. Brown et al.
[6] showed that the two CPs from [8] and [1] are equivalent, and their result
is based on the CP from [8], generalized to the weighted setting.

The additive valuation setting is a special case of the submodular valuation
setting, which is another important setting studied in the literature. In this
setting, instead of a $v_{ij}$ value for every $ij$ pair, we are given a
monotone submodular function $v_{i}:2^{{\mathcal{G}}}\to{\mathbb{R}}_{\geq 0}$
for every agent $i\in{\mathcal{A}}$. Our goal is to find an allocation
$\sigma:{\mathcal{G}}\to{\mathcal{A}}$ so as to maximize
$\prod_{i\in{\mathcal{A}}}\Big{(}v_{i}(\sigma^{-1}(i))\Big{)}^{w_{i}}$. A bulk
of the previous work has focused on the unweighted case; that is,
$w_{i}=\frac{1}{n}$ for all $i\in{\mathcal{A}}$. For this case, Garg et al.
[15] proved a hardness of $e/(e-1)\approx 1.5819$ using a reduction from
Max-3-Coloring; this is better than the $1.069$ hardness for the additive
valuation case.

On the positive side, Li and Vondrak [24] extended the techniques of Anari et
al. [1], to obtain an $e^{3}/(e-1)^{2}$-approximation algorithm for the
unweighted Nash Social Welfare problem for a large family of submodular
valuations, including coverage functions and linear combinations of matroid
rank functions. Later, Garg et al. [14] considered a family of submodular
functions called Rado functions, and gave an $O(1)$-approximation for this
family using the matching theory and convex program techniques. Li and Vondrak
[23] developped the first $O(1)$-approximation for general submodular
functions, with an approximation ratio of $380$. Recently, Garg et al. [13]
presented an elegant $4$-approximation local search algorithm for the problem,
which is the current best approximation result for the problem. All the
results discussed above are for the unweighted case. For the weighted case,
Garg et al. [13] gave an $O(nw_{\max})$-approximation, where
$n_{\max}=\max_{i\in{\mathcal{A}}}w_{i}$. Whether the weighted Nash Social
Welfare problem with submodular valuations admits a constant approximation is
a big open problem.

Recently, the problem has been studied in an even more general setting,
namely, the subadditive valuation setting. Dobzinski et al. [11] gives an
$O(1)$-approximation for the unweighted Nash Social Welfare problem in this
setting under the demand oracle model.

###  1.1 Our Result and Techniques

In this note, we give the first $O(1)$-approximation algorithm for the
weighted Nash Social Welfare problem with additive valuations:

######  Theorem 1.1.

For any $\epsilon>0$, there is a randomized $(e^{1/e}+\epsilon\approx
1.445+\epsilon)$-approximation algorithm for the weighted Nash Social Welfare
problem with additive valuations, with running time polynomial in the size of
the input and $\frac{1}{\epsilon}$.

Our approximation ratio of $e^{1/e}+\epsilon$ matches the best ratio for the
unweighted case due to Barman et al. [3]. In contrast, the ratio given by
Brown et al. [6] is $5\cdot\exp(2\cdot D_{\text{KL}}(w||\frac{\vec{1}}{n}))$,
which could be polynomial in $n$.

Our algorithm is based on a natural configuration LP for the problem, which
has not been studied before to the best of our knowledge. The configuration LP
contains a $y_{i,S}$ variable for every agent $i$ and subset $S$ of items,
indicating if the set of items $i$ gets is $S$ or not. We show that the
configuration LP can be solved in polynomial time to any precision, despite
having exponential number of variables. Once we obtain the LP solution, we
define $x_{ij}$ for every $i\in{\mathcal{A}}$ and $j\in{\mathcal{G}}$ to be
the fraction of $j$ assigned to $i$.

We use a randomized version of the Shmoys-Tardos rounding algorithm [30]
developed for unrelated machine scheduling problems, to round $x$ into an
integral solution. For every agent $i$, we break the fractional items assigned
to $i$ into groups from the most valuable to the least, each containing 1
fractional item. The rounding algorithm maintains marginal probabilities, and
the requirement that $i$ gets exactly one item from each group (except for the
last one, from which $i$ gets at most one item). In the analysis for each
agent $i$, we construct an instance of the unweighted Nash Social Welfare
problem with _identical_ additive valuations, that involves many copies of the
agent $i$, along with two alloations ${\mathcal{S}}$ and
${\mathcal{S}}^{\prime}$ to the instance. ${\mathcal{S}}$ corresponds to the
LP solution, and ${\mathcal{S}}^{\prime}$ corresponds to the randomized
solution given by the rounding algorithm. Thanks to the condition that every
group contains one item, the solution ${\mathcal{S}}^{\prime}$ is envy-free up
to one item (EF1). Using the result of [3] about EF1 allocations, we show that
the Nash social welfare of ${\mathcal{S}}^{\prime}$ is at least $e^{-1/e}$
times that of ${\mathcal{S}}$, which eventually leads to our
$(e^{1/e}+\epsilon)$-approximation.

We believe the configuration LP could be used in many other settings. We leave
as an immediate open problem whether it can give an $O(1)$-approximation for
the weighted Nash Social Welfare problem with submodular valuations.

##  2 $(e^{1/e}+\epsilon)$-Approximation Using Configuration LP

We describe the configuration LP in Section 2.1 and the rounding algorithm in
Section 2.2. The analysis is given in Section 2.3.

###  2.1 The Configuration LP

For convenience, for any value function $v:{\mathcal{G}}\to{\mathbb{R}}_{\geq
0}$, we define $v(S):=\sum_{j\in S}v_{j}$ for every $S\subseteq{\mathcal{G}}$
to be the total value of items in $S$ according to the value funciton $v$. In
the integer program correspondent to the configuration LP, for every $i\in\cal
A$ and $S\subseteq{\mathcal{G}}$, we have a variable $y_{i,S}\in\\{0,1\\}$
indicating if the set of items assigned to $i$ is $S$ or not. We relax the
integer constraint to obtain the following configuration LP:

$\displaystyle\max\sum_{i\in{\mathcal{A}},S\subseteq{\mathcal{G}}}w_{i}\cdot
y_{i,S}\cdot\ln v_{i}(S)\qquad\text{s.t.}$ (Conf-LP)
$\displaystyle\sum_{i\in{\mathcal{A}},S\ni j}y_{i,S}$ $\displaystyle\leq 1$
$\displaystyle\forall j\in{\mathcal{G}}$ (1)
$\displaystyle\sum_{S\subseteq{\mathcal{G}}}y_{i,S}$ $\displaystyle=1$
$\displaystyle\forall i\in{\mathcal{A}}$ (2) $\displaystyle y_{i,S}$
$\displaystyle\geq 0$ $\displaystyle\forall
i\in{\mathcal{A}},S\subseteq{\mathcal{G}}$ (3)

It is convenient for us to consider the natural logarithm of the Nash social
welfare function as the objective, which is
$\sum_{i\in{\mathcal{A}}}w_{i}\cdot\ln v_{i}(\sigma^{-1}(i))$. This leads to
the objective in (Conf-LP). (1) requires that every item $j$ is assigned to at
most one agent, and (2) requires that every agent $i$ is assigned one set of
items.

The configuration LP has exponential number of variables, but it can be solved
within an additive error of $\ln(1+\epsilon)$ for any $\epsilon>0$, in time
polynomial in the size of the instance and $\frac{1}{\epsilon}$. We defer the
details to Appendix A. Notice that we are considering the logarithm of Nash
social welfare, and the typical $(1+\epsilon)$-multiplicative factor becomes
an additive error of $\ln(1+\epsilon)$.

###  2.2 The Rounding Algorithm

From now on, we assume we have obtained a vector $y$ from solving the LP,
described using a list of non-zero coordinates; the value of $y$ to (Conf-LP)
is at least the optimum value minus $\ln(1+\epsilon)$. We can assume (1) holds
with equalities: $\sum_{i\in{\mathcal{A}},S\ni j}y_{i,S}=1$ for every
$j\in{\mathcal{G}}$. Then we let $x_{ij}=\sum_{S\ni j}y_{i,S}$ for every
$i\in{\mathcal{A}}$ and $j\in{\mathcal{G}}$. So
$\sum_{i\in{\mathcal{A}}}x_{ij}=1$ for every $j\in{\mathcal{G}}$.

In this paragraph, we fix an agent $i$ and break the fractional items assigned
to $i$ into a set $G_{i}$ of groups, each containing 1 fractional item. They
are created in non-increasing order of values, as in the Shmoys-Tardos
algorithm for unrelated machine scheduling problems. That is, the first group
contains the 1 fractional most valuable items assigned to $i$, the second
group contains the 1 fractional most valuable items assigned to $i$ after
removing the first group, and so on. Formally, we sort the items in
${\mathcal{G}}$ in non-increasing order of $v_{ij}$ values, breaking ties
arbitrarily. Let $p_{i}={\lceil\sum_{j\in{\mathcal{G}}}x_{ij}\rceil}$. Then we
can find vectors $g^{1},g^{2},\cdots,g^{p_{i}}\in[0,1]^{{\mathcal{G}}}$
satisfying the following properties:

  1. (P1)

For every $t\in[1,p_{i}-1]$, we have $|g^{t}|_{1}=1$; for $t=p_{i}$, we have
$|g^{t}|_{1}=\sum_{j\in{\mathcal{G}}}x_{ij}-(p_{i}-1)\in(0,1]$.

  2. (P2)

$\sum_{t=1}^{p_{i}}g^{t}_{j}=x_{ij}$ for every $j\in{\mathcal{G}}$.

  3. (P3)

For every $1\leq t<t^{\prime}\leq p_{i}$, and two items $j,j^{\prime}$ such
that $j$ appears before $j^{\prime}$ in the ordering, it can not happen that
$g^{t}_{j^{\prime}}>0$ and $g^{t^{\prime}}_{j}>0$.

It is easy to see that $g^{1},g^{2},\cdots,g^{p_{i}}$ are uniquely decided by
the three conditions. We say each $g^{t}$ is a group. Let
$G_{i}=\\{g^{1},g^{2},\cdots,g^{p_{i}}\\}$ be the set of all groups
constructed for this agent $i$.

Now we take all agents $i$ into consideration and let
$G=\uplus_{i\in{\mathcal{A}}}G_{i}$ be the set of all groups constructed.111It
is possible that two groups from different sets $G_{i}$ and $G_{i^{\prime}}$
have the same vector representation. So we treat $G$ as a multiset and we
assume we know which set $G_{i}$ each group $g\in G$ belongs to. The
representations of groups give a fractional matching between the groups $G$
and items ${\mathcal{G}}$: an item $j$ is matched to a group
$g\in[0,1]^{{\mathcal{G}}}$ with a fraction of $g_{j}$. Then each item is
matched to an extent of 1, and every group $g$ is matched to an extent of
$|g|_{1}$. So a group is matched to an extent of 1 if it is not the last group
for an agent, and at most 1 otherwise. Therefore, we can efficiently output a
randomized (partial-)matching between the groups $G$ and items ${\mathcal{G}}$
so that the marginal probabilities are maintained:

  1. ($\star$)

For every group $g\in G$ and item $j\in{\mathcal{G}}$, we have $\Pr[j\text{ is
matched to }g]=g_{j}$.

($\star$) implies that an item $j\in{\mathcal{G}}$ is matched with probability
1. If a group $g$ has $|g|_{1}=1$, then it is matched with probability 1.

The matching naturally gives us an allocation of items to agents: If an item
$j\in{\mathcal{G}}$ is matched to some group $g\in G_{i}$, then we assign $j$
to $i$. By ($\star$) we know that the probability that $j$ is assigned to $i$
is precisely $x_{ij}$. Let $S_{i}$ be the set of items assigned to $i$ in the
algorithm; notice that it is random. This finishes the description of the
randomized rounding algorithm.

###  2.3 The Analysis

To analyze our rounding algorithm, we first formally define an EF1 allocation.

######  Definition 2.1.

Given an instance of the unweighted Nash Social Welfare problem with agents
${\mathcal{A}}$, items ${\mathcal{G}}$, and identical additive valuation
$v:{\mathcal{G}}\to{\mathbb{R}}_{\geq 0}$ for all agents, an allocation
$\sigma:{\mathcal{G}}\to{\mathcal{A}}$ is said to be envy-free up to one item
(EF1), if for every two distinct agents $i,i^{\prime}$ with
$\sigma^{-1}(i^{\prime})\neq\emptyset$, there exists some
$j\in\sigma^{-1}(i^{\prime})$, such that $v(\sigma^{-1}(i^{\prime})\setminus
j)\leq v(\sigma^{-1}(i))$.

We use the following result from [3]:

######  Theorem 2.2 ([3]).

For the unweighted Nash Social Welfare problem with identical additive
valuations, any EF1-allocation is an $e^{1/e}$-approximate solution.

With the theorem, we prove the following key lemma:

######  Lemma 2.3.

For every $i\in{\mathcal{A}}$, we have

$\displaystyle\operatorname{\mathbb{E}}\big{[}\ln
v_{i}(S_{i})\big{]}\geq\sum_{S\subseteq{\mathcal{G}}}y_{i,S}\cdot\ln v_{i}(S)\
-\ \frac{1}{e}.$

###### Proof.

Throughout the proof, we fix the agent $i$. Let $\Delta>0$ be an integer, so
that every $y_{i,S}$ is an integer multiply of $1/\Delta$, and the probability
that $S_{i}=S$ for any $S$ is also an integer multiply of $1/\Delta$.222We can
assume all $y_{i,S}$ values are rational numbers. Under this condition, it is
easy to guarantee that the probabilities are rational numbers. We consider an
instance of the unweighted Nash Social Welfare problem with identical additive
valuations. In the instance, there are $\Delta$ copies of the agent $i$, and
$\Delta x_{ij}$ copies of every item $j\in{\mathcal{G}}$; so all the agents
are identical. The $y=(y_{i,S})_{S\subseteq{\mathcal{G}}}$ vector gives us an
allocation ${\mathcal{S}}$ to the instance: For every
$S\subseteq{\mathcal{G}}$, there are exactly $\Delta y_{i,S}$ agents who get a
copy of $S$. Notice that this is a valid solution, as $\sum_{S}y_{i,S}=1$ and
$\sum_{S\ni j}y_{i,S}=x_{ij}$ for every item $j$.

The Nash Social Welfare of the allocation ${\mathcal{S}}$ is

$\displaystyle\left(\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{\Delta
y_{i,S}}\right)^{1/\Delta}=\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{y_{i,S}}.$

The distribution for $S_{i}$ also corresponds to an allocation
${\mathcal{S}}^{\prime}$ of items to agents: For every
$S\subseteq{\mathcal{G}}$, there are $\Delta\cdot\Pr[S_{i}=S]$ agents who get
a copy of $S$. Again, this is a valid solution as $\sum_{S}\Pr[S_{i}=S]=1$ and
$\sum_{S\ni j}\Pr[S_{i}=S]=\operatorname{\mathbb{E}}[S_{i}\ni j]=x_{ij}$.

The Nash Social Welfare of the allocation ${\mathcal{S}}^{\prime}$ is

$\displaystyle\left(\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{\Delta\Pr[S_{i}=S]}\right)^{1/\Delta}=\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{\Pr[S_{i}=S]}.$

A crucial property for the solution ${\mathcal{S}}^{\prime}$ is that it is
EF1. Indeed, if $\Pr[S_{i}=S]>0$ for some $S$, then $S$ contains exactly one
item from each group in $G_{i}$ except for the last one, from which $S$
contains at most one item. Also, the items in the groups $G_{i}$ are sorted by
(P3). So if there are two sets $S$ and $S^{\prime}$ in the support of the
distribution for $S_{i}$, and we remove the most valuable item from
$S^{\prime}$, then $S$ beats $S^{\prime}$ item by item.

Therefore, by Theorem 2.2, we know that the Nash Social Welfare of
${\mathcal{S}}^{\prime}$ is at least $e^{-1/e}$ times that of the optimum
allocation for the instance, which is at least that of ${\mathcal{S}}$. That
is,

$\displaystyle\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{\Pr[S_{i}=S]}\geq
e^{-1/e}\cdot\prod_{S\subseteq{\mathcal{G}}}v_{i}(S)^{y_{i,S}}.$

Taking logarithm on both sides gives the lemma. ∎

Applying the lemma for every $i\in{\mathcal{A}}$ and using linearity of
expectation, we have

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{i\in{\mathcal{A}}}w_{i}\cdot\ln
v_{i}(S_{i})\right]\geq\sum_{i\in S,S\subseteq{\mathcal{G}}}w_{i}\cdot
y_{i,S}\cdot\ln v_{i}(S)-\frac{1}{e}.$

We used that $\sum_{i\in{\mathcal{A}}}w_{i}=1$.

By the convexity of exponential function, we have

$\displaystyle\operatorname{\mathbb{E}}\left[\prod_{i\in{\mathcal{A}}}v_{i}(S_{i})^{w_{i}}\right]\geq
e^{-1/e}\cdot\exp\left(\sum_{i\in S,S\subseteq{\mathcal{G}}}w_{i}\cdot
y_{i,S}\cdot\ln v_{i}(S_{i})\right)\geq
e^{-1/e}\cdot\frac{\text{opt}}{1+\epsilon},$

where opt is the Nash Social Welfare of the optimum allocation, and the second
inequality used that the value of our solution $y$ to (Conf-LP) is at least
its optimum value minus $\ln(1+\epsilon)$. By scaling $\epsilon$ down by an
absolute constant at the beginning, we can make the right side to be at least
$\frac{\text{opt}}{e^{1/e}+\epsilon}$. This finishes the proof of Theorem 1.1.

Finally, we briefly discuss how to derandomize the rounding algorithm. We
round the solution to the configuration LP in iterations, maintaining a
fractional assignment $\bar{x}$ of items to agents; $\bar{x}=x$ initially. Let
$\Delta$ be a large enough integer so that every $y_{i,S}$ is an integer
multiply of $1/\Delta$. Focus on a fixed agent $i\in{\mathcal{A}}$ and
consider the Nash Social Welfare instance containing $\Delta$ copies of $i$,
and $\Delta\bar{x}_{ij}$ copies of each item $j\in{\mathcal{G}}$. Group the
items as follows: the $\Delta$ most valuable items belong to the first group,
the next $\Delta$ most valuable items belong to the second group, and so on.
We define $\Phi_{i}$ to be the logarithm of the Nash Social Welfare of the
worst allocation satisfying the following condition: every agent gets at most
one item from each group. Fortunately, the worst allocation can be defined
naturally: the first agent takes the most valuable item from each group, and
the second agent takes the second most valuable item from each group, and so
on. Thus $\Phi_{i}$ can be computed efficiently. We define
$\Phi=\sum_{i}w_{i}\Phi_{i}$ to be the overall potential function. In the
randomized version of the algorithm, one can define the rotation operation
over the fractional matching between groups $G$ and items ${\mathcal{G}}$. In
expectation the operation does not decrease $\Phi$. To derandomize the
algorithm, we can perform the operation deterministically so that $\Phi$ does
not decrease. The potential value $\Phi$ at the end of the algorithm is at
least that at the beginning, which is at least the value of the configuration
LP minus $1/e$. On the other hand, the logarithm of the Nash Social Welfare of
the integral solution is exactly the final $\Phi$. Therefore, the Nash Social
Welfare is at least $e^{-1/e}$ times the exponential of the value of the
configuration LP.

## References

  * [1] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh.  Nash Social Welfare, Matrix Permanent, and Stable Polynomials.  In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [2] Julius Barbanel and Alan Taylor.  The Geometry of Efficient Fair Division.  The Geometry of Efficient Fair Division, pages 1–462, 01 2005.
  * [3] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding Fair and Efficient Allocations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 557–574, New York, NY, USA, 2018. Association for Computing Machinery.
  * [4] Steven J. Brams and Alan D. Taylor.  Fair Division: From Cake-Cutting to Dispute Resolution.  Cambridge University Press, 1996.
  * [5] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia.  Handbook of Computational Social Choice.  Cambridge University Press, USA, 1st edition, 2016.
  * [6] Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu, and Mohit Singh.  Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs.  In Proceedings of the Thirty-Fifth ACM-SIAM Symposium on Discrete Algorithms, 2024.
  * [7] Suchan Chae and Hervé Moulin.  Bargaining Among Groups: An Axiomatic Viewpoint.  International Journal of Game Theory, 39(1):71–88, 2010.
  * [8] Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod.  Convex Program Duality, Fisher Markets, and Nash Social Welfare.  In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, page 459–460, New York, NY, USA, 2017. Association for Computing Machinery.
  * [9] Richard Cole and Vasilis Gkatzelis.  Approximating the Nash Social Welfare with Indivisible Items.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 371–380, New York, NY, USA, 2015. Association for Computing Machinery.
  * [10] Dagmawi Mulugeta Degefu, Weijun He, Liang Yuan, An Min, and Qi Zhang.  Bankruptcy to Surplus: Sharing Transboundary River Basin’s Water under Scarcity.  Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), 32(8):2735–2751, 2018.
  * [11] Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, and Jan Vondrak.  A Constant Factor Approximation for Nash Social Welfare with Subadditive Valuations.  ArXiv, abs/2309.04656, 2023.
  * [12] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Satiation in Fisher Markets and Approximation of Nash Social Welfare.  Mathematics of Operations Research, 0(0):null, 2023.
  * [13] Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák.  Approximating Nash Social Welfare by Matching and Local Search.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1298–1310, New York, NY, USA, 2023. Association for Computing Machinery.
  * [14] Jugal Garg, Edin Husić, and László A. Végh.  Approximating Nash Social Welfare under Rado Valuations.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1412–1425, New York, NY, USA, 2021. Association for Computing Machinery.
  * [15] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni.  Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings.  ACM Trans. Algorithms, 19(4), sep 2023.
  * [16] John C. Harsanyi and Reinhard Selten.  A generalized nash solution for two-person bargaining games with incomplete information.  Management Science, 18(5):P80–P106, 1972.
  * [17] Harold Houba, Gerard van der Laan, and Yuyu Zeng.  Asymmetric Nash Solutions in the River Sharing Problem.  Game Theory & Bargaining Theory eJournal, 2013.
  * [18] E. Kalai.  Nonsymmetric Nash Solutions and Replications of 2-Person Bargaining.  Int. J. Game Theory, 6(3):129–133, sep 1977.
  * [19] Mamoru Kaneko and Kenjiro Nakamura.  The Nash Social Welfare Function.  Econometrica, 47(2):423–435, 1979.
  * [20] Frank Kelly.  Charging and Rate Control for Elastic Traffic.  European Transactions on Telecommunications, 8(1):33–37, 1997.
  * [21] Annick Laruelle and Federico Valenciano.  Bargaining in Committees as An Extension of Nash’s Bargaining Theory.  Journal of Economic Theory, 132(1):291–305, 2007.
  * [22] Euiwoong Lee.  APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items.  ArXiv, abs/1507.01159, 2015.
  * [23] W. Li and J. Vondrak.  A Constant-Factor Approximation Algorithm for Nash Social Welfare with Submodular Valuations.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 25–36, Los Alamitos, CA, USA, feb 2022. IEEE Computer Society.
  * [24] Wenzheng Li and Jan Vondrák.  Estimating the Nash Social Welfare for Coverage and Other Submodular Valuations.  In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 1119–1130, USA, 2021. Society for Industrial and Applied Mathematics.
  * [25] Herve Moulin.  Fair Division and Collective Welfare.  The MIT Press, 2004.
  * [26] John F. Nash.  The Bargaining Problem.  Econometrica, 18(2):155–162, 1950.
  * [27] Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and Jörg Rothe.  Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3, AAMAS ’12, page 1287–1288, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.
  * [28] Jack Robertson and William Webb.  Cake-Cutting Algorithms: Be Fair if You Can.  A K Peters/CRC Press, 1998.
  * [29] Jrg Rothe.  Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division.  Springer Publishing Company, Incorporated, 1st edition, 2015.
  * [30] David B. Shmoys and Éva Tardos.  An Approximation Algorithm for the Generalized Assignment Problem.  Mathematical Programming, 62(1):461–474, 1993.
  * [31] William Thomson.  Replication Invariance of Bargaining Solutions.  Int. J. Game Theory, 15(1):59–63, mar 1986.
  * [32] Hal R Varian.  Equity, Envy, and Efficiency.  Journal of Economic Theory, 9(1):63–91, 1974.
  * [33] H. Peyton Young.  Equity: In Theory and Practice.  Princeton University Press, 1994.
  * [34] S. Yu, E. C. van Ierland, H. P. Weikard, and X. Zhu.  Nash Bargaining Solutions for International Climate Agreements under Different Sets of Bargaining Weights.  International Environmental Agreements: Politics, Law and Economics, 17(5):709–729, 2017.

##  Appendix A Solving Configuration LP within an Additive Error of
$\ln(1+\epsilon)$

Let $\epsilon>0$ be upper bounded by a sufficiently small constant (we allow
$\epsilon$ to be a sub-constant). By only allowing every agent to get one
item, we can obtain an $m$-approximation for the our Nash Social Welfare
instance. Then, by making $O\Big{(}\frac{\log m}{\epsilon}\Big{)}$ guesses, we
can assume we are given a number $o$ such that the value of (Conf-LP) is in
$(o,o+\epsilon/3]$.

We consider the dual of (Conf-LP), with the objective replaced by a
constraint.

$\displaystyle\sum_{j\in{\mathcal{G}}}\alpha_{j}+\sum_{i\in{\mathcal{A}}}\beta_{i}$
$\displaystyle\leq o$ (4) $\displaystyle\sum_{j\in S}\alpha_{j}+\beta_{i}$
$\displaystyle\geq w_{i}\cdot\ln v_{i}(S)$ $\displaystyle\forall
i\in{\mathcal{A}},S\subseteq{\mathcal{G}}$ (5) $\displaystyle\alpha_{j}$
$\displaystyle\geq 0$ $\displaystyle\forall j\in{\mathcal{G}}$ (6)

Since (Conf-LP) has value strictly larger than $o$, the dual LP (4-6) is
infeasible. We design an approximate separation oracle for the LP. Given some
$\alpha\in{\mathbb{R}}_{\geq 0}^{\mathcal{G}}$ and
$\beta\in{\mathbb{R}}^{\mathcal{A}}$ that does not satisfy (5), we can find
some $i\in{\mathcal{A}}$ and $S\subseteq{\mathcal{G}}$ such that

$\displaystyle\sum_{j\in
S}\alpha_{j}+\beta_{i}<w_{i}\ln\big{(}(1+\epsilon/2)v_{i}(S)\big{)}.$

The running time of the oracle is polynomial in the input size and
$\frac{1}{\epsilon}$. This can be achieved using the standard dynamic
programming technique: For a fixed $i\in{\mathcal{A}}$, to find the $S$, we
guess the item $j^{*}\in S$ with the largest $v_{ij^{*}}$, coarsen the
$v_{ij}$ values based on the guess, and run a dynamic programming to find the
$S$.

So, using the ellipsoid method with the approximate separation oracle, we can
find polynomially many half spaces of the form $\sum_{j\in
S}\alpha_{j}+\beta_{i}\geq w_{i}\ln\big{(}(1+\epsilon/2)v_{i}(S)\big{)}$,
whose intersection is empty. Then, we consider the Nash Social Welfare
instance where all $v_{ij}$ values are scaled up by $1+\epsilon/2$, and (Conf-
LP) to the instance. By solving the LP restricted to the variables $y_{i,S}$
correspondent to the half spaces (that is, we let all other variables be $0$),
we obtain a solution $y$ whose value is at least $o$ w.r.t the scaled
instance. So, the value of the solution $y$ to (Conf-LP) w.r.t the original
instance is at least
$o-\sum_{i\in{\mathcal{A}},S\subseteq{\mathcal{G}}}y_{i,S}w_{i}\ln(1+\epsilon/2)=o-\sum_{i}w_{i}\ln(1+\epsilon/2)=o-\ln(1+\epsilon/2)$.

As the value of (Conf-LP) is at most $o+\epsilon/3$, we solved the LP up to an
additive error of $\epsilon/3+\ln(1+\epsilon/2)$. For a small enough
$\epsilon$, this is at most $\ln(1+\epsilon)$.


# Health-Focused Optimal Power Flow

Logesh Kumar⋆, Parikshit Pareek⋆, Sivakumar Nadarajan, Souvik Dasgupta, Amit
Gupta, and Hung D. Nguyen# # Corresponding Author⋆ The first two authors
contributed equally to this workKumar is with Rolls-Royce@NTU Corporate Lab
and School of EEE NTU, Singapore<EMAIL_ADDRESS>and Nguyen are
with School of EEE NTU, Singapore<EMAIL_ADDRESS>Dasgupta, and Gupta are with Rolls-Royce Electrical, Singapore
<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a novel Health-Focused Optimal Power Flow (HF-OPF)
to take into account the equipment health in operational and physical
constraints. The health condition index is estimated based on the possible
fault characteristics for generators and batteries. The paper addresses the
need for understanding the relationship between health condition index and the
operational constraints in OPF problems. Such a relationship is established
through Finite Element Method (FEM)-based simulations. The simulations for
generator and battery faults indicate the presence of an inflection point
after which effect of fault becomes severe. A microgrid system is used to
illustrate the performance of the proposed HF-OPF. The results show that
health condition inflicts high cost of generation and can lead to
infeasibility even with less critical faults.

##  I Introduction

The optimal power flow (OPF) is a fundamental problem for power system
operation. It is solved for finding an economical operating point within a
physical network and operational constraints [1]. In recent years, the
development of various microgrid architectures leads to several OPF
formulations, including various sources and load types [2]. The microgrid hold
conventional generators, renewable generators and as well as battery energy
storage systems (BESS) [3]. All these formulations consider all network
components to be working perfectly. To incorporate the effect of equipment
failures, an extension of classical OPF has been proposed which considered the
constraints arising due to operation under a fixed list of postulated
contingencies [4]. All these formulations handle equipment failure
contingencies in binary fashion i.e., either perfectly working or completely
failed. Due to this discrete handling of equipment health status, these
formulations cannot be used to examine and incorporate the effects of various
types of faults in generators or BESS. Further, Energy Management System (EMS)
for on-board microgrid of an aircraft [5], maritime systems on ships and
submarines [6] and remote areas without grid connection [7] are required to
work reliably for long and critical duration. These microgrid systems may not
be able to shut down a power source as they do not have access to extra power
most of the times. Also, the maintenance cannot be done on-site in most of the
cases, and system may need to work properly for long-duration before it is
safe to shut down for maintenance. In addition to these concerns, the
advancements in online health monitoring have enabled EMS to access health
conditions remotely. Hence EMS of microgrid can act upon these for preventive
as well as corrective actions. Therefore, it is imperative to incorporate the
effect of equipment health, in a non-discrete manner, in OPF. This will help
in maintaining the system reliability with the least cost infliction. In this
paper, we propose a novel Health-Focused Optimal Power Flow (HF-OPF)
incorporating the effect of equipment health condition as a continuous
function. This work attempts to understand the relationship between incipient
faults and OPF constraints. A health condition index is defined for generator
and BESS to reflect various fault conditions uniformly. Further, these health
condition index have been converted into OPF constraints. The HF-OPF is solved
using state-of-art Semi-Definite Programming (SDP) relaxation. The main
contributions of this paper are:

  * •

Proposing a novel Health-Focused Optimal Power Flow (HF-OPF) formulation to
incorporate equipment health by modelling OPF constraints as functions of
health condition index.

  * •

Defining health condition index for generator and battery for the
establishment of a relationship between health and OPF constraints via FEM
analysis.

  * •

Analysing the variation OPF constraints with health condition and cost
inflicted by health deterioration of equipment.

##  II Health Condition Monitoring

For a generator, various individual faults in generator such as Turn-Turn
Short Circuit (TTSC) [8], demagnetization fault [9], eccentricity fault have
been studied independently, and individual health condition have been
established. Yet, the insights into the overall, combined health condition of
the generator or battery system are not well studied. This paper develops the
overall health of generator and battery as a function of fault
characteristics. Further, the relationship between the health condition index
and OPF constraints has been established through FEM simulations. Below we
elaborate the notion of health condition index in more detail.

###  II-A Health Condition Index

For a machine, the health condition index is estimated based on the fault
characteristics established in this context as fault severity, fault factor,
and fault weightage. In general, calculating the health condition index of a
machine is nontrivial. In this paper, we leverage the component simulations
with high fidelity modelling to estimate a machine’s health condition. In
particular, Finite Element Method (FEM) will be performed for these fault
characteristics to establish with accuracy the corresponding OPF constraints.
The FEM software solves the magnetic field in case of generator to calculate
the inductance from which current, voltage, and power factor are obtained.

For a battery, the computational fluid dynamics (CFD) based ANSYS Fluent
solves the electrochemistry to establish the thermal characteristics from
which the electrical parameters are obtained. The obtained relationship can be
used in real-time monitoring environment to detect and diagnose the health of
the individual equipment.

Figure 1: Co-simulation of generator drive system in Twin Builder Figure 2:
Generator health condition index formulation block diagram

###  II-B Health Condition Index for Generator ($G_{HCI}$) and BESS
($B_{HCI}$)

The generator and battery health condition index is quantified in this
subsection. The key emphasis is on the definition alone, so the design aspect
and their parameters are not discussed as the health condition index are
normalized to their base rating. The health condition index of the generator
is simulated through a generator drive system with the electromagnetic field
solved in ANSYS Maxwell, and the control action is established in MATLAB-
SIMULINK environment to control the fluctuating DC load voltage. The co-
simulation is carried out in Twin Builder/Simplorer for the continuous
exchange of data between the FEA ANSYS and MATLAB and is shown in Figure 1.
The electrical faults in generator include open-circuited phase fault, short-
circuited fault which include TTSC, phase to phase, and phase to ground fault.
The mechanical fault includes static eccentricity, dynamic eccentricity,
mixed, and bearing fault.

The TTSC faults are generally initiated by insulation breakdown caused by
overheating or mechanical breakage [10]. TTSC faults, when undetected in
early-stage, may lead to other severe winding short faults due to high fault
loop current. The TTSC fault produces flux in opposite direction due to the
reactive nature of the fault, which increases the eddy current and hysteresis
loss in the machine. The TTSC fault is simulated in ANSYS Maxwell by splitting
the total conductors in coil A as a separate rectangular conductor. The
separate conductors are taken externally to the Twin Builder to model it as an
extra winding to carry the fault loop current. Two levels of fault severity
are simulated accounting for $8.33\%$, and $25\%$. The demagnetization fault
occurs due to either TTSC fault or prolonged overloading in the flux weakening
region of the machine. In severe cases, the demagnetization and TTSC fault may
lead to the saturation of the core resulting in asymmetrical flux distribution
in the machine. The demagnetization fault is simulated by increasing the
temperature of magnet using the BH curve. Two different fault severity of one
magnet and three magnets with fault factor of $100^{\circ}C$ and
$150^{\circ}C$ is simulated. The various causes for the mechanical faults are
misalignment due to manufacturing defects, unbalanced magnetic pull, or
mechanical resonance at critical speed. The eccentricity fault creates high-
frequency components based on the switching frequency as well as the length of
the cable. The low-frequency component is also produced in torque due to other
faults in machine leading to the increase in shaft voltage and consequently to
the bearing fault in the machine. In ANSYS Maxwell, the SE is introduced by
shifting the stator and the coils to 72% and 88.8% from normal position.
Similarly, DE is implemented by shifting the rotor and the magnets by 17.7%,
and 22.2% from their initial position.

Figure 3: Unbalanced factor calculated for TTSC fault condition

Various faults in asset exhibit different characteristics features. Common
platform to weigh these features for formulating the health index of the
generator is necessary. Figure 2 shows the block diagram for generator health
condition index, real power, and voltage formulation. The total harmonic
distortion (THD) according to IEEE standard ${519^{TM}-2014}$ provides
variation for any fault in the asset, so THD is used as an evaluating
signature to calculate the unbalanced factor. The unbalanced factor being
calculated for TTSC fault condition is shown in Figure 3. Similarly, the
unbalanced factor is calculated for all other generator fault based on the
harmonic content. The weightage factor for the fault indicators to be used
real-time are calculated based on the unbalanced factor. The real-time
obtained fault indicators are normalized with their respective weightage
factor. Finally, using the synthetic FEM simulation knowledge about the fault
threshold, the mapping of normalized value with the health index range is done
to obtain the health condition index of the generator and the values for
various generator fault cases are shown in Table I. The relationship between
the health condition index of the component and the constraint will not be
linear.

Figure 4: Temperature contour with SOC of $90\%$ for (a) Healthy (b) External
short-circuit (c) Internal short-circuit (d) Thermal runaway

This is due to the definition of index and their corresponding fault
characteristics. As different fault behaves differently, and their effect on
system parameters vary based on the fault type and their severity. So, this
non-linearity in parameters tend to occur with incipient fault cases.

TABLE I: Generator health condition index, P, and V calculated based on synthetic simulation data | Generator
---
fault cases
| Fault severity
---
based on RUL
P range | V range |  | $G_{HCI}$
---
range
Healthy | 0 | 0 | 0 | 1
Magnet fault | 0.5 | 0.06 | 0.075 | 0.99-0.96
| Static
---
eccentricity
0.8 | 0.08 | 0.11 | 0.96-0.94
| Dynamic
---
eccentricity
0.9 | 0.08 | 0.12 | 0.95-0.93
| Mixed
---
eccentricity
0.91 | 0.07 | 0.135 | 0.92
| Turn-turn short-
---
circuit
1 | 0.1 | 0.15 | 0.9-0.86
Phase-Ground | 3 | 0.49 | 0.469 | 0.79
Open-Phase | 4 | 0.59 | 0.527 | 0.76
Phase-Phase | 5 | 0.69 | 0.587 | 0.65
| Three-phase
---
open
7 | 0.75 | 0.827 | 0.51
| Bolted short-
---
circuited
10 | 0.89 | 0.934 | 0

The battery electrochemistry is solved in CFD based ANSYS Fluent. The three
common faults in battery are external short circuit, internal short circuit,
and thermal runaway. The internal short circuit is the incipient fault case
and can lead to thermal runaway in long run. The leading causes for internal
short circuit fault are lithium plating decomposition, electrode or
electrolyte decomposition, or various external factors contributing to
localized heat spots in the battery. The number of steps or cycles for healthy
and various fault cases will be different for the same c-rate and are
represented as end-of-discharge ($F$) factor over time. The external short
circuit fault is simulated by introducing an external resistance with the
battery terminal for 50% fault severity of $0.5\Omega$. The various SOC
condition for c-rate equal to one is formulated to get $B_{HCI}$ as shown in
Table II. The internal short circuit fault and thermal runaway are introduced
by patching the center of the battery to a resistance of $5\times
10^{-7}\Omega$ and $5\times 10^{-8}\Omega$ respectively. The temperature
contour for healthy and faulty cases with SOC of 90% is shown in Figure 4.

TABLE II: Battery health condition index, P, and V calculated based on synthetic simulation data | Battery
---
fault cases
| Fault severity
---
based on RUL
P range | V range |  | $B_{HCI}$
---
range
Healthy | 0 | 0 | 0 | 0.9
| External
---
short circuit
0.5 | 0.26 | 0.31 | 0.81
| Internal
---
short circuit
0.9 | 0.91 | 0.92 | 0.53
| Thermal
---
runaway
1 | 0.96 | 0.98 | 0

##  III Health-Focused OPF and Its SDP Relaxation

The conventional OPF is a constraint optimization problem for minimization of
an objective while working over a set of equality and inequality constraints
as:

$\displaystyle\min_{\mathbf{x}}$ $\displaystyle C(\mathbf{x})$ (1) s.t
$\displaystyle f_{i}(\mathbf{x})=0;\quad i=1,2\dots m$ $\displaystyle
x_{k}\leq x^{u}_{k};\quad k=1,2\dots n$

Here, $\mathbf{x}$ is variable vector having control and state variables,
$f_{i}(\mathbf{x})$ is equality constraint function while $x^{u}_{k}$
represents the upper limit of variable $x_{k}$. The upper bound vector
$\mathbf{x}^{u}$ is considered constant if the equipment is connected. The
proposed general HF-OPF formulation is given as:

$\displaystyle\min_{\mathbf{x}}$ $\displaystyle C(\mathbf{x})$ (2) s.t
$\displaystyle f_{i}(\mathbf{x})=0;\quad i=1,2\dots m$ $\displaystyle
x_{k}\leq x^{u}_{k}(\beta_{k}(h_{k}));\quad k=1,2\dots n$

It is essential to understand that health condition index cannot be determined
with certainty in various conditions. Therefore, we propose to use the
probability distribution of health, $\beta_{k}(h_{k})$, in defining the bounds
on $\mathbf{x}$. This way, the HF-OPF formulation (2) will have uncertain
limits which needed to take care by the chance-constrain or robust
optimization tools. Currently, for better understanding of the effects of
health on OPF, we use $\beta_{k}(h_{k})=h_{k}$, which can be interpreted as a
mean of the probability function. We define network node-set as $\mathcal{N}$,
generator node-set $\mathcal{G}\subseteq\mathcal{N}$ and the set of branches
as $\mathcal{L}$. We define $\mathcal{B}$ as a set of nodes having BESS and
use $k$ as node index. Other system parameters are defined as:

  * •

$S_{G_{k}}=P_{G_{k}}+jQ_{G_{k}}$:= Apparent power generation by generator
connected to $k\in\mathcal{G}$.

  * •

$S_{L_{k}}=P_{L_{k}}+jQ_{L_{k}}$:= Apparent power load at $k\in\mathcal{N}$.

  * •

$V_{k}=V_{x_{k}}+jV_{y_{k}}$:= Complex node voltage at node $k\in\mathcal{N}$.

  * •

$S_{kl}=P_{kl}+jQ_{kl}$:= The apparent, real, and reactive power flow in
branch from node $k$ to $l$ where $(k,l)\in\mathcal{L}$.

  * •

$C(P_{G_{k}})$:= Quadratic cost function for real power generation at node
$k\in\mathcal{G}$.

  * •

$\mathbf{Y}$:= Admittance matrix of size $\mathcal{N}\times\mathcal{N}$ with
elements ${y}_{kl}$ where $(k,l)\in\mathcal{L}$

The ACOPF model is studied in detail by various works [1, 11, 12, 13]. The
vital difference in proposed HF-OPF is that limits are a function of health
which are considered as constant in conventional ACOPF formulation. The HF-OPF
for the real power generation cost minimization objective can be expressed as
[14]:

min $\displaystyle~{}~{}~{}\sum\limits_{k\in\mathcal{G}}C(P_{G_{k}})$ (3a)
s.t. $\displaystyle V^{l}_{k}(h_{k})\leq|V_{k}|\leq
V^{u}_{k}(h_{k})\quad\;k\in\mathcal{N}$ (3b) $\displaystyle|S_{kl}|\leq
S^{u}_{kl}\quad\;(k,l)\in\mathcal{L}$ (3c) $\displaystyle
P^{l}_{G_{k}}(h_{k})\leq P_{G_{k}}\leq
P^{u}_{G_{k}}(h_{k})\quad\;k\in\mathcal{G}$ (3d) $\displaystyle
Q^{l}_{G_{k}}(h_{k})\leq Q_{G_{k}}\leq
Q^{u}_{G_{k}}(h_{k})\quad\;k\in\mathcal{G}$ (3e) $\displaystyle
S_{G_{k}}=S_{D_{k}}+\sum\limits_{l}S_{kl}\quad\;k\in\mathcal{N}$ (3f)
$\displaystyle
S_{kl}={y}^{\star}_{kl}V_{k}V_{k}^{\star}-{y}^{\star}_{kl}V_{k}V_{l}^{\star}\quad\;(k,l)\in\mathcal{L}$
(3g)

Here, it is essential to understand that HF-OPF considers a continuous health
condition index $h_{k}$, which affects the capabilities of the devices
connected with the network. Thus, it takes a very realistic situation into
account instead of event-based analysis where only binary conditions (on/off)
are considered. In the proposed formulation, the BESS is treated as a
generator with lower real power limits being negative and function of health
during the discharging. The additional constraint on BESS are:

$\displaystyle-P^{u}_{k}(h_{k})\leq$ $\displaystyle
P_{k}(t)\leq+P^{u}_{k}(h_{k})\quad\;k\in\mathcal{B}$ (4a) $\displaystyle
E^{l}_{k}(h_{k})\leq$ $\displaystyle E_{k}(t)\leq
E^{u}_{k}(h_{k})\quad\;k\in\mathcal{B}$ (4b)

Here, $E_{k}(t)$ represents state-of-charge (SOC), in works related OPF with
BESS, $P^{u}_{k}$ is has been taken as rated power capacity and
$E^{u}_{k}$/$E^{l}_{k}$ is a fixed number defining upper/lower limit of energy
stored [15]. In the proposed HF-OPF, the complexity arises in the non-convex
power flow equation (3g) solely due to the product term of voltage
($V_{k}V_{l}^{\star}$). In literature, various models have been proposed for
the convex relaxation of the ACOPF problem. One of the initial model was
presented in [14] using a lifting variable matrix $W$ which is equal to the
voltage product term as $W_{kl}=V_{k}V^{\star}_{l},(k,l\in\mathcal{N})$. In
this work, we use the model described in [14, 13] with
$W\in\mathbb{R}^{2n_{b}\times 2n_{b}}$ and $\mathbf{V}\in\mathbb{R}^{2n_{b}}$.
The HF-OPF problem (3a-3g), with matrix variable $W$ can be expressed as:

$\displaystyle\min\quad\sum\limits_{k\in\mathcal{G}}C(P_{G_{k}})$ (5a) Subject
to $\displaystyle
P^{l}_{G_{k}}(h_{k})-P_{D_{k}}\leq\operatorname{Tr}\\{\mathbf{Y}_{k}W\\}\leq
P^{u}_{G_{k}}(h_{k})-P_{D_{k}}$ (5b) $\displaystyle
Q^{l}_{G_{k}}(h_{k})-Q_{D_{k}}\leq\operatorname{Tr}\\{\mathbf{\overline{Y}}_{k}W\\}\leq
Q^{u}_{G_{k}}(h_{k})-Q_{D_{k}}$ (5c)
$\displaystyle(V^{l}_{k}(h_{k}))^{2}\leq\operatorname{Tr}\\{M_{k}W\\}\leq(V^{u}_{k}(h_{k}))^{2}$
(5d)
$\displaystyle\operatorname{Tr}\\{\mathbf{Y}_{kl}W\\}^{2}+\operatorname{Tr}\\{\mathbf{\overline{Y}}_{kl}W\\}^{2}\leq(S^{u}_{kl})^{2}$
(5e) $\displaystyle W=\mathbf{V}\mathbf{V}^{T}$ (5f)

Here, the real and reactive power generation and $\mathbf{V}$ are:

$\displaystyle P_{G_{k}}=\operatorname{Tr}\\{\mathbf{Y}_{k}W\\}+P_{D_{k}}$
(6a) $\displaystyle
Q_{G_{k}}=\operatorname{Tr}\\{\mathbf{\overline{Y}}_{k}W\\}+Q_{D_{k}}$ (6b)
$\displaystyle\mathbf{V}=[\mathbf{V}_{x}^{T}\;\;\mathbf{V}_{y}^{T}]^{T}$ (6c)

The definition of the constant matrices
$\mathbf{Y}_{k},~{}\mathbf{\overline{Y}}_{k},~{}\mathbf{Y}_{kl},~{}\mathbf{\overline{Y}}_{kl}$
and $M_{k}$ is similar the one presented in [14] and has not presented here to
avoid repetition. This non-convexity of power flow constraint (3f) is now
transferred into a single equality constraint (5f). For relaxed HF-OPF the
equality constraint (5f) has been replaced by:

$\displaystyle W$ $\displaystyle\succeq 0.$ (7)

The exactness of the HF-OPF has been sacrificed by removing the non-convex
rank-one constraint of $W$. The details of exactness conditions can be found
in [14] for similar relaxation. Thus, the SDP relaxed HF-OPF is minimization
of objective (5a) constrained to BESS SOC constrain (4b) and relaxed ACOPF
constrains (5b)- (5e), (6a), (6b) and (7) abd. The constrain (5b) is obtained
from (4a) for BESS modeled as real power generator.

##  IV Test Results

For testing the proposed HF-OPF and analysis of the effect of health on cost,
we use a 3-Bus test microgrid system as given in Fig. 5. The G1 is a costly
healthy generator while different fault conditions are simulated on G2 and
battery.

Figure 5: 3-Bus microgrid test network

First, we consider nominal loading condition. The relative cost change, with
respect to ACOPF solution having with perfectly healthy generator, is
calculated. Except for the variation in $P^{u}_{2}$, all other system and
solver parameters are kept constant to observe only the effect of health on
ACOPF solution. $P_{G_{2}}$ decreases sharply when the maximum output is
limited due to poor health and other costly power sources (BESS and G1) output
increases for load balancing.

Figure 6: Variations in relative cost change with $G_{HCI}$ at different cases

Due to the effect on voltage limit, the system may not have any solution as it
will violate the voltage tolerance band (considered as $0.9-1.1$ (pu) (5d)).
Therefore, results of relative cost variations, including health condition’s
effect on voltage, are given in Figure 6. Considering $V^{u}_{2}$ as a
function of generator health makes a more significant impact on the HF-OPF
solution cost in comparison to taking only $P^{u}_{2}(G_{HCI})$ into account.
These results also emphasize the requirement of HF-OPF as the effect on cost
is pronounced very rapidly with a decrease of $G_{HCI}$.

Figure 7: Effect of loading on HF-OPF cost solution

We also perform the test using three different scaling factors ($SF$). The
nominal loading condition shows the same results when only
$P^{u}_{2}(G_{HCI})$ is considered in Figure 7. Subsequently, at higher
loading, the effect on cost is very high with even small health decrease.
These results indicate that for critical microgrid systems, the health
monitoring and HF-OPF solution is essential. Similarly, we analyze the HF-OPF
results with the health condition of the battery. The cost variation is
observed and step change will be similar to the generator. This variation is
due to non-linearity in the effects of faults on the real power discharge
capacity of the battery. These results have been able to highlight the fact
that the HF-OPF solution differs from OPF solution significantly.

##  V Conclusion

The contingency-based OPF methods consider the health of power system
equipment discretely. The critical microgrid systems need to have better
incorporation of equipment health to ensure high availability and reliability.
To facilitate this, we propose a novel Health-Focused OPF formulation, which
includes constraints as a function of health condition index. The FEM based
analysis is used to establish the relationship of health condition index with
constraints. The test results indicate that health issues will cause severe
costs on real power generations, let alone the problems of infeasibility. The
proposed HF-OPF can work with online health monitoring systems, and EMS of
remote microgrid will provide improved reliability. Future works include the
establishment of the nonlinear relationship between health condition index and
OPF constraints as well as solving HF-OPF for uncertain health condition index
and constraints.

## Acknowledgment

This work is supported by NTU SUG and IAF-ICP, RRE Power System Health
Management project.

## References

  * [1] S. H. Low, “Convex relaxation of optimal power flow part 1: Formulations and equivalence,” _IEEE Trans. on Control of Network Systems_ , vol. 1, no. 1, pp. 15–27, 2014.
  * [2] H. Abdi, S. D. Beigvand, and M. La Scala, “A review of optimal power flow studies applied to smart grids and microgrids,” _Renewable and Sustainable Energy Reviews_ , vol. 71, pp. 742–766, 2017.
  * [3] Y. Levron, J. M. Guerrero, and Y. Beck, “Optimal power flow in microgrids with energy storage,” _IEEE Trans. on Power Systems_ , vol. 28, no. 3, pp. 3226–3234, 2013.
  * [4] F. Capitanescu, J. M. Ramos, P. Panciatici, D. Kirschen, A. M. Marcolini, L. Platbrood, and L. Wehenkel, “State-of-the-art, challenges, and future trends in security constrained optimal power flow,” _Electric Power Systems Research_ , vol. 81, no. 8, pp. 1731–1741, 2011.
  * [5] G. Buticchi, S. Bozhko, M. Liserre, P. Wheeler, and K. Al-Haddad, “On-board microgrids for the more electric aircraft—technology review,” _IEEE Trans. on Industrial Electronics_ , vol. 66, no. 7, pp. 5588–5599, 2018.
  * [6] Z. Jin, M. Savaghebi, J. C. Vasquez, L. Meng, and J. M. Guerrero, “Maritime dc microgrids-a combination of microgrid technologies and maritime onboard power system for future ships,” in _2016 IEEE 8th IPEMC-ECCE Asia_. IEEE, 2016, pp. 179–184.
  * [7] S. Mizani and A. Yazdani, “Design and operation of a remote microgrid,” in _2009 35th Annual Conference of IEEE Industrial Electronics_. IEEE, 2009, pp. 4299–4304.
  * [8] S. Nadarajan, S. K. Panda, B. Bhangu, and A. K. Gupta, “Hybrid model for wound-rotor synchronous generator to detect and diagnose turn-to-turn short-circuit fault in stator windings,” _IEEE Trans. on Industrial Electronics_ , vol. 62, no. 3, pp. 1888–1900, 2014.
  * [9] K. Ahsanullah, S. Panda, and J. Elango, “Demagnetization fault detection for pmsm based marine propulsion motors using search coils in the stator slots,” in _2017 IEEE INTERMAG_. IEEE, 2017, pp. 1–2.
  * [10] C. Lai, A. Balamurali, V. Bousaba, K. L. V. Iyer, and N. C. Kar, “Analysis of stator winding inter-turn short-circuit fault in interior and surface mounted permanent magnet traction machines,” in _2014 IEEE ITEC_. IEEE, 2014, pp. 1–6.
  * [11] D. Lee, H. D. Nguyen, K. Dvijotham, and K. Turitsyn, “Convex restriction of power flow feasibility sets,” _IEEE Trans. on Control of Network Systems_ , vol. 6, no. 3, pp. 1235–1245, 2019.
  * [12] H. D. Nguyen, K. Dvijotham, and K. Turitsyn, “Constructing convex inner approximations of steady-state security regions,” _IEEE Trans. on Power Systems_ , vol. 34, no. 1, pp. 257–267, 2018.
  * [13] P. Pareek and H. D. Nguyen, “Small-signal stability constrained optimal power flow: A convexification approach,” _arXiv preprint arXiv:1911.12001_ , 2019\.
  * [14] J. Lavaei and S. H. Low, “Zero duality gap in optimal power flow problem,” _IEEE Trans. on Power Systems_ , vol. 27, no. 1, pp. 92–107, 2012.
  * [15] S. J. Hossain and et.al., “An integrated battery optimal power dispatch architecture for end-user-driven microgrid in islanded and grid-connected mode of operation,” _IEEE Trans. on Industry Applications_ , vol. 54, no. 4, pp. 3806–3819, 2018.