# MeV gamma rays from Q-ball decay

Shinta Kasuyaa, Masahiro Kawasakib,c, Naomi Tsujia,d a Physics Division,
Faculty of Science, Kanagawa University, Kanagawa 221-8686, Japan
b Institute for Cosmic Ray Research, the University of Tokyo, Chiba 277-8582,
Japan
c Kavli Institute for the Physics and Mathematics of the Universe (WPI), Todai
Institutes for Advanced Study, the University of Tokyo, Chiba 277-8582, Japan
d Interdisciplinary Theoretical and Mathematical Science Program (iTHEMS),
RIKEN, Saitama 351-0198, Japan

(March 4, 2024)

###### Abstract

We study the supersymmetric Q balls which decay at present and find that they
create a distinctive spectrum of gamma rays at around O(10) MeV. The charge of
the Q ball is lepton numbers in order for the lifetime to be as long as the
present age of the universe, and the main decay products are light leptons.
However, as the charge of the Q ball decreases, the decay channel into pions
becomes kinematically allowed towards the end of the decay, and the pions are
produced at rest. Immediately, $\pi^{0}$ decays into two photons with the
energy of 67.5 MeV, half the pion mass, which exhibits a unique emission line.
In addition, $\pi^{\pm}$ decay into $\mu^{\pm}$, which further decay with
emitting internal bremsstrahlung, whose spectrum has a sharp cutoff at
$\sim$50 MeV. If the observations would find these peculiar features of the
gamma-ray spectrum in the future, it could be a smoking gun of the
supersymmetric Q-ball decay at present.

##  I Introduction

There exist non-topological solitons, Q balls Coleman:1985ki , which consist
of scalar fields such as squarks and sleptons in supersymmetric theories
Kusenko:1997zq . Q balls with large charge can form after inflation
Kusenko:1997si ; Kasuya:1999wu  à la Affleck-Dine Affleck:1984fy . Large Q
balls with $Q$ being the baryon number are stable against the decay into
nucleons, and could be dark matter of the universe Kusenko:1997si . Such Q
ball dark matter may be detected in the large volume detectors Kusenko:1997vp
; Arafune:2000yv ; Kasuya:2001hg ; Kasuya:2015uka . If detected, it is not
only the detection of the dark matter, but also might be the observational
clue of the supersymmetry (SUSY).

On the other hand, large Q balls with lepton charge is not stable against the
decay into light leptons, but they could long lived. Their decay leaves some
observational consequences such that they may result in the source of the 511
keV line gamma rays from the galactic center Kasuya:2005ay , provide late-time
entropy production Kasuya:2007cy , or enhance the secondary gravitational
waves Kasuya:2022cko ; Kawasaki:2023rfx .

Here we study yet another way to find the observational trace of SUSY Q balls
with $Q$ being the lepton number. We look for clues of the Q balls whose
lifetime is just as long as the present age of the universe. Since the charge
of the Q ball (lepton number in this case) should be very large for such
lifetime, the mass per unit charge is a little bit larger than the electron
(positron) mass. Therefore, Q balls decay into neutrinos, anti-neutrinos,
electrons, and positrons in the first place, decreasing the Q-ball charge. As
the charge gets smaller, the mass per unit charge becomes larger, and finally
the decay channels to pions open up towards the end of the decay, and hence
the pions are produced almost at rest. This is the unique feature of the
Q-ball decay.

Produced pions decay immediately. Neutral pions decay into two photons with
the energy of half the pion mass, which shows a 67.5 MeV emission line, while
charged pions decay into muons, which further decay emitting photons through
internal bremsstrahlung (IB). The resulting spectrum of the photons has such
peculiar features in the 1–100 MeV range.

The structure of the paper is as follows. In the next section, we provide
basic characters of the Q ball considered in this paper. In Sec.III, we
investigate the process of the decreasing charge $Q$ for the Q-ball decay at
present, and consider the decay products and their fractions in Sec. IV. In
Sec.V, we estimate the gamma-ray spectra produced by the Q-ball decay for both
the galactic and extragalactic emissions. Finally we conclude in Sec. VI. We
explain the internal bremsstrahlung in pion and muon decays in App.A, and the
upper bound on Q-ball abundance in App.B.

##  II Q balls in the gauge mediation

The Q ball is the energy minimum configuration of the scalar fields for the
fixed charge $Q$ Coleman:1985ki . Those scalar fields $\Phi$, called flat
directions, are all classified in terms of gauge-invariant monomials in the
minimal supersymmetric standard model Gherghetta:1995dv ; Dine:1995kz . In the
gauge-mediated SUSY breaking scenario, the scalar potential is written as

$V(\Phi)=M_{F}^{4}\left(\log\frac{|\Phi|^{2}}{M_{S}^{2}}\right)^{2}+m_{3/2}^{2}\left(1+K\log\frac{|\Phi|^{2}}{M_{\rm
P}^{2}}\right)|\Phi|^{2},$ (1)

where $m_{3/2}$ is the gravitino mass and $M_{\rm P}=2.4\times 10^{18}$ GeV is
the Planck mass. The first term comes from the gauge-mediation effects above
the messenger scale $M_{S}$ deGouvea:1997afu . $M_{F}$ is related to the $F$
component of a gauge-singlet chiral multiplet in the messenger sector, and its
range is given by Kasuya:2015uka

$4\times 10^{4}~{}{\rm GeV}\lesssim M_{F}\lesssim 0.1\left(m_{3/2}M_{\rm
P}\right)^{1/2}.$ (2)

The second term is due to the gravity-mediation effects. Here, $K$ is a
coefficient of the one-loop corrections to the mass, and negative for most of
the flat directions with $|K|=$0.01–0.1. Since the gravitino mass is
relatively small in the gauge-mediation models, the second term dominates over
the first one for field values larger than

$\phi_{\rm eq}\simeq\frac{\sqrt{2}M_{F}^{2}}{m_{3/2}},$ (3)

where we define $\Phi=\frac{1}{\sqrt{2}}\phi e^{i\theta}$.

There are two types of the Q ball depending on which term of the potential is
dominant when it forms. If the first term of Eq.(1) dominates the potential,
the gauge-mediation type Q balls are created, while the so-called new-type Q
balls are produced when the second term overwhelms the first Kasuya:2000sc .
The important property which concerns with following discussion is the mass
per unit charge of the Q ball, $\omega_{Q}$, equivalent to the effective mass
of $\Phi$ inside the Q ball:

$\omega_{Q}\simeq\left\\{\begin{array}[]{ll}\sqrt{2}\pi\zeta
M_{F}Q^{-1/4}&({\rm gauge\mbox{\scriptsize-}med.\ type}),\\\\[5.69054pt]
m_{3/2}&({\rm new\ type}),\end{array}\right.$ (4)

where $\zeta\simeq 2.5$ Hisano:2001dr .

As shown later, we need very large charge $Q$ so that the new-type Q balls
form for the field amplitude well above $\phi_{eq}$. The charge of the Q ball
is thus estimated as Kasuya:2000wx

$Q=\beta_{N}\left(\frac{\phi_{0}}{m_{3/2}}\right)^{2},$ (5)

where $\beta_{N}\simeq 0.01$ Hiramatsu:2010dx , and $\phi_{0}$ is the
amplitude of $\Phi$ at the beginning of its oscillations. The mass and size of
this type of the Q ball are given respectively by Enqvist:1998en ;
Kasuya:2000sc

$M_{Q}\simeq m_{3/2}Q,\quad R_{Q}\simeq|K|^{-1/2}m_{3/2}^{-1}.$ (6)

##  III Q-ball decay

Q-ball decay occurs if some decay particles carry the same kind of the charge
of the Q ball and the mass of all the decay particles is less than the mass of
the Q ball per unit charge $\omega_{Q}$. Since the decay products carrying
lepton numbers are light fermions, once the Fermi sea is filled, further decay
proceeds only when produced fermions escape from the surface of the Q ball.
The upper bound of the decay rate is thus determined by the maximum outgoing
flow of the fermions Cohen:1986ct . This saturation occurs when the field
value is large inside the Q ball, which is the case here. Then the decay rate
is estimated as Cohen:1986ct

$\Gamma_{Q}\simeq\frac{1}{Q}\frac{\omega_{Q}^{3}}{192\pi^{2}}4\pi
R_{Q}^{2}\simeq\frac{m_{3/2}}{48\pi|K|Q},$ (7)

where we use Eq.(6) in the last equality. Since we consider the Q balls that
decay at present, its lifetime is set to be $\tau_{Q}=\Gamma_{Q}^{-1}\simeq
t_{0}\simeq 13.8$ Gyr, which leads to the charge of the Q ball as

$Q\simeq 2.2\times
10^{38}\left(\frac{|K|}{0.02}\right)^{-1}\left(\frac{m_{3/2}}{\rm
MeV}\right).$ (8)

From Eqs.(5) and (8), we obtain the charge of the formed new-type Q ball and
the gravitino mass respectively as

$Q_{\rm D}\simeq 6.3\times
10^{38}\left(\frac{\beta_{N}}{0.01}\right)^{1/3}\left(\frac{|K|}{0.02}\right)^{-2/3}\left(\frac{\phi_{0}}{0.3M_{\rm
P}}\right)^{2/3},$ (9) $m_{3/2}\simeq 2.9~{}{\rm
MeV}\left(\frac{\beta_{N}}{0.01}\right)^{1/3}\left(\frac{|K|}{0.02}\right)^{1/3}\left(\frac{\phi_{0}}{0.3M_{\rm
P}}\right)^{2/3}.$ (10)

Notice that the scenario works for broader parameter space, but here we take
$\phi_{0}=0.3M_{\rm P}$ and $|K|=0.02$ as a typical example.111For the
gravitino mass smaller than 100 keV, the gauge-mediation type Q balls can form
and decay at present to produce same signatures of MeV gamma rays.

As the charge of the Q ball decreases, the new-type Q ball transforms into the
gauge-mediation type Kasuya:2009by  when the charge becomes

$Q_{\rm tr}\simeq 4\left(\frac{M_{F}}{m_{3/2}}\right)^{4}\simeq 2.8\times
10^{38}\left(\frac{m_{3/2}}{2.9~{}{\rm MeV}}\right)^{-2},$ (11)

where we use the upper bound of $M_{F}$ in Eq.(2) in the second equality.
Thereafter, $\omega_{Q}$ increases as the charge diminishes as in the upper
line in Eq.(4). Since pions consist of quark and anti-quark pairs, the decay
channel to pions opens when $\omega_{Q}=m_{\pi}/2$, where the charge of the Q
ball becomes

$Q_{\pi}\simeq\left(\frac{2\sqrt{2}\pi\zeta}{m_{\pi}}\right)^{4}M_{F}^{4}\simeq
3.0\times 10^{36}\left(\frac{m_{3/2}}{2.9~{}{\rm MeV}}\right)^{2}.$ (12)

Here the upper bound of $M_{F}$ in Eq.(2) is used in the last equality. As the
decay into pions has just come to be kinematically allowed at that time, pions
are produced at rest. This is the unique property of the Q-ball decay.

In Fig. 1, we show the evolution of the charge of the Q ball by the purple
arrow. Here we plot the charge at the formation (5), that for the decay at
present (8), that when the transformation from the new-type into the gauge-
mediation type takes place (11), and that when the decay channel to pions
opens (12) as the function of $m_{3/2}$, for $\phi_{0}=0.3M_{\rm P}$ and
$|K|=0.02$.

Figure 1: Evolution of the Q-ball charge is shown in the purple arrow. We show
the charge at the formation (5), that for the decay at present (8), that when
the transformation from the new-type into the gauge-mediation type takes place
(11), and that when the decay channel to pions opens (12) as the function of
$m_{3/2}$, for $\phi_{0}=0.3M_{\rm P}$ and $|K|=0.02$, in blue, red, magenta,
and green lines, respectively.

##  IV Decay products

We must identify the particles emitted by the Q-ball decay. To this end, we
choose the $\Phi^{5}={\cal Q}u{\cal Q}ue$ direction as a concrete example
below.222Similar argument holds in other leptonic directions. ${\cal Q}$
represents SU(2)L-doublet squarks, $u$ and $e$ are SU(2)L-singlet squarks and
sleptons, respectively. We further assume that they consist only of the fields
in the first generation, so that it can be written as
$\tilde{u}_{L}\tilde{u}_{R}^{*}\tilde{d}_{L}\tilde{u}_{R}^{*}\tilde{e}_{R}^{*}$.
Since this direction carries lepton number $L=-1$, the field $\Phi$ possesses
$L=-1/5$.

In the process of the Q-ball decay, all the decay particles must have masses
smaller than $\omega_{Q}$, and some should carry anti-lepton numbers. In
addition, the electric charge neutrality holds through the decay process,
since the Q ball consists of the flat direction which is gauge invariant. Thus
the composition changes before and after the decay channel into pions opens.
Before that time, it is kinematically allowed to decay only into electrons,
positrons, neutrinos, and anti-neutrinos.333The branching ratio to photons can
be extremely suppressed due to the very small left-right mixings for squarks
and sleptons for the first and second generations Martin:1997ns . Selectrons
$\tilde{e}_{R}^{*}$ carrying anti-lepton number decay into anti-electron
neutrinos $\bar{\nu}_{e}$. Since the Q-ball decay is saturated, there is no
phase space left for $\bar{\nu}_{e}$ to be further produced. Therefore, the
other decay particles are the following six patterns of combinations:
$\nu_{\mu}\bar{\nu}_{\mu}\nu_{\mu}\bar{\nu}_{\mu}$,
$\nu_{\mu}\bar{\nu}_{\mu}\nu_{\tau}\bar{\nu}_{\tau}$,
$\nu_{\tau}\bar{\nu}_{\tau}\nu_{\tau}\bar{\nu}_{\tau}$,
$\nu_{\mu}\bar{\nu}_{\mu}e^{+}e^{-}$, $\nu_{\tau}\bar{\nu}_{\tau}e^{+}e^{-}$,
and $e^{+}e^{-}e^{+}e^{-}$.

On the other hand, after the decay into pions are kinematically allowed, anti-
lepton numbers could be conveyed by $e^{+}$, in addition to $\bar{\nu}_{e}$,
since $\pi^{-}$ exists in the decay particles to compensate the electric
charge of positrons. The phase spaces of produced $\bar{\nu}_{e}$ and $e^{+}$
are filled by the saturated decay so that they cannot be included in the
remaining decay particles. In the case of $\bar{\nu}_{e}$, the combinations of
other decay particles are $\nu_{\mu}\bar{\nu}_{\mu}\nu_{\mu}\bar{\nu}_{\mu}$,
$\nu_{\mu}\bar{\nu}_{\mu}\nu_{\tau}\bar{\nu}_{\tau}$,
$\nu_{\tau}\bar{\nu}_{\tau}\nu_{\tau}\bar{\nu}_{\tau}$, $\pi^{+}\nu_{e}e^{-}$,
$\pi^{+}\nu_{\mu}\mu^{-}$, $\pi^{0}\nu_{\mu}\bar{\nu}_{\mu}$,
$\pi^{0}\nu_{\tau}\bar{\nu}_{\tau}$, $\pi^{+}\pi^{-}$, or $\pi^{0}\pi^{0}$,
while they are $\pi^{-}\pi^{0}$, $\pi^{-}\nu_{\mu}\bar{\nu}_{\mu}$, or
$\pi^{-}\nu_{\tau}\bar{\nu}_{\tau}$ for $e^{+}$.

Now we are ready to estimate the fraction of the produced particle per unit
anti-lepton number or per unit charge of the Q ball. After pions are
kinematically allowed to produced from the Q-ball decay, the numbers of
particles per unit Q-ball charge are obtained as $f_{\pi^{0}}=1/12$ for
$\pi^{0}$, $f_{\pi^{+}}=1/20$ for $\pi^{+}$, $f_{\pi^{-}}=1/15$ for $\pi^{-}$,
$f_{\mu^{-}}=1/60$ for $\mu^{-}$, while $f_{e^{+}}=2/15$ for $e^{+}$ when the
decay channel to pions is not open.

##  V Photon spectrum

###  V.1 Galactic gamma-ray emission

Pions are produced at rest just after they are kinematically allowed, and
immediately they emit photons which has peculiar spectrum as explained in the
following. $\pi^{0}$ decays into two photons with the energy of half the
$\pi^{0}$ mass, 67.5 MeV. We first consider the galactic gamma-ray emission.
The spectrum of this line gamma rays can be obtained as

$\varepsilon_{\gamma}^{2}\frac{d\Phi_{2\gamma}}{d\varepsilon_{\gamma}}=\frac{1}{4\pi}\frac{{\Omega_{Q}\cal
D}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{0}}2\left(\frac{\varepsilon_{\gamma}}{\Delta\varepsilon_{\gamma}}\right)\varepsilon_{\gamma},$
(13)

where $\Omega_{Q}$ is the density parameter of the Q ball. $\Delta\tau_{Q}=\xi
t_{0}$, where $\xi$ represents the uncertainty of the lifetimes of the Q balls
due to some variance in their sizes.
$\Delta\varepsilon_{\gamma}/\varepsilon_{\gamma}$ is the energy resolution of
the observation. $Q_{\pi}/Q_{\rm D}$ implies the fraction of the charge of the
Q ball that can decay into pions, and $f_{\pi^{0}}$ is the number of $\pi^{0}$
produced per unit Q-ball charge, as described in the previous section. ${\cal
D}$ is a D-factor, given by

${\cal D}=\frac{1}{\Delta\Omega}\int_{\Delta\Omega}d\ell db\cos
b\int_{0}^{s_{\rm max}}ds\rho_{\rm DM}(r(\ell,b,s)),$ (14)

where $\ell$ and $b$ are galactic longitude and latitude, respectively.
$\Delta\Omega$ denotes the solid angle of the observation. $s$ is the distance
along the line of sight. The distance from the galactic center is expressed as
$r(\ell,b,s)=\left(R_{GC}^{2}-2sR_{\rm GC}\cos\psi+s^{2}\right)^{1/2}$, where
$\psi$ is the angle between the direction to the galactic center and the line
of sight so that $\cos\psi=\cos\ell\cos b$. $s_{\rm max}=\left(R_{\rm
MW}^{2}-\sin^{2}\psi R_{\rm GC}^{2}\right)^{1/2}+R_{\rm GC}\cos\psi$ with
$R_{MW}=30$ kpc being assumed as the size of the dark halo. We adopt the
Navaro-Frenk-White profile Navarro:1995iw  for the dark matter halo density,
written as

$\rho_{\rm
DM}(r)=\frac{\rho_{0}}{\left(\frac{r}{r_{0}}\right)\left(1+\frac{r}{r_{0}}\right)^{2}}.$
(15)

Here we take $\rho_{0}=0.53$ GeV/cm3 and $r_{0}=15$ kpc so that we have the
solar local density of $\rho_{\rm DM}(R_{\rm GC})=0.4$ GeV/cm3, where $R_{\rm
GC}=8.23$ kpc is the distance to the galactic center from the sun
Leung:2022dno .

On the other hand, $\pi^{+}$ and $\pi^{-}$ decay into $\mu^{+}$ and $\mu^{-}$,
respectively. Photons are emitted through the internal bremsstrahlung with the
branching ratio Bressi:1997gs ; Brown:1964zza ; Neville:1961zz

$\displaystyle\frac{dB_{\pi{\rm IB}}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{2\pi}\frac{1}{(1-p)^{2}}\frac{2}{m_{\pi^{\pm}}}\frac{1}{x}$
$\displaystyle\times\left[\frac{\left\\{x^{2}+4(1-p)(1-x)\right\\}(x^{2}+p-1)}{1-x}\right.$
$\displaystyle\left.+\left\\{2(1-p)(1+p-x)+x^{2}\right\\}\log\frac{1-x}{p}\right],$

where $\alpha=1/137$ is the fine structure constant,
$p=(m_{\mu}/m_{\pi^{\pm}})^{2}$, and $x=2\varepsilon_{\gamma}/m_{\pi^{\pm}}$.
See App. A for the details. The spectrum of IB photons is thus given by

$\varepsilon_{\gamma}^{2}\frac{d\Phi_{\pi{\rm
IB}}}{d\varepsilon_{\gamma}}=\frac{1}{4\pi}\frac{\Omega_{Q}{\cal
D}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{\pm}}\frac{dB_{\pi{\rm
IB}}}{d\varepsilon_{\gamma}}\varepsilon_{\gamma}^{2},$ (17)

where $f_{\pi^{\pm}}=f_{\pi^{+}}+f_{\pi^{-}}=7/60$ since the spectrum of
internal bremsstrahlung is the same for both $\pi^{+}$ and $\pi^{-}$ decays.

In addition, $\mu^{+}$ and $\mu^{-}$ decay into $e^{+}$ and $e^{-}$,
respectively, similarly emitting internal bremsstrahlung with the branching
ratio Kuno:1999jp

$\displaystyle\frac{dB_{\mu{\rm IB}}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{2\pi}\frac{2}{m_{\mu}}\frac{2(1-y)}{3y}$ (18)
$\displaystyle\times\left[-\frac{17}{2}-\frac{3}{4}(1-y)+\frac{16}{3}(1-y)^{2}-\frac{55}{12}(1-y)^{3}\right.$
$\displaystyle\left.+\left\\{3-2(1-y)^{2}+2(1-y)^{3}\right\\}\log\frac{1-y}{q}\right],$

where $q=(m_{e}/m_{\mu})^{2}$ and $y=2\varepsilon_{\gamma}/m_{\mu}$. See App.
A for the details. The spectrum of the IB photons is then written as

$\varepsilon_{\gamma}^{2}\frac{d\Phi_{\mu{\rm
IB}}}{d\varepsilon_{\gamma}}=\frac{1}{4\pi}\frac{\Omega_{Q}{\cal
D}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\mu^{\pm}}\frac{dB_{\mu{\rm
IB}}}{d\varepsilon_{\gamma}}\varepsilon_{\gamma}^{2},$ (19)

where $f_{\mu^{\pm}}=f_{\pi^{\pm}}+f_{\mu^{-}}=2/15$, since the charged pions
decay into muons.

We illustrate the spectra (13), (17) and (19) in Fig. 2. Here we consider the
region with $|\ell|<30^{\circ}$ and $|b|<5^{\circ}$, and set
$\Omega_{Q}/\xi\simeq 1\times 10^{-8}$, well below the rough upper bound
explained in App. B.444Since Q-ball abundance would be by far much larger than
this value for usual formation à la Affleck-Dine, it is necessary to reduce
it. One mechanism is considered in Ref. Kasuya:2005ay  using resonant decay of
the flat direction in most of the region of the universe, and another one may
be late-time entropy production before nucleosynthesis.  Also shown are the
observations of the gamma-ray diffuse emission from the inner galactic region
measured by COMPTEL in 1–30 MeV Strong:1998ck  and EGRET in 30–100 MeV
Strong:2004de . We adopt
$\Delta\varepsilon_{\gamma}/\varepsilon_{\gamma}=0.15$ in Eq.(13) to compare
with the EGRET data Thompson:2008rw . It should be noted that the spectra
obtained by COMPTEL and EGRET include the galactic diffuse emission, and there
may be an excess component in addition to the galactic diffuse emission to
reconcile with the observed spectra (See, e.g., Refs. Strong:2004de ; Fermi-
LAT:2012edv ; Orlando:2017mvd ). The excess could be contributed from the
gamma rays originated from the Q-ball decay, unresolved sources Tsuji:2022pfw
, dark matter Boddy:2015efa ; Binder:2022pmf ; Christy:2022pvy  and/or cosmic
neutrinos Fang:2022trf , or may be explained by the uncertainties of the model
of the galactic diffuse emission (e.g., Ref. Bouchet:2011fn ).

Figure 2: Photon spectra from the Q-ball decay. We display the spectra (13),
(17) and (19) in blue, green, and red lines, respectively. Observations of the
galactic diffuse gamma-ray emission are also shown in cyan (COMPTEL) and gray
points (EGRET).

We can see that the unique feature of the spectrum is the line-gamma rays at
$\varepsilon_{\gamma}=67.5$ MeV. Astrophysical sources could hardly produce
such an emission line. It could be detected by future observations such as
AMEGO-X Fleischhack:2021mhc , CubeSat for MeV observations (MeVCube)
Lucchetta:2022nrm , e-ASTROGAM e-ASTROGAM:2017pxr , GECCO Moiseev:2021mdo ,
GRAINE Rokujo:2018ggw , GRAMS Aramaki:2019bpi , and SMILE-3 Takada:2021iug
.555Although the gamma-ray data by Fermi-LAT below 100 MeV is available, there
is no dedicated search for 67.5 MeV line emission because of the technical
difficulty at the lower energy band.666 COSI-SMEX Tomsick:2019wvo , to be
launched in 2027, is not sensitive to the gamma rays above 5 MeV. For example,
GRAMS has 67.5 MeV line sensitivity of $\sim 10^{-6}$ MeV/cm2/s
Aramaki:2019bpi . Detection of this line by some future observations would
prove this Q-ball decay scenario. If not, it may result in lowering the upper
bound on $\Omega_{Q}$. In addition, the Q-ball decay produces almost the same
amount of $\pi^{0}$ and $\pi^{\pm}$, so that photons from the radiative muon
decay through the internal bremsstrahlung will appear in the energy range
$\varepsilon_{\gamma}\lesssim 50$ MeV with a sharp cutoff at around 50 MeV.
Continuum sensitivity of GRAMS may reach to observe this internal
bremsstrahlung on the top of the diffuse background for a satellite mission
Aramaki:2019bpi . Measurements of the 67.5 MeV line and/or this broad spectrum
with a cutoff at around 50 MeV could be the evidence of the Q-ball decay
model.

###  V.2 Extragalactic gamma-ray emission

Let us now study the extragalactic gamma-ray emission. For $\pi^{0}\rightarrow
2\gamma$, taking into account the cosmic expansion, we can estimate the
present flux as Kawasaki:1997ah ; Asaka:1997rv

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi^{\rm
ext}_{2\gamma}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{\varepsilon_{\gamma}^{2}}{4\pi}\int_{(1-\xi)t_{0}}^{t_{0}}dt^{\prime}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{0}}$ (20) $\displaystyle\times
2(1+z)\delta\left[\varepsilon_{\gamma}^{\prime}-\frac{m_{\pi^{0}}}{2}\right],$

where $\rho_{c0}$ is the present critical density of the universe, $z$ is the
redshift, and $\varepsilon_{\gamma}^{\prime}=(1+z)\varepsilon_{\gamma}$ is the
photon energy produced at the decay time for the photon with energy
$\varepsilon_{\gamma}$ at present. The redshift $z$ is related to cosmic time
$t$ as

$\frac{dt}{dz}=-(1+z)^{-5/2}H_{0}^{-1}\left[\Omega_{\rm
M}+\frac{\Omega_{\Lambda}}{(1+z)^{3}}\right]^{-1/2},$ (21)

where $H_{0}$ is the Hubble parameter at present, $\Omega_{M}$ and
$\Omega_{\Lambda}$ are the present density parameters of matter and
cosmological constant, respectively, and the flat universe is assumed.
Therefore, we obtain the flux as

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi_{2\gamma}^{\rm
ext}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}H_{0}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{0}}\varepsilon_{\gamma}\left(\frac{2\varepsilon_{\gamma}}{m_{\pi^{0}}}\right)^{3/2}$
(22) $\displaystyle\times\left[\Omega_{\rm
M}+\Omega_{\Lambda}\left(\frac{2\varepsilon_{\gamma}}{m_{\pi^{0}}}\right)^{3}\right]^{-1/2}.$

Notice that the spectrum has a rather narrow shape where the upper and lower
edges are respectively located at the energy of 67.5 MeV and
$67.5/(1+z_{\xi})$ MeV, where $z_{\xi}$ corresponds to the redshift at the
cosmic time $(1-\xi)t_{0}$.

For the internal bremsstrahlung from pions, we have

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi_{\pi{\rm IB}}^{\rm
ext}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{\varepsilon_{\gamma}^{2}}{4\pi}\int_{(1-\xi)t_{0}}^{t_{0}}dt^{\prime}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{\pm}}$ (23) $\displaystyle\times(1+z)\frac{dB_{\pi{\rm
IB}}}{d\varepsilon^{\prime}_{\gamma}}(\varepsilon^{\prime}_{\gamma}),$

where Eq.(LABEL:dBpi) is used. Changing the variable of integration to $z$, we
obtain

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi_{\pi{\rm IB}}^{\rm
ext}}{\varepsilon_{\gamma}}=\frac{\varepsilon_{\gamma}}{4\pi}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}H_{0}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\pi^{\pm}}\frac{\alpha}{2\pi}\frac{1}{(1-p)^{2}}\hskip 28.45274pt$
$\displaystyle\hskip
42.67912pt\times\int_{0}^{z_{\xi}}dz\frac{K_{\pi}\left((1+z)\frac{2\varepsilon_{\gamma}}{m_{\pi^{\pm}}})\right)}{\sqrt{\Omega_{\rm
M}(1+z)^{5}+\Omega_{\Lambda}(1+z)^{2}}},$ (24)

where

$\displaystyle K_{\pi}(x)$ $\displaystyle=$
$\displaystyle\frac{\left\\{x^{2}+4(1-p)(1-x)\right\\}(x^{2}+p-1)}{1-x}$
$\displaystyle+\left\\{2(1-p)(1+p-x)+x^{2}\right\\}\log\frac{1-x}{p}.$

On the other hand, the spectrum of the internal bremsstrahlung from muons can
be calculated as

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi_{\mu{\rm IB}}^{\rm
ext}}{d\varepsilon_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{\varepsilon_{\gamma}^{2}}{4\pi}\int_{(1-\xi)t_{0}}^{t_{0}}dt^{\prime}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\mu^{\pm}}$ (26) $\displaystyle\times(1+z)\frac{dB_{\mu{\rm
IB}}}{d\varepsilon^{\prime}_{\gamma}}(\varepsilon^{\prime}_{\gamma}),$

where Eq.(18) is exploited. Converting the variable of integration to $z$, we
get

$\displaystyle\varepsilon_{\gamma}^{2}\frac{d\Phi_{\mu{\rm IB}}^{\rm
ext}}{d\varepsilon_{\gamma}}=\frac{\varepsilon_{\gamma}}{4\pi}\frac{\Omega_{Q}\rho_{c0}}{\omega_{Q}\Delta\tau_{Q}H_{0}}\frac{Q_{\pi}}{Q_{\rm
D}}f_{\mu^{\pm}}\hskip 71.13188pt$ $\displaystyle\hskip
14.22636pt\times\int_{0}^{z_{\xi}}dz\frac{2\left[J_{+}\left((1+z)\frac{2\varepsilon_{\gamma}}{m_{\mu}})\right)+J_{+}\left((1+z)\frac{2\varepsilon_{\gamma}}{m_{\mu}})\right)\right]}{\sqrt{\Omega_{\rm
M}(1+z)^{5}+\Omega_{\Lambda}(1+z)^{2}}},$ (27)

where Eqs.(32) and (33) are used.

We plot the spectra of (22), (24) and (27) in Fig. 3. The integrals in
Eqs.(24) and (27) are estimated numerically. Cosmological parameters are set
to be $\Omega_{M}=0.311$, $\Omega_{\Lambda}=0.689$, and $H_{0}=67.7$ km/s/Mpc
Planck:2018vyg . We illustrate the cases for $\xi=0.1$ and $0.5$, which
correspond respectively to $z_{\xi}\simeq 0.1$ and $0.8$. Also shown are the
observations of the extragalactic diffuse gamma-ray emission by EGRET (above
30 MeV) Strong:2004ry , COMPTEL (below 30 MeV) Weidenspointer2000 , and the
Solar Maximum Mission (SMM) Gamma-Ray Spectrometer in the energy range 0.3–8.0
MeV Watanabe2000 . The origin of this extragalactic MeV gamma-ray background
remains unknown, and contributions from seyfert galaxies or blazars are
suggested (e.g., Refs. Inoue:2007tn ; Ajello:2009ip ).

Figure 3: Extragalactic photon spectra from the Q-ball decay. We display the
spectra (22) in blue, (24) in green, and (27) in red lines. Solid and dashed
lines denote the cases with $\xi=0.1$ and $0.5$, respectively. Observations of
the extragalactic diffuse gamma-ray emission are also shown in cyan (COMPTEL)
and gray (EGRET) points, and in orange lines (SMM).

We can see a thick line-like emission at $\lesssim 67.5$ MeV, and broad
spectra of internal bremsstrahlung with sharp cutoffs at 50 MeV and 30 MeV for
muon and pion decays, respectively. They have similar features as in the
galactic diffuse gamma-ray spectrum. Future MeV gamma-ray observations could
prove or falsify these signals from the Q-ball decay.

##  VI Conclusion

We have investigated the observational clues of the SUSY Q balls which decay
at present. Such Q balls are realized by having very large lepton numbers as
the charge of the Q ball in the gauge-mediated SUSY breaking models. The new-
type Q balls form and transform to the gauge-mediation type towards the end of
the decay. Then the mass per unit charge $\omega_{Q}$ increases as the charge
$Q$ decreases, and subsequently the decay channels into pions become
kinematically allowed to create pions at rest. This is the distinctive
mechanism of the Q-ball decay to produce pions at rest.

Neutral pions decay into two photons with the energy of half the pion mass,
making the sharp emission line at 67.5 MeV. If detected, it would be a smoking
gun of the SUSY Q ball since it is the unique feature of the Q-ball decay and
no astrophysical sources would create such an emission line. In addition,
charged pions decay into muons which further decay radiatively to emit
internal bremsstrahlung whose spectrum has a sharp edge at around 50 MeV. We
may expect that these photons could be detected by future MeV gamma-ray
observations.

## Acknowledgments

The authors are grateful to Tsuguo Aramaki for useful comments. This work is
supported by JSPS KAKENHI Grant Nos. 20H05851(M. K.), 21K03567(M. K.), and
22K14064 (N. T.).

##  Appendix A Internal bremsstrahlung

When charged pions decay into muons, they partially emit internal
bremsstrahlung. Its differential branching ratio is written as Bressi:1997gs ;
Brown:1964zza ; Neville:1961zz

$\displaystyle\frac{dB_{\pi{\rm IB}}}{dxdw}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{2\pi}\frac{1}{(1-p)^{2}}\frac{1-w+p}{x^{2}(x+w-1-p)}$
$\displaystyle\times\left[x^{2}+2(1-x)(1-p)-\frac{2xp(1-p)}{x+w-1-p}\right],$

where $\alpha=1/137$ is the fine structure constant,
$p=(m_{\mu}/m_{\pi^{\pm}})^{2}$, $x=2\varepsilon_{\gamma}/m_{\pi^{\pm}}$, and
$w=2E_{\mu}/m_{\pi^{\pm}}$ is the normalized muon energy. $w$\- and $x$-ranges
are

$\begin{array}[]{rcl}2\sqrt{p}\leq&w&\leq 1+p,\\\\[5.69054pt]
1-\frac{w}{2}-\frac{\sqrt{w^{2}-4p}}{2}\leq&x&\leq
1-\frac{w}{2}+\frac{\sqrt{w^{2}-4p}}{2},\end{array}$ (29)

respectively. Integration with respective to $w$ over the $w$-range of (29)
leads to

$\displaystyle\frac{dB_{\pi{\rm IB}}}{dx}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{2\pi}\frac{1}{(1-p)^{2}}\frac{1}{x}$
$\displaystyle\times\left[\frac{\left\\{x^{2}+4(1-p)(1-x)\right\\}(x+p-1)}{1-x}\right.$
$\displaystyle\left.+\left\\{2(1-p)(1+p-x)+x^{2}\right\\}\log\frac{1-x}{p}\right].$

On the other hand, polarized muons are produced by the decay of charged pions
at rest. The photon spectrum by radiative muon decay is given by Kuno:1999jp

$\displaystyle\frac{dB(\mu^{\pm}\rightarrow
e^{\pm}\nu\bar{\nu}\gamma)}{dyd\cos\theta_{\gamma}}$ $\displaystyle=$
$\displaystyle\frac{1}{y}\left[J_{+}(y)\left(1\pm
P_{\mu}\cos\theta_{\gamma}\right)\right.$ (31)
$\displaystyle\left.+J_{-}(y)\left(1\mp
P_{\mu}\cos\theta_{\gamma}\right)\right],$

where $y=2\varepsilon_{\gamma}/m_{\mu}$, $P_{\mu}$ is a magnitude of the muon
spin polarization vector, $\theta_{\gamma}$ is the angle between the muon spin
polarization and the photon momentum. $J_{+}(y)$ and $J_{-}(y)$ are written
respectively as

$\displaystyle J_{+}(y)$ $\displaystyle=$
$\displaystyle\frac{\alpha}{6\pi}(1-y)\left[\left(3\log\frac{1-y}{q}-\frac{17}{2}\right)\right.$
(32) $\displaystyle+\left(-3\log\frac{1-y}{q}+7\right)(1-y)$
$\displaystyle\left.+\left(2\log\frac{1-y}{q}-\frac{13}{3}\right)(1-y)^{2}\right],$
$\displaystyle J_{-}(y)$ $\displaystyle=$
$\displaystyle\frac{\alpha}{6\pi}(1-y)^{2}\left[\left(3\log\frac{1-y}{q}-\frac{31}{4}\right)\right.$
(33) $\displaystyle+\left(-4\log\frac{1-y}{q}+\frac{29}{3}\right)(1-y)$
$\displaystyle\left.+\left(2\log\frac{1-y}{q}-\frac{55}{12}\right)(1-y)^{2}\right],$

where $q=(m_{e}/m_{\mu})^{2}$. Since the produced muons have no specific
direction, we must integrate Eq.(31) with respect to $\theta_{\gamma}$ over
the whole angles, and hence obtain the spectrum as

$\displaystyle\frac{dB_{\mu{\rm IB}}}{dy}$ $\displaystyle=$
$\displaystyle\frac{2}{y}\left[J_{+}(y)+J_{-}(y)\right]$ (34) $\displaystyle=$
$\displaystyle\frac{\alpha}{2\pi}\frac{2(1-y)}{3y}$
$\displaystyle\times\left[-\frac{17}{2}-\frac{3}{4}(1-y)+\frac{16}{3}(1-y)^{2}-\frac{55}{12}(1-y)^{3}\right.$
$\displaystyle\left.+\left\\{3-2(1-y)^{2}+2(1-y)^{3}\right\\}\log\frac{1-y}{q}\right].$

##  Appendix B Rough constraint on $\Omega_{Q}$

Q-ball decay produces positrons with energy $\lesssim\omega_{Q}$ which may
annihilate with electrons at the galactic center to generate 511 keV gamma
rays. Since the morphology of the dark matter halo in our galaxy is still not
known, we make very rough estimate for the upper bound of the Q-ball abundance
according to Ref. Hooper:2004qf . Assuming the half of the total 511 keV flux
is emitted from an angular region of $9^{\circ}$ circle, we have

$\frac{M_{(<9^{\circ})}\Omega_{Q}}{\omega_{Q}\Delta\tau_{Q}}f_{e^{+}}\left[\frac{f}{4}+(1-f)\right]=\frac{1}{2}\Phi_{511}4\pi
R_{\rm GC}^{2},$ (35)

where $f$ is the fraction of positrons which annihilate via positronium,
$\Phi_{511}(\simeq 10^{-3}$ cm-2s-1) is the observed total flux of 511 keV
line, and $\Delta\tau_{Q}=\xi\tau_{Q}$. We assume $\tau_{Q}\simeq t_{0}$. The
total mass within the $9^{\circ}$ circle is given by

$M_{(<9^{\circ})}=\int_{(<9^{\circ})}\rho_{\rm DM}(r)4\pi r^{2}dr.$ (36)

Therefore, we obtain the constraint on the density parameter as

$\displaystyle\frac{\Omega_{Q}}{\xi}$ $\displaystyle\lesssim$ $\displaystyle
2.4\times 10^{-7}\left(\frac{\Phi_{511}}{10^{-3}~{}{\rm cm}^{-2}{\rm
s}^{-1}}\right)$ (37) $\displaystyle\times\left(\frac{R_{\rm GC}}{8.23~{}{\rm
kpc}}\right)^{2}\left(\frac{\omega_{Q}}{2.9{\rm
MeV}}\right)\left(\frac{\tau_{Q}}{t_{0}}\right).$

## References

  * (1) S. R. Coleman, Nucl. Phys. B 262, no.2, 263 (1985).
  * (2) A. Kusenko, Phys. Lett. B 405, 108 (1997).
  * (3) A. Kusenko and M. E. Shaposhnikov, Phys. Lett. B 418, 46-54 (1998).
  * (4) S. Kasuya and M. Kawasaki, Phys. Rev. D 61, 041301 (2000).
  * (5) I. Affleck and M. Dine, Nucl. Phys. B 249, 361-380 (1985).
  * (6) A. Kusenko, V. Kuzmin, M. E. Shaposhnikov and P. G. Tinyakov, Phys. Rev. Lett. 80, 3185-3188 (1998).
  * (7) J. Arafune, T. Yoshida, S. Nakamura and K. Ogure, Phys. Rev. D 62, 105013 (2000).
  * (8) S. Kasuya and M. Kawasaki, Phys. Rev. D 64, 123515 (2001).
  * (9) S. Kasuya, M. Kawasaki and T. T. Yanagida, PTEP 2015, no.5, 053B02 (2015).
  * (10) S. Kasuya and F. Takahashi, Phys. Rev. D 72, 085015 (2005).
  * (11) S. Kasuya and F. Takahashi, JCAP 11, 019 (2007).
  * (12) S. Kasuya, M. Kawasaki and K. Murai, JCAP 05, 053 (2023).
  * (13) M. Kawasaki and K. Murai, JCAP 01, 050 (2024).
  * (14) T. Gherghetta, C. F. Kolda and S. P. Martin, Nucl. Phys. B 468, 37-58 (1996).
  * (15) M. Dine, L. Randall and S. D. Thomas, Nucl. Phys. B 458, 291-326 (1996).
  * (16) A. de Gouvea, T. Moroi and H. Murayama, Phys. Rev. D 56, 1281-1299 (1997).
  * (17) S. Kasuya and M. Kawasaki, Phys. Rev. Lett. 85, 2677-2680 (2000).
  * (18) J. Hisano, M. M. Nojiri and N. Okada, Phys. Rev. D 64, 023511 (2001).
  * (19) S. Kasuya and M. Kawasaki, Phys. Rev. D 62, 023512 (2000).
  * (20) T. Hiramatsu, M. Kawasaki and F. Takahashi, JCAP 06, 008 (2010).
  * (21) K. Enqvist and J. McDonald, Nucl. Phys. B 538, 321-350 (1999).
  * (22) A. G. Cohen, S. R. Coleman, H. Georgi and A. Manohar, Nucl. Phys. B 272, 301-321 (1986).
  * (23) S. Kasuya and M. Kawasaki, Phys. Rev. D 80, 123529 (2009).
  * (24) S. P. Martin, Adv. Ser. Direct. High Energy Phys. 18, 1-98 (1998).
  * (25) J. F. Navarro, C. S. Frenk and S. D. M. White, Astrophys. J. 462, 563-575 (1996).
  * (26) H. W. Leung, J. Bovy, J. T. Mackereth, J. A. S. Hunt, R. R. Lane and J. C. Wilson, Mon. Not. Roy. Astron. Soc. 519, no.1, 948-960 (2022).
  * (27) G. Bressi, G. Carugno, E. Conti, A. T. Meneguzzo, S. Cerdonio and D. Zanello, Nucl. Phys. B 513, 555-572 (1998).
  * (28) S. G. Brown and S. A. Bludman, Phys. Rev. 136, B1160-B1163 (1964).
  * (29) D. E. Neville, Phys. Rev. 124, 2037-2046 (1961).
  * (30) Y. Kuno and Y. Okada, Rev. Mod. Phys. 73, 151-202 (2001).
  * (31) A. W. Strong, H. Bloemen, R. Diehl, W. Hermsen and V. Schoenfelder, Astrophys. Lett. Commun. 39, 209 (1999).
  * (32) A. W. Strong, I. V. Moskalenko and O. Reimer, Astrophys. J. 613, 962-976 (2004).
  * (33) D. J. Thompson, Rept. Prog. Phys. 71, 116901 (2008).
  * (34) M. Ackermann et al. [Fermi-LAT], Astrophys. J. 750, 3 (2012).
  * (35) E. Orlando, Mon. Not. Roy. Astron. Soc. 475, no.2, 2724-2742 (2018).
  * (36) N. Tsuji, Y. Inoue, H. Yoneda, R. Mukherjee and H. Odaka, Astrophys. J. 943, no.1, 48 (2023).
  * (37) K. K. Boddy and J. Kumar, Phys. Rev. D 92, no.2, 023533 (2015).
  * (38) T. Binder, S. Chakraborti, S. Matsumoto and Y. Watanabe, JHEP 01, 106 (2023).
  * (39) J. G. Christy, J. Kumar and A. Rajaraman, Phys. Rev. D 106, no.12, 123021 (2022).
  * (40) K. Fang, J. S. Gallagher and F. Halzen, Astrophys. J. 933, no.2, 190 (2022).
  * (41) L. Bouchet, A. W. Strong, T. A. Porter, I. V. Moskalenko, E. Jourdain and J. P. Roques, Astrophys. J. 739, 29 (2011).
  * (42) H. Fleischhack, PoS ICRC2021, 649 (2021).
  * (43) G. Lucchetta, M. Ackermann, D. Berge and R. Bühler, JCAP 08, no.08, 013 (2022).
  * (44) A. De Angelis et al. [e-ASTROGAM], JHEAp 19, 1-106 (2018).
  * (45) A. Moiseev, PoS ICRC2021, 648 (2021).
  * (46) H. Rokujo, S. Aoki, K. Hamada, T. Hara, T. Inoue, K. Ishiguro, A. Iyono, H. Kawahara, K. Kodama and R. Komatani, et al. PTEP 2018, no.6, 063H01 (2018); S. Takahashi, S. Aoki, A. Iyono, A. Karasuno, K. Kodama, R. Komatani, M. Komatsu, M. Komiyama, K. Kuretsubo and T. Marushima, et al. Astrophys. J. 960, no.1, 47 (2024).
  * (47) T. Aramaki, P. Hansson Adrian, G. Karagiorgi and H. Odaka, Astropart. Phys. 114, 107-114 (2020).
  * (48) A. Takada, T. Takemura, K. Yoshikawa, Y. Mizumura, T. Ikeda, Y. Nakamura, K. Onozaka, M. Abe, K. Hamaguchi and H. Kubo, et al. Astrophys. J. 930, no.1, 6 (2022).
  * (49) J. A. Tomsick, A. Zoglauer, C. Sleator, H. Lazar, J. Beechert, S. Boggs, J. Roberts, T. Siegert, A. Lowell and E. Wulf, et al., BAAS 51, 98 (2019).
  * (50) M. Kawasaki and T. Yanagida, Phys. Lett. B 399, 45-48 (1997).
  * (51) T. Asaka, J. Hashiba, M. Kawasaki and T. Yanagida, Phys. Rev. D 58, 083509 (1998).
  * (52) N. Aghanim et al. [Planck], Astron. Astrophys. 641, A6 (2020) [erratum: Astron. Astrophys. 652, C4 (2021)].
  * (53) A. W. Strong, I. V. Moskalenko and O. Reimer, Astrophys. J. 613, 956-961 (2004).
  * (54) G. Weidenspointer et al., AIP Conf. Proc. 510, 467-475 (2000).
  * (55) K. Watanabe, M. D. Leising, G. H. Share, AIP Conf. Proc. 510, 471-470 (2000).
  * (56) Y. Inoue, T. Totani and Y. Ueda, Astrophys. J. Lett. 672, L5 (2008).
  * (57) M. Ajello, L. Costamante, R. M. Sambruna, N. Gehrels, J. Chiang, A. Rau, A. Escala, J. Greiner, J. Tueller and J. V. Wall, et al. Astrophys. J. 699, 603-625 (2009).
  * (58) D. Hooper and L. T. Wang, Phys. Rev. D 70, 063506 (2004).


# HARRIS: Hybrid Ranking and Regression Forests
for Algorithm Selection

Lukas Fehring1, Jonas Hanselle1, Alexander Tornede2
1 Department of Computer Science, Paderborn University, Germany
2 Institute of Artificial Intelligence, Leibniz University Hannover
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

It is well known that different algorithms perform differently well on an
instance of an algorithmic problem, motivating algorithm selection (AS): Given
an instance of an algorithmic problem, which is the most suitable algorithm to
solve it? As such, the AS problem has received considerable attention
resulting in various approaches – many of which either solve a regression or
ranking problem under the hood. Although both of these formulations yield very
natural ways to tackle AS, they have considerable weaknesses. On the one hand,
correctly predicting the performance of an algorithm on an instance is a
sufficient, but not a necessary condition to produce a correct ranking over
algorithms and in particular ranking the best algorithm first. On the other
hand, classical ranking approaches often do not account for concrete
performance values available in the training data, but only leverage rankings
composed from such data. We propose ybrid rAnking and RegRessIon foreSts - a
new algorithm selector leveraging special forests, combining the strengths of
both approaches while alleviating their weaknesses. ecisions are based on a
forest model, whose trees are created based on splits optimized on a hybrid
ranking and regression loss function. As our preliminary experimental study on
ASLib shows, proves over standard algorithm selection approaches on some
scenarios showing that combining ranking and regression in trees is indeed
promising for AS.

##  1 Introduction

To this day, there are competitions on solving hard instances of the SAT
(boolean satisfiability problem) problem [10, 7]. In these competitions, one
deals with a set of problems with the goal of solving them faster than the
competitors. Here, the participants rarely use one algorithm to solve all
problem instances. Instead, they utilize so-called algorithm selectors, often
featuring machine learning models at their core, to predict the performance of
different algorithms on the instance to select the one presumably performing
best. In practice, most algorithm selectors either leverage a regression [23,
2, 8] or a ranking [3, 6, 20] model to predict the best algorithm.

Unfortunately, both ranking and regression models feature considerable
drawbacks when used at the core of a selector. While creating a ranking across
algorithms according to their predicted performance does indeed yield the
correct ranking as long as the predictions are correct, such a ranking can
also be created without correctly estimating the performance. More precisely,
correct performance predictions are a sufficient, but not a necessary
criterion to create a correct ranking across the algorithms. Correspondingly,
one may wonder whether solving a regression problem might not be much harder
than what is required. From this perspective, ranking models are a more
intuitive solution. However, they often do not take the concrete performance
values, which are usually present as training data, into account, but are
trained based on rankings created from these. Correspondingly, these ranking
models are trained based on qualitative comparisons losing the actual
quantitative information contained in the precise performance evaluations. As
such, they lack the means to quantify how close two algorithms are in a
predicted ranking and thus are more susceptible to problems arising from
algorithms with actually very similar performance.

In this paper, we propose a new algorithm selector leveraging a machine
learning model trained based on a composite loss with both a ranking and
regression component, dubbed n particular, the core of formed by a random
forest, whose trees are formed according to splits optimized on the
aforementioned composite loss. By doing so, mbines the strengths of both
ranking and regression models while alleviating their weaknesses.

##  2 The Algorithm Selection Problem

In Algorithm Selection (AS) [15], we aim to find the best algorithm $A_{i}$
from a set of candidate algorithms $\\{A_{1},...,A_{k}\\}=\mathcal{A}$ for a
problem instance $I\in\mathcal{I}$ from a problem instance space
$\mathcal{I}$. Formally, we seek to find a mapping, called algorithm selector
$s:\mathcal{I}\rightarrow\mathcal{A}$, which maximizes a costly-to-evaluate
performance measure $m:\mathcal{A}\times\mathcal{I}\rightarrow\mathbb{R}$.
Correspondingly, the optimal selector, called an oracle, is defined as

$s^{*}(I)\in\arg\max\limits_{A\in\mathcal{A}}\mathbb{E}[m(A,I)]\,\,\,.$ (1)

As the performance measure $m$ is costly to evaluate, an exhaustive
enumeration over the set of algorithms to choose the best performing one is no
practical solution. This holds especially for constraint satisfaction
problems, where one is finally interested in the solution to the instance,
which is obtained as a result of the first algorithm run anyway. As a solution
to this, most AS approaches leverage machine learning to learn a surrogate
performance measure
$\widehat{m}:\mathcal{A}\times\mathcal{I}\rightarrow\mathbb{R}$ mimicking the
original performance measure $m$, while, in contrast to the original
performance measure, being cheap to evaluate. Using such a surrogate
$\widehat{m}$, selectors can be constructed as
$s(I)=\arg\max\limits_{A\in\mathcal{A}}\widehat{m}(A,I)$.

To learn such surrogates, we assume that we can represent instances in terms
of features, which are at least somewhat correlated with the performance of
one or multiple of the algorithms. Formally, these features are computed by a
feature function $g:\mathcal{I}\rightarrow\mathcal{X}$ and we will write
$\boldsymbol{x}_{I}\in\mathcal{X}$, when we want to address the features of
instance $i\in\mathcal{I}$. When considering the algorithmic problem of SAT,
such features could be, for example, the number of clauses or the number of
variables. Moreover, we assume that we are given some prior evaluations of the
performance measure $m$ for at least some of the algorithms on some training
instances $\mathcal{I}_{\mathit{train}}\subset\mathcal{I}$, which we can use
for learning. More formally, we assume training data with labels
$\boldsymbol{y}_{I}=[m(I,A_{1}),\ldots,m(I,A_{k})]\in\mathbb{R}^{k}$ where
$A_{i}\in\mathcal{A}$, i.e.,

$\mathcal{D}_{\mathit{train}}=\left\\{(\boldsymbol{x}_{I},\boldsymbol{y}_{I})|I\in\mathcal{I}_{\mathit{train}}\right\\}\,\,\,.$
(2)

##  3 From Pure Ranking or Regression to Hybrid Ranking and Regression

In practice, the surrogate performance measure $\widehat{m}$ is often
implemented as a regression or ranking model based on a loss function
$\ell:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$, where we
assume rankings to be represented as a $k$-dimensional real-valued vector for
simplicity. While the first kind of models is trained using a regression loss
function such as the mean squared error, which is aimed at minimizing the
differences between the predicted algorithm performances
$\widehat{m}(\cdot,\cdot)$ and the true performances $m(\cdot,\cdot)$ on the
training data $\mathcal{D}$ making it a quantitative approach. Contrary to
that, ranking models are trained based on ranking losses such as the (inverse
of the) Spearman correlation [17], which tries to maximize the correlation
between the ranking across the algorithms imposed by the predicted latent
utility values $\widehat{m}(\cdot,\cdot)$ and the ranking imposed by the true
performances $m(\cdot,\cdot)$ making it a qualitative approach.

Recall that both of these approaches have a significant disadvantage: On the
one hand, regression approaches try to predict the performance of an algorithm
on an instance as accurately as possible, solving a, perhaps, harder problem
than necessary as we are actually just interested in correctly ranking the
algorithms. On the other hand, ranking approaches often ignore the concrete
performance evaluations available in the training data and instead focus only
on the ground truth ranking imposed by such values and correspondingly, ignore
valuable data.

This problem has been discussed before in [9] in the context of AS (and
earlier in a more general setting in [16]), who advocate leveraging hybrid
ranking and regression loss functions

$\ell_{\lambda}(\boldsymbol{y},\boldsymbol{\widehat{y}})=\lambda\ell_{\textit{regression}}(\boldsymbol{y},\boldsymbol{\widehat{y}})+(1-\lambda)\ell_{\textit{ranking}}(\boldsymbol{y},\boldsymbol{\widehat{y}})$
(3)

composed of a convex combination of a regression loss function
$\ell_{\textit{regression}}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$
and a ranking loss function
$\ell_{\textit{ranking}}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$.
Here, $\lambda\in[0,1]$ is a hyperparameter controlling how strong the two
loss functions influence the hybrid loss. The underlying idea is to leverage
the strengths of the two approach classes, i.e., focusing on the ranking
problem while also incorporating the precise performance information available
in the training data and as such, eliminate their main weaknesses in the
context of AS. The authors of [9] found that training simple linear models and
neural networks to predict latent utility values for algorithms based on such
a hybrid loss function can indeed be beneficial and in particular, that values
of $0<\lambda<1$ can yield the best performance.

##  4 Hybrid Ranking and Regression Forests

Building upon the successful work [9], in this work, we generalize the idea of
training models based on such a hybrid loss function to tree-based models,
known to be very effective in AS [21]. We build forests of hybrid trees,
detailed in the following, analogously to standard random forests [4].

Recall that decision trees [5] are trained by splitting the training data
$\mathcal{D}_{train}$ recursively into two subsets, i.e., nodes
$\mathcal{D}^{+}_{train},\mathcal{D}^{-}_{train}$ based on a feature until a
stopping criterion is reached and hence, that particular node is not split
further. Such a leaf node is assigned a label computed from the associated
dataset. In our case, we associate two labels with each node: First, a
regression label
$\widehat{\boldsymbol{y}}^{\mathit{regression}}_{\mathcal{D}}\in\mathbb{R}^{k}$
obtained by averaging the labels in the associated dataset $\mathcal{D}$ and
second, a ranking label
$\widehat{\boldsymbol{y}}^{\mathit{ranking}}_{\mathcal{D}}\in\mathbb{R}^{k}$
obtained by computing a consensus ranking through Borda’s method [13].

We choose splits, consisting of a feature $f^{*}\in\mathbb{F}$, where
$\mathbb{F}$ is the set of features, and a split point $p^{*}$, to minimize
the weighted sum of the resulting dataset’s losses wrt. the corresponding node
labels, i.e.

$(f^{*},p^{*})\in\operatornamewithlimits{arg\,min}\limits_{(f,p)\in\mathbb{F}\times\mathbb{R}}\frac{|\mathcal{D}_{train}^{+}|}{|\mathcal{D}_{train}|}\cdot\mathcal{L}(\mathcal{D^{+}})+\frac{|\mathcal{D}_{train}^{-}|}{|\mathcal{D}_{train}|}\cdot\mathcal{L}(\mathcal{D^{-}})\,\,\,.$
(4)

These losses quantify the homogeneity of labels in the dataset and are
calculated as a convex combination of ranking and regression losses
$\mathcal{L}(\mathcal{D})=\lambda\mathcal{L}_{ranking}(\mathcal{D})+(1-\lambda)\mathcal{L}_{regression}(\mathcal{D})$
where
$\mathcal{L}(\mathcal{D})=\frac{1}{|\mathcal{D}|}\sum\nolimits_{(\boldsymbol{x}_{I},\boldsymbol{y}_{I})\in\mathcal{D}}\ell(\boldsymbol{y}_{I},\widehat{\boldsymbol{y}}_{\mathcal{D}})$
and $\widehat{\boldsymbol{y}}_{\mathcal{D}}$ either corresponds to the ranking
or regression label depending on whether $\ell$ is a ranking or regression
loss function. We solve the optimization problem in Equation 4 by a simple
enumeration of all possible features and splitting points imposed by the
training data and choosing the best one. We utilize the mean squared error
over all algorithms and instances as a regression loss
$\mathcal{L}_{regression}$ as in [9]. As a ranking loss, we leverage the
Spearman correlation turned into a loss function by subtracting it from $1$,
as we found this to work best in preliminary experiments. For the same reason
we leverage the depth of a tree as a stopping criterion.

At prediction time, we propagate the instance down the tree until a leaf node
$l$ with $\mathcal{D}_{l}$ is reached. Based on label
$\widehat{\boldsymbol{y}}^{\mathit{regression}}_{\mathcal{D}_{l}}$ we finally
return the algorithm performing best according to this label.

Since the choice of split is dependent on the utilized loss functions, their
behavior is the dominant factor in the model’s quality. However, we found that
not all ranking loss functions are well suited for Hybrid Forests and a
mismatch in the scale of ranking and regression losses can result in one loss
dominating the other thereby mitigating the impact of $\lambda$. To solve this
we scaled the losses to the unit interval by scaling the performance data and
dividing the ranking loss by the maximum possible loss. Moreover, the
performance of avily depends on the right choice of $\lambda$.

##  5 Evaluation

We assess the quality of HARRIS with an experimental evaluation on a small
subset of the ASLib benchmark [2]. All experiments were run on Intel Xeon
E5-2695 v3 @ 2.30GHz CPU and 64 GB RAM. To set our results into context, we
evaluate against ISAC [11], random forest regressor (RFR) that predicts each
algorithms performance with a random forests, and SATzilla’11 [22] as done in
several recent works [21, 18, 19]. In the interest of reproducibility, all
code is available at 111Github link: https://github.com/LukasFehring/HARRIS-
Hybrid_rAnking_and_RegRessIon_foreSts.

The quality of each approach is evaluated using 10-fold cross validation with
Kendall’s Tau-b [12] and PAR10 [2]. Kendall’s Tau quantifies the correlation
between two rankings, where $1$ indicates a perfect and $-1$ an inverse
correlation. The PAR10 score corresponds to the runtime of the selected
algorithm, if it is below a threshold $C$ and $10\cdot C$ otherwise. This
threshold $C$ is provided by the benchmark and corresponds to an upper bound
on the runtime.

Table 1: Quality of the best known nfiguration and competitors quantified with
PAR10.

| HARRIS | ISAC | RFR | SAT
---|---|---|---|---
Scenario Name
CSP-Minizinc-Time-2016  | 476.97 |  $\pm$661.60 | 1194.64 |  $\pm$592.74 | 1044.55 |  $\pm$886.96 | 1058.08 |  $\pm$1184.75
MIP-2016  | 1728.82 |  $\pm$1649.62 | 2975.35 |  $\pm$3205.29 | 4332.53 |  $\pm$3320.56 | 2989.38 |  $\pm$2836.52
QBF-2016  | 1382.08 |  $\pm$328.42 | 1704.74 |  $\pm$757.74 | 1722.20 |  $\pm$836.78 | 1607.81 |  $\pm$627.32
CPMP-2015  | 4891.47 |  $\pm$1205.64 | 6094.06 |  $\pm$1972.29 | 5634.73 |  $\pm$2181.76 | 5152.87 |  $\pm$1521.40
ASP-POTASSCO  | 209.47 |  $\pm$59.07 | 348.57 |  $\pm$133.53 | 178.81 |  $\pm$52.20 | 236.48 |  $\pm$74.78
MAXSAT12-PMS  | 795.44 |  $\pm$399.61 | 1067.84 |  $\pm$700.12 | 631.14 |  $\pm$425.60 | 553.61 |  $\pm$371.80
QBF-2011  | 2464.69 |  $\pm$721.31 | 3271.56 |  $\pm$1270.76 | 1865.75 |  $\pm$804.27 | 1520.36 |  $\pm$630.32
SAT12-HAND  | 2150.58 |  $\pm$497.06 | 2587.54 |  $\pm$484.89 | 1552.95 |  $\pm$264.20 | 1135.70 |  $\pm$204.81
SAT12-ALL  | 2476.95 |  $\pm$202.07 | 1999.36 |  $\pm$321.40 | 1144.46 |  $\pm$280.86 | 1349.94 |  $\pm$173.25
Average Rank  | 2.11 | 3.56 | 2.33 | 2.00

Table 1 displays the PAR10 scores averaged across all folds of each approach
on the corresponding scenario including the standard deviation. Bold letters
indicate the best performance. Note that the performances shown for e
optimistic as they correspond to the best performance achieved by varying
$\lambda$ in steps of $0.1$ and the tree depth in $\\{2,4,6,8.10\\}$. Thus,
they can only serve to get an idea of what capable of, if $\lambda$ can be
tuned correctly. According to the average rank, the second best approach.

Figure 1: Visulisation of $\lambda$’s impact on the quality of HARRIS

Figure 1 visualizes the change in quality of th fixed depth for varying
$\lambda$ in the PAR10 metric. The results indicate that while $\lambda$
strongly impacts the overall model quality, there are scenarios for which
HARRIS is the superior/inferior model. More figures can be found in the
appendix (Section 7).

##  6 Conclusion

In this work, we proposed a hybrid ranking and regression tree-based approach
to AS called, onceptually, leviates the weaknesses of pure ranking and
regression AS solutions. In a prototypical experimental study, we showed that
with appropriately set hyperparameters, n outperform existing algorithm
selectors on some scenarios. In future work, we plan to investigate whether
tuning these hyperparameters automatically via means of hyperparameter
optimization [1] yields good values on a scenario as suggested in [14].
Moreover, we plan to investigate other options for combining regression and
ranking loss functions, for example, by working with probabilistic loss
functions as this alleviates possible problems related to different scales.

### Acknowledgements

This work was supported by the German Research Foundation (DFG) within the
Collaborative Research Center “On-The-Fly Computing” (SFB 901/3 project no.
160364472).

## References

  * [1] Bernd Bischl, Martin Binder, Michel Lang, Tobias Pielok, Jakob Richter, Stefan Coors, Janek Thomas, Theresa Ullmann, Marc Becker, Anne-Laure Boulesteix, Difan Deng and Marius Lindauer  “Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges”  In _CoRR_ abs/2107.05847, 2021  arXiv: https://arxiv.org/abs/2107.05847
  * [2] Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown, Kevin Tierney and Joaquin Vanschoren  “ASlib: A benchmark library for algorithm selection”  In _Artificial Intelligence_ 237, 2016, pp. 41–58  DOI: 10.1016/j.artint.2016.04.003
  * [3] Pavel Brazdil and Carlos Soares  “A Comparison of Ranking Methods for Classification Algorithm Selection”  In _ECML 2000: Proceedings of the 11th European Conference on Machine Learning_ 1810, Lecture Notes in Computer Science  Springer, 2000, pp. 63–74  DOI: 10.1007/3-540-45164-1\\_8
  * [4] Leo Breiman  “Random Forests”  In _Mach. Learn._ 45.1, 2001, pp. 5–32  DOI: 10.1023/A:1010933404324
  * [5] Leo Breiman, J.. Friedman, R.. Olshen and C.. Stone  “Classification and Regression Trees”  Wadsworth, 1984
  * [6] Tiago Cunha, Carlos Soares and André C…. Carvalho  “A label ranking approach for selecting rankings of collaborative filtering algorithms”  In _SAC 2018: Proceedings of the 33rd Annual ACM Symposium on Applied Computing_ ACM, 2018, pp. 1393–1395  DOI: 10.1145/3167132.3167418
  * [7] Nils Froleyks, Marijn Heule, Markus Iser, Matti Järvisalo and Martin Suda  “SAT Competition 2020”  In _Artificial Intelligence_ 301, 2021, pp. 103572  DOI: 10.1016/j.artint.2021.103572
  * [8] Jonas Hanselle, Alexander Tornede, Marcel Wever and Eyke Hüllermeier  “Algorithm Selection as Superset Learning: Constructing Algorithm Selectors from Imprecise Performance Data”  In _PAKDD 2021: Proceedings of the 25th Pacific-Asia Conference_ 12712, Lecture Notes in Computer Science  Springer, 2021, pp. 152–163  DOI: 10.1007/978-3-030-75762-5\\_13
  * [9] Jonas Hanselle, Alexander Tornede, Marcel Wever and Eyke Hüllermeier  “Hybrid Ranking and Regression for Algorithm Selection”  In _KI 2020: Proceedings of the 43rd German Conference on AI_ 12325, Lecture Notes in Computer Science  Springer, 2020, pp. 59–72  DOI: 10.1007/978-3-030-58285-2\\_5
  * [10] Marijn J.. Heule, Matti Järvisalo and Martin Suda  “SAT Competition 2018”  In _J. Satisf. Boolean Model. Comput._ 11.1, 2019, pp. 133–154  DOI: 10.3233/SAT190120
  * [11] Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann and Kevin Tierney  “ISAC - Instance-Specific Algorithm Configuration”  In _ECAI 2010: Proceedings of the 19th European Conference on Artificial Intelligence_ 215, Frontiers in Artificial Intelligence and Applications  IOS Press, 2010, pp. 751–756  DOI: 10.3233/978-1-60750-606-5-751
  * [12] Maurice G Kendall  “The treatment of ties in ranking problems”  In _Biometrika_ 33.3 JSTOR, 1945, pp. 239–251
  * [13] Shili Lin  “Rank aggregation methods”  In _Wiley Interdisciplinary Reviews: Computational Statistics_ 2.5 Wiley Online Library, 2010, pp. 555–570
  * [14] Marius Lindauer, Holger H. Hoos, Frank Hutter and Torsten Schaub  “AutoFolio: An Automatically Configured Algorithm Selector”  In _Journal of Artificial Intelligence Research_ 53, 2015, pp. 745–778  DOI: 10.1613/jair.4726
  * [15] John R. Rice  “The Algorithm Selection Problem”  In _Adv. Comput._ 15, 1976, pp. 65–118  DOI: 10.1016/S0065-2458(08)60520-3
  * [16] D. Sculley  “Combined regression and ranking”  In _SIGKDD 2010: Proceedings of the 16th ACM International Conference on Knowledge Discovery and Data Mining_ ACM, 2010, pp. 979–988  DOI: 10.1145/1835804.1835928
  * [17] C. Spearman  “"General Intelligence" Objectively Determined and Measured”, Studies in individual differences: The search for intelligence  East Norwalk, CT, US: Appleton-Century-Crofts, 1961  DOI: 10.1037/11491-006
  * [18] A. Tornede, M. Wever and E. Hüllermeier  “Towards Meta-Algorithm Selection”  In _Workshop on Meta-Learning (MetaLearn 2020) @ NeurIPS 2020_ , 2020
  * [19] Alexander Tornede, Lukas Gehring, Tanja Tornede, Marcel Wever and Eyke Hüllermeier  “Algorithm selection on a meta level”  In _Machine Learning_ Springer, 2022, pp. 1–34
  * [20] Alexander Tornede, Marcel Wever and Eyke Hüllermeier  “Extreme Algorithm Selection with Dyadic Feature Representation”  In _DS 2020: Proceedings of the 23rd International Conference on Discovery Science_ 12323, Lecture Notes in Computer Science  Springer, 2020, pp. 309–324  DOI: 10.1007/978-3-030-61527-7\\_21
  * [21] Alexander Tornede, Marcel Wever, Stefan Werner, Felix Mohr and Eyke Hüllermeier  “Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis”  In _ACML 2020: Proceedings of The 12th Asian Conference on Machine Learning_ 129, Proceedings of Machine Learning Research  PMLR, 2020, pp. 737–752  URL: http://proceedings.mlr.press/v129/tornede20a.html
  * [22] Lin Xu, Frank Hutter, Holger H Hoos and Kevin Leyton-Brown  “Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming”  In _RCRA workshop on experimental evaluation of algorithms for solving problems with combinatorial explosion@IJCAI 2011_ , 2011, pp. 16–30
  * [23] Lin Xu, Frank Hutter, Holger H. Hoos and Kevin Leyton-Brown  “The Design and Analysis of an Algorithm Portfolio for SAT”  In _CP 2007: Proceedings of the 13th International Conference on Constraint Programming_ 4741, Lecture Notes in Computer Science  Springer, 2007, pp. 712–727  DOI: 10.1007/978-3-540-74970-7\\_50

##  7 Appendix

### Benchmark Scenarios

As mentioned in the paper, we evaluated the competitors performances with the
ASlib [2] benchmark. However, we were not able to evaluate on all scenarios
but just a subset of them. Key properties of them are shown in Table 2.

Table 2: Properties of the benchmark scenarios used for model evaluation.

Scenario | Problem | Instances | Algorithms | Features | Unsolved Instances | Proportion Unsolved Instances | Proportion Missing Evaluation | Cutoff
---|---|---|---|---|---|---|---|---
ASP-POTASSCO | ASP | 1294 | 11 | 138 | 82 | 0.06 | 0.20 | 600.0
CPMP-2015 | CPMP | 527 | 4 | 22 | 0 | 0.00 | 0.28 | 3600.0
CSP-Minizinc-Time-2016 | CSP | 100 | 20 | 95 | 17 | 0.17 | 0.50 | 1200.0
MAXSAT12-PMS | MAXSAT12 | 876 | 6 | 37 | 129 | 0.15 | 0.41 | 2100.0
MIP-2016 | MIP | 218 | 5 | 143 | 0 | 0.00 | 0.20 | 7200.0
QBF-2011 | QBF | 1368 | 5 | 46 | 314 | 0.23 | 0.55 | 3600.0
QBF-2016 | QBF | 825 | 24 | 46 | 55 | 0.07 | 0.36 | 1800.0
SAT12-HAND | SAT12 | 767 | 31 | 115 | 229 | 0.30 | 0.67 | 1200.0
SAT12-INDU | SAT12 | 1167 | 31 | 115 | 209 | 0.18 | 0.50 | 1200.0

An instance is unsolved if no candidate algorithm solves the instance before
the cutoff is reached. An evaluation of some algorithm on an instance is
missing if the algorithm does not finish it’s calculation before the cutoff is
reached.

### Further Evaluation Results

In the paper we were only able to give a brief overview over the results of
our evalaution. Further resutls are shown in the following figures.

Figure 2 shows the results of our PAR10 evaluation for all considered
scenarios.

Figure 2: Quality Comparison of different HARRIS configurations with the
Random Forest Regressor. The model quality is quantified with PAR10.

Figure 3 shows the results of our Kendall’s Tau-b evaluation for all
considered scenarios.

Figure 3: Quality Comparison of different HARRIS combinations with the Random
Forest Regressor. The model quality is quantified with the Kendall’s Tau
metric.

Figure 4 shows the results of our evaluation of different tree depths in terms
of the PAR10 number of the resulting algorithm selector.

Figure 4: Evaluation of the stopping criterion’s impact on the overall model
quality. Note that the results indicate that ght improve for increasing depth
on some scenarios.