smullyan tableaux/.style=for tree=math content,where n children=1!1.before
computing xy=l=,!1.no edge,closed/.style=label=below:$\times$,,
11institutetext: The Czech Academy of Sciences, Institute of Computer Science,
Prague
11email<EMAIL_ADDRESS>22institutetext: Department of Cognitive Science,
Rensselaer Polytechnic Institute, Troy, USA
22email<EMAIL_ADDRESS>33institutetext: Univ. Bordeaux, CNRS,
Bordeaux INP, LaBRI, UMR 5800, Talence, France
33email<EMAIL_ADDRESS>
# Simple tableaux for two expansions
of Gödel modal logic††thanks: The research of Marta Bílková and Thomas
Ferguson was supported by the grant 22-01137S of the Czech Science Foundation.
The research of Daniil Kozhemiachenko is part of the project INTENDED
(ANR-19-CHIA-0014).

Marta Bílková 11 0000-0002-3490-2083 Thomas Ferguson 1122 0000-0002-6494-1833
Daniil Kozhemiachenko 33 0000-0002-1533-8034

###### Abstract

This paper considers two logics. The first one,
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$, is an expansion of the Gödel modal
logic $\mathbf{K}\mathsf{G}$ with the involutive negation
${\sim_{\mathsf{i}}}$ defined as $v({\sim_{\mathsf{i}}}\phi,w)=1-v(\phi,w)$.
The second one, $\mathbf{K}\mathsf{G}_{\mathsf{bl}}$, is the expansion of
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ with the bi-lattice connectives and
modalities. We explore their semantical properties w.r.t. the standard
semantics on $[0,1]$-valued Kripke frames and define a unified tableaux
calculus that allows for the explicit countermodel construction. For this, we
use an alternative semantics with the finite model property. Using the
tableaux calculus, we construct a decision algorithm and show that
satisfiability and validity in $\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$ are $\mathsf{PSpace}$-complete.

###### Keywords:

constraint tableaux Gödel modal logic involutive negation bi-lattice logics.

##  1 Introduction

When people evaluate their uncertainty or beliefs, they usually do it in two
ways: either quantitatively, by assigning a specific number to the value of
the belief, e.g., _‘the rain today is $73\%$ likely’_ or qualitatively, by
comparing degrees of two beliefs without explicitly mentioning their numerical
values as in _‘I think that my wallet is more likely to be in the drawer than
in the bag’_. In most cases, a person does not assign exact values to their
beliefs, and thus, reasons qualitatively. Formally, this can be represented
via Gödel modal logic $\mathbf{K}\mathsf{G}$ or, if one wishes to construe
‘rather’ as ‘strictly more likely’, its expansion with $\triangle$ (Baaz’
Delta [Baaz1996]) or $\Yleft$ (co-implication [Rauszer1974]111The symbol
$\Yleft$ is due to [Gore2000].) $\mathbf{K}\mathsf{biG}$.

Note that it is natural not only to compare degrees of certainty in two
different events but also to say something like _‘my wallet is likely in the
drawer’_ meaning _‘I think that my wallet is in the drawer rather than
elsewhere’_. I.e., the (subjective) likelihood of the wallet being in the
drawer is greater than $\frac{1}{2}$. As Gödel logic ($\mathsf{G}$) can
express only $0$ and $1$, such statements cannot be formalised in
$\mathbf{K}\mathsf{G}$ or $\mathbf{K}\mathsf{biG}$. However, $\frac{1}{2}$ is
expressible with the involutive negation ${\sim_{\mathsf{i}}}$ defined as
$v({\sim_{\mathsf{i}}}\phi)=1-v(\phi)$:
$v(p\leftrightarrow{\sim_{\mathsf{i}}}p)=1$ iff $v(p)=\frac{1}{2}$.

In this paper, we will present modal logics that can formalise this kind of
reasoning about beliefs. Let us now provide a broader context of our work.

Gödel logics with additional negations All logics that we consider here expand
the propositional Gödel logic with involutive negation
($\mathsf{G}_{\mathsf{inv}}$) that was introduced in
[EstevaGodoHajekNavara2000]. Adding ${\sim_{\mathsf{i}}}$ greatly enhances the
expressivity of the Gödel logic. Not only (as we mentioned above) can
$\frac{1}{2}$ be defined but also coimplication and the Baaz Delta.

$\displaystyle\phi\Yleft\chi$
$\displaystyle\coloneqq{\sim_{\mathsf{i}}}({\sim_{\mathsf{i}}}\chi\rightarrow{\sim_{\mathsf{i}}}\phi)$
$\displaystyle\triangle\phi$
$\displaystyle\coloneqq\mathbf{1}\Yleft(\mathbf{1}\Yleft\phi)$

Moreover, $\mathsf{G}_{\mathsf{inv}}$ is _paraconsistent_ in the following
sense: (1) $(p\wedge{\sim_{\mathsf{i}}}p)\rightarrow q$ is not valid; (2)
$p,{\sim_{\mathsf{i}}}p\not\models_{\mathsf{G}_{\mathsf{inv}}}q$ if
$\phi\models_{\mathsf{G}_{\mathsf{inv}}}\chi$ is interpreted as _‘
$v(\phi)\leq v(\chi)$, for each valuation $v$’_. These properties were
investigated in [ErtolaEstevaFlaminioGodoNoguera2015,
ConiglioEstevaGispertGodo2021]. Furthermore, $\mathsf{G}_{\mathsf{inv}}$ is
closely connected to $\mathsf{G}^{2}$ that was first discussed in
[Ferguson2014] and independently studied in more detail in
[BilkovaFrittellaKozhemiachenko2021,
BilkovaFrittellaKozhemiachenkoMajer2023IJAR]. $\mathsf{G}^{2}$ is an expansion
of $\mathsf{G}$ with a paraconsistent negation $\neg$ whose semantics is
defined via two independent valuations $v_{1}$ (support of truth or positive
support) and $v_{2}$ (support of falsity or negative support). It is shown in
[Ferguson2014] that $\mathsf{G}_{\mathsf{inv}}$ is obtained from
$\mathsf{G}^{2}$ by setting $v_{1}(p)=1-v_{2}(p)$.

Gödel modal and description logics Modal expansions of Gödel logics and their
applications have been extensively studied. The $\Box$ and $\lozenge$
fragments222Note that $\Box$ and $\lozenge$ are not interdefinable in Gödel
modal logic. of $\mathbf{K}\mathsf{G}$ were axiomatised in
[CaicedoRodriguez2010]. Hypersequent calculi were constructed in
[MetcalfeOlivetti2009, MetcalfeOlivetti2011] and used to obtain the
$\mathsf{PSpace}$-completeness of both fragments. $\mathbf{K}\mathsf{G}$ in
the bi-modal language was axiomatised in [CaicedoRodriguez2015,
RodriguezVidal2021] (for fuzzy and crisp333A frame $\langle W,R\rangle$ is
called _fuzzy_ if $R:W\times W\rightarrow[0,1]$ and _crisp_ if $R:W\times
W\rightarrow\\{0,1\\}$. frames, respectively). Moreover, it was shown in
[CaicedoMetcalfeRodriguezRogger2013, CaicedoMetcalfeRodriguezRogger2017] that
crisp and fuzzy $\mathbf{K}\mathsf{G}$ are $\mathsf{PSpace}$-complete.

The applications of Gödel modal logics and its expansions are well researched.
In [RodriguezTuytEstevaGodo2022], the completeness of $\mathbf{K45}$ and
$\mathbf{KD45}$ extensions of $\mathbf{K}\mathsf{G}$ w.r.t. non-normalised and
normalised possibilistic frames was established. In [AguileraDieguezFernandez-
DuqueMcLean2022], a temporal logic expanding the Gödel logic with co-
implication was proposed. In addition, paraconsistent expansions of
$\mathbf{K}\mathsf{G}$ that can be used to reason about contradictory beliefs
were proposed and studied in [BilkovaFrittellaKozhemiachenko2022IJCAR,
BilkovaFrittellaKozhemiachenko2023IGPL].

Gödel description logics (DLs) were proposed in [BobilloDelgadoGomez-
RamiroStraccia2009] to represent graded information in the ontologies and were
further studied in [BobilloDelgadoGomez-RamiroStraccia2012]. Just as the
classical description logics are notational variants of the classical logics
with the global (universal) modality, Gödel DLs can be considered a notational
variant of global Gödel modal logics. Moreover, Gödel DLs are usually equipped
with the involutive negation. They differ from Łukasiewicz and Product fuzzy
DLs because they are decidable and often have the same complexity as their
classical counterparts even for expressive logics
[BorgwardtDistelPenaloza2014DL, BorgwardtDistelPenaloza2014KR,
Borgwardt2014PhD, BorgwardtPenaloza2017].

Bi-lattice logics Our third source of inspiration is the work on bi-lattice
logics. Two orders on a bi-lattice can be interpreted as information order and
truth order. The bi-lattice language has two sets of connectives: truth
connectives and informational connectives. Bi-lattices were used to analyse
reasoning about beliefs and uncertainty in [Ginsberg1988] and further studied
in [Rivieccio2010PhD, JansanaRivieccio2012]. In [JungRivieccio2013] and
[RivieccioJungJansana2017], the semantics and duality theory of modal bi-
lattice logics were studied.

Note that $\mathsf{G}^{2}$ can be seen as a bi-lattice logic (with truth
connectives). Indeed, even though its semantics was originally defined via two
independent valuations $v_{1}$ and $v_{2}$ on $[0,1]$, it is possible to
combine them into one valuation on the bi-lattice $[0,1]^{\Join}$ (cf. Fig.
1). Likewise, in its modal extension $\mathbf{K}\mathsf{G}^{2}$, the semantics
of $\Box$ and $\lozenge$ is defined using $\bigwedge$ and $\bigvee$ — supremum
and infimum w.r.t. the truth order.

$(0,1)$$(0,0)$$(1,1)$$(1,0)$$\bullet$$(x,y)$truthinformation

Figure 1: $[0,1]^{\Join}$

In either approach, $v_{1}$ (the first coordinate) can be interpreted as the
_support of truth_ (the degree to which the statement is _asserted_) and
$v_{2}$ (the second coordinate) as the _support of falsity_ (the degree to
which the statement is _denied_ 444Here, we differentiate between _denials_ or
_refutations_ , i.e., assertions of falsity and _rejections_ — lack of
support. Cf. [BilkovaFrittellaKozhemiachenko2022IJCAR,
BilkovaFrittellaKozhemiachenko2023IGPL,
BilkovaFrittellaKozhemiachenko2023nonstandard] for more details concerning
this distinction.).

In [BilkovaFrittellaKozhemiachenko2023nonstandard],
$\mathsf{G}^{2\pm}_{\blacksquare,\blacklozenge}$, an expansion of
$\mathsf{G}^{2}$ with informational modalities $\blacksquare$ and
$\blacklozenge$ was proposed and studied. As expected, the value of
$\blacksquare\phi$ was computed using $\bigsqcap$ (informational infimum on
$[0,1]^{\Join}$), and the value of $\blacklozenge\phi$ via $\bigsqcup$
(informational supremum). In this paper, we combine $\mathbf{K}\mathsf{G}^{2}$
and $\mathsf{G}^{2\pm}_{\blacksquare,\blacklozenge}$ into one logic with the
full set of truth and informational connectives.

This paper In this paper, we present $\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$ — expansions of $\mathbf{K}\mathsf{G}$
with involution and with bi-lattice connectives and construct a tableaux
calculus that can be used to establish their $\mathsf{PSpace}$-completeness.
Our contribution is three-fold. First, we establish the result analogous to
the one in [Speranski2022] and construct faithful embeddings between
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$. Second, following
[CaicedoMetcalfeRodriguezRogger2013, CaicedoMetcalfeRodriguezRogger2017], we
present an alternative (and equivalent) semantics for
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and $\mathbf{K}\mathsf{G}_{\mathsf{bl}}$
that possess the finite model property. Third, using this semantics, we
construct a sound and complete tableaux calculus by combining the ideas from
[DAgostino1990], [Haehnle1994], and [Rogger2016phd].

The rest of the text is as follows. In Section 2, we present the Gödel modal
logic with involution and discuss its semantical properties. Section
LABEL:sec:KblG is dedicated to the bi-lattice Gödel modal logic
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$. We present its language and semantics
and construct faithful embeddings of $\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$ into one another. In Section
LABEL:sec:Fmodels, we present an alternative semantics that we use in Section
LABEL:sec:TKinvG to construct a sound and complete tableaux calculus. Using
tableaux, we prove $\mathsf{PSpace}$-completeness of
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ and
$\mathbf{K}\mathsf{G}_{\mathsf{bl}}$. Finally, in Section
LABEL:sec:conclusion, we summarise the results of the paper and provide a
roadmap for future research.

##  2 Gödel modal logic with involution

Let us present the language and semantics of
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$.

######  Definition 1 (Frames)

  * •

A _fuzzy frame_ is a tuple $\mathfrak{F}=\langle W,R\rangle$ with
$W\neq\varnothing$ and $R:W\times W\rightarrow[0,1]$.

  * •

A _crisp frame_ is a tuple $\mathfrak{F}=\langle W,R\rangle$ with
$W\neq\varnothing$ and $R:W\times W\rightarrow\\{0,1\\}$.

###### Convention 1

Let $\mathfrak{F}=\langle W,R\rangle$ be a frame and $w\in W$. We use the
following shorthand: $R(w)\coloneqq\\{w^{\prime}:wRw^{\prime}>0\\}$.

######  Definition 2 ($\mathbf{K}\mathsf{G}_{\mathsf{inv}}$)

We fix a countable set $\mathtt{Prop}$ and define the language
$\mathscr{L}_{{\sim_{\mathsf{i}}},\Box,\lozenge}$ using the grammar below.

$\displaystyle\mathscr{L}_{{\sim_{\mathsf{i}}},\Box,\lozenge}\ni\phi$
$\displaystyle\coloneqq
p\in\mathtt{Prop}\mid{\sim_{\mathsf{i}}}\phi\mid(\phi\wedge\phi)\mid(\phi\rightarrow\phi)\mid\Box\phi\mid\lozenge\phi$
(1)

A $\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ model is a tuple $\mathfrak{M}=\langle
W,R,v\rangle$ with $\langle W,R\rangle$ being a frame and
$v:\mathtt{Prop}\times W\rightarrow[0,1]$ (a
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ valuation) extended to the complex
formulas as follows.  $\displaystyle v({\sim_{\mathsf{i}}}\phi,w)$
$\displaystyle=1\\!-\\!v(\phi,w)$ $\displaystyle
v(\phi\\!\rightarrow\\!\chi,w)$ $\displaystyle=\begin{cases}1\text{ if
}v(\phi,w)\\!\leq\\!v(\chi,w)\\\ v(\chi)\text{ otherwise}\end{cases}$
$\displaystyle v(\phi\wedge\chi,w)$ $\displaystyle=\min(v(\phi,w),v(\chi,w))$
$\displaystyle v(\Box\phi,w)$ $\displaystyle=\inf\limits_{w^{\prime}\in
W}\\{wRw^{\prime}\\!\rightarrow\\!v(\phi,w^{\prime})\\}$ $\displaystyle
v(\lozenge\phi,w)$ $\displaystyle=\sup\limits_{w^{\prime}\in
W}\\{wRw^{\prime}\\!\wedge\\!v(\phi,w^{\prime})\\}$

We say that $\phi\in\mathscr{L}_{{\sim_{\mathsf{i}}},\Box,\lozenge}$ is
_$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ -valid on a pointed frame
$\langle\mathfrak{F},w\rangle$_
($\mathfrak{F},w\\!\models_{\mathbf{K}\mathsf{G}_{\mathsf{inv}}}\\!\phi$) iff
$v(\phi,w)=1$ for any model $\mathfrak{M}$ on $\mathfrak{F}$. $\phi$ is
_$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ valid on frame $\mathfrak{F}$_
($\mathfrak{F}\\!\models_{\mathbf{K}\mathsf{biG}}\\!\phi$) iff
$\mathfrak{F},w\\!\models_{\mathbf{K}\mathsf{G}_{\mathsf{inv}}}\\!\phi$ for
any $w\in\mathfrak{F}$.

###### Convention 2

Given a formula $\phi$, we use $\mathtt{Prop}(\phi)$ to denote the set of
variables occurring in it and $|\phi|$ for the number of symbols. We are going
to use $\phi\leftrightarrow\chi$ as a shorthand for
$(\phi\rightarrow\chi)\wedge(\chi\rightarrow\phi)$ and use the following
defined connectives:

$\displaystyle\mathbf{1}$ $\displaystyle\coloneqq p\rightarrow p$
$\displaystyle\mathbf{0}$
$\displaystyle\coloneqq{\sim_{\mathsf{i}}}\mathbf{1}$
$\displaystyle{\sim}\phi$ $\displaystyle\coloneqq\phi\rightarrow\mathbf{0}$
$\displaystyle\phi\vee\chi$
$\displaystyle\coloneqq{\sim_{\mathsf{i}}}({\sim_{\mathsf{i}}}\phi\wedge{\sim_{\mathsf{i}}}\chi)$
$\displaystyle\phi\Yleft\chi$
$\displaystyle\coloneqq{\sim_{\mathsf{i}}}({\sim_{\mathsf{i}}}\chi\rightarrow{\sim_{\mathsf{i}}}\phi)$
$\displaystyle\triangle\phi$
$\displaystyle\coloneqq\mathbf{1}\Yleft(\mathbf{1}\Yleft\phi)$ (2)

Additionally, we will use the following notation:

  * •

$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$ is the set of all
$\mathscr{L}_{{\sim_{\mathsf{i}}},\Box,\lozenge}$-formulas valid over all
frames;

  * •

$\mathscr{L}_{\triangle,\Box,\lozenge}$ is the ${\sim_{\mathsf{i}}}$-free
fragment of $\mathscr{L}_{{\sim_{\mathsf{i}}},\Box,\lozenge}$ with $\triangle$
and $\sim$555Recall that $\vee$ can be defined in $\mathsf{G}$ as follows:
$\phi\vee\chi\coloneqq((\phi\rightarrow\chi)\rightarrow\chi)\wedge((\chi\rightarrow\phi)\rightarrow\phi)$.
treated as primitive connectives; $\mathbf{K}\mathsf{biG}$ is the set of all
$\mathscr{L}_{\triangle,\Box,\lozenge}$-formulas valid over all frames;

  * •

$\mathscr{L}_{\Box,\lozenge}$ is the $\triangle$-free fragment of
$\mathscr{L}_{\triangle,\Box,\lozenge}$; $\mathbf{K}\mathsf{G}$ is the set of
all $\mathscr{L}_{\Box,\lozenge}$-formulas valid over all frames.

One can check that if $\phi\in\mathscr{L}_{\Box,\lozenge}$ is
$\mathbf{K}\mathsf{G}$-valid, it is also $\mathbf{K}\mathsf{biG}$-valid and
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$-valid and that if
$\phi\in\mathscr{L}_{\triangle,\Box,\lozenge}$ is
$\mathbf{K}\mathsf{biG}$-valid, it is
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$-valid too.

Moreover, given a model $\mathfrak{M}$, we will write $W_{\mathfrak{M}}$,
$R_{\mathfrak{M}}$, and $v_{\mathfrak{M}}$ to designate that $W$ is its the
set, $R$ is its accessibility relation, and $v$ is its valuation.

######  Definition 3 (Frame definability)

Let $\mathscr{L}$ be a language. A class $\mathbb{F}$ of frames is _definable
by a formula $\phi\in\mathscr{L}$_ iff the following condition holds:

$\displaystyle\forall\mathfrak{F}:\mathfrak{F}\models_{\mathbf{K}\mathsf{G}_{\mathsf{inv}}}\phi\text{
iff }\mathfrak{F}\in\mathbb{F}$

Let us discuss several important semantical properties of
$\mathbf{K}\mathsf{G}_{\mathsf{inv}}$. First of all, it is easy to see that
$\Box p\leftrightarrow{\sim_{\mathsf{i}}}\lozenge{\sim_{\mathsf{i}}}p$ defines
the class of crisp frames. On the other hand, $\Box$ and $\lozenge$ are not
interdefinable on fuzzy frames.

###### Theorem 2.1

  1. 1.

$\mathfrak{F}\models_{\mathbf{K}\mathsf{G}_{\mathsf{inv}}}\Box
p\leftrightarrow{\sim_{\mathsf{i}}}\lozenge{\sim_{\mathsf{i}}}p$ iff
$\mathfrak{F}$ is crisp.

  2. 2.

$\Box$ and $\lozenge$ are not interdefinable on fuzzy frames.

###### Proof

We begin with 1. Observe that
$v(\Box\phi,w)=\inf\\{v(\phi,w^{\prime}):wRw^{\prime}\\}$ and
$v(\lozenge\phi,w)=\sup\\{v(\phi,w^{\prime}):wRw^{\prime}\\}$ on crisp frames.
From here, it is evident that $\Box
p\leftrightarrow{\sim_{\mathsf{i}}}\lozenge{\sim_{\mathsf{i}}}p$ is valid on
crisp frames. For the converse, assume that $\mathfrak{F}$ is not crisp, i.e.,
there are $w,w^{\prime}\in\mathfrak{F}$ s.t. $wRw^{\prime}=x$ for some
$0<x<1$. Now for every $w^{\prime\prime}\in W$, set
$v(p,w^{\prime\prime})=x^{\prime\prime}$ s.t. $x^{\prime\prime}\geq
wRw^{\prime\prime}$ and $v(p,w^{\prime\prime})=1$ only if
$wRw^{\prime\prime}=1$. It is clear that $v(\Box p,w)=1$. On the other hand,
we have that $v(\lozenge{\sim_{\mathsf{i}}}p,w)>0$ since
$0<v({\sim_{\mathsf{i}}}p,w^{\prime})\leq 1-x<1$ and $wRw^{\prime}=x$. But
then, $v({\sim_{\mathsf{i}}}\lozenge{\sim_{\mathsf{i}}}p,w)\neq 1$, as
required.

For 2., take the model below (all variables have the same values as $p$) and
note that $v(\Box p,w)=\frac{1}{5}$ and $v(\lozenge p,w)=\frac{1}{4}$.


100_50_4 | 105996 | 105996 | 0.000 |  | 2 | 1.0 | 105996.00 | 105996 | 0.000 | 1.0 |  | 2 | 105996.00 | 105996 | 0.000 | 1.0 |  | 2 | 105996.00 | 105996 | 0.000 | 1.0 |  | 1 | 105996.00 | 105996 | 0.000 | 1.0
100_50_5 | 56464 | 56464 | 0.000 |  | 4 | 1.0 | 56464.00 | 56464 | 0.000 | 1.0 |  | 4 | 56464.00 | 56464 | 0.000 | 1.0 |  | 3 | 56464.00 | 56464 | 0.000 | 1.0 |  | 3 | 56464.00 | 56464 | 0.000 | 1.0
100_50_6 | 16083 | 16083 | 0.000 |  | 2 | 1.0 | 16083.00 | 16083 | 0.000 | 1.0 |  | 2 | 16083.00 | 16083 | 0.000 | 1.0 |  | 2 | 16083.00 | 16083 | 0.000 | 1.0 |  | 1 | 16083.00 | 16083 | 0.000 | 1.0
100_50_7 | 52819 | 52819 | 0.000 |  | 2 | 1.0 | 52819.00 | 52819 | 0.000 | 1.0 |  | 2 | 52819.00 | 52819 | 0.000 | 1.0 |  | 2 | 52819.00 | 52819 | 0.000 | 1.0 |  | 2 | 52819.00 | 52819 | 0.000 | 1.0
100_50_8 | 54246 | 54246 | 0.000 |  | 4 | 1.0 | 54246.00 | 54246 | 0.000 | 1.0 |  | 4 | 54246.00 | 54246 | 0.000 | 1.0 |  | 4 | 54246.00 | 54246 | 0.000 | 1.0 |  | 4 | 54246.00 | 54246 | 0.000 | 1.0
100_50_9 | 68974 | 68974 | 0.000 |  | 3 | 1.0 | 68974.00 | 68974 | 0.000 | 1.0 |  | 3 | 68974.00 | 68974 | 0.000 | 1.0 |  | 3 | 68974.00 | 68974 | 0.000 | 1.0 |  | 2 | 68974.00 | 68974 | 0.000 | 1.0
100_50_10 | 88634 | 88634 | 0.000 |  | 9 | 1.0 | 88607.00 | 88634 | 0.000 | 0.5 |  | 9 | 88607.00 | 88634 | 0.000 | 0.5 |  | 8 | 88613.70 | 88634 | 0.000 | 0.7 |  | 8 | 88613.70 | 88634 | 0.000 | 0.7
100_75_1 | 189137 | 189137 | 0.000 |  | 3 | 1.0 | 189089.00 | 189137 | 0.000 | 0.9 |  | 1 | 189137.00 | 189137 | 0.000 | 1.0 |  | 3 | 189137.00 | 189137 | 0.000 | 1.0 |  | 1 | 189137.00 | 189137 | 0.000 | 1.0
100_75_2 | 95074 | 95074 | 0.000 |  | 4 | 1.0 | 95032.90 | 95074 | 0.000 | 0.5 |  | 4 | 95032.90 | 95074 | 0.000 | 0.5 |  | 5 | 95064.80 | 95074 | 0.000 | 0.8 |  | 5 | 95064.80 | 95074 | 0.000 | 0.8
100_75_3 | 62098 | 62098 | 0.000 |  | 2 | 1.0 | 62098.00 | 62098 | 0.000 | 1.0 |  | 2 | 62098.00 | 62098 | 0.000 | 1.0 |  | 2 | 62098.00 | 62098 | 0.000 | 1.0 |  | 1 | 62098.00 | 62098 | 0.000 | 1.0
100_75_4 | 72245 | 72245 | 0.000 |  | 7 | 1.0 | 72232.20 | 72245 | 0.000 | 0.5 |  | 7 | 72232.20 | 72245 | 0.000 | 0.5 |  | 9 | 72244.50 | 72245 | 0.000 | 0.9 |  | 9 | 72244.50 | 72245 | 0.000 | 0.9
100_75_5 | 27616 | 27616 | 0.000 |  | 3 | 1.0 | 27616.00 | 27616 | 0.000 | 1.0 |  | 1 | 27616.00 | 27616 | 0.000 | 1.0 |  | 2 | 27616.00 | 27616 | 0.000 | 1.0 |  | 1 | 27616.00 | 27616 | 0.000 | 1.0
100_75_6 | 145273 | 145273 | 0.000 |  | 2 | 1.0 | 145273.00 | 145273 | 0.000 | 1.0 |  | 2 | 145273.00 | 145273 | 0.000 | 1.0 |  | 2 | 145273.00 | 145273 | 0.000 | 1.0 |  | 2 | 145273.00 | 145273 | 0.000 | 1.0
100_75_7 | 110979 | 110979 | 0.000 |  | 6 | 1.0 | 110960.70 | 110979 | 0.000 | 0.5 |  | 6 | 110960.70 | 110979 | 0.000 | 0.5 |  | 7 | 110977.20 | 110979 | 0.000 | 0.8 |  | 7 | 110977.20 | 110979 | 0.000 | 0.8
100_75_8 | 19570 | 19570 | 0.000 |  | 2 | 1.0 | 19570.00 | 19570 | 0.000 | 1.0 |  | 2 | 19570.00 | 19570 | 0.000 | 1.0 |  | 2 | 19570.00 | 19570 | 0.000 | 1.0 |  | 1 | 19570.00 | 19570 | 0.000 | 1.0
100_75_9 | 104341 | 104341 | 0.000 |  | 8 | 1.0 | 104262.50 | 104341 | 0.000 | 0.3 |  | 8 | 104262.50 | 104341 | 0.000 | 0.3 |  | 6 | 104328.10 | 104341 | 0.000 | 0.8 |  | 6 | 104328.10 | 104341 | 0.000 | 0.8
100_75_10 | 143740 | 143740 | 0.000 |  | 8 | 1.0 | 143702.40 | 143740 | 0.000 | 0.7 |  | 8 | 143702.40 | 143740 | 0.000 | 0.7 |  | 6 | 143740.00 | 143740 | 0.000 | 1.0 |  | 1 | 143740.00 | 143740 | 0.000 | 1.0
100_100_1 | 81978 | 81978 | 0.000 |  | 5 | 1.0 | 81978.00 | 81978 | 0.000 | 1.0 |  | 5 | 81978.00 | 81978 | 0.000 | 1.0 |  | 5 | 81978.00 | 81978 | 0.000 | 1.0 |  | 5 | 81978.00 | 81978 | 0.000 | 1.0
100_100_2 | 190424 | 190424 | 0.000 |  | 4 | 1.0 | 190410.40 | 190424 | 0.000 | 0.8 |  | 4 | 190410.40 | 190424 | 0.000 | 0.8 |  | 4 | 190416.20 | 190424 | 0.000 | 0.8 |  | 4 | 190416.20 | 190424 | 0.000 | 0.8
100_100_3 | 225434 | 225434 | 0.000 |  | 3 | 1.0 | 225412.40 | 225434 | 0.000 | 0.7 |  | 3 | 225412.40 | 225434 | 0.000 | 0.7 |  | 3 | 225434.00 | 225434 | 0.000 | 1.0 |  | 2 | 225434.00 | 225434 | 0.000 | 1.0
100_100_4 | 63028 | 63028 | 0.000 |  | 3 | 1.0 | 63028.00 | 63028 | 0.000 | 1.0 |  | 3 | 63028.00 | 63028 | 0.000 | 1.0 |  | 3 | 63028.00 | 63028 | 0.000 | 1.0 |  | 1 | 63028.00 | 63028 | 0.000 | 1.0
100_100_5 | 230076 | 230076 | 0.000 |  | 3 | 1.0 | 229861.00 | 230076 | 0.000 | 0.7 |  | 3 | 229861.00 | 230076 | 0.000 | 0.7 |  | 3 | 230076.00 | 230076 | 0.000 | 1.0 |  | 1 | 230076.00 | 230076 | 0.000 | 1.0
100_100_6 | 74358 | 74358 | 0.000 |  | 3 | 1.0 | 74358.00 | 74358 | 0.000 | 1.0 |  | 3 | 74358.00 | 74358 | 0.000 | 1.0 |  | 3 | 74358.00 | 74358 | 0.000 | 1.0 |  | 3 | 74358.00 | 74358 | 0.000 | 1.0
100_100_7 | 10330 | 10330 | 0.000 |  | 4 | 1.0 | 10330.00 | 10330 | 0.000 | 1.0 |  | 4 | 10330.00 | 10330 | 0.000 | 1.0 |  | 4 | 10330.00 | 10330 | 0.000 | 1.0 |  | 4 | 10330.00 | 10330 | 0.000 | 1.0
100_100_8 | 62582 | 62582 | 0.000 |  | 3 | 1.0 | 62582.00 | 62582 | 0.000 | 1.0 |  | 3 | 62582.00 | 62582 | 0.000 | 1.0 |  | 3 | 62582.00 | 62582 | 0.000 | 1.0 |  | 1 | 62582.00 | 62582 | 0.000 | 1.0
100_100_9 | 232754 | 232754 | 0.000 |  | 7 | 1.0 | 232270.00 | 232754 | 0.000 | 0.2 |  | 7 | 232270.00 | 232754 | 0.000 | 0.2 |  | 4 | 232754.00 | 232754 | 0.000 | 1.0 |  | 2 | 232754.00 | 232754 | 0.000 | 1.0
100_100_10 | 193262 | 193262 | 0.000 |  | 7 | 1.0 | 193246.10 | 193262 | 0.000 | 0.7 |  | 7 | 193246.10 | 193262 | 0.000 | 0.7 |  | 4 | 193262.00 | 193262 | 0.000 | 1.0 |  | 2 | 193262.00 | 193262 | 0.000 | 1.0
200_25_1 | 204441 | 204441 | 0.000 |  | 5 | 1.0 | 200560.60 | 204401 | 0.020 | 0.0 |  | 5 | 204006.70 | 204401 | 0.020 | 0.0 |  | 7 | 204351.60 | 204441 | 0.000 | 0.4 |  | 7 | 204397.30 | 204441 | 0.000 | 0.7
200_25_2 | 239573 | 239573 | 0.000 |  | 10 | 1.0 | 237686.30 | 239573 | 0.000 | 0.1 |  | 3 | 239511.70 | 239573 | 0.000 | 0.2 |  | 10 | 239568.50 | 239573 | 0.000 | 0.7 |  | 3 | 239570.00 | 239573 | 0.000 | 0.8
200_25_3 | 245463 | 245463 | 0.000 |  | 8 | 1.0 | 242063.30 | 245463 | 0.000 | 0.3 |  | 8 | 242063.30 | 245463 | 0.000 | 0.3 |  | 9 | 245338.30 | 245463 | 0.000 | 0.4 |  | 6 | 245119.50 | 245463 | 0.000 | 0.5
200_25_4 | 222361 | 222361 | 0.000 |  | 6 | 1.0 | 220185.30 | 222361 | 0.000 | 0.3 |  | 4 | 222134.60 | 222361 | 0.000 | 0.8 |  | 6 | 222323.90 | 222361 | 0.000 | 0.8 |  | 6 | 222361.00 | 222361 | 0.000 | 1.0
200_25_5 | 187324 | 187324 | 0.000 |  | 8 | 1.0 | 186980.30 | 187316 | 4.3E-3 | 0.0 |  | 4 | 187130.00 | 187324 | 0.000 | 0.1 |  | 7 | 187310.80 | 187324 | 0.000 | 0.3 |  | 5 | 187318.10 | 187324 | 0.000 | 0.3
200_25_6 | 80351 | 80351 | 0.000 |  | 5 | 1.0 | 80227.90 | 80351 | 0.000 | 0.5 |  | 5 | 80271.00 | 80351 | 0.000 | 0.5 |  | 5 | 80309.10 | 80351 | 0.000 | 0.5 |  | 5 | 80312.90 | 80351 | 0.000 | 0.5
200_25_7 | 59036 | 59036 | 0.000 |  | 7 | 1.0 | 59029.20 | 59036 | 0.000 | 0.8 |  | 7 | 59029.20 | 59036 | 0.000 | 0.8 |  | 9 | 59036.00 | 59036 | 0.000 | 1.0 |  | 9 | 59036.00 | 59036 | 0.000 | 1.0
200_25_8 | 149433 | 149433 | 0.000 |  | 9 | 1.0 | 149152.30 | 149407 | 0.017 | 0.0 |  | 9 | 149152.30 | 149407 | 0.017 | 0.0 |  | 8 | 149394.10 | 149433 | 0.000 | 0.4 |  | 8 | 149394.10 | 149433 | 0.000 | 0.4
200_25_9 | 49366 | 49366 | 0.000 |  | 7 | 1.0 | 49363.20 | 49366 | 0.000 | 0.8 |  | 7 | 49363.20 | 49366 | 0.000 | 0.8 |  | 7 | 49366.00 | 49366 | 0.000 | 1.0 |  | 7 | 49366.00 | 49366 | 0.000 | 1.0
200_25_10 | 48459 | 48459 | 0.000 |  | 4 | 1.0 | 48459.00 | 48459 | 0.000 | 1.0 |  | 4 | 48459.00 | 48459 | 0.000 | 1.0 |  | 4 | 48459.00 | 48459 | 0.000 | 1.0 |  | 4 | 48459.00 | 48459 | 0.000 | 1.0

TABLE XIII: Full Results of Ising Machine on Medium-sized Instances
(continued).

Instance | Gurobi |  | AE |  | AE-R |  | AE-I |  | AE-RI
---|---|---|---|---|---|---|---|---|---
$n$_$d$_id | Optimal | Score | Gap |  | $a$ | FS | Mean | Best | Gap | SR |  | $a$ | Mean | Best | Gap | SR |  | $a$ | Mean | Best | Gap | SR |  | $a$ | Mean | Best | Gap | SR
200_50_1 | 372097 | 372097 | 0.000 |  | 4 | 1.0 | 372097.00 | 372097 | 0.000 | 1.0 |  | 3 | 372097.00 | 372097 | 0.000 | 1.0 |  | 4 | 372097.00 | 372097 | 0.000 | 1.0 |  | 2 | 372097.00 | 372097 | 0.000 | 1.0
200_50_2 | 211130 | 211130 | 0.000 |  | 4 | 0.6 | 203100.17 | 211122 | 3.8E-3 | 0.0 |  | 4 | 210236.80 | 211122 | 3.8E-3 | 0.0 |  | 10 | 210992.40 | 211130 | 0.000 | 0.1 |  | 3 | 211052.50 | 211130 | 0.000 | 0.1
200_50_3 | 227185 | 227185 | 0.000 |  | 9 | 1.0 | 226925.00 | 227185 | 0.000 | 0.1 |  | 9 | 226925.00 | 227185 | 0.000 | 0.1 |  | 6 | 227167.10 | 227185 | 0.000 | 0.9 |  | 1 | 227185.00 | 227185 | 0.000 | 1.0
200_50_4 | 228572 | 228572 | 0.000 |  | 4 | 1.0 | 228572.00 | 228572 | 0.000 | 1.0 |  | 4 | 228572.00 | 228572 | 0.000 | 1.0 |  | 4 | 228572.00 | 228572 | 0.000 | 1.0 |  | 3 | 228572.00 | 228572 | 0.000 | 1.0
200_50_5 | 479651 | 479651 | 0.000 |  | 9 | 1.0 | 477806.20 | 479651 | 0.000 | 0.4 |  | 9 | 477806.20 | 479651 | 0.000 | 0.4 |  | 9 | 479548.30 | 479651 | 0.000 | 0.5 |  | 3 | 479551.00 | 479651 | 0.000 | 0.5
200_50_6 | 426777 | 426672 | 0.025 |  | 8 | 1.0 | 424845.00 | 426777 | 0.000 | 0.1 |  | 8 | 424845.00 | 426777 | 0.000 | 0.1 |  | 7 | 426750.20 | 426777 | 0.000 | 0.7 |  | 7 | 426757.10 | 426777 | 0.000 | 0.7
200_50_7 | 220890 | 220890 | 0.000 |  | 6 | 1.0 | 220720.90 | 220890 | 0.000 | 0.2 |  | 6 | 220720.90 | 220890 | 0.000 | 0.2 |  | 6 | 220841.30 | 220890 | 0.000 | 0.3 |  | 1 | 220868.40 | 220890 | 0.000 | 0.7
200_50_8 | 317952 | 317952 | 0.000 |  | 5 | 1.0 | 317803.90 | 317952 | 0.000 | 0.2 |  | 5 | 317803.90 | 317952 | 0.000 | 0.2 |  | 5 | 317913.90 | 317952 | 0.000 | 0.7 |  | 2 | 317952.00 | 317952 | 0.000 | 1.0
200_50_9 | 104936 | 104936 | 0.000 |  | 5 | 1.0 | 104742.10 | 104936 | 0.000 | 0.1 |  | 5 | 104742.10 | 104936 | 0.000 | 0.1 |  | 6 | 104884.90 | 104936 | 0.000 | 0.9 |  | 3 | 104904.60 | 104936 | 0.000 | 0.9
200_50_10 | 284751 | 284751 | 0.000 |  | 5 | 1.0 | 284299.40 | 284745 | 2.1E-3 | 0.0 |  | 5 | 284299.40 | 284745 | 2.1E-3 | 0.0 |  | 5 | 284632.00 | 284751 | 0.000 | 0.2 |  | 5 | 284635.70 | 284751 | 0.000 | 0.3
200_75_1 | 442894 | 442894 | 0.000 |  | 10 | 1.0 | 441907.10 | 442672 | 0.050 | 0.0 |  | 10 | 441907.10 | 442672 | 0.050 | 0.0 |  | 10 | 442719.90 | 442894 | 0.000 | 0.3 |  | 3 | 442752.70 | 442894 | 0.000 | 0.5
200_75_2 | 286643 | 286643 | 0.000 |  | 5 | 1.0 | 286572.50 | 286643 | 0.000 | 0.2 |  | 5 | 286572.50 | 286643 | 0.000 | 0.2 |  | 5 | 286630.60 | 286643 | 0.000 | 0.6 |  | 5 | 286630.90 | 286643 | 0.000 | 0.6
200_75_3 | 61924 | 61924 | 0.000 |  | 10 | 1.0 | 61924.00 | 61924 | 0.000 | 1.0 |  | 10 | 61924.00 | 61924 | 0.000 | 1.0 |  | 7 | 61924.00 | 61924 | 0.000 | 1.0 |  | 1 | 61924.00 | 61924 | 0.000 | 1.0
200_75_4 | 128351 | 128351 | 0.000 |  | 3 | 1.0 | 128351.00 | 128351 | 0.000 | 1.0 |  | 3 | 128351.00 | 128351 | 0.000 | 1.0 |  | 3 | 128351.00 | 128351 | 0.000 | 1.0 |  | 1 | 128351.00 | 128351 | 0.000 | 1.0
200_75_5 | 137885 | 137885 | 0.000 |  | 9 | 1.0 | 137842.90 | 137885 | 0.000 | 0.7 |  | 9 | 137842.90 | 137885 | 0.000 | 0.7 |  | 5 | 137885.00 | 137885 | 0.000 | 1.0 |  | 5 | 137885.00 | 137885 | 0.000 | 1.0
200_75_6 | 229631 | 229631 | 0.000 |  | 7 | 1.0 | 228703.10 | 229631 | 0.000 | 0.1 |  | 7 | 228703.10 | 229631 | 0.000 | 0.1 |  | 6 | 229159.00 | 229631 | 0.000 | 0.3 |  | 3 | 229592.90 | 229631 | 0.000 | 0.9
200_75_7 | 269887 | 269887 | 0.000 |  | 5 | 1.0 | 269846.60 | 269887 | 0.000 | 0.6 |  | 5 | 269846.60 | 269887 | 0.000 | 0.6 |  | 6 | 269863.10 | 269887 | 0.000 | 0.9 |  | 6 | 269863.10 | 269887 | 0.000 | 0.9
200_75_8 | 600858 | 600858 | 0.000 |  | 5 | 0.7 | 592861.00 | 600819 | 6.5E-3 | 0.0 |  | 5 | 600507.50 | 600858 | 0.000 | 0.4 |  | 7 | 600155.90 | 600858 | 0.000 | 0.3 |  | 5 | 600858.00 | 600858 | 0.000 | 1.0
200_75_9 | 516771 | 516771 | 0.000 |  | 10 | 1.0 | 516262.00 | 516619 | 0.029 | 0.0 |  | 10 | 516262.00 | 516619 | 0.029 | 0.0 |  | 8 | 516714.90 | 516771 | 0.000 | 0.5 |  | 8 | 516714.90 | 516771 | 0.000 | 0.5
200_75_10 | 142694 | 142694 | 0.000 |  | 6 | 1.0 | 142683.60 | 142694 | 0.000 | 0.9 |  | 6 | 142683.60 | 142694 | 0.000 | 0.9 |  | 4 | 142694.00 | 142694 | 0.000 | 1.0 |  | 1 | 142694.00 | 142694 | 0.000 | 1.0
200_100_1 | 937149 | 937149 | 0.000 |  | 10 | 1.0 | 932240.80 | 936716 | 0.046 | 0.0 |  | 4 | 936329.60 | 936742 | 0.043 | 0.0 |  | 10 | 937143.80 | 937149 | 0.000 | 0.8 |  | 9 | 937146.40 | 937149 | 0.000 | 0.9
200_100_2 | 303058 | 303058 | 0.000 |  | 10 | 1.0 | 302835.40 | 303058 | 0.000 | 0.2 |  | 10 | 302835.40 | 303058 | 0.000 | 0.2 |  | 10 | 303019.90 | 303058 | 0.000 | 0.6 |  | 10 | 303019.90 | 303058 | 0.000 | 0.6
200_100_3 | 29367 | 29367 | 0.000 |  | 4 | 1.0 | 29367.00 | 29367 | 0.000 | 1.0 |  | 4 | 29367.00 | 29367 | 0.000 | 1.0 |  | 4 | 29367.00 | 29367 | 0.000 | 1.0 |  | 4 | 29367.00 | 29367 | 0.000 | 1.0
200_100_4 | 100838 | 100838 | 0.000 |  | 4 | 1.0 | 100838.00 | 100838 | 0.000 | 1.0 |  | 4 | 100838.00 | 100838 | 0.000 | 1.0 |  | 3 | 100838.00 | 100838 | 0.000 | 1.0 |  | 1 | 100838.00 | 100838 | 0.000 | 1.0
200_100_5 | 786635 | 786635 | 0.000 |  | 6 | 1.0 | 786527.90 | 786635 | 0.000 | 0.1 |  | 3 | 786516.60 | 786635 | 0.000 | 0.5 |  | 5 | 786604.80 | 786635 | 0.000 | 0.8 |  | 6 | 786605.20 | 786635 | 0.000 | 0.8
200_100_6 | 41171 | 41171 | 0.000 |  | 3 | 1.0 | 41171.00 | 41171 | 0.000 | 1.0 |  | 3 | 41171.00 | 41171 | 0.000 | 1.0 |  | 3 | 41171.00 | 41171 | 0.000 | 1.0 |  | 1 | 41171.00 | 41171 | 0.000 | 1.0
200_100_7 | 701094 | 701094 | 0.000 |  | 9 | 1.0 | 700500.00 | 701094 | 0.000 | 0.1 |  | 9 | 700500.00 | 701094 | 0.000 | 0.1 |  | 7 | 701088.50 | 701094 | 0.000 | 0.9 |  | 9 | 701088.50 | 701094 | 0.000 | 0.9
200_100_8 | 782443 | 782443 | 0.000 |  | 10 | 1.0 | 781342.10 | 782201 | 0.031 | 0.0 |  | 10 | 781342.10 | 782201 | 0.031 | 0.0 |  | 9 | 782403.30 | 782443 | 0.000 | 0.3 |  | 3 | 782356.30 | 782443 | 0.000 | 0.4
200_100_9 | 628992 | 628992 | 0.000 |  | 6 | 1.0 | 627248.30 | 628948 | 7.0E-3 | 0.0 |  | 6 | 627248.30 | 628948 | 7.0E-3 | 0.0 |  | 4 | 628932.40 | 628992 | 0.000 | 0.5 |  | 4 | 628974.90 | 628992 | 0.000 | 0.5
200_100_10 | 378442 | 378442 | 0.000 |  | 8 | 1.0 | 378240.50 | 378442 | 0.000 | 0.1 |  | 8 | 378240.50 | 378442 | 0.000 | 0.1 |  | 7 | 378442.00 | 378442 | 0.000 | 1.0 |  | 7 | 378442.00 | 378442 | 0.000 | 1.0
300_25_1 | 29140 | 29140 | 0.000 |  | 9 | 1.0 | 29129.20 | 29140 | 0.000 | 0.5 |  | 9 | 29129.20 | 29140 | 0.000 | 0.5 |  | 9 | 29140.00 | 29140 | 0.000 | 1.0 |  | 2 | 29140.00 | 29140 | 0.000 | 1.0
300_25_2 | 281990 | 281990 | 0.000 |  | 10 | 1.0 | 281559.20 | 281990 | 0.000 | 0.1 |  | 10 | 281559.20 | 281990 | 0.000 | 0.1 |  | 8 | 281832.50 | 281990 | 0.000 | 0.2 |  | 6 | 281960.30 | 281990 | 0.000 | 0.3
300_25_3 | 231075 | 231075 | 0.000 |  | 9 | 1.0 | 230378.60 | 230873 | 0.087 | 0.0 |  | 4 | 231075.00 | 231075 | 0.000 | 1.0 |  | 8 | 230863.20 | 231075 | 0.000 | 0.3 |  | 1 | 231075.00 | 231075 | 0.000 | 1.0
300_25_4 | 444759 | 444759 | 0.000 |  | 9 | 1.0 | 430978.60 | 444247 | 0.115 | 0.0 |  | 2 | 444401.60 | 444725 | 7.6E-3 | 0.0 |  | 5 | 444430.00 | 444759 | 0.000 | 0.1 |  | 5 | 444709.30 | 444759 | 0.000 | 0.3
300_25_5 | 14988 | 14988 | 0.000 |  | 9 | 1.0 | 14988.00 | 14988 | 0.000 | 1.0 |  | 4 | 14988.00 | 14988 | 0.000 | 1.0 |  | 9 | 14988.00 | 14988 | 0.000 | 1.0 |  | 4 | 14988.00 | 14988 | 0.000 | 1.0
300_25_6 | 269782 | 269782 | 0.000 |  | 10 | 1.0 | 268277.20 | 269601 | 0.067 | 0.0 |  | 2 | 269536.10 | 269782 | 0.000 | 0.9 |  | 8 | 269272.67 | 269782 | 0.000 | 0.1 |  | 2 | 269770.90 | 269782 | 0.000 | 0.9
300_25_7 | 485263 | 485263 | 0.000 |  | 8 | 0.9 | 479607.22 | 484736 | 0.109 | 0.0 |  | 6 | 484404.90 | 485004 | 0.053 | 0.0 |  | 4 | 485143.38 | 485263 | 0.000 | 0.1 |  | 4 | 485125.60 | 485263 | 0.000 | 0.1
300_25_8 | 9343 | 9343 | 0.000 |  | 10 | 1.0 | 9343.00 | 9343 | 0.000 | 1.0 |  | 10 | 9343.00 | 9343 | 0.000 | 1.0 |  | 9 | 9343.00 | 9343 | 0.000 | 1.0 |  | 1 | 9343.00 | 9343 | 0.000 | 1.0
300_25_9 | 250761 | 250761 | 0.000 |  | 9 | 1.0 | 250555.80 | 250751 | 4.0E-3 | 0.0 |  | 9 | 250555.80 | 250751 | 4.0E-3 | 0.0 |  | 9 | 250695.10 | 250761 | 0.000 | 0.2 |  | 7 | 250755.00 | 250761 | 0.000 | 0.4
300_25_10 | 383377 | 383377 | 0.000 |  | 8 | 1.0 | 382810.20 | 383377 | 0.000 | 0.1 |  | 4 | 383377.00 | 383377 | 0.000 | 1.0 |  | 7 | 383263.50 | 383377 | 0.000 | 0.3 |  | 1 | 383377.00 | 383377 | 0.000 | 1.0
300_50_1 | 513379 | 513379 | 0.000 |  | 10 | 1.0 | 513018.60 | 513379 | 0.000 | 0.2 |  | 10 | 513018.60 | 513379 | 0.000 | 0.2 |  | 10 | 513353.00 | 513379 | 0.000 | 0.7 |  | 5 | 513372.30 | 513379 | 0.000 | 0.9
300_50_2 | 105543 | 105543 | 0.000 |  | 6 | 1.0 | 105523.80 | 105543 | 0.000 | 0.9 |  | 4 | 105543.00 | 105543 | 0.000 | 1.0 |  | 6 | 105543.00 | 105543 | 0.000 | 1.0 |  | 3 | 105543.00 | 105543 | 0.000 | 1.0
300_50_3 | 875788 | 875788 | 0.000 |  | 10 | 1.0 | 873068.30 | 874564 | 0.140 | 0.0 |  | 4 | 873757.50 | 875788 | 0.000 | 0.2 |  | 6 | 874591.60 | 875769 | 2.2E-3 | 0.0 |  | 5 | 875684.50 | 875788 | 0.000 | 0.3
300_50_4 | 307124 | 307124 | 0.000 |  | 10 | 1.0 | 306912.10 | 307124 | 0.000 | 0.1 |  | 4 | 305157.30 | 307124 | 0.000 | 0.2 |  | 9 | 307079.70 | 307124 | 0.000 | 0.5 |  | 7 | 307123.30 | 307124 | 0.000 | 0.9
300_50_5 | 727820 | 727820 | 0.000 |  | 9 | 1.0 | 727446.60 | 727820 | 0.000 | 0.1 |  | 5 | 727441.60 | 727820 | 0.000 | 0.2 |  | 10 | 727779.20 | 727820 | 0.000 | 0.7 |  | 10 | 727779.20 | 727820 | 0.000 | 0.7
300_50_6 | 734053 | 734053 | 0.000 |  | 8 | 1.0 | 730756.60 | 734053 | 0.000 | 0.1 |  | 5 | 733876.80 | 734053 | 0.000 | 0.3 |  | 8 | 732651.30 | 734053 | 0.000 | 0.2 |  | 5 | 734048.20 | 734053 | 0.000 | 0.8
300_50_7 | 43595 | 43595 | 0.000 |  | 8 | 1.0 | 43558.60 | 43595 | 0.000 | 0.2 |  | 8 | 43558.60 | 43595 | 0.000 | 0.2 |  | 4 | 43570.90 | 43595 | 0.000 | 0.6 |  | 4 | 43571.80 | 43595 | 0.000 | 0.6
300_50_8 | 767977 | 767977 | 0.000 |  | 8 | 1.0 | 767291.40 | 767937 | 5.2E-3 | 0.0 |  | 4 | 767869.30 | 767948 | 3.8E-3 | 0.0 |  | 10 | 767834.40 | 767977 | 0.000 | 0.1 |  | 3 | 767952.80 | 767977 | 0.000 | 0.4
300_50_9 | 761351 | 761351 | 0.000 |  | 7 | 0.6 | 732640.67 | 761007 | 0.045 | 0.0 |  | 4 | 761153.00 | 761351 | 0.000 | 0.2 |  | 10 | 760476.40 | 761351 | 0.000 | 0.1 |  | 2 | 761351.00 | 761351 | 0.000 | 1.0
300_50_10 | 996070 | 996070 | 0.000 |  | 7 | 1.0 | 977326.60 | 993922 | 0.216 | 0.0 |  | 5 | 994350.00 | 996069 | 1.0E-4 | 0.0 |  | 7 | 995135.60 | 996070 | 0.000 | 0.4 |  | 1 | 995605.10 | 996070 | 0.000 | 0.8

TABLE XIV: Full Results of Ising Machine on Large Instances (Greedy, AE, and
AE-I).

Instance | Greedy |  | AE |  | AE-I |
---|---|---|---|---|---|---
$n$_$d$_id | Best-known | Score | Gap |  | $a$ | FS | Mean | Best | Gap | SR |  | $a$ | FS | Mean | Best | Gap | SR
1000_25_1 | 6172407 | 6165313 | 0.115 |  | 8 | 1.0 | 6046565.20 | 6143481 | 0.469 | 0.0 |  | 7 | 1.0 | 6168157.90 | 6172407 | 0.000 | 0.1
1000_25_2 | 229941 | 229941 | 0.000 |  | 9 | 0.1 | 227137.00 | 227137 | 1.219 | 0.0 |  | 9 | 0.1 | 229057.00 | 229057 | 0.384 | 0.0
1000_25_3 | 172418 | 172362 | 0.032 |  | 8 | 0.1 | 118485.00 | 118485 | 31.280 | 0.0 |  | 8 | 0.1 | 137516.00 | 137516 | 20.243 | 0.0
1000_25_4 | 367426 | 367426 | 0.000 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_25_5 | 4885611 | 4884016 | 0.033 |  | 18 | 1.0 | 4794876.00 | 4865871 | 0.404 | 0.0 |  | 7 | 0.9 | 4882635.56 | 4885573 | 7.8E-4 | 0.0
1000_25_6 | 15689 | 15689 | 0.000 |  | 9 | 1.0 | 15689.00 | 15689 | 0.000 | 1.0 |  | 9 | 1.0 | 15689.00 | 15689 | 0.000 | 1.0
1000_25_7 | 4945810 | 4943898 | 0.039 |  | 5 | 0.9 | 4877049.44 | 4908591 | 0.753 | 0.0 |  | 4 | 0.9 | 4944271.78 | 4945810 | 0.000 | 0.1
1000_25_8 | 1710198 | 1709986 | 0.012 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_25_9 | 496315 | 496315 | 0.000 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_25_10 | 1173792 | 1173627 | 0.014 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_50_1 | 5663590 | 5663518 | 1.3E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_50_2 | 180831 | 180725 | 0.059 |  | 6 | 0.1 | 178358.00 | 178358 | 1.368 | 0.0 |  | 6 | 0.1 | 180220.00 | 180220 | 0.338 | 0.0
1000_50_3 | 11384283 | 11384182 | 8.9E-4 |  | 8 | 1.0 | 10942873.80 | 11304391 | 0.702 | 0.0 |  | 3 | 1.0 | 11384044.80 | 11384283 | 0.000 | 0.1
1000_50_4 | 322226 | 322170 | 0.017 |  | 9 | 0.1 | 314771.00 | 314771 | 2.314 | 0.0 |  | 9 | 0.1 | 320179.00 | 320179 | 0.635 | 0.0
1000_50_5 | 9984247 | 9983024 | 0.012 |  | 13 | 1.0 | 9756809.50 | 9932876 | 0.515 | 0.0 |  | 4 | 0.8 | 9981206.50 | 9984002 | 2.5E-3 | 0.0
1000_50_6 | 4106261 | 4105256 | 0.024 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_50_7 | 10498370 | 10497911 | 4.4E-3 |  | 5 | 1.0 | 10293633.60 | 10426694 | 0.683 | 0.0 |  | 2 | 0.9 | 10497958.56 | 10498370 | 0.000 | 0.1
1000_50_8 | 4981146 | 4978776 | 0.048 |  | 17 | 0.1 | 4858893.00 | 4858893 | 2.454 | 0.0 |  | 13 | 0.1 | 4978216.00 | 4978216 | 0.059 | 0.0
1000_50_9 | 1727861 | 1727861 | 0.000 |  | 10 | 0.1 | 1654507.00 | 1654507 | 4.245 | 0.0 |  | 10 | 0.1 | 1682796.00 | 1682796 | 2.608 | 0.0
1000_50_10 | 2340724 | 2340115 | 0.026 |  | 18 | 0.1 | 2332302.00 | 2332302 | 0.360 | 0.0 |  | 18 | 0.1 | 2336272.00 | 2336272 | 0.190 | 0.0
1000_75_1 | 11570056 | 11568107 | 0.017 |  | 14 | 0.7 | 11434541.71 | 11489586 | 0.696 | 0.0 |  | 17 | 0.8 | 11521261.50 | 11569868 | 1.6E-3 | 0.0
1000_75_2 | 1901389 | 1901083 | 0.016 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_75_3 | 2096485 | 2090674 | 0.277 |  | 19 | 0.3 | 1991055.00 | 2086915 | 0.456 | 0.0 |  | 20 | 0.3 | 2084592.33 | 2091367 | 0.244 | 0.0
1000_75_4 | 7305321 | 7305320 | 1.4E-5 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_75_5 | 13970842 | 13967977 | 0.021 |  | 16 | 1.0 | 13730507.30 | 13900932 | 0.500 | 0.0 |  | 8 | 1.0 | 13968979.30 | 13969760 | 7.7E-3 | 0.0
1000_75_6 | 12288738 | 12287677 | 8.6E-3 |  | 10 | 1.0 | 12106698.20 | 12171993 | 0.950 | 0.0 |  | 10 | 1.0 | 12285291.60 | 12288736 | 1.6E-5 | 0.0
1000_75_7 | 1095837 | 1093066 | 0.253 |  | 10 | 0.1 | 528554.00 | 528554 | 51.767 | 0.0 |  | 10 | 0.1 | 579407.00 | 579407 | 47.127 | 0.0
1000_75_8 | 5575813 | 5571863 | 0.071 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_75_9 | 695774 | 695060 | 0.103 |  | 10 | 0.1 | 692459.00 | 692459 | 0.476 | 0.0 |  | 10 | 0.1 | 694689.00 | 694689 | 0.156 | 0.0
1000_75_10 | 2507677 | 2507415 | 0.010 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_100_1 | 6243494 | 6240386 | 0.050 |  | 20 | 0.1 | 6237741.00 | 6237741 | 0.092 | 0.0 |  | 20 | 0.1 | 6241605.00 | 6241605 | 0.030 | 0.0
1000_100_2 | 4854086 | 4851219 | 0.059 |  | 19 | 0.2 | 4026639.50 | 4740591 | 2.338 | 0.0 |  | 19 | 0.2 | 4808609.50 | 4851243 | 0.059 | 0.0
1000_100_3 | 3172022 | 3169717 | 0.073 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_100_4 | 754727 | 754041 | 0.091 |  | 20 | 1.0 | 753275.30 | 754048 | 0.090 | 0.0 |  | 20 | 1.0 | 754459.30 | 754663 | 8.5E-3 | 0.0
1000_100_5 | 18646620 | 18644356 | 0.012 |  | 19 | 1.0 | 18411742.00 | 18553784 | 0.498 | 0.0 |  | 18 | 1.0 | 18612884.10 | 18646307 | 1.7E-3 | 0.0
1000_100_6 | 16020232 | 16019071 | 7.2E-3 |  | 10 | 0.5 | 15832101.20 | 15900553 | 0.747 | 0.0 |  | 8 | 0.6 | 16004784.50 | 16019644 | 3.7E-3 | 0.0
1000_100_7 | 12936205 | 12935892 | 2.4E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_100_8 | 6927738 | 6927088 | 9.4E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_100_9 | 3874959 | 3874666 | 7.6E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
1000_100_10 | 1334494 | 1333599 | 0.067 |  | 20 | 0.8 | 1331945.25 | 1332813 | 0.126 | 0.0 |  | 20 | 0.8 | 1333752.88 | 1334390 | 7.8E-3 | 0.0
2000_25_1 | 5268188 | 5268172 | 3.0E-4 |  | 19 | 0.1 | 4264680.00 | 4264680 | 19.048 | 0.0 |  | 19 | 0.1 | 5264179.00 | 5264179 | 0.076 | 0.0
2000_25_2 | 13294030 | 13292220 | 0.014 |  | 18 | 0.6 | 13197215.00 | 13238963 | 0.414 | 0.0 |  | 12 | 0.1 | 13293975.00 | 13293975 | 4.1E-4 | 0.0
2000_25_3 | 5500433 | 5499695 | 0.013 |  | 19 | 0.1 | 3862911.00 | 3862911 | 29.771 | 0.0 |  | 19 | 0.1 | 5492238.00 | 5492238 | 0.149 | 0.0
2000_25_4 | 14625118 | 14624957 | 1.1E-3 |  | 20 | 0.9 | 14438872.67 | 14558124 | 0.458 | 0.0 |  | 10 | 0.7 | 14621883.71 | 14625118 | 0.000 | 0.1
2000_25_5 | 5975751 | 5974429 | 0.022 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_25_6 | 4491691 | 4491649 | 9.4E-4 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_25_7 | 6388756 | 6388705 | 8.0E-4 |  | 20 | 0.1 | 5854140.00 | 5854140 | 8.368 | 0.0 |  | 20 | 0.1 | 6387505.00 | 6387505 | 0.020 | 0.0
2000_25_8 | 11769873 | 11767061 | 0.024 |  | 19 | 0.3 | 11534726.00 | 11722386 | 0.403 | 0.0 |  | 18 | 0.2 | 11768276.50 | 11768330 | 0.013 | 0.0
2000_25_9 | 10960328 | 10960313 | 1.4E-4 |  | 19 | 0.2 | 10577342.50 | 10900905 | 0.542 | 0.0 |  | 8 | 0.1 | 10960113.00 | 10960113 | 2.0E-3 | 0.0
2000_25_10 | 139236 | 139236 | 0.000 |  | 16 | 0.1 | 3945.00 | 3945 | 97.167 | 0.0 |  | 16 | 0.1 | 55528.00 | 55528 | 60.120 | 0.0
2000_50_1 | 7070736 | 7064882 | 0.083 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_50_2 | 12587545 | 12587266 | 2.2E-3 |  | 11 | 0.1 | 12276905.00 | 12276905 | 2.468 | 0.0 |  | 12 | 0.1 | 12585105.00 | 12585105 | 0.019 | 0.0
2000_50_3 | 27268336 | 27268336 | 0.000 |  | 20 | 0.7 | 26632622.14 | 27148430 | 0.440 | 0.0 |  | 11 | 0.2 | 27267716.50 | 27268037 | 1.1E-3 | 0.0
2000_50_4 | 17754434 | 17752803 | 9.2E-3 |  | 15 | 0.3 | 15946463.67 | 17665973 | 0.498 | 0.0 |  | 15 | 0.3 | 17750698.00 | 17752976 | 8.2E-3 | 0.0
2000_50_5 | 16806059 | 16803639 | 0.014 |  | 15 | 0.1 | 16161265.00 | 16161265 | 3.837 | 0.0 |  | 12 | 0.1 | 16802163.00 | 16802163 | 0.023 | 0.0
2000_50_6 | 23076155 | 23074597 | 6.8E-3 |  | 17 | 0.3 | 22841543.00 | 22867634 | 0.904 | 0.0 |  | 17 | 0.3 | 23062541.67 | 23074825 | 5.8E-3 | 0.0
2000_50_7 | 28759759 | 28756239 | 0.012 |  | 9 | 0.2 | 28600532.50 | 28600679 | 0.553 | 0.0 |  | 8 | 0.2 | 28756905.00 | 28757496 | 7.9E-3 | 0.0
2000_50_8 | 1580242 | 1580242 | 0.000 |  | 16 | 0.1 | 1206100.00 | 1206100 | 23.676 | 0.0 |  | 16 | 0.1 | 1282894.00 | 1282894 | 18.817 | 0.0
2000_50_9 | 26523791 | 26523221 | 2.1E-3 |  | 9 | 0.4 | 25837132.25 | 26348755 | 0.660 | 0.0 |  | 11 | 0.4 | 26521898.00 | 26523328 | 1.7E-3 | 0.0
2000_50_10 | 24747047 | 24747047 | 0.000 |  | 20 | 0.2 | 24559204.00 | 24630282 | 0.472 | 0.0 |  | 10 | 0.1 | 24746954.00 | 24746954 | 3.8E-4 | 0.0
2000_75_1 | 25121998 | 25119968 | 8.1E-3 |  | 17 | 0.1 | 24941261.00 | 24941261 | 0.719 | 0.0 |  | 13 | 0.2 | 25094179.50 | 25119908 | 8.3E-3 | 0.0
2000_75_2 | 12664670 | 12664008 | 5.2E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_75_3 | 43943994 | 43941916 | 4.7E-3 |  | 19 | 0.5 | 43299897.20 | 43678829 | 0.603 | 0.0 |  | 8 | 0.2 | 43943590.00 | 43943703 | 6.6E-4 | 0.0
2000_75_4 | 37496613 | 37496099 | 1.4E-3 |  | 20 | 0.4 | 33300362.50 | 37331383 | 0.441 | 0.0 |  | 9 | 0.1 | 37496271.00 | 37496271 | 9.1E-4 | 0.0
2000_75_5 | 24835349 | 24833545 | 7.3E-3 |  | 17 | 0.2 | 20223954.50 | 22728621 | 8.483 | 0.0 |  | 13 | 0.1 | 24832245.00 | 24832245 | 0.012 | 0.0
2000_75_6 | 45137758 | 45137758 | 0.000 |  | 10 | 0.4 | 44662139.25 | 44868910 | 0.596 | 0.0 |  | 5 | 0.2 | 45137345.00 | 45137758 | 0.000 | 0.1
2000_75_7 | 25502608 | 25502409 | 7.8E-4 |  | 15 | 0.1 | 24935633.00 | 24935633 | 2.223 | 0.0 |  | 18 | 0.1 | 25478168.00 | 25478168 | 0.096 | 0.0
2000_75_8 | 10067892 | 10067546 | 3.4E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_75_9 | 14177079 | 14169391 | 0.054 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_75_10 | 7815755 | 7813832 | 0.025 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_100_1 | 37929909 | 37929771 | 3.6E-4 |  | 17 | 0.2 | 35696999.50 | 37675871 | 0.670 | 0.0 |  | 8 | 0.1 | 37927936.00 | 37927936 | 5.2E-3 | 0.0
2000_100_2 | 33665281 | 33639083 | 0.078 |  | 12 | 0.2 | 28996903.50 | 32350573 | 3.905 | 0.0 |  | 8 | 0.2 | 33640008.00 | 33642902 | 0.066 | 0.0
2000_100_3 | 29952019 | 29949832 | 7.3E-3 |  | 11 | 0.1 | 29346552.00 | 29346552 | 2.021 | 0.0 |  | 12 | 0.1 | 29948550.00 | 29948550 | 0.012 | 0.0
2000_100_4 | 26949268 | 26947203 | 7.7E-3 |  | 15 | 0.1 | 26626386.00 | 26626386 | 1.198 | 0.0 |  | 14 | 0.2 | 26946246.00 | 26947244 | 7.5E-3 | 0.0
2000_100_5 | 22041715 | 22038689 | 0.014 |  | 19 | 0.1 | 20086249.00 | 20086249 | 8.872 | 0.0 |  | 19 | 0.1 | 22035826.00 | 22035826 | 0.027 | 0.0
2000_100_6 | 18868887 | 18867393 | 7.9E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_100_7 | 15850597 | 15848026 | 0.016 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_100_8 | 13628967 | 13628029 | 6.9E-3 |  | - | 0 | - | - | - | - |  | - | 0 | - | - | - | -
2000_100_9 | 8394562 | 8388596 | 0.071 |  | 19 | 0.1 | 7097454.00 | 7097454 | 15.452 | 0.0 |  | 19 | 0.1 | 7249975.00 | 7249975 | 13.635 | 0.0
2000_100_10 | 4923559 | 4921159 | 0.049 |  | 18 | 0.1 | 3111936.00 | 3111936 | 36.795 | 0.0 |  | 15 | 0.1 | 3291205.00 | 3291205 | 33.154 | 0.0

TABLE XV: Full Results of Ising Machine on Large Instances (Gurobi, AE-R, and
AE-RI).

Instance | Gurobi |  | AE-R |  | AE-RI
---|---|---|---|---|---
$n$_$d$_id | Best-known | Score | Gap |  | $a$ | Mean | Best | Gap | SR |  | $a$ | Mean | Best | Gap | SR
1000_25_1 | 6172407 | 6172407 | 0.000 |  | 4 | 6129734.5 | 6164169 | 0.133 | 0.0 |  | 7 | 6168834.5 | 6172407 | 0.000 | 0.2
1000_25_2 | 229941 | 229941 | 0.000 |  | 1 | 228355.2 | 229902 | 0.017 | 0.0 |  | 1 | 229933.5 | 229941 | 0.000 | 0.9
1000_25_3 | 172418 | 172418 | 0.000 |  | 6 | 172418.0 | 172418 | 0.000 | 1.0 |  | 6 | 172418.0 | 172418 | 0.000 | 1.0
1000_25_4 | 367426 | 367426 | 0.000 |  | 7 | 365784.3 | 367014 | 0.112 | 0.0 |  | 1 | 367426.0 | 367426 | 0.000 | 1.0
1000_25_5 | 4885611 | 4885611 | 0.000 |  | 6 | 4884277.2 | 4885538 | 1.5E-3 | 0.0 |  | 4 | 4885138.5 | 4885611 | 0.000 | 0.1
1000_25_6 | 15689 | 15689 | 0.000 |  | 5 | 15689.0 | 15689 | 0.000 | 1.0 |  | 1 | 15689.0 | 15689 | 0.000 | 1.0
1000_25_7 | 4945810 | 4945810 | 0.000 |  | 4 | 4943097.0 | 4945810 | 0.000 | 0.1 |  | 4 | 4945608.4 | 4945810 | 0.000 | 0.3
1000_25_8 | 1710198 | 1710132 | 3.9E-3 |  | 7 | 1709246.1 | 1710017 | 0.011 | 0.0 |  | 10 | 1710007.7 | 1710198 | 0.000 | 0.3
1000_25_9 | 496315 | 496315 | 0.000 |  | 6 | 496304.9 | 496315 | 0.000 | 0.9 |  | 5 | 496315.0 | 496315 | 0.000 | 1.0
1000_25_10 | 1173792 | 1173789 | 2.6E-4 |  | 2 | 1172790.6 | 1173694 | 8.3E-3 | 0.0 |  | 10 | 1173639.3 | 1173792 | 0.000 | 0.1
1000_50_1 | 5663590 | 5663590 | 0.000 |  | 6 | 5663158.6 | 5663590 | 0.000 | 0.1 |  | 6 | 5663574.2 | 5663590 | 0.000 | 0.7
1000_50_2 | 180831 | 180831 | 0.000 |  | 10 | 179702.8 | 180831 | 0.000 | 0.2 |  | 5 | 180831.0 | 180831 | 0.000 | 1.0
1000_50_3 | 11384283 | 11384283 | 0.000 |  | 4 | 11354296.1 | 11384247 | 3.2E-4 | 0.0 |  | 5 | 11384256.1 | 11384283 | 0.000 | 0.7
1000_50_4 | 322226 | 322226 | 0.000 |  | 10 | 320732.0 | 322222 | 1.2E-3 | 0.0 |  | 9 | 322220.4 | 322226 | 0.000 | 0.9
1000_50_5 | 9984247 | 9984155 | 9.2E-4 |  | 5 | 9979380.1 | 9983164 | 0.011 | 0.0 |  | 5 | 9983901.4 | 9984155 | 9.2E-4 | 0.0
1000_50_6 | 4106261 | 4106261 | 0.000 |  | 6 | 4104720.9 | 4106084 | 4.3E-3 | 0.0 |  | 4 | 4106142.3 | 4106261 | 0.000 | 0.8
1000_50_7 | 10498370 | 10498370 | 0.000 |  | 6 | 10485633.4 | 10498272 | 9.3E-4 | 0.0 |  | 6 | 10498331.4 | 10498370 | 0.000 | 0.6
1000_50_8 | 4981146 | 4981143 | 6.0E-5 |  | 12 | 4978197.9 | 4979892 | 0.025 | 0.0 |  | 16 | 4979493.7 | 4980274 | 0.018 | 0.0
1000_50_9 | 1727861 | 1727861 | 0.000 |  | 6 | 1724044.1 | 1727861 | 0.000 | 0.6 |  | 6 | 1727861.0 | 1727861 | 0.000 | 1.0
1000_50_10 | 2340724 | 2340724 | 0.000 |  | 16 | 2339432.1 | 2340724 | 0.000 | 0.1 |  | 16 | 2340023.7 | 2340724 | 0.000 | 0.3
1000_75_1 | 11570056 | 11570056 | 0.000 |  | 11 | 11544807.4 | 11568936 | 9.7E-3 | 0.0 |  | 6 | 11569740.8 | 11570055 | 8.6E-6 | 0.0
1000_75_2 | 1901389 | 1901389 | 0.000 |  | 5 | 1894235.8 | 1901231 | 8.3E-3 | 0.0 |  | 10 | 1899475.3 | 1901389 | 0.000 | 0.5
1000_75_3 | 2096485 | 2096485 | 0.000 |  | 16 | 2093204.3 | 2096485 | 0.000 | 0.1 |  | 16 | 2096471.0 | 2096485 | 0.000 | 0.8
1000_75_4 | 7305321 | 7305315 | 8.2E-5 |  | 5 | 7292449.8 | 7304592 | 0.010 | 0.0 |  | 6 | 7305152.0 | 7305321 | 0.000 | 0.5
1000_75_5 | 13970842 | 13970842 | 0.000 |  | 13 | 13941909.1 | 13968310 | 0.018 | 0.0 |  | 10 | 13969208.3 | 13969984 | 6.1E-3 | 0.0
1000_75_6 | 12288738 | 12288738 | 0.000 |  | 6 | 12287280.1 | 12288115 | 5.1E-3 | 0.0 |  | 1 | 12288438.5 | 12288738 | 0.000 | 0.4
1000_75_7 | 1095837 | 1095837 | 0.000 |  | 7 | 1092604.3 | 1093131 | 0.247 | 0.0 |  | 4 | 1093343.1 | 1095837 | 0.000 | 0.1
1000_75_8 | 5575813 | 5575813 | 0.000 |  | 6 | 5574312.1 | 5575811 | 3.6E-5 | 0.0 |  | 15 | 5575505.5 | 5575813 | 0.000 | 0.4
1000_75_9 | 695774 | 695767 | 1.0E-3 |  | 5 | 694039.0 | 695064 | 0.102 | 0.0 |  | 5 | 695496.2 | 695774 | 0.000 | 0.1
1000_75_10 | 2507677 | 2507677 | 0.000 |  | 6 | 2506795.2 | 2507677 | 0.000 | 0.1 |  | 6 | 2507567.5 | 2507677 | 0.000 | 0.5
1000_100_1 | 6243494 | 6243494 | 0.000 |  | 11 | 6238463.1 | 6242478 | 0.016 | 0.0 |  | 11 | 6243143.8 | 6243494 | 0.000 | 0.1
1000_100_2 | 4854086 | 4854086 | 0.000 |  | 14 | 4851616.1 | 4852477 | 0.033 | 0.0 |  | 15 | 4853764.5 | 4854043 | 8.9E-4 | 0.0
1000_100_3 | 3172022 | 3172022 | 0.000 |  | 6 | 3169655.3 | 3170376 | 0.052 | 0.0 |  | 7 | 3171416.8 | 3172022 | 0.000 | 0.5
1000_100_4 | 754727 | 754539 | 0.025 |  | 12 | 754120.8 | 754645 | 0.011 | 0.0 |  | 12 | 754591.7 | 754727 | 0.000 | 0.2
1000_100_5 | 18646620 | 18646607 | 7.0E-5 |  | 11 | 18601616.7 | 18643031 | 0.019 | 0.0 |  | 9 | 18645693.5 | 18646535 | 4.6E-4 | 0.0
1000_100_6 | 16020232 | 16020232 | 0.000 |  | 5 | 16012775.7 | 16016672 | 0.022 | 0.0 |  | 5 | 16019834.7 | 16020232 | 0.000 | 0.3
1000_100_7 | 12936205 | 12936205 | 0.000 |  | 6 | 12935073.5 | 12936083 | 9.4E-4 | 0.0 |  | 5 | 12928785.2 | 12936205 | 0.000 | 0.4
1000_100_8 | 6927738 | 6927671 | 9.7E-4 |  | 6 | 6925298.8 | 6925940 | 0.026 | 0.0 |  | 6 | 6927168.3 | 6927606 | 1.9E-3 | 0.0
1000_100_9 | 3874959 | 3874959 | 0.000 |  | 4 | 3874196.9 | 3874959 | 0.000 | 0.1 |  | 6 | 3874917.8 | 3874959 | 0.000 | 0.8
1000_100_10 | 1334494 | 1334494 | 0.000 |  | 13 | 1333903.0 | 1334457 | 2.8E-3 | 0.0 |  | 11 | 1334474.0 | 1334494 | 0.000 | 0.5
2000_25_1 | 5268188 | 5268188 | 0.000 |  | 8 | 5267547.6 | 5268188 | 0.000 | 0.2 |  | 8 | 5268171.6 | 5268188 | 0.000 | 0.4
2000_25_2 | 13294030 | 13293975 | 4.1E-4 |  | 5 | 13281482.0 | 13293956 | 5.6E-4 | 0.0 |  | 12 | 13293730.1 | 13293975 | 4.1E-4 | 0.0
2000_25_3 | 5500433 | 5500411 | 4.0E-4 |  | 13 | 5497914.6 | 5499944 | 8.9E-3 | 0.0 |  | 7 | 5499740.7 | 5500403 | 5.5E-4 | 0.0
2000_25_4 | 14625118 | 14625031 | 5.9E-4 |  | 13 | 14620474.6 | 14624980 | 9.4E-4 | 0.0 |  | 8 | 14625069.6 | 14625118 | 0.000 | 0.3
2000_25_5 | 5975751 | 5975751 | 0.000 |  | 13 | 5973488.1 | 5975675 | 1.3E-3 | 0.0 |  | 13 | 5975276.2 | 5975751 | 0.000 | 0.3
2000_25_6 | 4491691 | 4491635 | 1.2E-3 |  | 12 | 4485267.1 | 4491630 | 1.4E-3 | 0.0 |  | 10 | 4491691.0 | 4491691 | 0.000 | 1.0
2000_25_7 | 6388756 | 6388756 | 0.000 |  | 13 | 6388445.2 | 6388756 | 0.000 | 0.2 |  | 13 | 6388744.1 | 6388756 | 0.000 | 0.7
2000_25_8 | 11769873 | 11769873 | 0.000 |  | 2 | 11757436.7 | 11769873 | 0.000 | 0.1 |  | 11 | 11769820.5 | 11769873 | 0.000 | 0.7
2000_25_9 | 10960328 | 10960263 | 5.9E-4 |  | 3 | 10952474.0 | 10960207 | 1.1E-3 | 0.0 |  | 11 | 10960066.9 | 10960328 | 0.000 | 0.1
2000_25_10 | 139236 | 139236 | 0.000 |  | 16 | 138459.9 | 139236 | 0.000 | 0.2 |  | 1 | 139236.0 | 139236 | 0.000 | 1.0
2000_50_1 | 7070736 | 7070736 | 0.000 |  | 12 | 7062808.2 | 7070341 | 5.6E-3 | 0.0 |  | 12 | 7068396.4 | 7070736 | 0.000 | 0.2
2000_50_2 | 12587545 | 12587545 | 0.000 |  | 12 | 12586350.3 | 12587482 | 5.0E-4 | 0.0 |  | 12 | 12587507.0 | 12587545 | 0.000 | 0.7
2000_50_3 | 27268336 | 27268336 | 0.000 |  | 3 | 27268335.2 | 27268336 | 0.000 | 0.9 |  | 3 | 27268336.0 | 27268336 | 0.000 | 1.0
2000_50_4 | 17754434 | 17754388 | 2.6E-4 |  | 12 | 17752283.1 | 17753673 | 4.3E-3 | 0.0 |  | 12 | 17754087.3 | 17754434 | 0.000 | 0.1
2000_50_5 | 16806059 | 16805435 | 3.7E-3 |  | 11 | 16801525.3 | 16804057 | 0.012 | 0.0 |  | 12 | 16804680.5 | 16805490 | 3.4E-3 | 0.0
2000_50_6 | 23076155 | 23076097 | 2.5E-4 |  | 12 | 23074405.9 | 23075875 | 1.2E-3 | 0.0 |  | 11 | 23075852.7 | 23076155 | 0.000 | 0.2
2000_50_7 | 28759759 | 28759759 | 0.000 |  | 11 | 27410959.4 | 28756657 | 0.011 | 0.0 |  | 10 | 28757135.3 | 28757834 | 6.7E-3 | 0.0
2000_50_8 | 1580242 | 1580242 | 0.000 |  | 11 | 1577163.4 | 1580242 | 0.000 | 0.3 |  | 1 | 1580242.0 | 1580242 | 0.000 | 1.0
2000_50_9 | 26523791 | 26523791 | 0.000 |  | 8 | 26519303.3 | 26523462 | 1.2E-3 | 0.0 |  | 7 | 26523472.8 | 26523791 | 0.000 | 0.2
2000_50_10 | 24747047 | 24747047 | 0.000 |  | 8 | 24743522.7 | 24746936 | 4.5E-4 | 0.0 |  | 1 | 24747047.0 | 24747047 | 0.000 | 1.0
2000_75_1 | 25121998 | 25121998 | 0.000 |  | 11 | 25120313.9 | 25121457 | 2.2E-3 | 0.0 |  | 11 | 25121744.4 | 25121998 | 0.000 | 0.4
2000_75_2 | 12664670 | 12664670 | 0.000 |  | 11 | 12656539.5 | 12664244 | 3.4E-3 | 0.0 |  | 10 | 12662072.5 | 12664670 | 0.000 | 0.4
2000_75_3 | 43943994 | 43943994 | 0.000 |  | 16 | 43800921.7 | 43943366 | 1.4E-3 | 0.0 |  | 8 | 43943724.9 | 43943994 | 0.000 | 0.6
2000_75_4 | 37496613 | 37496613 | 0.000 |  | 3 | 37493330.7 | 37496308 | 8.1E-4 | 0.0 |  | 2 | 37496367.3 | 37496613 | 0.000 | 0.2
2000_75_5 | 24835349 | 24835349 | 0.000 |  | 11 | 24828628.7 | 24831592 | 0.015 | 0.0 |  | 11 | 24834632.9 | 24834948 | 1.6E-3 | 0.0
2000_75_6 | 45137758 | 45137758 | 0.000 |  | 3 | 45132276.3 | 45137758 | 0.000 | 0.9 |  | 8 | 45137758.0 | 45137758 | 0.000 | 1.0
2000_75_7 | 25502608 | 25502608 | 0.000 |  | 12 | 25467707.7 | 25502608 | 0.000 | 0.1 |  | 4 | 25495828.7 | 25502608 | 0.000 | 0.3
2000_75_8 | 10067892 | 10067892 | 0.000 |  | 11 | 10064140.4 | 10067750 | 1.4E-3 | 0.0 |  | 10 | 10063814.3 | 10067892 | 0.000 | 0.3
2000_75_9 | 14177079 | 14177079 | 0.000 |  | 11 | 14163838.4 | 14168633 | 0.060 | 0.0 |  | 14 | 14171401.8 | 14171994 | 0.036 | 0.0
2000_75_10 | 7815755 | 7815334 | 5.4E-3 |  | 12 | 7811373.0 | 7812703 | 0.039 | 0.0 |  | 20 | 7814965.3 | 7815611 | 1.8E-3 | 0.0
2000_100_1 | 37929909 | 37929909 | 0.000 |  | 4 | 37926908.4 | 37929909 | 0.000 | 0.1 |  | 12 | 37929518.3 | 37929909 | 0.000 | 0.6
2000_100_2 | 33665281 | 33665281 | 0.000 |  | 12 | 32835326.4 | 33637892 | 0.081 | 0.0 |  | 12 | 33644437.0 | 33646541 | 0.056 | 0.0
2000_100_3 | 29952019 | 29951413 | 2.0E-3 |  | 12 | 29553629.4 | 29948391 | 0.012 | 0.0 |  | 10 | 29951436.0 | 29952019 | 0.000 | 0.1
2000_100_4 | 26949268 | 26948616 | 2.4E-3 |  | 13 | 26943483.1 | 26947024 | 8.3E-3 | 0.0 |  | 11 | 26948996.6 | 26949268 | 0.000 | 0.2
2000_100_5 | 22041715 | 22041314 | 1.8E-3 |  | 11 | 22032284.4 | 22034438 | 0.033 | 0.0 |  | 17 | 22038647.2 | 22041221 | 2.2E-3 | 0.0
2000_100_6 | 18868887 | 18868887 | 0.000 |  | 10 | 18834013.3 | 18868626 | 1.4E-3 | 0.0 |  | 10 | 18866428.5 | 18868887 | 0.000 | 0.2
2000_100_7 | 15850597 | 15850597 | 0.000 |  | 10 | 15847566.7 | 15848960 | 0.010 | 0.0 |  | 11 | 15850259.2 | 15850594 | 1.9E-5 | 0.0
2000_100_8 | 13628967 | 13628967 | 0.000 |  | 12 | 13622163.4 | 13626547 | 0.018 | 0.0 |  | 12 | 13628850.7 | 13628967 | 0.000 | 0.4
2000_100_9 | 8394562 | 8394101 | 5.5E-3 |  | 11 | 8388749.0 | 8390723 | 0.046 | 0.0 |  | 20 | 8394196.6 | 8394562 | 0.000 | 0.4
2000_100_10 | 4923559 | 4923387 | 3.5E-3 |  | 13 | 4918213.2 | 4919752 | 0.077 | 0.0 |  | 14 | 4922601.9 | 4923470 | 1.8E-3 | 0.0

(a) $n=1000,d=25$

(b) $n=1000,d=50$

(c) $n=1000,d=75$

(d) $n=1000,d=100$

(e) $n=2000,d=25$

(f) $n=2000,d=50$

(g) $n=2000,d=75$

(h) $n=2000,d=100$

Figure 7:  Aggregated optimality gap for AE-RI on all 80 large QKP instances.
Color bar for gap is shown in log scale. Zero gap (i.e. 100% success rate) is
shown in black. Instances are sorted with tightness ratio
$\alpha=C/\sum_{i}w_{i}$ for each combination of problem size $n$ and density
$d$. Note that penalty coefficient is rescaled and x-axis actually denotes $a$
in Eq. (18). Due to this rescaling, we see less trends in distribution of good
penalty coefficient than Fig. 6.

###  B-B Results on Ising Machine

Full results of the benchmark of AE conducted in Section V are shown in Table
XIII, XIV and XV. Legends for columns are the same as those in Table XI except
for the optimal penalty coefficient $\lambda$. As we rescaled $\lambda$ as in
Eq. (18), the value of $\lambda$ is defined according to the value of $a$ in
Eq. (18). Therefore, we report the value of $a$ giving the optimal $\lambda$.
Since there are several large instances on which AE cannot obtain feasible a
solution even with $a=20$, the results on those instances are not reported.

We also plot the aggregated optimality gap for AE-RI on each instance in Fig.
7. We observe that the tested range of penalty coefficients seems to cover
optimal coefficients on most instances. Note that the x-axis corresponds to
values of $a$ in Eq. (18), not $\lambda$. Due to the rescaling of $\lambda$,
we see less visual trends in Figure 7 compared to Fig. 6. This indicates that
the rescaling based on SA analysis also works well when using the Ising
machine for large-scale instances.