∎ 11institutetext: Institute of Informatics, University of Szeged, Hungary
11email: {ahmad, boglarka<EMAIL_ADDRESS>
# Exact Methods for the Longest Induced Cycle Problem

Ahmad T. Anaqreh  Boglárka G.-Tóth  Tamás Vinkó

(draft version: )

###### Abstract

The longest induced (or chordless) cycle problem is a graph problem classified
as NP-complete and involves the task of determining the largest possible
subset of vertices within a graph in such a way that the induced subgraph
forms a cycle. Within this paper, we present three integer linear programs
specifically formulated to yield optimal solutions for this problem. The
branch-and-cut algorithm has been used for two models. To demonstrate the
computational efficiency of these methods, we utilize them on a range of real-
world graphs as well as random graphs. Additionally, we conduct a comparative
analysis against approaches previously proposed in the literature.

###### Keywords:

longest induced cycle longest chordless cycle mixed integer linear programming
branch-and-cut algorithm valid inequalities

††journal:

##  1 Introduction

Cycles in graphs. A significant part of combinatorial optimization is closely
related to graphs. Within graph theory, the concept of graph cycles has
fundamental importance. Identifying a simple cycle or a cycle with a specific
structure within a graph forms the basis for numerous graph-theoretical
problems that have been under investigation for many years. One such problem
is the Eulerian walk, a cyclic path that traverses each edge exactly once, as
discussed in west . Another example is the Hamiltonian cycle, which traverses
every vertex exactly once, as explored in akiyama .

Longest cycle. Kumar et al. kumar , introduced a heuristic algorithm for the
longest simple cycle problem. The authors utilized both adjacency matrices and
adjacency lists, achieving a time complexity for the proposed algorithm
proportional to the number of nodes plus the number of edges of the graph. In
alon , the authors investigated the longest cycle within a graph with a large
minimal degree. For a graph $G=(V,E)$ with a vertex count of $|V|=n$, the
parameter $\mathrm{min\\_deg}(G)$ denotes the smallest degree among all
vertices in $G$, while ${\mathrm{c}}(G)$ represents the size of the longest
cycle within $G$. The authors demonstrated that for $n>k\geq 2$, with
$\mathrm{min\\_deg}(G)\geq n/k$, the lower bound
${\mathrm{c}}(G)\geq[n/(k-1)]$ holds. Broersma et al. broersma  proposed exact
algorithms for identifying the longest cycles in claw-free graphs. A claw, in
this context, refers to a star graph including three edges. The authors
introduced two algorithms for identifying the longest cycle within such graphs
containing $n$ vertices: one algorithm operates in $\mathcal{O}(1.6818^{n})$
time with exponential space complexity, while the second algorithm functions
in $\mathcal{O}(1.8878^{n})$ time with polynomial space complexity.

Longest isometric cycle. In the work by Lokshtanov Lokshtanov , the focus lies
on the examination of the longest isometric cycle within a graph, which is
defined as the longest cycle where the distance between any two vertices on
the cycle remains consistent with their distances in the original graph. The
author introduced a polynomial-time algorithm to address this specific
problem.

Longest induced cycle. Our primary focus in this paper is dedicated to
addressing the challenge of identifying the longest induced (or chordless)
cycle problem. For a graph $G=(V,E)$ and a subset $W\subseteq V$, the
$W$-induced graph $G[W]$ comprises all the vertices from set $W$ and the edges
from $G$ that connect vertices exclusively within $W$. The objective of the
longest induced cycle problem is to determine the largest possible subset $W$
for which the graph $G[W]$ forms a cycle. While it may seem straightforward to
obtain an induced cycle since every isometric cycle is an induced cycle, it
has been shown that identifying the longest induced cycle within a graph is an
NP-complete problem, as demonstrated by Garey et al. garey .

The longest induced path ($P$), discussed in Matsypura , represents a sequence
of vertices within graph $G$, where each consecutive pair of vertices is
connected by an edge $e\in E$ and there is no edge between non-consecutive
vertices within $P$. In the context of a general graph $G$, determining the
existence of an induced path with a specific length is proven to be NP-
complete, as detailed in garey . Consequently, the longest induced cycle can
be considered as a special case of the longest induced path.

Holes in a graph, defined as induced cycles with four or more vertices, play a
significant role in various contexts. Perfect graphs, for instance, are
characterized by the absence of odd holes or their complements chen2007 .
Moreover, when addressing challenges like finding maximum independent sets in
a graph nemhauser1992 , the existence of odd holes leads to the formulation of
odd hole inequalities, strengthening approaches for these problems. Similarly,
in other problem domains such as set packing and set partitioning
borndorfer1998 , these odd hole inequalities serve as crucial components.

Several papers have explored the longest induced cycle problem in graphs with
specific structures. In fuchs , the author investigated the longest induced
cycle within the unit circulant graph. To define the unit circulant graph
$X_{n}=Cay(\mathbb{Z}_{n};\mathbb{Z}_{n}^{*})$, where $n$ is a positive
integer, consider the following. The vertex set of $X_{n}$, denoted as $V(n)$,
comprises the elements of $\mathbb{Z}_{n}$, the ring of integers modulo $n$.
The edge set of $X_{n}$, represented as $E(n)$, for $x,y\in V(n)$, $(x,y)\in
E(n)$ if and only if $x-y\in\mathbb{Z}_{n}^{*}$, with $\mathbb{Z}_{n}^{*}$
being the set of units within the ring $\mathbb{Z}_{n}$. The author
demonstrates that if the positive integer $n$ has $r$ distinct prime divisors,
then $X_{n}$ contains an induced cycle of length $2^{r}+2$. In a separate
study by Wojciechowski et al. wojciechowski , the authors examine the longest
induced cycles within hypercube graphs. If $G$ represents a $d$-dimensional
hypercube, they proved the existence of an induced cycle with a length
$\geq(9/64)\cdot 2^{d}$.

Almost parallel to our work, Pereira et al. pereira  dealt with the longest
cordless cycle problem, which is equivalent to the longest induced cycle
problem. They presented an integer linear program (ILP) formulation along with
additional valid inequalities to strengthen and refine the formulation, all of
which were incorporated into a branch-and-cut algorithm. They applied a multi-
start heuristic method for initial solution generation and then conducted
performance evaluations of the algorithm on a range of randomly generated
graphs, including those with up to 100 vertices. They could solve the largest
problems within 3,011.17 seconds. Our aim is to provide models and methods
that can work more efficiently. The models and the best branch-and-cut
versions proposed in pereira  are discussed in Section 2.5.

Our paper proposes three integer linear programs (ILPs) designed to handle the
longest induced cycle problem within general graphs. Some of these models were
built based on those used in previous work focused on solving the longest
induced path problem, as seen in the studies by Marzo et al. Marzo  and Bokler
et al. Bokler . Matsypura et al. Matsypura  introduced three integer
programming (IP) formulations and an exact iterative algorithm based on these
IP formulations for tackling the longest induced path problem. However, it is
important to note that we do not extend these methods, as they were found to
be less effective compared to models in Marzo ; Bokler .

The rest of the paper is organized as follows. Section 2 and 3 discuss the
models and methodologies used to solve the problem together with the best
models and methods presented in pereira . Section 4 reports the numerical
results to show the efficiency of our models, also compared to the results in
pereira . The conclusion of our work is presented in Section 5.

##  2 Models

###  2.1 Notations

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set
$E\subset V\times V$. An edge $e\in E$ can be given as $(i,j)$ for some
$i,j\in V$. However, the symmetric pair $\bar{e}=(j,i)$ is not included in
$E$. Thus, we introduce the symmetric edge set
$E^{*}=E\cup\\{\bar{e}=(j,i):e=(i,j)\in E\\}$. Throughout, an edge $e=(i,j)$,
and $\bar{e}=(j,i)$ unless explicitly stated otherwise.

We use the notation $\delta$ for adjacent edges over vertices and edges as
follows. Let us denote the outgoing and incoming edges incident to vertex $i$
with $\delta^{+}(i)=\\{(i,k)\in E^{*}\\}$, and $\delta^{-}(i)=\\{(k,i)\in
E^{*}\\}$, respectively. Additionally,
$\delta(i)=\delta^{+}(i)\cup\delta^{-}(i)$ denote all the edges incident to
vertex $i$.

For an edge $e=(i,j)\in E^{*}$, outgoing edges are
$\delta^{+}(e)=\delta^{+}(i)\cup\delta^{+}(j)\setminus\\{e,\bar{e}\\}$, and
similarly, incoming edges are
$\delta^{-}(e)=\delta^{-}(i)\cup\delta^{-}(j)\setminus\\{e,\bar{e}\\}$. The
neighbour edges of $e$ are denoted by
$\delta(e)=\delta^{+}(e)\cup\delta^{-}(e)$ for all $e\in E^{*}$. This notation
can be extended to any subset of vertices $C\subset V$, where
$\delta^{+}(C):=\\{(k,l)\in E^{*}:k\in C,l\in V\setminus C\\}$ and
$\delta^{-}(C):=\\{(k,l)\in E^{*}:l\in C,k\in V\setminus C\\}$ denote the
outgoing and incoming edges of $C$, respectively, and
$\delta(C)=\delta^{+}(C)\cup\delta^{-}(C)$ all edges that connect $C$ with
$V\setminus C$.

###  2.2 Order-based model

The first model to discuss, called _LIC_ , is an MILP model using order-based
formulation to avoid subtours. The formalism of the model is as follows:

$\max\sum_{i\in V}y_{i}$ (1)

subject to

$\displaystyle x_{e}+x_{\bar{e}}$ $\displaystyle\leq 1$
$\displaystyle\quad\forall\ e\in E$ (2)
$\displaystyle\sum_{g\in\delta^{+}(e)}x_{g}$ $\displaystyle\leq 1$
$\displaystyle\quad\forall\ e\in E^{*}$ (3) $\displaystyle y_{i}$
$\displaystyle=\sum_{\begin{subarray}{c}g\in\delta^{+}(i)\end{subarray}}x_{g}$
$\displaystyle\quad\forall i\in V$ (4) $\displaystyle y_{i}$
$\displaystyle=\sum_{\begin{subarray}{c}g\in\delta^{-}(i)\end{subarray}}x_{g}$
$\displaystyle\quad\forall i\in V$ (5) $\displaystyle\sum_{i\in V}w_{i}$
$\displaystyle=1$ (6) $\displaystyle w_{i}$ $\displaystyle\leq y_{i}$
$\displaystyle\quad\forall\ i\in V$ (7) $\displaystyle u_{i}-u_{j}$
$\displaystyle\leq n(1-x_{e})-1+nw_{i}$ $\displaystyle\quad\forall e\in E^{*}$
(8) $\displaystyle\sum_{i\in V}iw_{i}$ $\displaystyle\leq jy_{j}+n(1-y_{j})$
$\displaystyle\quad\forall\ j\in V$ (9) $\displaystyle y_{i},u_{i}\geq 0$
$\displaystyle\quad\forall i\in V$ (10) $\displaystyle x_{e}\in\\{0,1\\}$
$\displaystyle\quad\forall e\in E^{*}$ (11) $\displaystyle w_{i}\in\\{0,1\\}$
$\displaystyle\quad\forall i\in V$ (12)

The variable $y_{i}$ indicates whether vertex $i$ is part of the longest
induced cycle or not. Consequently, the objective in (1) aims to maximize the
sum of these variables, which directly corresponds to the length of the cycle.
The decision variable $x_{e}$ is one if the edge $e$ is included in the
solution, and zero otherwise.

The constraints can be understood as follows. Given that $E^{*}$ is symmetric,
constraint (2) guarantees that only one of the edges $e$ or $\bar{e}$ can
exist in the cycle, preventing the formation of small cycles. Constraint (3)
ensures that for any edge $e=(i,j)\in E^{*}$, only one outgoing edge from
either vertex $i$ or vertex $j$ can be part of the cycle. Constraints (4) and
(5) ensure that for a given vertex $i$, only one outgoing edge and one
incoming edge can be chosen to be part of the cycle. The constraint (8) is a
modified Miller-Tucker-Zemlin (MTZ) order-based formulation: if edge $e$ is in
the cycle, vertices $i$ and $j$ must be arranged in sequential order unless
the binary variable $w_{i}$ equals 1. This variable is introduced to handle
the position of the last vertex in the cycle, facilitating the ordering
process. Constraint (9) functions as a symmetry-breaking constraint, as
described in walsh . It enforces that the last vertex in the cycle must have
the smallest index among all vertices in the cycle.

For a variation of the above introduced _LIC_ model consider the following
constraint:

$\displaystyle x_{e}+x_{\bar{e}}$ $\displaystyle\geq y_{i}+y_{j}-1$
$\displaystyle\qquad\forall\ e=(i,j)\in E$ (13)

Constraint (13) guarantees that either edge $e$ or $\bar{e}$ must be included
in the solution if both endpoints $i$ and $j$ are part of the solution.
Conversely, if an edge is not selected for the solution, neither of its
endpoints can be included in the solution. By substituting constraint (3) in
the original _LIC_ model with constraint (13), we create a new model, _LIC_
2\. This modification leads to improved runtime performance compared to _LIC_
, as demonstrated in Section 4.

###  2.3 Subtour-elimimation model

The second model we employ to address the longest induced cycle problem is
based on the model presented by Bokler et al. Bokler , which is referred to
_ILP_ cut and was originally designed for identifying the longest induced
path. $E^{*}$ is the symmetric edge set, as defined previously. Let
$\mathcal{C}$ represent the set of cycles in $G$. The model is defined as
follows:

$\max\frac{1}{2}\sum_{e\in E^{*}}x_{e}$ (14)

subject to

$\displaystyle x_{e}$ $\displaystyle=x_{\bar{e}}$ $\displaystyle\qquad\forall
e\in E$ (15) $\displaystyle x_{e}$
$\displaystyle\leq\sum_{g\in\delta^{-}(i)}x_{g}$ $\displaystyle\qquad\forall\
e=(i,j)\in E^{*}$ (16)
$\displaystyle\sum_{g\in\delta^{-}(i)}x_{g}+\sum_{g\in\delta^{+}(j)}x_{g}$
$\displaystyle\leq 2$ $\displaystyle\qquad\forall\ e=(i,j)\in E^{*}$ (17)
$\displaystyle\sum_{e\in\delta(i)}x_{e}$
$\displaystyle\leq\sum_{g\in\delta(C)}x_{g}$ $\displaystyle\qquad\forall
C\in\mathcal{C},i\in C$ (18) $\displaystyle x_{e}\in\\{0,1\\}$
$\displaystyle\qquad\forall e\in E^{*}$ (19)

The binary decision variable $x_{e}$ indicates whether edge $e$ is a part of
the longest induced cycle, but unlike in the _LIC_ model (in Section 2.2), in
this case, edge selection is symmetric. Consequently, the objective is to
maximize half of the sum of these variables, as defined in objective function
(14). Symmetry of the solution is guaranteed by (15). Constraint (16) enforces
that the solution forms a cycle or cycles, while constraint (17) specifies
that for any edge $e$, precisely two of its adjacent edges must also be
selected. This ensures the induced property of the solution. Constraint (18)
is utilized to eliminate small cycles in the graph.

###  2.4 Cycle-elimination model

Our third model, called _cec_ , is a modified version of the _cec_ model
introduced in Marzo  to find the longest induced path. In this model, the
symmetry of the edges is not used. The formalism of the model is as follows:

$\max\sum_{i\in V}y_{i}$ (20)

subject to

$\displaystyle\sum_{e\in\delta(i)}x_{e}$ $\displaystyle=2y_{i}$
$\displaystyle\quad\forall\ i\in V$ (21) $\displaystyle x_{e}$
$\displaystyle\leq y_{i}$ $\displaystyle\quad\forall\ i\in V,e\in\delta(i)$
(22) $\displaystyle x_{e}$ $\displaystyle\geq y_{i}+y_{j}-1$
$\displaystyle\quad\forall e=(i,j)\in E$ (23) $\displaystyle\sum_{i\in
C}y_{i}$ $\displaystyle\leq|C|-1$ $\displaystyle\quad\forall C\in\mathcal{C}$
(24) $\displaystyle y_{i}\in\\{0,1\\}$ $\displaystyle\quad\forall i\in V$ (25)
$\displaystyle x_{e}\in\\{0,1\\}$ $\displaystyle\quad\forall e\in E$ (26)

The binary decision variable $y_{i}$ maintains its previous interpretation,
equal to one if vertex $i$ is part of the solution. Additionally, variable
$x_{e}$ is set to one if edge $e$ is included in the solution. However, in
this context, the symmetric edge is not needed. The objective function (20)
seeks to maximize the number of vertices within the induced cycle. Constraint
(21) guarantees that each vertex within the solution is connected to precisely
two vertices in the cycle. Constraints (22) and (23) are in place to ensure
that the cycle is induced. To eliminate solutions composed of small cycles
from consideration, constraint (24) is introduced. $\mathcal{C}$ represents a
set of the cycles for the given graph. Constraint (24) is combined into the
model to enforce the solution to consist of a single cycle. This means that
multiple small cycles are not deemed valid solutions.

###  2.5 Cordless-cycle model

The CCP formulation was introduced by Pereira et al. pereira  to deal with the
problem at hand. The CCP formulation is formally described as follows:

$\max\sum_{i\in V}y_{i}$ (27)

subject to

$\displaystyle\sum_{e\in E}x_{e}$ $\displaystyle=\sum_{i\in V}y_{i}$ (28)
$\displaystyle\sum_{i\in V}y_{i}$ $\displaystyle\geq 4$ (29)
$\displaystyle\sum_{e\in\delta(i)}x_{e}$ $\displaystyle=2y_{i}$
$\displaystyle\quad\forall\ i\in V$ (30)
$\displaystyle\sum_{g\in\delta(C)}x_{g}$ $\displaystyle\geq 2(y_{i}+y_{j}-1)$
$\displaystyle\quad C\subset V,i\in C,j\in V\setminus C$ (31) $\displaystyle
x_{e}$ $\displaystyle\leq y_{i}$ $\displaystyle\quad\forall\ i\in
V,e\in\delta(i)$ (32) $\displaystyle x_{e}$ $\displaystyle\geq y_{i}+y_{j}-1$
$\displaystyle\quad\forall\ e=(i,j)\in E$ (33) $\displaystyle
x_{e}\in\\{0,1\\}$ $\displaystyle\quad\forall e\in E$ (34) $\displaystyle
y_{i}\in\\{0,1\\}$ $\displaystyle\quad\forall i\in V$ (35)

The formulation includes the usual sets of binary variables: $y_{i}$ and
$x_{e}$, indicating whether vertex $i$ and edge $e$ are in the cycle or not.
Consequently, the number of selected vertices and edges is equal, as required
by (28), and at most four vertices must be selected by (29). Each vertex
within the solution is incident to precisely two edges, as guaranteed by (30).
Moreover, the subgraph defined by $x$ and $y$ remains connected, as guaranteed
by the subtour elimination constraint (31). Furthermore, (32)–(33) ensures
that any solution is an induced subgraphs of $G$. More specifically, any edge
of $G$ with both its endpoints belonging to the solution must be part of the
solution.

The CCP formulation was employed by the authors of pereira , along with
various valid inequalities. They introduced nine branch-and-cut (_BC_)
algorithms and subsequently chose the top three among them. The first one,
labeled as _BC_ 1 contains constraints (28)-(35), and in addition the
following constraint:

$\displaystyle\sum_{g\in\delta(C)}x_{g}$ $\displaystyle\geq 2x_{e}$
$\displaystyle\quad C\subset V,e=(i,j)\in E,i\in C,j\in V\setminus C$ (36)

This algorithm initiates by separating (31), and subsequently, the resulting
inequality is enhanced to the more robust form of (36). This specific
constraint ensures that if $x_{e}=1$, then it is mandatory for $y_{i}=y_{j}=1$
to hold true, due to the presence of inequalities (32)-(33).

For the _BC_ 2 and _BC_ 3 algorithms, both constraints (37) and (38) were
included together with constraints (28)-(36).

$\displaystyle\sum_{i\in Q}y_{i}$ $\displaystyle\leq 2$ (37)
$\displaystyle\sum_{e\in E(Q)}x_{e}$ $\displaystyle\geq\sum_{i\in Q}y_{i}-1$
(38)

For a clique $Q\subset V$, $|Q|\geq 3$. Constraint (37) ensures that within a
clique $Q$ at most two of its vertices can be part of the induced cycle. On
the other hand, constraint (38) guarantees that for a clique $Q$ the number of
vertices that can be part of the induced cycle is limited to at most one more
than the number of edges that can be included from the clique. Namely, only
one of the edges from $Q$ might be included in the solution.

For the _BC_ 2 algorithm, they implemented a rule that imposes no restrictions
on the number of separation rounds. In other words, whenever a violated
inequality is detected, it is included in the cut pool. Conversely, for _BC_
3, a fixed number of separation rounds, specifically 30, was established, and
inequalities were added to the cut pool if a clique did not share two or more
vertices with a clique in a previously accepted inequality. The order of
inequalities in the cut pool was determined by descending order of the
absolute values of their corresponding linear programming relaxation dual
variables. All three algorithms utilized the lower bounds obtained from the
multi-start CCP heuristic, which is a constructive procedure that takes a
predefined edge as input data. The algorithm then seeks to extend a tentative
path, $P$, containing the selected vertices. Vertices are added to $P$ one at
a time, accepted if they are adjacent to one of the path’s current extremities
and not adjacent to any internal vertices. The procedure terminates when the
endpoints of $P$ meet, resulting in a chordless cycle of $G$, or when further
expansion of $P$ becomes impossible.

##  3 Algorithms

Out of the three models we have introduced, only _LIC_ (and _LIC_ 2) can be
directly solved using any MILP solver. Both $ILP_{cut}$ and $cec$ rely on the
set of small cycles, which are usually created as part of the solution
process, either through an iterative cut generation approach or, more
effectively, via branch-and-cut algorithm by employing separation.

Note that subtour elimination inequalities (18) and (24), present in the _ILP_
cut and _cec_ models respectively, exhibit exponential complexity.
Consequently, attempting to enumerate all inequalities corresponding to each
subtour within the graph and subsequently cutting them becomes impractical.
Instead, we have added these inequalities to the _ILP_ cut and _cec_ models as
soon as facing them. Hence, the cut generation approach is employed as
follows: the method is initiated with a model relaxing all subtour elimination
inequalities, and if subtours arise in integer solutions, violated
inequalities are added, and this process is repeated until the optimal
solution is reached. For that, callback functionality from Gurobi gurobi  was
employed, which can be used to add these inequalities iteratively.

We employed the Depth-First Search (DFS) algorithm on the induced subgraph of
the integer solution to identify cycles, subsequently introducing a new
inequality for each subtour discovered. The entire procedure, which combines
the models and cut generations, is shown in Algorithms 1 and 2.

###  3.1 Initialization

In the initialization phase of the procedure, the _ILP_ cut and _cec_ models
are created, encompassing the creation of their variables, constraints, and
objective functions.

###  3.2 Cut generation

To tackle the _ILP_ cut and _cec_ models, we combine the cut generation
mechanism with the Branch-and-bound method, as explained earlier in this
Section. Consequently, each model was addressed using two distinct
methodologies, as outlined below.

####  3.2.1 Soft approach

The first approach involves cut generation as outlined in Algorithm 1. In each
iteration, a subproblem from the Branch-and-Bound tree is solved. In line 1
the algorithm checks if the solution of the subproblem is an integer solution.
Based on this, the DFS algorithm is employed to detect any subtours within the
solution, as shown in line 1. If a subtour exists, and its length is less than
or equal to the value of the variable longest_induced_cycle, a cut is appended
for that cycle. If not, the value of the variable is updated to reflect the
length of the cycle, and there is no need to introduce a cut because the cycle
could potentially be the optimal solution. These details are clarified in
lines 1 through 1. The cut generation terminates when there are no further
subtours present in the solution, indicating the completion of the procedure.

1 model Initialization(__) // setting up the $ILP_{cut}$ or $cec$ model
components

2 longest_induced_cycle=0

3 Function  _Cut_Generation1(__)_

4 if  _model.status $==$feasible_integer_ then // model has integer solution

5 C=DFS(feasible_integer) // find subtour in the solution

6 if  _length(C) $\leq$ longest_induced_cycle_ then

7 model.addConstr(18,24) // add cut (18) or (24) to the model

8

9 else

10 longest_induced_cycle=length(C) // update variable value

11

12

13 model.optimize(Cut_Generation1(__)) // solve the model using cut generation

print(longest_induced_cycle)

Algorithm 1 Cut_Generation1

####  3.2.2 Tough approach

The second cut generation-based approach is detailed in Algorithm 2. In each
iteration, a subproblem is solved, and if an integer solution is obtained, the
algorithm verifies the presence of any subtours using the DFS algorithm, as
described in lines 2 through 2. If any cycles are detected, a cut is
integrated into the model (line 2), and the length of the cycle is updated if
it exceeds the value of the variable longest_induced_cycle (line 2). Although
we may cut the optimal induced cycle, its length (and possibly the cycle
itself) is recorded. It is important to note that in order to further improve
the procedure, a constraint is added to the model in line 2. This constraint
ensures that the objective value must be greater than the length of the
largest induced cycle discovered so far. By using this cut generation, the
branch-and-cut indicates the infeasibility of the problem, yet the longest
induced cycle length recorded in the variable longest_induced_cycle.

14 model Initialization(__) // setting up the $ILP_{cut}$ or $cec$ model
components

15 longest_induced_cycle=0

16 Function  _Cut_Generation2(__)_

17 if  _model.status $==$feasible_integer_ then // model has integer solution

18 C=DFS(feasible_integer) // find subtour in the solution

19 model.addConstr(18,24) // add cut (18) or (24) to the model

20 if  _length(C) $>$ longest_induced_cycle_ then

21 longest_induced_cycle=length(C)

22 model.addConstr(model.ObjVal $\geq$ longest_induced_cycle+1)

23

24

25 model.optimize(Cut_Generation2(__)) // solve the model using cut generation

print(longest_induced_cycle)

Algorithm 2 Cut_Generation2

###  3.3 Longest Isometric Cycle

Lokshtanov’s algorithm, as described in Lokshtanov , aims to identify the
longest isometric cycle within a graph. In accordance with the definition of
an isometric cycle, as discussed in Section 1, if a given graph $G$ contains
an isometric cycle with a length of $\ell$, then there must also exist an
induced cycle within the graph with a length of $m$ where $m\geq\ell$.
Consequently, the longest isometric cycle serves as a benchmark for the
longest induced cycle. The algorithm’s objective is to verify the existence of
an isometric cycle with a length of $k$ in a given graph $G=(V,E)$. If such a
cycle exists, the graph $G$ can be employed to construct a new graph $G_{k}$
with vertices as vertex-pairs of $G$. Namely, $V(G_{k})=\\{(u,v)\in
V:d(u,v)=\lfloor k/2\rfloor\\}$, where $d(u,v)$ is the length of the shortest
path between $u$ and $v$, and its edge set given by
$E(G_{k})=\\{((u,v),(w,x)):(u,w)\in E(G)\wedge(v,x)\in E(G)\\}$.

The method is outlined in Algorithm 3. For a given value of $k$, the algorithm
computes the graph $G_{k}$ and examines whether there exists a pair of
vertices $(u,v)$ and $(v,x)$ within $V(G_{k})$ such that $(v,x)$ belongs to
the set $M_{k}(u,v):=\\{(u,x):(u,x)\in V(G_{k})\wedge(v,x)\in E(G)\\}$ and
$d_{G_{k}}[(u,v),(v,x)]=\lfloor{k/2}\rfloor$. If such a pair is found, it
indicates the presence of an isometric cycle with a length of $k$.

26 LISC=0

27 for  _$\forall l\in V,i\in V,j\in V$_ do // distance calculation

28 $d(i,j)=\min\\{d(i,j),d(i,l)+d(j,l)\\}$ // by Floyd algorithm

29

30if  _$G$ is a tree_ then // no cycles in tree graph

31 return LISC

32for  _$k=3\to n$_ do

33 $V_{k}=\emptyset$ // vertices of $G_{k}$

34 for  _$u\wedge v\in V$_ do

35 if  _$d(u,v)=\lfloor k/2\rfloor$_ then

36 $V_{k}=V_{k}\cup\\{(u,v)\\}$

37

38 $E_{k}=\emptyset$ // edges of $G_{k}$

39 for  _$(u,v)\wedge(w,x)\in V_{k}$_ do

40 if  _$(u,w)\in E\wedge(v,x)\in E$_ then

41 $E_{k}=E_{k}\cup\\{((u,v),(w,x))\\}$

42

43 $G_{k}=(V_{k},E_{k})$

44 for  _$(u,v,x)\in V$_ do

45 if  _$(u,v)\in V_{k}\wedge(v,x)\in M_{k}(v,u)\wedge
d_{G_{k}}[(u,v),(v,x)]=\lfloor k/2\rfloor$_ then

46 LISC$:=k$

47

48

print(LISC)

Algorithm 3 Longest Isometric Cycle

##  4 Numerical experiments

To demonstrate and evaluate the effectiveness of the proposed methods, we
present numerical results for three models: the _LIC_ model, the _ILP_ cut
model, and the _cec_ model. Furthermore, we conducted a comparison between our
best results and results from pereira  on randomly generated graphs to
highlight the efficiency of our approach in comparison to existing methods.

###  4.1 Computational environment and datasets

The algorithms detailed in Section 3 were implemented in Julia 1.7.0,
utilizing the JuMP package version 0.22.1. We employed Gurobi 9.5.0 as the
solver for all experiments. Each run was constrained to a one-hour time limit
and a single thread. For the longest isometric cycle algorithm, we implemented
it using Python 3.8 with a 24-hour time limit. These computations were
performed on a computer with an Intel Core i7-4600U CPU, 8GB of RAM, and
running the Windows 10 operating system.

To verify the efficacy of our methods, we employed two sets of network
datasets. The first is the RWC set, comprising 19 real-world networks that
encompass communication and social networks within companies, networks of book
characters, as well as transportation, biological, and engineering networks,
as described in Matsypura . Additionally, we utilized the Movie Galaxy (MG)
set, consisting of 773 graphs that represent social networks among movie
characters, as detailed in kaminski . For further information about these
instances, the reader is referred to the following link:
http://tcs.uos.de/research/lip.

To perform a comparison with the results presented in pereira , we conducted
experiments on random graphs with varying values of $n$ ranging from 50 to
100, considering both 10% and 30% density, as in pereira . For every case, 10
graphs were generated. Every run was restricted to a maximum duration of one
hour, with no restrictions on the number of threads, and with an initial
solution set to 4, as described in pereira . Regarding the hardware
comparison, we utilized the information available in cpu  to collect the
details of the CPU utilized in all experiments, as outlined in Table 1. It is
evident that the computer used in pereira  is more powerful than ours. To
ensure a fair comparison, we normalized the execution times in all cases. The
ratio between the single-thread ratings gives a good approximation of the
relative speed. Therefore, we calculated this ratio in the last row of Table
1. The run time was then modified by multiplying it by the obtained ratio.

Table 1: CPU performance comparison between the CPU used in this paper and in pereira . Benchmarks |  Intel Core i7-4600U |  Intel Xeon W-3223
---|---|---
Clock Speed (GHz) | 2.1 | 3.5
Turbo Speed (GHz) | Up to 3.3 | Up to 4.0 GHz
Number of Physical Cores | 2 (Threads: 4) | 8 (Threads: 16)
Single Thread Rating | 1641 | 2480
Ratio | 0.66 | 1

###  4.2 Computational results

Table LABEL:table:exper1 presents the computational experiments conducted on
the RWC instances. The second column displays the optimal solutions for each
instance (opt). In the third column, we find the length of the longest
isometric cycle (_LISC_), if possible. The fourth and fifth columns
respectively indicate the number of vertices ($N$) and edges ($M$) of the
corresponding graph. Columns six through eleven show the time in seconds
required to identify the optimal solution using the various methods employed
in this study. Specifically, _ILP_ cut2 and _cec_ 2 refer to the methods
outlined in Algorithm 2. For all these methods, we initiated the search using
the _LISC_ value, incorporating the constraint ObjVal $\geq$ LISC. These
methods are indicated in every second row corresponding to each graph.
Instances that resulted in timeouts are denoted by the symbol 🕐.

Table 2: Running times on RWC instances, time is given in seconds.

graph | opt | LISC | $N$ | $M$ | _LIC_ |  _LIC_ 2 | _ILP cut_ | _ILP ${}_{cut}2$_ | _cec_ |  _cec_ 2
---|---|---|---|---|---|---|---|---|---|---
high-tech | 10 | 5 | 33 | 91 | 1.22 | 0.63 | 0.95 | 0.33 | 0.38 | 0.14
0.99 | 0.42 | 1.15 | 1.57 | 1.02 | 0.77
karate | 6 | 5 | 34 | 78 | 0.63 | 0.58 | 0.21 | 0.24 | 0.20 | 0.19
0.66 | 0.53 | 0.23 | 0.29 | 0.24 | 0.17
mexican | 13 | 7 | 35 | 117 | 0.92 | 0.82 | 0.66 | 0.88 | 0.24 | 0.20
0.83 | 0.78 | 0.69 | 0.74 | 0.20 | 0.20
sawmill | 6 | 5 | 36 | 62 | 0.54 | 0.43 | 0.18 | 0.37 | 0.15 | 0.10
0.33 | 0.30 | 0.36 | 0.16 | 0.13 | 0.11
tailorS1 | 12 | 7 | 39 | 158 | 2.93 | 1.11 | 1.37 | 1.45 | 0.34 | 0.33
1.38 | 0.89 | 1.76 | 1.76 | 0.37 | 0.44
chesapeake | 15 | 5 | 39 | 170 | 1.01 | 0.69 | 0.56 | 0.81 | 0.24 | 0.22
1.05 | 0.72 | 0.97 | 0.87 | 0.28 | 0.31
tailorS2 | 12 | 5 | 39 | 223 | 3.11 | 2.05 | 3.49 | 4.46 | 0.74 | 0.65
3.25 | 3.09 | 3.74 | 4.62 | 0.83 | 0.75
attiro | 28 | 9 | 59 | 128 | 0.93 | 1.24 | 0.55 | 0.53 | 0.18 | 0.24
0.67 | 0.71 | 0.52 | 0.68 | 0.28 | 0.31
krebs | 8 | 7 | 62 | 153 | 10.91 | 7.23 | 1.19 | 0.94 | 0.94 | 0.48
10.39 | 5.56 | 0.86 | 1.02 | 0.57 | 0.38
dolphins | 20 | 7 | 62 | 159 | 14.75 | 23.70 | 1.81 | 2.35 | 1.70 | 1.02
10.66 | 13.83 | 2.80 | 2.98 | 0.74 | 1.50
prison | 28 | 9 | 67 | 142 | 5.90 | 10.22 | 0.83 | 1.56 | 0.62 | 0.61
6.93 | 10.23 | 4.81 | 1.03 | 0.66 | 0.48
huck | 5 | 5 | 69 | 297 | 519.95 | 299.12 | 19.53 | 17.79 | 4.31 | 4.51
447.72 | 493.74 | 18.22 | 19.71 | 3.34 | 3.31
sanjuansur | 35 | 11 | 75 | 144 | 6.16 | 5.85 | 0.68 | 0.71 | 0.37 | 0.49
7.70 | 3.61 | 0.82 | 1.36 | 0.44 | 0.38
jean | 7 | 5 | 77 | 254 | 276.98 | 147.77 | 15.93 | 14.57 | 2.45 | 2.41
150 | 147.85 | 13.97 | 14.80 | 2.32 | 2.41
david | 15 | 8 | 87 | 406 | 544.99 | 308.06 | 46.23 | 54.23 | 5.22 | 4.36
219.14 | 323.96 | 45.24 | 38.33 | 3.31 | 3.47
ieeebus | 32 | 13 | 118 | 179 | 2.52 | 5.14 | 0.76 | 0.94 | 0.43 | 0.62
7.82 | 5.82 | 0.79 | 1.35 | 0.33 | 0.3
sfi | 3 | 3 | 118 | 200 | 6.98 | 6.51 | 0.74 | 0.90 | 0.3 | 0.31
6.40 | 2.80 | 0.84 | 1.32 | 0.34 | 0.31
anna | 15 | 🕐 | 138 | 493 | 90.75 | 52.11 | 10.60 | 23.65 | 1.37 | 1.71
- | - | - | - | - | -
494bus | 116 | 🕐 | 494 | 586 | 108.48 | 126.77 | 27.13 | 33.09 | 2.73 | 2.10
- | - | - | - | - | -
average |  |  |  |  | 84.19 | 52.63 | 7.02 | 8.41 | 1.21 | 1.09
51.52 | 59.70 | 5.75 | 5.45 | 0.9 | 0.92

The various methods exhibit diverse performance characteristics in terms of
execution time and the number of instances solved optimally. Key observations
from Table LABEL:table:exper1 are as follows:

  * •

_cec_ 2 outperforms _cec_ in 13 cases, _ILP_ cut, _ILP_ cut2, _LIC_ and _LIC_
2 in all the cases.

  * •

_ILP_ cut2 was faster than _LIC_ 2 for 15 cases and _LIC_ for all instances.

  * •

_LIC_ 2 outperforms _LIC_ in 14 cases.

  * •

For some instances in _ILP_ cut and _cec_ , the graphs and results are
indicated by boldface and underlined in Table LABEL:table:exper1. This is to
emphasize that these graphs contain multiple longest induced cycles of the
same length, and the procedures described in Algorithm 1 cut the cycle if its
length is less than or equal to the longest induced cycle found so far. Thus,
for these graphs, all the longest cycles are found by the method.

  * •

Using _LISC_ as an initial solution does not contribute significantly to
improving the execution time in the majority of cases.

  * •

The results emphasize the correlation between graph density and execution
time. Graph density is defined as the ratio of the edges present in a graph to
the maximum number of edges it can hold. This relationship is particularly
evident for dense graphs like huck, jean, and david, especially in the case of
_LIC_ and _LIC_ 2 models. However, it is not the case for _cec_ and _cec_ 2
models as their running times show less sensitivity to the graph’s density.

Table 3: Running times on MG instances, time is given in seconds. nr. of edges | nr. of instances | _LIC_ |  _LIC_ 2 | _ILP cut_ | _ILP ${}_{cut}2$_ | _cec_ |  _cec_ 2
---|---|---|---|---|---|---|---
1–49 | 107 | 0.14 | 0.14 | 0.12 | 0.18 | 0.09 | 0.08
50–74 | 135 | 0.37 | 0.29 | 0.2 | 0.3 | 0.17 | 0.12
75–99 | 151 | 0.7 | 0.58 | 0.32 | 0.39 | 0.22 | 0.17
100–124 | 121 | 1.74 | 1.32 | 0.51 | 0.65 | 0.29 | 0.24
125–149 | 90 | 4.5 | 3.67 | 0.82 | 0.99 | 0.37 | 0.34
150–199 | 89 | 10.45 | 7.48 | 1.49 | 1.7 | 0.56 | 0.49
200–629 | 80 | 169.38 | 110.49 | 13.28 | 16.39 | 2.41 | 1.9
average |  | 157.23 | 126.35 | 44.73 | 57.28 | 26.84 | 22.01

The results for the MG instances, organized into groups based on the number of
edges, are presented in Table 3. Unlike _LIC_ and _LIC_ 2, where the running
times increase proportionally with the instance size, the results indicate
that _cec_ and _cec_ 2 are more reliable, with running times showing less
sensitivity to the graph’s size.

Table 4: Running times on random instances for _cec_ 2, _BC_ 1, _BC_ 2, and
_BC_ 3, time is given in seconds. Values in brackets show the original
execution time of _cec_ 2. Randomly generated graphs: 10% density
---
$n$ |  _cec_ 2 |  _BC_ 1 |  _BC_ 2 |  _BC_ 3
50 | 0.32 (0.49) | 0.33 | 0.3 | 0.39
60 | 0.79 (1.2) | 1.19 | 1.2 | 1.34
70 | 4.17 (6.32) | 5.57 | 4.93 | 5.58
80 | 20.5 (31.1) | 37.15 | 26.9 | 27.34
90 | 93.93 (142.32) | 160.1 | 155.82 | 168.02
100 | 518.75 (785.99) | 1321.41 | 1129.47 | 1094.8
average | 106.41 | 254.29 | 219.77 | 216.25
Randomly generated graphs: 30% density
$n$ |  _cec_ 2 |  _BC_ 1 |  _BC_ 2 |  _BC_ 3
50 | 4.15 (6.28) | 8.21 | 9.6 | 8.78
60 | 26.14 (39.6) | 39.82 | 46.18 | 51.9
70 | 90.11 (136.52) | 234.45 | 206.36 | 283.28
80 | 203.81 (308.8) | 935.78 | 676.52 | 1139.55
90 | 544.88 (825.58) | 2072.16 | 1874.91 | 3011.17
100 | 1810.49 (2743.17) |  |  |
average | 446.6 | 658.08 | 562.71 | 898.94

The results for the random graphs are presented in Table 4, where we compare
_cec_ 2 against the top three algorithms introduced in pereira . The runtime
represents the average duration on the ten graphs in each case. Notably, _cec_
2 outperforms these algorithms in all cases, even before normalizing the
execution times with the ratio listed in Table 1. Moreover, _cec_ 2
successfully solved the instance with 100 vertices and 30% density, a scenario
where none of the algorithms in pereira  succeeded.

##  5 Conclusion

Considering that the longest induced cycle problem is NP-hard, it is essential
to find an efficient approach that can yield optimal solutions within a
reasonable time. In this regard, we introduced three integer linear programs,
some of which are extensions of models originally formulated for solving the
longest induced path problem. These newly proposed programs showed differing
execution times and success rates in terms of achieving optimal solutions,
outperforming the models presented in the literature. We have found that the
$cec2$ formulation with tough cut generation yields the most efficient method.

## Acknowledgements

The research leading to these results has received funding from the national
project TKP2021-NVA-09. Project no. TKP2021-NVA-09 has been implemented with
the support provided by the Ministry of Innovation and Technology of Hungary
from the National Research, Development and Innovation Fund, financed under
the TKP2021-NVA funding scheme. The work was also supported by the grant
SNN-135643 of the National Research, Development, and Innovation Office,
Hungary.

## References

  * (1) Pereira, Dilson Lucas and Lucena, Abilio and Salles da Cunha, Alexandre and Simonetti, Luidi: Exact solution algorithms for the chordless cycle problem.  INFORMS Journal on Computing. 34(4),1970–1986 (2022)
  * (2) Marzo, Ruslán G and Melo, Rafael A and Ribeiro, Celso C and Santos, Marcio C: New formulations and branch-and-cut procedures for the longest induced path problem.  Computers & Operations Research. 139, 105627 (2022)
  * (3) Bökler F., Chimani M., Wagner M.H., Wiedera T: An experimental study of ILP formulations for the longest induced path problem.  International Symposium on Combinatorial Optimization, 89–101 (2020)
  * (4) Gurobi Optimization Inc. Gurobi Optimizer Reference Manual (2020)
  * (5) Matsypura, Dmytro and Veremyev, Alexander and Prokopyev, Oleg A and Pasiliao, Eduardo L: On exact solution approaches for the longest induced path problem.  European Journal of Operational Research 278(2),546–562 (2019)
  * (6) Kaminski, Jermain and Schober, Michael and Albaladejo, Raymond and Zastupailo, Oleksandr and Hidalgo, César: Moviegalaxies-social networks in movies.  Harvard Dataverse, (2018)
  * (7) Kumar, Parveen and Gupta, Nitin: A heuristic algorithm for longest simple cycle problem.  Proceedings of the International Conference on Wireless Networks (ICWN), pp. 202–208 (2014)
  * (8) Broersma, Hajo and Fomin, Fedor V and van’t Hof, Pim and Paulusma, Daniël: Exact algorithms for finding longest cycles in claw-free graphs.  Algorithmica 65(1), 129–145 (2013)
  * (9) Walsh, Toby: Symmetry breaking constraints: Recent results.  Proceedings of the AAAI Conference on Artificial Intelligence 26(1), 2192–2198 (2012)
  * (10) Lokshtanov, Daniel: Finding the longest isometric cycle in a graph.  Discrete Applied Mathematics.157(12),2670–2674 (2009)
  * (11) Chen, Yijia and Flum, Jorg: On parameterized path and chordless path problems.  Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pp. 250–263 (2007)
  * (12) Fuchs, Elena D: Longest induced cycles in circulant graphs.  The Electronic Journal of Combinatorics, Article Number R52 (2005)
  * (13) West, Douglas Brent and others: Introduction to Graph Theory.  Prentice Hall (2001)
  * (14) Borndörfer, Ralf: Aspects of set packing, partitioning, and covering.  PhD thesis, TU Berlin, Berlin. (1998)
  * (15) Nemhauser, George L and Sigismondi, Gabriele: A strong cutting plane/branch-and-bound algorithm for node packing.  Journal of the Operational Research Society. 43(5), 443–457 (1992)
  * (16) Garey, Michael R. and Johnson, David S.: Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co. (1990)
  * (17) Wojciechowski, Jerzy Marian: Long induced cycles in the hypercube and colourings of graphs.  University of Cambridge (1990)
  * (18) Alon, Noga: The longest cycle of a graph with a large minimal degree.  Journal of Graph Theory. 10(1), 123–127 (1986)
  * (19) Akiyama, Takanori and Nishizeki, Takao and Saito, Nobuji: NP-completeness of the Hamiltonian cycle problem for bipartite graphs.  Journal of Information Processing. 3(2), 73–76 (1980)
  * (20) PassMark Software - CPU Benchmarks: https://www.cpubenchmark.net/compare (2023)


* [127] S. Haben, J. Ward, D. V. Greetham, C. Singleton, and P. Grindrod, “A new error measure for forecasts of household-level, high resolution electrical energy consumption,” _International Journal of Forecasting_ , vol. 30, no. 2, pp. 246–256, 2014.
  * [128] T. Hong, J. Wilson, and J. Xie, “Long term probabilistic load forecasting and normalization with hourly information,” _IEEE Trans. Smart Grid_ , vol. 5, no. 1, pp. 456–462, 2014.
  * [129] PJM, “PJM Load Forecast Report January 2015 Prepared by PJM Resource Adequacy Planning Department,” https://www.pjm.com/-/media/library/reports-notices/load-forecast/2015-load-forecast-report.ashx?la=en, Tech. Rep., 2015.
  * [130] R. J. Hyndman and S. Fan, “Density forecasting for long-term peak electricity demand,” _IEEE Transactions on Power Systems_ , vol. 25, no. 2, pp. 1142–1153, 2010.
  * [131] D. Gan, Y. Wang, S. Yang, and C. Kang, “Embedding based quantile regression neural network for probabilistic load forecasting,” _Journal of Modern Power Systems and Clean Energy_ , vol. 6, no. 2, pp. 244–254, 2018.
  * [132] J. Black, A. Hofmann, T. Hong, J. Roberts, and P. Wang, “Weather data for energy analytics: from modeling outages and reliability indices to simulating distributed photovoltaic fleets,” _IEEE Power and Energy Magazine_ , vol. 16, no. 3, pp. –, May 2018.
  * [133] J. Xie, T. Hong, T. Laing, and C. Kang, “On normality assumption in residual simulation for probabilistic load forecasting,” _IEEE Trans. Smart Grid_ , vol. 8, no. 3, pp. 1046–1053, May 2017.
  * [134] Y. Wang, N. Zhang, Y. Tan, T. Hong, D. Kirschen, and C. Kang, “Combining probabilistic load forecasts,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2018.
  * [135] J. Xie and T. Hong, “Variable selection methods for probabilistic load forecasting: Empirical evidence from seven states of the united states,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [136] S. Arora and J. W. Taylor, “Forecasting electricity smart meter data using conditional kernel density estimation,” _Omega_ , vol. 59, pp. 47–59, 2016\.
  * [137] P. Zhang, X. Wu, X. Wang, and S. Bi, “Short-term load forecasting based on big data technologies,” _CSEE Journal of Power and Energy Systems_ , vol. 1, no. 3, pp. 59–67, 2015.
  * [138] S. Humeau, T. K. Wijaya, M. Vasirani, and K. Aberer, “Electricity load forecasting for residential customers: Exploiting aggregation and correlation between households,” in _Sustainable Internet and ICT for Sustainability (SustainIT)_ , 2013, pp. 1–6.
  * [139] S. Zhong and K.-S. Tam, “Hierarchical classification of load profiles based on their characteristic attributes in frequency domain,” _IEEE Trans. Power Systems_ , vol. 30, no. 5, pp. 2434–2441, 2015.
  * [140] D. Vercamer, B. Steurtewagen, D. V. den Poel, and F. Vermeulen, “Predicting consumer load profiles using commercial and open data,” _IEEE Trans. Power Systems_ , vol. 31, no. 5, pp. 3693–3701, Sept 2016.
  * [141] A. Kavousian, R. Rajagopal, and M. Fischer, “Determinants of residential electricity consumption: Using smart meter data to examine the effect of climate, building characteristics, appliance stock, and occupants’ behavior,” _Energy_ , vol. 55, pp. 184–194, 2013.
  * [142] F. McLoughlin, A. Duffy, and M. Conlon, “Characterising domestic electricity consumption patterns by dwelling and occupant socio-economic variables: An irish case study,” _Energy and Buildings_ , vol. 48, pp. 240–248, 2012.
  * [143] Y. Han, X. Sha, E. Grover-Silva, and P. Michiardi, “On the impact of socio-economic factors on power load forecasting,” in _IEEE International Conference on Big Data_ , 2014, pp. 742–747.
  * [144] R. Granell, C. J. Axon, and D. C. Wallom, “Clustering disaggregated load profiles using a dirichlet process mixture model,” _Energy Conversion and Management_ , vol. 92, pp. 507–516, 2015.
  * [145] K. Hopf, M. Sodenkamp, I. Kozlovkiy, and T. Staake, “Feature extraction and filtering for household classification based on smart electricity meter data,” _Computer Science-Research and Development_ , vol. 31, no. 3, pp. 141–148, 2016.
  * [146] M. Sodenkamp, I. Kozlovskiy, and T. Staake, “Supervised classification with interdependent variables to support targeted energy efficiency measures in the residential sector,” _Decision Analytics_ , vol. 3, no. 1, p. 1, 2016\.
  * [147] A. Albert and R. Rajagopal, “Smart meter driven segmentation: What your consumption says about you,” _IEEE Trans. power systems_ , vol. 28, no. 4, pp. 4019–4030, 2013.
  * [148] J. Kwac, J. Flora, and R. Rajagopal, “Household energy consumption segmentation using hourly data,” _IEEE Trans. Smart Grid_ , vol. 5, no. 1, pp. 420–430, 2014.
  * [149] Y. Bai, H. Zhong, and Q. Xia, “Real-time demand response potential evaluation: A smart meter driven method,” in _IEEE Power and Energy Society General Meeting_ , 2016, pp. 1–5.
  * [150] A. Jindal, N. Kumar, and M. Singh, “A data analytical approach using support vector machine for demand response management in smart grid,” in _IEEE Power and Energy Society General Meeting_ , 2016, pp. 1–5.
  * [151] M. E. Dyson, S. D. Borgeson, M. D. Tabone, and D. S. Callaway, “Using smart meter data to estimate demand response potential, with application to solar energy integration,” _Energy Policy_ , vol. 73, pp. 607–619, 2014.
  * [152] A. Albert and R. Rajagopal, “Thermal profiling of residential energy use,” _IEEE Trans. Power Systems_ , vol. 30, no. 2, pp. 602–611, 2015.
  * [153] ——, “Finding the right consumers for thermal demand-response: an experimental evaluation,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [154] N. Mahmoudi-Kohan, M. P. Moghaddam, M. Sheikh-El-Eslami, and E. Shayesteh, “A three-stage strategy for optimal price offering by a retailer based on clustering techniques,” _International Journal of Electrical Power & Energy Systems_, vol. 32, no. 10, pp. 1135–1142, 2010.
  * [155] S. Joseph and J. Erakkath Abdu, “Real-time retail price determination in smart grid from real-time load profiles,” _International Transactions on Electrical Energy Systems_ , 2018.
  * [156] N. Mahmoudi-Kohan, M. P. Moghaddam, and M. Sheikh-El-Eslami, “An annual framework for clustering-based pricing for an electricity retailer,” _Electric Power Systems Research_ , vol. 80, no. 9, pp. 1042–1048, 2010.
  * [157] M. Crow _et al._ , “Clustering-based methodology for optimal residential time of use design structure,” in _North American Power Symposium (NAPS)_ , 2014, pp. 1–6.
  * [158] R. Li, Z. Wang, C. Gu, F. Li, and H. Wu, “A novel time-of-use tariff design based on gaussian mixture model,” _Applied Energy_ , vol. 162, pp. 1530–1536, 2016.
  * [159] T. K. Wijaya, M. Vasirani, and K. Aberer, “When bias matters: An economic assessment of demand response baselines for residential customers,” _IEEE Trans. Smart Grid_ , vol. 5, no. 4, pp. 1755–1763, 2014.
  * [160] Y. Weng and R. Rajagopal, “Probabilistic baseline estimation via gaussian process,” in _IEEE Power & Energy Society General Meeting_, 2015, pp. 1–5.
  * [161] Y. Zhang, W. Chen, R. Xu, and J. Black, “A cluster-based method for calculating baselines for residential loads,” _IEEE Trans. Smart Grid_ , vol. 7, no. 5, pp. 2368–2377, 2016.
  * [162] L. Hatton, P. Charpentier, and E. Matzner-Løber, “Statistical estimation of the residential baseline,” _IEEE Trans. Power Systems_ , vol. 31, no. 3, pp. 1752–1759, 2016.
  * [163] W. Luan, J. Peng, M. Maras, J. Lo, and B. Harapnuk, “Smart meter data analytics for distribution network connectivity verification,” _IEEE Trans. Smart Grid_ , vol. 6, no. 4, pp. 1964–1971, 2015.
  * [164] J. Peppanen, S. Grijalva, M. J. Reno, and R. J. Broderick, “Distribution system low-voltage circuit topology estimation using smart metering data,” in _IEEE/PES Transmission and Distribution Conference and Exposition_ , 2016, pp. 1–5.
  * [165] Y. Weng, Y. Liao, and R. Rajagopal, “Distributed energy resources topology identification via graphical modeling,” _IEEE Trans. Power Systems_ , vol. 32, no. 4, pp. 2682–2694, July 2017.
  * [166] Y. Liao, Y. Weng, and R. Rajagopal, “Urban distribution grid topology reconstruction via lasso,” in _IEEE Power and Energy Society General Meeting (PESGM)_ , 2016, pp. 1–5.
  * [167] S. J. Pappu, N. Bhatt, R. Pasumarthy, and A. Rajeswaran, “Identifying Topology of Low Voltage (LV) Distribution Networks Based on Smart Meter Data,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [168] M. Xu, R. Li, and F. Li, “Phase identification with incomplete data,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2016.
  * [169] V. C. Gungor, D. Sahin, T. Kocak, S. Ergut, C. Buccella, C. Cecati, and G. P. Hancke, “A survey on smart grid potential applications and communication requirements,” _IEEE Trans. Industrial Informatics_ , vol. 9, no. 1, pp. 28–42, 2013.
  * [170] H. Tram, “Technical and operation considerations in using smart metering for outage management,” in _IEEE/PES Transmission and Distribution Conference and Exposition_ , 2008, pp. 1–3.
  * [171] Y. He, N. Jenkins, and J. Wu, “Smart metering for outage management of electric power distribution networks,” _Energy Procedia_ , vol. 103, pp. 159–164, 2016.
  * [172] K. Kuroda, R. Yokoyama, D. Kobayashi, and T. Ichimura, “An approach to outage location prediction utilizing smart metering data,” in _8th Asia Modelling Symposium (AMS)_ , 2014, pp. 61–66.
  * [173] Y. Jiang, C.-C. Liu, M. Diedesch, E. Lee, and A. K. Srivastava, “Outage management of distribution systems incorporating information from smart meters,” _IEEE Trans. Power Systems_ , vol. 31, no. 5, pp. 4144–4154, 2016\.
  * [174] R. Moghaddass and J. Wang, “A hierarchical framework for smart grid anomaly detection using large-scale smart meter data,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [175] J. Zheng, D. W. Gao, and L. Lin, “Smart meters in smart grid: An overview,” in _IEEE Green Technologies Conference_ , 2013, pp. 57–64.
  * [176] T. Andrysiak, Ł. Saganowski, and P. Kiedrowski, “Anomaly detection in smart metering infrastructure with the use of time series analysis,” _Journal of Sensors_ , vol. 2017, 2017.
  * [177] M. P. Tcheou, L. Lovisolo, M. V. Ribeiro, E. A. da Silva, M. A. Rodrigues, J. M. Romano, and P. S. Diniz, “The compression of electric signal waveforms for smart grids: State of the art and future trends,” _IEEE Trans. Smart Grid_ , vol. 5, no. 1, pp. 291–302, 2014.
  * [178] A. Unterweger and D. Engel, “Resumable load data compression in smart grids,” _IEEE Trans. Smart Grid_ , vol. 6, no. 2, pp. 919–929, 2015.
  * [179] A. Unterweger, D. Engel, and M. Ringwelski, “The effect of data granularity on load data compression,” in _DA-CH Conference on Energy Informatics_ , 2015, pp. 69–80.
  * [180] A. Notaristefano, G. Chicco, and F. Piglione, “Data size reduction with symbolic aggregate approximation for electrical load pattern grouping,” _IET Generation, Transmission & Distribution_, vol. 7, no. 2, pp. 108–117, 2013.
  * [181] C. Rottondi, G. Verticale, and C. Krauss, “Distributed privacy-preserving aggregation of metering data in smart grids,” _IEEE Journal on Selected Areas in Communications_ , vol. 31, no. 7, pp. 1342–1354, 2013.
  * [182] L. Sankar, S. R. Rajagopalan, and S. Mohajer, “Smart meter privacy: A theoretical framework,” _IEEE Trans. Smart Grid_ , vol. 4, no. 2, pp. 837–846, 2013.
  * [183] M. Savi, C. Rottondi, and G. Verticale, “Evaluation of the precision-privacy tradeoff of data perturbation for smart metering,” _IEEE Trans. Smart Grid_ , vol. 6, no. 5, pp. 2409–2416, 2015.
  * [184] G. Eibl and D. Engel, “Influence of data granularity on smart meter privacy,” _IEEE Trans. Smart Grid_ , vol. 6, no. 2, pp. 930–939, 2015.
  * [185] C. E. Kement, H. Gultekin, B. Tavli, T. Girici, and S. Uludag, “Comparative analysis of load shaping based privacy preservation strategies in smart grid,” _IEEE Trans. Industrial Informatics_ , vol. PP, no. 99, pp. 1–1, 2017\.
  * [186] T. Hong, C. Chen, J. Huang, N. Lu, L. Xie, and H. Zareipour, “Guest editorial big data analytics for grid modernization,” _IEEE Trans. Smart Grid_ , vol. 7, no. 5, pp. 2395–2396, 2016.
  * [187] T. Hong, “Big data analytics: making smart grid smarter,” _IEEE Power and Energy Magazine_ , vol. 16, no. 3, pp. –, May 2018.
  * [188] Z. Lv, H. Song, P. Basanta-Val, A. Steed, and M. Jo, “Next-generation big data analytics: State of the art, challenges, and future research topics,” _IEEE Trans. Industrial Informatics_ , vol. 13, no. 4, pp. 1891–1899, Aug 2017.
  * [189] R. J. Hyndman, X. Liu, and P. Pinson, “Visualizing big energy data: solutions for this crucial component of data analysis,” _IEEE Power and Energy Magazine_ , vol. 16, no. 3, pp. –, May 2018.
  * [190] J. Baek, Q. H. Vu, J. K. Liu, X. Huang, and Y. Xiang, “A secure cloud computing based framework for big data information management of smart grid,” _IEEE Trans. cloud computing_ , vol. 3, no. 2, pp. 233–244, 2015\.
  * [191] S. Bera, S. Misra, and J. J. Rodrigues, “Cloud computing applications for smart grid: A survey,” _IEEE Trans. Parallel and Distributed Systems_ , vol. 26, no. 5, pp. 1477–1494, 2015.
  * [192] S. Mittal, “A survey of techniques for architecting and managing gpu register file,” _IEEE Trans. Parallel and Distributed Systems_ , vol. 28, no. 1, pp. 16–28, 2017.
  * [193] A. Rodriguez and A. Laio, “Clustering by fast search and find of density peaks,” _Science_ , vol. 344, no. 6191, pp. 1492–1496, 2014.
  * [194] F. A. Gers, J. Schmidhuber, and F. Cummins, “Learning to forget: Continual prediction with lstm,” _Neural computation_ , vol. 12, no. 10, pp. 2451–2471, 2000.
  * [195] D. L. Marino, K. Amarasinghe, and M. Manic, “Building energy load forecasting using deep neural networks,” in _Industrial Electronics Society, IECON 2016-42nd Annual Conference of the IEEE_. IEEE, 2016, pp. 7046–7051.
  * [196] S. J. Pan and Q. Yang, “A survey on transfer learning,” _IEEE Trans. knowledge and data engineering_ , vol. 22, no. 10, pp. 1345–1359, 2010.
  * [197] Y. Bengio, “Deep learning of representations for unsupervised and transfer learning,” in _Proceedings of ICML Workshop on Unsupervised and Transfer Learning_ , 2012, pp. 17–36.
  * [198] T. Diethe and M. Girolami, “Online learning with (multiple) kernels: A review,” _Neural computation_ , vol. 25, no. 3, pp. 567–625, 2013.
  * [199] Y. Xie, W. Zhang, C. Li, S. Lin, Y. Qu, and Y. Zhang, “Discriminative object tracking via sparse representation and online dictionary learning,” _IEEE Trans. cybernetics_ , vol. 44, no. 4, pp. 539–553, 2014.
  * [200] Q. Zhang, C. Zhu, L. T. Yang, Z. Chen, L. Zhao, and P. Li, “An Incremental CFS Algorithm for Clustering Large Data in Industrial Internet of Things,” _IEEE Trans. Industrial Informatics_ , vol. 13, no. 3, pp. 1193–1201, 2017\.
  * [201] F. A. Rahimi and A. Ipakchi, “Transactive energy techniques: closing the gap between wholesale and retail markets,” _The Electricity Journal_ , vol. 25, no. 8, pp. 29–35, 2012.
  * [202] K. Kok and S. Widergren, “A society of devices: Integrating intelligent distributed resources with transactive energy,” _IEEE Power and Energy Magazine_ , vol. 14, no. 3, pp. 34–45, 2016.
  * [203] B. CELIK, R. Roche, D. Bouquain, and A. Miraoui, “Decentralized neighborhood energy management with coordinated smart home energy sharing,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [204] N. Liu, X. Yu, C. Wang, and J. Wang, “Energy Sharing Management for Microgrids With PV Prosumers: A Stackelberg Game Approach,” _IEEE Trans. Industrial Informatics_ , vol. 13, no. 3, pp. 1088–1098, June 2017.
  * [205] G. Ye, G. Li, D. Wu, X. Chen, and Y. Zhou, “Towards cost minimization with renewable energy sharing in cooperative residential communities,” _IEEE Access_ , vol. 5, pp. 11 688–11 699, 2017.
  * [206] H. Shaker, H. Zareipour, and D. Wood, “Estimating power generation of invisible solar sites using publicly available data,” _IEEE Trans. Smart Grid_ , vol. 7, no. 5, pp. 2456–2465, 2016.
  * [207] Y. Wang, N. Zhang, Q. Chen, D. S. Kirschen, P. Li, and Q. Xia, “Data-Driven Probabilistic Net Load Forecasting With High Penetration of Behind-the-Meter PV,” _IEEE Trans. Power Systems_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [208] H. Chitsaz, P. Zamani-Dehkordi, H. Zareipour, and P. Parikh, “Electricity price forecasting for operational scheduling of behind-the-meter storage systems,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [209] T. Krause, G. Andersson, K. Frohlich, and A. Vaccaro, “Multiple-energy carriers: modeling of production, delivery, and consumption,” _Proceedings of the IEEE_ , vol. 99, no. 1, pp. 15–27, 2011.
  * [210] Y. Wu, B. Chen, J. Weng, Z. Wei, X. Li, B. Qiu, and N. Liu, “False load attack to smart meters by synchronously switching power circuits,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2018.
  * [211] K. Xing, C. Hu, J. Yu, X. Cheng, and F. Zhang, “Mutual privacy preserving $k$ -means clustering in social participatory sensing,” _IEEE Trans. Industrial Informatics_ , vol. 13, no. 4, pp. 2066–2076, Aug 2017.
  * [212] L. Wei, A. D. Sarwate, J. Corander, A. Hero, and V. Tarokh, “Analysis of a privacy-preserving pca algorithm using random matrix theory,” in _IEEE Global Conference on Signal and Information Processing (GlobalSIP)_ , 2016, pp. 1335–1339.
  * [213] S. Salehkalaibar, F. Aminifar, and M. Shahidehpour, “Hypothesis testing for privacy of smart meters with side information,” _IEEE Trans. Smart Grid_ , vol. PP, no. 99, pp. 1–1, 2017.
  * [214] Y. Yan, Y. Qian, H. Sharif, and D. Tipper, “A survey on cyber security for smart grid communications,” _IEEE Communications Surveys Tutorials_ , vol. 14, no. 4, pp. 998–1010, Fourth 2012.
  * [215] Z. Zhang, M. Dong, L. Zhu, Z. Guan, R. Chen, R. Xu, and K. Ota, “Achieving privacy-friendly storage and secure statistics for smart meter data on outsourced clouds,” _IEEE Trans. Cloud Computing_ , vol. PP, no. 99, pp. 1–1, 2017.

|  Yi Wang (S’14) received the B.S. degree from the Department of Electrical
Engineering in Huazhong University of Science and Technology (HUST), Wuhan,
China, in 2014.
He is currently pursuing Ph.D. degree in Tsinghua University. He is also a
visiting student researcher at the University of Washington, Seattle, WA, USA.
His research interests include data analytics in smart grid and multiple
energy systems.
---|---
|  Qixin Chen (M’10-SM’15) received the Ph.D. degree from the Department of
Electrical Engineering, Tsinghua University, Beijing, China, in 2010.
He is currently an Associate Professor at Tsinghua University. His research
interests include electricity markets, power system economics and
optimization, low-carbon electricity, and power generation expansion planning.
---|---
|  Tao Hong received the B.Eng. degree in automation from Tsinghua University,
Beijing, China, in 2005, and the Ph.D. degree in operation research and
electrical engineering from North Carolina State University, Raleigh, NC, USA,
in 2010.
He is the Director of the Big Data Energy Analytics Laboratory (BigDEAL), and
an Associate Professor of System Engineering and Engineering Management at the
University of North Carolina at Charlotte, Charlotte, NC. Dr. Hong is the
Founding Chair of the IEEE Working Group on Energy Forecasting and the General
Chair of the Global Energy Forecasting Competition.
---|---
|  Chongqing Kang (M’01-SM’08-F’17) received the Ph.D. degree from the
Department of Electrical Engineering in Tsinghua University, Beijing, China,
in 1997.
He is currently a Professor in Tsinghua University. His research interests
include power system planning, power system operation, renewable energy, low
carbon electricity technology and load forecasting.
---|---