###### Abstract

The prominent flat-spectrum radio quasar J0017+8135 (S5 0014+81) at $z$ =
3.366 is one of the most luminous active galactic nuclei (AGN) known. Its
milliarcsecond-scale radio jet structure has been studied with very long
baseline interferometry (VLBI) since the 1980s. The quasar was selected as one
of the original defining objects of the International Celestial Reference
Frame, but left out from its current second realization (ICRF2) because of
systematic long-term positional variations. Here we analyse archival 8.6- and
2.3-GHz VLBI imaging data collected at nearly 100 different epochs during more
than 20 years, to obtain information about the kinematics of jet components.
Because of the cosmological time dilation, extensive VLBI monitoring data are
essential to reveal changes in the jet structure of high-redshift AGN. In the
case of J0017+8135, the data can be described with a simple kinematic model of
jet precession with a 12-year periodicity in the observer’s frame.

###### keywords:

blazars; jets; very long baseline interferometry; precession; high redshift

10 10.3390/galaxies4030010 4 Academic Editor: Jose L. Gómez, Alan P. Marscher
and Svetlana G. Jorstad Received: 12 July 2016; Accepted: 18 August 2016
Precessing Jet in the High-Redshift Blazar J0017+8135 Kristóf Rozgonyi 1 and
Sándor Frey 2,* Kristóf Rozgonyi and Sándor Frey Correspondence:
<EMAIL_ADDRESS>
##  1 Introduction

The blazar J0017+8135 (S5 0014+81) is listed in the S5 sample of strong
northern radio sources with $S$ = 551 mJy total flux density at 5 GHz 1 . Its
spectroscopic redshift is $z$ = 3.366 2 . This flat-spectrum radio quasar is
known as one of the most luminous active galactic nuclei (AGN) and has been
subject to various studies at multiple wavebands, from the radio to X-rays
(e.g., 3 ; 4 ; 5 ; 6 ). The mass of its central black hole is $M=4\times
10^{10}M_{\odot}$, among the highest values measured in AGN 5 . The source has
been extensively studied with very long baseline interferometry (VLBI) since
the 1980s, and it was also one of the sources first observed with space VLBI 7
; 8 . The one-sided core–jet structure of J0017+8135 extending towards the
south at milliarcsecond (mas) angular scales is typical for blazars. The jet
components show no or moderate apparent superluminal motion 9 ; 10 .
J0017+8135 was selected as one of the original defining objects of the
International Celestial Reference Frame (ICRF), but left out from its current
second realization (ICRF2) because of systematic long-term positional
variations 11 . In this paper, we make use of the publicly available archival
2.3- and 8.6-GHz VLBI imaging data spanning more than two decades, to
investigate the positional variations of the jet components in J0017+8135. We
find indication of periodic changes and attempt to explain them in the
framework of a simple jet precession model. A detailed jet kinematic study for
a blazar at such a high redshift is unique. Changes in the source structure
appear slower by a factor of $(1+z)$ in the observer’s frame due to
cosmological time dilation; therefore, long-term VLBI monitoring is necessary
to reliably reveal them in the case of high-redshift radio-loud AGN.

##  2 VLBI Observations, Images and Brightness Distribution Modeling

The study presented here is based on 95 VLBI imaging data sets at 8.6 GHz (X
band). In 74 cases, VLBI data obtained at the same epochs are also available
at 2.3 GHz (S band). The observations were done with the U.S. National Radio
Astronomy Observatory (NRAO) Very Long Baseline Array (VLBA), occasionally
supplemented with various other radio telescopes, covering the time range from
August 1994 to February 2015. We used the calibrated visibility data sets
downloaded from 12 .

The imaging and model-fitting were performed through standard procedures using
Difmap 13  in an automated way. The visibility data were modeled with sets of
2 or 3 Gaussian brightness distributions. The core was fitted with an
elliptical Gaussian component at both frequencies. The jet at 8.6 GHz was
fitted with one, and at 2.3 GHz with two circular Gaussians. A pair of typical
VLBI images of the source with the fitted model components is presented in
Figure 1.

Figure 1: Pair of typical very long baseline interferometry (VLBI) images of
the source J0017+8135. The images were taken in October 1998 at 8.6 GHz (a)
and 2.3 GHz (b). The lowest contours correspond to 1% of the peak brightness,
the positive contours increase by a factor of 2. The white circles are
centered at the positions of the fitted Gaussian model components. Their
radius corresponds to the full-width-at-half-maximum diameter of the given
component. The restoring beam is indicated in the lower-left corner.

The core is labeled as C, the jet components are J1, J2 and J3, respectively.
In the 2.3-GHz images, the central component is labeled as C+J1 as it blends
the two innermost components found in the higher-resolution 8.6-GHz data.
Although an opacity correction would be needed, it would have a minor effect
due to the relatively close observing frequencies. Thus, in both cases, the
central component was considered as the kinematic centre for the modeling.

##  3 A Simple Jet Precession Model

We fitted a kinematic model 14  to the relative positions of the brightness
distribution components measured as a function of time, to quantitatively
describe the periodic behaviour of their motion. We assumed that the plasma
blobs ejected at different epochs move in a ballistic trajectory. At each
epoch, we see the ejected components at their actual projected positions, and
the base of the jet as the optically thick ‘core’ region. The relative
positions of the identified components can change over time if the core is
wobbling (i.e., changing its absolute position). Thus, if we choose the core
component as the kinematic centre of the jet, the movements of the core will
be reflected in the relative movements of the ejected components. The relative
positions of the jet components show periodic difference from the ballistic
track, thus we assume a possible precession of the jet.

In our precession model, we make three assumptions for the kinematics and
geometry of the jet: (1) the jet sweeps a conical surface whose half opening
angle $\Omega$ and axis are constant over time; (2) the jet is precessing with
a constant $\omega$ angular velocity around the cone axis; and (3) the jet
components ejected at $t_{0}$ epoch can be described at $t$ with two time-
dependent angles: $\eta(t)$ and $\Phi(t)$. In this scenario, the ejected
components will follow a helical path in the plane of the sky. The projections
of this kind of motion to the right ascension (RA) and declination (Dec) axes
can be described as superpositions of a linear and a periodic function. The
angular frequency of the projected motions is characteristic to the jet
precession, thus it has to be equal in both directions. The apparent
precessing motion of the jet is the combination of the two perpendicular
oscillations in this model. Figure 2 shows the geometric configuration of the
jet model.

Figure 2: Jet precession geometry. The line of sight is parallel to the $z$
axis. Right ascension and declination correspond to the $x$ and $y$ axes,
respectively. The $\eta$ position angle is measured from north through east.

Assuming this configuration, for each jet feature, we can fit a superposition
of a linear and a periodic function to the projected component RA and Dec
angular distances from the core:

$s_{i}(t)=s_{0i}+\mu_{i}t+A_{i}(\omega t+\varphi_{i}),$ (1)

where $i\in[{\rm RA,Dec}]$, $s_{i}(t)$ is the component distance from the core
at the time $t$, $s_{0i}$ is the component distance from the core at $t=0$,
$\mu_{i}$ is the proper motion of the component, $\omega$ is the common
angular frequency, $A_{i}$ and $\varphi_{i}$ are the fitted amplitude and
phase, respectively.

As a boundary condition, the model requires that the relative RA and Dec
positions of the components at the ejection epoch $t_{0}$ are

$s_{\rm RA}(t_{0})\>=\>s_{\rm Dec}(t_{0})\>=\>0.$ (2)

However, if the amplitude of the precession is small, we can simplify this
condition so that only the fitted ballistic slopes have to intersect the $t$
axis at the same point. From this assumption, we get

$\frac{s_{0\,\rm RA}}{\mu_{\rm RA}}=\frac{s_{0\,\rm Dec}}{\mu_{\rm Dec}}.$ (3)

Thus we have to fit the model to the relative RA and Dec position data for all
components at the same time, with the common parameter $\omega$. Considering
the simplified boundary condition, the kinematic model can be expressed as

$\displaystyle s_{\rm RA}(t)=\frac{s_{0\,\rm Dec}\mu_{\rm RA}}{\mu_{\rm
Dec}}+\mu_{\rm RA}t+A_{\rm RA}(\omega t+\varphi_{\rm RA}),$ (4) $\displaystyle
s_{\rm Dec}(t)=s_{0\,\rm Dec}+\mu_{\rm Dec}t+A_{\rm Dec}(\omega t+\varphi_{\rm
Dec}).$

##  4 Jet Kinematic Model Parameter Estimates

To analyze the precession of the jet model components, we fitted Equation (4)
to the jet component positions relative to the core as derived from the multi-
epoch VLBI data. We applied the Metropolis–Hastings algorithm 15 ; 16  to look
for the best-fit parameters for each component. Figure 3 illustrates the
fitted model for the jet components.

Figure 3: The relative separation of the components from the core as a
function of time, and the best-fitting model (solid curves). Not all
components were detected at each epoch, and the dense time sampling allowed us
to drop out positional outliers over 3$\sigma$ from the analysis. As a result,
the fitted precession model is based on 73, 56, and 55 observing epochs for
components J1, J2, and J3, respectively.

Based on the best-fitting model parameters, we can express the main kinematic
properties of the jet components (Table 1). We estimated the angular frequency
$\omega$, the precession period $T$, and the apparent proper motions
$\beta_{\rm app}$ for each component (expressed in the units of the speed of
light $c$). To estimate $\phi(t_{0})$ and $\Omega$ with reasonably small
error, we would have to observe more model components in the jet 14 .
Nevertheless, we also estimated the projected angle of the precession cone
axis on the plane of the sky at the ejection epoch, $\eta(t_{0})$, measured
from north through east.

Table 1: The kinematic properties of model components. Parameter | J1 | J2 | J3
---|---|---|---
$\omega$ (year-1) | $0.51\>\pm\>0.08$ | $0.51\>\pm\>0.15$ | $0.5\>\pm\>0.1$
$T$ (year) | $12\>\pm\>2$ | $12\>\pm\>4$ | $12\>\pm\>2$
$\beta_{\rm app}$ | $0.9\>\pm\>0.2$ | $1.8\>\pm\>1.0$ | $2.0\>\pm\>0.3$
$\eta(t_{0})$ (∘) | $180\>\pm\>15$ | $195\>\pm\>34$ | $189\>\pm\>10$

##  5 Discussion

We found that, according to the expectations, the ejection epochs were in
chronological order for the J3, J2, and J1 components, respectively. The
apparent motion of the components is dominantly in the Dec direction, and the
amplitude of the periodic motion is higher in this direction. Thus the
precession cone is projected onto the sky as an ellipse stretched in the
north–south direction, in accordance with the absolute astrometric position
changes 11 . Somewhat similarly to earlier results based on VLBI observations
spanning shorter intervals 9 ; 10 , our analysis reveals mild superluminal
motion ($\sim$$1-2c$) in the jet components of J0017+8135 but with smaller
uncertainties.

In the framework of the kinematic model applied here, the jet has a precession
period of ($12\>\pm\>3$) year in the observer’s frame. This is a unique result
for a blazar at $z>3$ where the cosmological time dilation makes it more
difficult to detect periodicities compared to low-redshift sources. However,
it should be noted that this analysis is based on data that span an interval
shorter than twice the putative period. Therefore any stochastic variability
might be mistakenly identified as periodic. Continuing VLBI monitoring of
J0017+8135 on a longer term, and the analysis of absolute astrometric position
variations 11  and total flux density monitoring data 17  in the context of
the jet precession model would help confirming our results in the future.

Finally, it is also possible that physical mechanisms other than precession
cause the observed apparently helical path of the jet components. For example,
plasma instabilities propagating along a conical jet can cause this effect. In
fact, studies of large samples of sources monitored with VLBI revealed that
non-ballistic motion is ubiquitous in pc-scale AGN jets (18  and references
therein).

###### Acknowledgements.

This work was supported by the Hungarian National Research, Development and
Innovation Office (OTKA K104539). The NRAO is a facility of the National
Science Foundation operated under cooperative agreement by Associated
Universities, Inc. The Astrogeo Center Database of brightness distributions,
correlated flux densities, and images of compact radio sources produced with
VLBI is maintained by L. Petrov. Kristóf Rozgonyi analyzed the data and
performed the modeling, Sándor Frey contributed to the design of the study and
the interpretation of the results. Both authors participated in the writing of
the paper. The authors declare no conflict of interest.

## References

  * (1) Kühr, H.; Pauliny-Toth, I.I.K.; Witzel, A.; Schmidt, J. The 5-GHz strong source surveys. V—Survey of the area between declinations 70∘ and 90∘. Astron. J. 1986, 86, 854–863.
  * (2) Osmer, P.S.; Porter, A.C.; Green, R.F. Luminosity effects and the emission-line properties of quasars with $0<z<3.8$. Astrophys. J. 1994, 436, 678–695.
  * (3) Kühr, H.; Liebert, J.W.; Strittmatter, P.A.; Schmidt, G.D.; Mackay, C. The most luminous quasar: S5 0014+81. Astrophys. J. 1983, 275, L33–L37.
  * (4) Cappi, M.; Matsuoka, M.; Comastri, A.; Brinkmann, W.; Elvis, M.; Palumbo, G.G.C.; Vignali, C. ASCA and ROSAT X-ray spectra of high-redshift radio-loud quasars. Astrophys. J. 1997, 478, 492–510.
  * (5) Ghisellini, G.; Foschini, L.; Volonteri, M.; Ghirlanda, G.; Haardt, F.; Burlon, D.; Tavecchio, F. The blazar S5 0014+813: A real or apparent monster? Mon. Not. R. Astron. Soc. 2009, 399, L24–L29.
  * (6) Paliya, V.S.; Parker, M.L.; Fabian, A.C.; Stalin, C.S. Broadband observations of high redshift blazars. Astrophys. J. 2016, 825, 74.
  * (7) Hirabayashi, H.; Hirosawa, H.; Kobayashi, H.; Murata, Y.; Edwards P.G.; Fomalont, E.B.; Fujisawa, K.; Ichikawa, T.; Kii, T.; Lovell, J.E.J.; et al. Overview and initial results of the very long baseline interferometry space observatory programme. Science 1998, 281, 1825–1829.
  * (8) Gurvits, L.I.; Frey, S.; Schilizzi, R.T.; Kellermann, K.I.; Lobanov, A.P.; Kawaguchi, N.; Kobayashi, H.; Murata, Y.; Hirabayashi, H.; Pauliny-Toth, I.I.K. Dual-frequency VSOP observations of extremely high redshift quasars. Adv. Space Res. 2000, 26, 719–722.
  * (9) Piner, B.G.; Mahmud, M.; Fey, A.L.; Gospodinova, K. Relativistic jets in the radio reference frame image database. I. Apparent speeds from the first 5 years of data. Astron. J. 2007, 133, 2357–2388.
  * (10) Piner, B.G.; Pushkarev, A.B.; Kovalev, Y.Y.; Marvin, C.J.; Arenson, J.G.; Charlot, P.; Fey, A.L.; Collioud, A.; Voitsik, P.A. Relativistic jets in the radio reference frame image database. II. Blazar jet accelerations from the first 10 years of data (1994–2003). Astrophys. J. 2012, 758, 84.
  * (11) Fey, A.L.; Gordon, D.; Jacobs, C.S.; Ma, C.; Gaume, R.A.; Arias, E.F.; Bianco, G.; Boboltz, D.A.; Böckmann, S.; Bolotin, S.; et al. The second realization of the international celestial reference frame by very long baseline interferometry. Astron. J. 2015, 150, 58.
  * (12) Astrogeo Database. Available online: blackhttp://astrogeo.org/cgi-bin/imdb_get_source.csh?source=J0017%2B8135blue (accessed on 7 July 2016).
  * (13) Shepherd, M.C.; Pearson, T.J.; Taylor, G.B. DIFMAP: An interactive program for synthesis imaging. Bull. Am. Astron. Soc. 1994, 26, 987–989.
  * (14) Caproni, A.; Abraham, Z. Can long-term periodic variability and jet helicity in 3C 120 be explained by jet precession? Mon. Not. R. Astron. Soc., 2004, 349, 1218–1226.
  * (15) Metropolis, N.; Ulam, S. The monte carlo method. J. Am. Stat. Assoc. 1949, 44, 335–341.
  * (16) Hastings, W.K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 1970, 57, 97–109.
  * (17) Richards, J.L.; Max-Moerbeck, W.; Pavlidou, V.; King, O.G.; Pearson, T.J.; Readhead, A.C.S.; Reeves, R.; Shepherd, M.C.; Stevenson, M.A.; Weintraub, L.C.; et al. Blazars in the Fermi Era: The OVRO 40-m telescope monitoring program. Astrophys. J. Suppl. Ser. 2011, 194, 29.
  * (18) Lister, M.L.; Aller, M.F.; Aller, H.D.; Homan, D.C.; Kellermann, K.I.; Kovalev, Y.Y.; Pushkarev, A.B.; Richards, J.L.; Ros, E.; Savolainen, T. MOJAVE XIII. Parsec-scale AGN jet kinematics analysis based on 19 years of VLBA observations at 15 GHz. Astron. J. 2016, 152, 12.


# Text-to-Motion Retrieval: Towards Joint Understanding of
Human Motion Data and Natural Language

Nicola Messina  ISTI-CNRPisaItaly<EMAIL_ADDRESS>,  Jan
Sedmidubsky  Masaryk UniversityBrnoCzechia<EMAIL_ADDRESS>,  Fabrizio
Falchi  ISTI-CNRPisaItaly<EMAIL_ADDRESS>and  Tomáš Rebok
Masaryk UniversityBrnoCzechia<EMAIL_ADDRESS>
(2023)

###### Abstract.

Due to recent advances in pose-estimation methods, human motion can be
extracted from a common video in the form of 3D skeleton sequences. Despite
wonderful application opportunities, effective and efficient content-based
access to large volumes of such spatio-temporal skeleton data still remains a
challenging problem. In this paper, we propose a novel content-based text-to-
motion retrieval task, which aims at retrieving relevant motions based on a
specified natural-language textual description. To define baselines for this
uncharted task, we employ the BERT and CLIP language representations to encode
the text modality and successful spatio-temporal models to encode the motion
modality. We additionally introduce our transformer-based approach, called
Motion Transformer (MoT), which employs divided space-time attention to
effectively aggregate the different skeleton joints in space and time.
Inspired by the recent progress in text-to-image/video matching, we experiment
with two widely-adopted metric-learning loss functions. Finally, we set up a
common evaluation protocol by defining qualitative metrics for assessing the
quality of the retrieved motions, targeting the two recently-introduced KIT
Motion-Language and HumanML3D datasets. The code for reproducing our results
is available here: https://github.com/mesnico/text-to-motion-retrieval.

human motion data, skeleton sequences, CLIP, BERT, deep language models,
ViViT, motion retrieval, cross-modal retrieval

††copyright: acmcopyright††journalyear: 2023††copyright:
rightsretained††conference: Proceedings of the 46th International ACM SIGIR
Conference on Research and Development in Information Retrieval; July 23–27,
2023; Taipei, Taiwan††booktitle: Proceedings of the 46th International ACM
SIGIR Conference on Research and Development in Information Retrieval (SIGIR
’23), July 23–27, 2023, Taipei, Taiwan††doi: 10.1145/3539618.3592069††isbn:
978-1-4503-9408-6/23/07††ccs: Information systems Novelty in information
retrieval††ccs: Information systems Language models††ccs: Information systems
Evaluation of retrieval results††ccs: Information systems Data access methods

Figure 1. Five motions retrieved for two different queries specified by free
text (CLIP as text encoder, MoT as motion encoder).

##  1\. Introduction and Related Work

Pose-estimation methods (Dubey and Dixit, 2022) can detect 3D human-body
keypoints in a single RGB video stream. The keypoints detected in individual
frames constitute a simplified spatio-temporal representation of human motion
in the form of a so-called _skeleton sequence_. As indicated in (Sedmidubsky
et al., 2021), the analysis of such representation opens unprecedented
application potential in many domains, ranging from virtual reality, through
robotics and security, to sports and medicine. The ever-increasing popularity
of skeleton data calls for technologies able to effectively and efficiently
access large volumes of such spatio-temporal data based on its content.

Research in skeleton-data processing mainly focuses on designing deep-learning
architectures for classification of labeled actions (Cheng et al., 2021a; Peng
et al., 2021; Lv et al., 2021) or detection of such actions in continuous
streams (Papadopoulos et al., 2019; Song et al., 2018). The proposed
architectures are often learned in a supervised way based on transformers
(Aksan et al., 2020; Cheng et al., 2021a, b), convolutional (Lv et al., 2021),
recurrent (Song et al., 2018), or graph-convolutional (Duan et al., 2022; Peng
et al., 2021) networks. Recently, self-supervised methods are becoming
increasingly popular as they can learn motion semantics without knowledge of
labels using reconstruction-based (Zhang et al., 2023; Sedmidubsky et al.,
2023) or contrastive-based learning (Yang et al., 2022; Lin et al., 2020).

The trained architectures can serve as _motion encoders_ that express the
motion semantics by a high-dimensional _feature_ vector extracted from the
last hidden network layer. This concept can be transferred to the _motion
retrieval_ task to support content-based access based on the _query-by-
example_ paradigm (Sedmidubsky et al., 2021; Budikova et al., 2021;
Sedmidubsky et al., 2020), which aims at identifying the database motions that
are the most similar to a user-defined query motion. Besides balancing
descriptiveness and indexability of the motion features, the most critical
issue is to specify a convenient query motion example. The example can be
selected from available skeleton sequences (Sedmidubsky et al., 2023), drawn
in a visualization-driven graphical user interface (Bernard et al., 2013),
modeled by puppet interfaces (Numaguchi et al., 2011), specified as a set of
logical constraints (Kapadia et al., 2013), or artificially generated (Deng et
al., 2009). However, such a query example may not ever exist, or its
construction requires professional modeling skills. This paper focuses on
motion retrieval but simplifies query specification by enabling users to
formulate a query by free text.

With the current advances in cross-modal learning, especially in the field of
textual-visual processing, the trend is to learn common multi-modal spaces
(Messina et al., 2022a) so that similar images can be described and searched
with textual descriptions (Messina et al., 2021b). A representative example is
the CLIP model (Radford et al., 2021), which learns an effective common space
for the visual and textual modalities. This allows the use of open
vocabularies or complex textual queries for searching images.

Our work has many analogies with the text-to-video retrieval task (Fang et
al., 2021; Luo et al., 2022; Shvetsova et al., 2022; Zhao et al., 2022; Liu et
al., 2022), given that the moving skeleton also evolves in space and time.
Despite the popularity of such powerful and versatile text-vision models, no
effort has been made for the skeleton-data modality. Differently from video
data, the skeleton is anonymized and avoids learning many common biases
present in video datasets. To the best of our knowledge, there is only one
approach (Kim et al., 2022) that relates to text-to-motion matching. However,
it uses pre-training and tackles only the classification task. A few available
datasets providing the training data for text-to-motion retrieval – e.g., the
KIT Motion Language (Plappert et al., 2016) and recently-released HumanML3D
(Guo et al., 2022a) datasets – are primarily used for motion generation from a
textual description (Zhang et al., 2023; Guo et al., 2022b; Tevet et al.,
2022; Zhang et al., 2022; Petrovich et al., 2021), where the idea is to align
text and motion embeddings into a common space, but never explicitly handling
the text-to-motion retrieval task.

### Contributions of this Paper

We tackle the above-mentioned gap by introducing a novel _text-to-motion_
retrieval task, which aims at searching databases of skeleton sequences and
retrieving those that are the most relevant to a detailed textual query. For
this task, we define evaluation metrics, establish new qualitative baselines,
and propose the first text-to-motion retrieval approach. These initial
contributions can be employed for future studies on this challenging yet
unexplored task.

Specifically, one of the main paper contributions is the proposal of a fair
baseline by adopting promising (1) _motion encoders_ already employed as
backbones in other motion-related tasks and (2) _text encoders_ successfully
applied in natural language processing (NLP) and text-to-image retrieval. The
core of this baseline is a two-stream pipeline where the motion and text
modalities are processed by separate encoders. The obtained representations
are then projected into the same common space, for which a metric is learned
in a similar way as in CLIP (Radford et al., 2021) or ALADIN (Messina et al.,
2022b) in the text-to-image scenario. The choice of a two-stream pipeline is
strategic to make the approach scalable to large motion collections, as
feature vectors extracted from both modalities can be easily stored in off-
the-shelf indexes implementing efficient similarity search access.

Inspired by recent advances in video processing (Arnab et al., 2021), we also
propose a transformer-based motion encoder – the Motion Transformer (MoT) –
that employs divided space-time attention on skeleton joints. We show that MoT
reaches competitive results with respect to a state-of-the-art motion encoder,
DG-STGCN (Duan et al., 2022), on both KIT Motion Language and HumanML3D
datasets.

Figure 2. Schematic illustration of the learning process of the common space
of both the text and motion modalities.

##  2\. Text-to-Motion Retrieval Pipeline

The main idea of our approach is to rely on a two-stream pipeline, where
motion and text features are first extracted through ad-hoc encoders and then
projected into the same common space, as schematically illustrated in Figure
2. In this section, we sketch the whole pipeline which consists of the: (i)
text encoder, (ii) motion encoder, and (iii) loss function used to optimize
the common space.

###  2.1. Text Encoders

Inspired by recent works in NLP, we rely on two pre-trained textual models,
namely BERT (Kenton and Toutanova, 2019) and the textual encoder from CLIP
(Radford et al., 2021).

BERT. We use the implementation from (Ghosh et al., 2021), which performed the
task of motion synthesis conditioned on a natural language prompt. This model
stacks together a BERT pre-trained module and an LSTM model composed of two
layers for aggregating the BERT output tokens, producing the final text
embedding. We take the final hidden state of the LSTM model as our final
sentence representation. As in (Ghosh et al., 2021), the BERT model is fixed.
At training time, we only update the LSTM weights.

CLIP. It is a recently-introduced vision-language model trained in a
contrastive manner for projecting images and natural language descriptions in
the same common space (Radford et al., 2021). Here, we use the textual encoder
of CLIP, which is composed of a transformer encoder (Vaswani et al., 2017)
with modifications introduced in (Radford et al., 2019), and employs lower-
cased byte pair encoding (BPE) representation of the text. We then stack an
affine projection to the CLIP representation, which – similarly to the
BERT+LSTM case – is the only layer to be trained.

###  2.2. Motion Encoders

Differently from the textual pipeline, which takes as input an unstructured
natural language sentence, the input to motion encoder models is a vector
$\mathbf{x}\in\mathbb{R}^{T\times J\times D}$, where $T$ is the time length of
the motion, $J$ is the number of joints of the human-body skeleton, and $D$ is
the number of features used to encode each joint.

Bidirectional GRU. This architecture is widely adopted in time-series
processing, and an early variant that used LSTM was applied to frame-level
action detection in continuous motion data (Carrara et al., 2019). In
particular, we first increase the dimensionality of the input – which is $D=9$
in our case – by using a two-layer feed-forward network (FFN) before feeding
it into the GRU:
$\overrightarrow{\bar{\mathbf{z}}},\overleftarrow{\bar{\mathbf{z}}}=\overleftrightarrow{\text{GRU}}(\text{FFN}(\mathbf{x}))$.
Then, we compute the final motion embedding by concatenating the
representations $\overrightarrow{z}$ and $\overleftarrow{z}$.

Upper-Lower GRU. To better learn semantics of different body parts, we adopt
the model in (Ghosh et al., 2021) to independently process the upper and lower
parts of the skeleton using two GRU layers.

DG-STGCN. This architecture (Duan et al., 2022) recently reached state-of-the-
art results in motion classification. Their GCN module features a spatial
module, built of affinity matrices to capture dynamic graphical structures,
and a temporal module that performs temporal aggregation using group-wise
temporal convolutions. We refer the reader to the original formulation (Duan
et al., 2022) for further details.

MoT. Our proposed architecture that we built on top of the successful
transformer-based video processing network ViViT (Arnab et al., 2021). In the
original implementation, which processes a sequence of frames, the dimension
$J$ is the number of grid-arranged rectangular patches from each frame. In our
case, instead, the spatial features come from the joints. Instead of using as
$J$ all individual skeleton joints, we first aggregate them obtaining features
for five different body parts, similar to the pre-processing performed in
Upper-Lower GRU. In this way, $J=5$, which is far less than the total number
of skeleton joints. This is beneficial from a computational point of view, and
we found that this solution also reaches the best performance.

###  2.3. Optimization

We explore two widely-adopted metric learning loss functions, namely the
symmetric triplet loss widely used in text-to-image (Messina et al., 2021a)
and the InfoNCE Loss, introduced for cross-modal matching in (Zhang et al.,
2020) and employed in CLIP (Radford et al., 2021) and recent cross-modal works
(Luo et al., 2022). We assume $(\mathbf{m}_{i},\mathbf{c}_{i})$ is the $i$-th
motion and caption embedding pair, $S(\cdot,\cdot)$ is the cosine similarity,
and $B$ is the batch size.

The symmetric triplet loss is defined as:

$\frac{1}{B}\sum_{i}^{B}\max_{j,j\neq
i}[\alpha+S(\mathbf{m}_{i},\mathbf{c}_{j})-S(\mathbf{m}_{i},\mathbf{c}_{i})]_{+}+\max_{j,j\neq
i}[\alpha+S(\mathbf{m}_{j},\mathbf{c}_{i})-S(\mathbf{m}_{i},\mathbf{c}_{i})]_{+}$

where $[x]_{+}\equiv max(0,x)$ and $\alpha$ is a fixed margin. The index $j$
identifies the hardest negative of the element with index $i$.

Info-NCE is basically a symmetric cross-entropy loss, defined as:

$\begin{split}-\frac{1}{B}\sum_{i}^{B}\log\frac{\exp(S(\mathbf{m}_{i},\mathbf{c}_{i})/\tau)}{\sum_{j}^{B}\exp(S(\mathbf{m}_{i},\mathbf{c}_{j})/\tau)}+\log\frac{\exp(S(\mathbf{m}_{i},\mathbf{c}_{i})/\tau)}{\sum_{j}^{B}\exp(S(\mathbf{m}_{j},\mathbf{c}_{i})/\tau)}\end{split}$

where $\tau$ is a temperature parameter learned during training.

##  3\. Experimental Evaluation

Table 1. Text-to-motion retrieval results on both the KIT Motion Language Dataset and HumanML3D Dataset. We report the best and the second-best results with bold and underlined font, respectively. |  | KIT Motion Language Dataset | HumanML3D Dataset
---|---|---|---
|  | Recall@k $\uparrow$ | Rank $\downarrow$ | nDCG $\uparrow$ | Recall@k $\uparrow$ | Rank $\downarrow$ | nDCG $\uparrow$
Text Model | Motion Model | r1 | r5 | r10 | mean | med | SPICE | spaCy | r1 | r5 | r10 | mean | med | SPICE | spaCy
BERT+LSTM | BiGRU | 3.7 | 15.2 | 23.8 | 72.3 | 30 | 0.271 | 0.706 | 2.9 | 11.8 | 19.8 | 253.9 | 55 | 0.250 | 0.768
UpperLowerGRU | 3.2 | 15.7 | 25.3 | 90.2 | 34 | 0.263 | 0.697 | 2.4 | 10.5 | 17.7 | 285.7 | 68 | 0.242 | 0.763
DG-STGCN | 6.2 | 24.5 | 38.2 | 40.6 | 17 | 0.339 | 0.740 | 2.0 | 8.4 | 14.4 | 242.0 | 73 | 0.231 | 0.767
MoT | 5.3 | 21.3 | 32.0 | 51.1 | 20 | 0.318 | 0.723 | 2.5 | 11.2 | 19.4 | 234.5 | 51 | 0.247 | 0.768
CLIP | BiGRU | 6.6 | 21.5 | 32.3 | 52.0 | 22 | 0.316 | 0.729 | 3.4 | 14.3 | 23.1 | 201.9 | 43 | 0.272 | 0.780
UpperLowerGRU | 6.4 | 22.0 | 32.2 | 52.3 | 22 | 0.321 | 0.732 | 3.1 | 12.6 | 20.8 | 200.4 | 47 | 0.269 | 0.779
DG-STGCN | 7.2 | 26.1 | 38.2 | 36.9 | 16 | 0.355 | 0.751 | 4.1 | 16.0 | 26.5 | 159.6 | 33 | 0.291 | 0.789
MoT | 6.5 | 26.4 | 42.6 | 35.5 | 14 | 0.352 | 0.748 | 3.5 | 14.8 | 24.5 | 166.2 | 38 | 0.280 | 0.785

###  3.1. Metrics

##### Exact-search

Exact-search metrics leverage the intrinsic ground truth available in the
employed datasets, where motions come with one (or more) textual descriptions.
We can consider motions associated with the given textual query as the exact
solutions, while all the other ones as irrelevant by default. In this context,
the recall@k measures the percentage of queries that find the correct result
within the first k elements in the results list, while the median and mean
ranks represent the median and mean rank of the exact result computed among
all the queries.

##### Relevance-based

There can exist motions relevant to a certain extent to the given textual
query that are not paired in the dataset. In this context, the normalized
Discounted Cumulative Gain (nDCG) metric is widely employed. The DCG takes
into consideration the relevance a specific item has with the query,
discounting it with a logarithmic factor that depends on the rank of that
item:
$\text{DCG}_{p}=\sum_{i=1}^{p}\frac{2^{\text{rel}_{i}}-1}{\log_{2}{(i+1)}}.$
The nDCG normalizes DCG by its maximum theoretical value and thus returns
values in the $[0,1]$ range. We define the relevance similarly to previous
works in image-to-text retrieval (Messina et al., 2021a, c; Carrara et al.,
2018), that use a proxy relevance between textual descriptions, which is much
easier to compute. In this work, we use two textual relevance functions: (i)
the SPICE relevance (Anderson et al., 2016) – a hand-crafted relevance that
exploits graphs associated with the syntactic parse trees of the sentences and
has a certain degree of robustness against synonyms; and (ii) the spaCy
relevance obtained from the spaCy Python tool, which implements a deep
learning-powered similarity score for pairs of texts.

###  3.2. Datasets and Evaluation Protocol

We employ two recently introduced datasets, HumanML3D (Guo et al., 2022a) and
KIT Motion Language (Plappert et al., 2016). Both datasets carry one or more
human-written descriptions for each motion. We employ the same pre-processing
pipeline for both datasets – the one developed in the codebase of the
HumanML3D dataset (Guo et al., 2022a). We employ $D=9$ features to represent
each joint: six features encoding continuous rotation representation plus
three features encoding rotation-invariant forward kinematics joint positions.

KIT Motion-Language Dataset contains 3,911 recordings of full-body motion in
the Master Motor Map form (Terlemez et al., 2014), along with textual
descriptions for each motion. It has a total of 6,278 annotations in English,
where each motion recording has one or more annotations that explain the
action, like ”A human walks two steps forwards, pivots 180 degrees, and walks
two steps back”.

HumanML3D is, in its essence, very similar to KIT Motion Language Dataset.
However, it is a more recent dataset developed by adding textual annotations
to already-existing and widely-used motion-capture datasets – AMASS (Mahmood
et al., 2019) and HumanAct12 (Guo et al., 2020). It contains 14,616 motions
annotated by 44,970 textual descriptions.

The results are reported on the test set of the respective datasets after
removing possibly redundant queries. In particular, we use 938 and 8,401
textual queries to search among 734 and 4,198 motions for the KIT and
HumanML3D datasets, respectively. For HumanML3D, these motions are obtained by
splitting the originally provided ones using the available segment annotations
associating a motion subsequence with the text that describes it. In this
sense, HumanML3D enables a finer retrieval, as texts are more likely to
describe the correct subsequence instead of the whole motion.

###  3.3. Results

We report text-to-motion retrieval results in Table 1, obtained with the
InfoNCE loss (see Section 3.3.1 for a comparison of loss functions). The best
results are competitively achieved by both DG-STGCN and our transformer-based
MoT. The first remarkable insight is the superiority of CLIP over the
BERT+LSTM on all the metrics in both datasets. With CLIP, the effectiveness of
DG-STGCN and MoT over GRU-based methods is evident, especially on the KIT
dataset, where the mean rank is almost 30 % lower. The nDCG metric, through
the highly-semantic text-based relevance scores, confirms the trend of the
recall@k values, suggesting that the CLIP model paired with GCNs and
Transformers can both retrieve exact and relevant results in earlier positions
in the results list. Notably, from an absolute perspective, all the methods
reach overall low performance on exact search, confirming the difficulty of
the introduced text-to-motion retrieval task. This may be due to (i) some
intrinsic limitations that are hard to eliminate – e.g., textual descriptions
are written by annotators by possibly looking at the original video, which the
network has no access to – or (ii) difficulties in capturing high-level
semantics in motion or text data.

(a) Recall@10

(b) nDCG (SPICE)

Figure 3. Performance varying space dimensionality.

(a) Text models dependence

(b) Motion models dependence

Figure 4. Improvement of InfoNCE loss over Triplet loss.

In Figure 1, we report two qualitative examples of text-to-motion retrieval
using CLIP + MoT, on HumanML3D. We can notice the potential of such natural-
language-based approach to motion retrieval. Specifically, note how the
approach is sensible to asymmetries – in the first case, where the
counterclockwise adjective is specified in the query, only the correctly-
oriented motions are returned in the first positions; in the second case,
where no right or left is specified, both the original and mirrored motions
are returned (e.g., the 1st and 2nd results).

####  3.3.1. Ablation Study on Loss Function and Space Dimensionality

In Figure 3, we report performance when varying the dimensionality of the
common space, for the two motion models DG-STGCN and MoT employing the CLIP
text model. We can notice how, on both metrics in Figure 3(a)/3(b), the
effectiveness remains quite high even for very small dimensions of the common
space, with a negligible improvement after 256 dimensions. Specifically, with
only 16 dimensions instead of 256, the performance drops by only about 6 % on
nDCG with SPICE relevance and on average 15 % on Recall@10, considering both
motion encoders. This suggests that the intrinsic dimensionality of the
learned space is quite small, opening the way for further studies and feature
visualization in future works.

In Figure 4, we also report the remarkable performance gain achieved by
InfoNCE loss over the standard symmetric triplet loss. We can see how the
InfoNCE loss induces the best results basically in all the configurations,
confirming its power even in the under-explored text-motion joint domain.
Breaking down the contributions of this variation on the text and motion
models in Figures 4(a) and 4(b) respectively, we notice how the best gains are
achieved by using the CLIP textual model and the MoT motion model.

##  4\. Conclusions

In this paper, we introduced the task of text-to-motion retrieval as an
alternative to the query-by-example search, and inherently different from the
searching using a query label from a fixed pool of labels. We employed two
state-of-the-art text-encoder networks, as well as widely adopted motion-
encoder networks, for learning a common space and producing the first
baselines for this novel task. We demonstrated that the CLIP text encoder
works best also for encoding domain-specific natural sentences inherently
different from image-descriptive ones, and that Transformers and GCNs obtain
better motion representation than GRU-based encoders. In future works, we plan
to train the models jointly on the two datasets and perform some cross-dataset
evaluation to measure their generalization abilities and robustness. Other
improvements include the use of video modality other than the motion and some
unsupervised pre-training methods for boosting performance.

###### Acknowledgements.

This research was supported by ERDF “CyberSecurity, CyberCrime and Critical
Information Infrastructures Center of Excellence” (No.
CZ.02.1.01/0.0/0.0/16_019/0000822), by AI4Media – A European Excellence Centre
for Media, Society, and Democracy (EC, H2020 No. 951911), and by SUN – Social
and hUman ceNtered XR (EC, Horizon Europe No. 101092612).

## References

  * (1)
  * Aksan et al. (2020) Emre Aksan, Manuel Kaufmann, Peng Cao, and Otmar Hilliges. 2020.  A Spatio-temporal Transformer for 3D Human Motion Prediction.  _arXiv_ (2020).  https://doi.org/10.48550/ARXIV.2004.08692
  * Anderson et al. (2016) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016.  Spice: Semantic propositional image caption evaluation. In _European Conference on Computer Vision_. Springer, 382–398.
  * Arnab et al. (2021) Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. 2021.  ViViT: A Video Vision Transformer. In _IEEE/CVF International Conference on Computer Vision (ICCV)_. 6836–6846.
  * Bernard et al. (2013) J. Bernard, N. Wilhelm, B. Krüger, T. May, T. Schreck, and J. Kohlhammer. 2013\.  MotionExplorer: Exploratory Search in Human Motion Capture Data Based on Hierarchical Aggregation.  _IEEE Transactions on Visualization and Computer Graphics_ 19, 12 (2013), 2257–2266.
  * Budikova et al. (2021) Petra Budikova, Jan Sedmidubsky, and Pavel Zezula. 2021\.  Efficient Indexing of 3D Human Motions. In _International Conference on Multimedia Retrieval (ICMR)_. ACM, 10–18.  https://dl.acm.org/doi/10.1145/3460426.3463646
  * Carrara et al. (2019) Fabio Carrara, Petr Elias, Jan Sedmidubsky, and Pavel Zezula. 2019.  LSTM-based real-time action detection and prediction in human motion streams.  _Multimedia Tools and Applications_ 78, 19 (2019), 27309–27331.  https://doi.org/10.1007/s11042-019-07827-3
  * Carrara et al. (2018) Fabio Carrara, Andrea Esuli, Tiziano Fagni, Fabrizio Falchi, and Alejandro Moreo Fernández. 2018\.  Picture it in your mind: Generating high level visual representations from textual descriptions.  _Information Retrieval Journal_ 21, 2 (2018), 208–229.
  * Cheng et al. (2021a) Yi-Bin Cheng, Xipeng Chen, Junhong Chen, Pengxu Wei, Dongyu Zhang, and Liang Lin. 2021a.  Hierarchical Transformer: Unsupervised Representation Learning for Skeleton-Based Human Action Recognition. In _IEEE International Conference on Multimedia and Expo (ICME)_. 1–6.  https://doi.org/10.1109/ICME51207.2021.9428459
  * Cheng et al. (2021b) Yi-Bin Cheng, Xipeng Chen, Dongyu Zhang, and Liang Lin. 2021b.  Motion-Transformer: Self-Supervised Pre-Training for Skeleton-Based Action Recognition. In _2nd ACM International Conference on Multimedia in Asia (MMAsia)_. ACM, New York, NY, USA.  https://doi.org/10.1145/3444685.3446289
  * Deng et al. (2009) Z. Deng, Q. Gu, and Q. Li. 2009.  Perceptually consistent example-based human motion retrieval. In _Symposium on Interactive 3D Graphics (SI3D)_. ACM, 191–198.
  * Duan et al. (2022) Haodong Duan, Jiaqi Wang, Kai Chen, and Dahua Lin. 2022\.  DG-STGCN: Dynamic Spatial-Temporal Modeling for Skeleton-based Action Recognition.  _arXiv_ (2022).  https://doi.org/10.48550/ARXIV.2210.05895
  * Dubey and Dixit (2022) Shradha Dubey and Manish Dixit. 2022.  A comprehensive survey on human pose estimation approaches.  _Multimedia Systems_ (2022), 1–29.  https://doi.org/10.1007/s00530-022-00980-0
  * Fang et al. (2021) Han Fang, Pengfei Xiong, Luhui Xu, and Yu Chen. 2021\.  Clip2video: Mastering video-text retrieval via image clip.  _arXiv preprint arXiv:2106.11097_ (2021).
  * Ghosh et al. (2021) Anindita Ghosh, Noshaba Cheema, Cennet Oguz, Christian Theobalt, and Philipp Slusallek. 2021.  Synthesis of compositional animations from textual descriptions. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 1396–1406.
  * Guo et al. (2022a) Chuan Guo, Shihao Zou, Xinxin Zuo, Sen Wang, Wei Ji, Xingyu Li, and Li Cheng. 2022a.  Generating Diverse and Natural 3D Human Motions From Text. In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. 5152–5161.
  * Guo et al. (2022b) Chuan Guo, Xinxin Zuo, Sen Wang, and Li Cheng. 2022b.  TM2T: Stochastic and Tokenized Modeling for the Reciprocal Generation of 3D Human Motions and Texts. In _European Conference on Computer Vision (ECCV)_. Springer Nature Switzerland, Cham, 580–597.
  * Guo et al. (2020) Chuan Guo, Xinxin Zuo, Sen Wang, Shihao Zou, Qingyao Sun, Annan Deng, Minglun Gong, and Li Cheng. 2020\.  Action2motion: Conditioned generation of 3d human motions. In _Proceedings of the 28th ACM International Conference on Multimedia_. 2021–2029.
  * Kapadia et al. (2013) M. Kapadia, I-K. Chiang, T. Thomas, N.I. Badler, and J. T. Kider Jr. 2013.  Efficient motion retrieval in large motion databases. In _Symposium on Interactive 3D Graphics and Games (I3D)_. ACM, 19–28.
  * Kenton and Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of NAACL-HLT_. 4171–4186.
  * Kim et al. (2022) Jihoon Kim, Youngjae Yu, Seungyoun Shin, Taehyun Byun, and Sungjoon Choi. 2022.  Learning Joint Representation of Human Motion and Language.  _arXiv preprint arXiv:2210.15187_ (2022).
  * Lin et al. (2020) Lilang Lin, Sijie Song, Wenhan Yang, and Jiaying Liu. 2020\.  MS2L: Multi-Task Self-Supervised Learning for Skeleton Based Action Recognition. In _28th ACM International Conference on Multimedia (MM)_. ACM, New York, NY, USA, 2490–2498.  https://doi.org/10.1145/3394171.3413548
  * Liu et al. (2022) Yu Liu, Huai Chen, Lianghua Huang, Di Chen, Bin Wang, Pan Pan, and Lisheng Wang. 2022.  Animating Images to Transfer CLIP for Video-Text Retrieval. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1906–1911.
  * Luo et al. (2022) Huaishao Luo, Lei Ji, Ming Zhong, Yang Chen, Wen Lei, Nan Duan, and Tianrui Li. 2022.  CLIP4Clip: An empirical study of CLIP for end to end video clip retrieval and captioning.  _Neurocomputing_ 508 (2022), 293–304.
  * Lv et al. (2021) Na Lv, Ying Wang, Zhiquan Feng, and Jingliang Peng. 2021\.  Deep Hashing for Motion Capture Data Retrieval. In _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2215–2219.  https://doi.org/10.1109/ICASSP39728.2021.9413505
  * Mahmood et al. (2019) Naureen Mahmood, Nima Ghorbani, Nikolaus F Troje, Gerard Pons-Moll, and Michael J Black. 2019\.  AMASS: Archive of motion capture as surface shapes. In _Proceedings of the IEEE/CVF international conference on computer vision_. 5442–5451.
  * Messina et al. (2021a) Nicola Messina, Giuseppe Amato, Andrea Esuli, Fabrizio Falchi, Claudio Gennaro, and Stéphane Marchand-Maillet. 2021a.  Fine-grained visual textual alignment for cross-modal retrieval using transformer encoders.  _ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM)_ 17, 4 (2021), 1–23.
  * Messina et al. (2021b) Nicola Messina, Giuseppe Amato, Fabrizio Falchi, Claudio Gennaro, and Stéphane Marchand-Maillet. 2021b.  Towards efficient cross-modal visual textual retrieval using transformer-encoder deep features. In _2021 International Conference on Content-Based Multimedia Indexing (CBMI)_. IEEE, 1–6.
  * Messina et al. (2022a) Nicola Messina, Davide Alessandro Coccomini, Andrea Esuli, and Fabrizio Falchi. 2022a.  Transformer-Based Multi-modal Proposal and Re-Rank for Wikipedia Image-Caption Matching.  _arXiv preprint arXiv:2206.10436_ (2022).
  * Messina et al. (2021c) Nicola Messina, Fabrizio Falchi, Andrea Esuli, and Giuseppe Amato. 2021c.  Transformer reasoning network for image-text matching and retrieval. In _2020 25th International Conference on Pattern Recognition (ICPR)_. IEEE, 5222–5229.
  * Messina et al. (2022b) Nicola Messina, Matteo Stefanini, Marcella Cornia, Lorenzo Baraldi, Fabrizio Falchi, Giuseppe Amato, and Rita Cucchiara. 2022b.  ALADIN: Distilling Fine-grained Alignment Scores for Efficient Image-Text Matching and Retrieval. In _Proceedings of the 19th International Conference on Content-based Multimedia Indexing_. 64–70.
  * Numaguchi et al. (2011) N. Numaguchi, A. Nakazawa, T. Shiratori, and J. K. Hodgins. 2011.  A Puppet Interface for Retrieval of Motion Capture Data. In _Eurographics/ACM SIGGRAPH Symposium on Computer Animation (SCA)_. Eurographics Assoc., 157–166.
  * Papadopoulos et al. (2019) Konstantinos Papadopoulos, Enjie Ghorbel, Renato Baptista, Djamila Aouada, and Björn E. Ottersten. 2019.  Two-Stage RGB-Based Action Detection Using Augmented 3D Poses. In _18th International Conference on Computer Analysis of Images and Patterns (CAIP)_ , Vol. 11678. Springer, 26–35.  https://doi.org/10.1007/978-3-030-29888-3_3
  * Peng et al. (2021) Wei Peng, Xiaopeng Hong, and Guoying Zhao. 2021.  Tripool: Graph Triplet Pooling for 3D Skeleton-Based Action Recognition.  _Pattern Recognition_ 115 (2021), 107921.  https://doi.org/10.1016/j.patcog.2021.107921
  * Petrovich et al. (2021) Mathis Petrovich, Michael J. Black, and Gül Varol. 2021\.  Action-Conditioned 3D Human Motion Synthesis With Transformer VAE. In _IEEE/CVF International Conference on Computer Vision (ICCV)_. 10985–10995.
  * Plappert et al. (2016) Matthias Plappert, Christian Mandery, and Tamim Asfour. 2016\.  The KIT Motion-Language Dataset.  _Big Data_ 4, 4 (2016), 236–252.  https://doi.org/10.1089/big.2016.0028
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021\.  Learning Transferable Visual Models From Natural Language Supervision.  _arXiv_ (2021).  https://doi.org/10.48550/ARXIV.2103.00020
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Sedmidubsky et al. (2020) Jan Sedmidubsky, Petra Budikova, Vlastislav Dohnal, and Pavel Zezula. 2020.  Motion Words: A Text-like Representation of 3D Skeleton Sequences. In _42nd European Conference on Information Retrieval (ECIR)_. Springer, 527–541.
  * Sedmidubsky et al. (2023) Jan Sedmidubsky, Fabio Carrara, and Giuseppe Amato. 2023\.  SegmentCodeList: Unsupervised Representation Learning for Human Skeleton Data Retrieval. In _45th European Conference on Information Retrieval (ECIR)_. Springer, Cham, 110–124.  https://doi.org/10.1007/978-3-031-28238-6_8
  * Sedmidubsky et al. (2021) Jan Sedmidubsky, Petr Elias, Petra Budikova, and Pavel Zezula. 2021.  Content-based Management of Human Motion Data: Survey and Challenges.  _IEEE Access_ 9 (2021), 64241–64255.  https://doi.org/10.1109/ACCESS.2021.3075766
  * Shvetsova et al. (2022) Nina Shvetsova, Brian Chen, Andrew Rouditchenko, Samuel Thomas, Brian Kingsbury, Rogerio S Feris, David Harwath, James Glass, and Hilde Kuehne. 2022.  Everything at once-multi-modal fusion transformer for video retrieval. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 20020–20029.
  * Song et al. (2018) Sijie Song, Cuiling Lan, Junliang Xing, Wenjun Zeng, and Jiaying Liu. 2018.  Spatio-Temporal Attention-Based LSTM Networks for 3D Action Recognition and Detection.  _IEEE Transactions on Image Processing_ 27, 7 (2018), 3459–3471.  https://doi.org/10.1109/TIP.2018.2818328
  * Terlemez et al. (2014) Ömer Terlemez, Stefan Ulbrich, Christian Mandery, Martin Do, Nikolaus Vahrenkamp, and Tamim Asfour. 2014\.  Master Motor Map (MMM)—Framework and toolkit for capturing, representing, and reproducing human motion on humanoid robots. In _2014 IEEE-RAS International Conference on Humanoid Robots_. IEEE, 894–901.
  * Tevet et al. (2022) Guy Tevet, Sigal Raab, Brian Gordon, Yonatan Shafir, Daniel Cohen-Or, and Amit H. Bermano. 2022\.  Human Motion Diffusion Model.  _arXiv_ (2022), 1–12.  https://doi.org/10.48550/ARXIV.2209.14916
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Yang et al. (2022) Yang Yang, Guangjun Liu, and Xuehao Gao. 2022.  Motion Guided Attention Learning for Self-Supervised 3D Human Action Recognition.  _IEEE Transactions on Circuits and Systems for Video Technology_ (2022), 1–13.  https://doi.org/10.1109/TCSVT.2022.3194350
  * Zhang et al. (2023) Jianrong Zhang, Yangsong Zhang, Xiaodong Cun, Shaoli Huang, Yong Zhang, Hongwei Zhao, Hongtao Lu, and Xi Shen. 2023\.  T2M-GPT: Generating Human Motion from Textual Descriptions with Discrete Representations.  _arXiv_ (2023), 1–14.  https://doi.org/10.48550/ARXIV.2301.06052
  * Zhang et al. (2022) Mingyuan Zhang, Zhongang Cai, Liang Pan, Fangzhou Hong, Xinying Guo, Lei Yang, and Ziwei Liu. 2022.  MotionDiffuse: Text-Driven Human Motion Generation with Diffusion Model.  _arXiv_ (2022), 1–16.  https://doi.org/10.48550/ARXIV.2208.15001
  * Zhang et al. (2020) Yuhao Zhang, Hang Jiang, Yasuhide Miura, Christopher D Manning, and Curtis P Langlotz. 2020.  Contrastive learning of medical visual representations from paired images and text.  _arXiv preprint arXiv:2010.00747_ (2020).
  * Zhao et al. (2022) Shuai Zhao, Linchao Zhu, Xiaohan Wang, and Yi Yang. 2022\.  Centerclip: Token clustering for efficient text-video retrieval. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 970–981.


# Verifying MILP Certificates with SMT Solvers

Runtian Zhou
Davidson College,
Davidson, NC 28035
<EMAIL_ADDRESS>&Haoze Wu
Stanford University,
Stanford, CA 94305
<EMAIL_ADDRESS>&Hammurabi Mendes
Davidson College,
Davidson, NC 28035
<EMAIL_ADDRESS>&Jonad Pulaj
Davidson College,
Davidson, NC 28035
<EMAIL_ADDRESS>
###### Abstract

We present a SMT-based checker for the recently proposed VIPR certificate, the
first proof format for the correctness of answers produced by mixed-integer
linear programming (MILP) solvers. The checker is based on the equivalence
between the correctness of a VIPR certificate and the satisfiability of a
formula in the theory of linear/integer real arithmetic. Evaluation on
existing benchmark instances demonstrates the effectiveness of this approach.

##  1 Introduction

Computational mixed-integer linear programing (MILP) is widely considered a
successful blend of algorithmic improvement with advancements in hardware and
compilers (?), where current state-of-the-art MILP solvers can solve problems
with millions of variables and constraints (?).

Demand for MILP solvers is largely driven by applications in industry, hence
underlying numerical computations typically rely on floating-point arithmetic
for efficiency. For most such applications, in order to achieve a high degree
of numerical stability, floating point computations are combined with
numerical error tolerances. However, MILP solvers are also used in
experimental mathematics to find counterexamples (?; ?) or provide numerical
evidence (?; ?). For theorem proving correctness is tantamount and additional
safeguards are needed to counter the use of inexact floating-point arithmetic
and/or programming or algorithmic errors. The best known example in this case
is the verification in Isabelle/HOL of the infeasibility of thousands of
linear programs involved in the proof of Kepler’s conjecture (?).

Another set of tools that have been successfully deployed in automated theorem
proving tasks are Boolean satisfiability (SAT) solvers and Satisfiability
modulo theories (SMT) solvers (?). For example, SAT solvers have had
spectacular success in settling a number of long-standing mathematical
problems including the Erdos discrepancy conjecture (?), the Boolean
Pythagorean triples conjecture (?), and the determination of the fifth Schur
number (?). On the other hand, SMT solvers are increasingly used as
subroutines for proof assistants (?; ?) to automatically resolve proof goals.
In those applications, SAT/SMT solvers are often required to produce proofs,
which can be independently checked by proof checkers to guarantee the
correctness of the solver outputs. One theory particularly relevant to MILP is
the theory of Linear Real Arithmetic, for which proof production is supported
in state-of-the-art SMT solvers such as Z3 (?), cvc5 (?), and MathSAT5 (?).

Although verification of answers returned by MILP solvers is not as well-
established as in analogous solvers in the SAT/SMT community, significant
steps forward have been made. VIPR is the first, recently proposed branch-and-
cut certificate format for MILP instances, designed with simplicity in mind,
which is composed of a list of statements that can be sequentially verified
using a limited number of inference rules (?). This certificate format was
used in the proof of special cases of Chvátal’s conjecture (?), and in the
proof of the 3-sets conjecture (?). The VIPR certificate format is currently
implemented in the latest versions of exact SCIP (?), together with a C++
checker for the corresponding certificates.

Our motivation for this work is to leverage advances in SMT solvers for
verifying the certificates of MILP instances. Towards this end, we design a
checker for VIPR certificates by encoding the format’s inference rules as SMT
instances. As a straightforward baseline, we also implement a translation tool
from MILP feasibility problems to SMT instances. All associated code with this
project is publicly available111https://github.com/zhoum929/Satisfiability-
modulo-theories-for-verifying-MILP-certificates/tree/main. We summarize our
main contributions as follows:

  * •

We present a translator that encodes the feasibility of an MILP as an SMT
problem in the theory of quantifier-free linear real/integer arithmetic
(QF_LIRA);

  * •

We present a VIPR proof checker that encodes the correctness of a VIPR
certificate as a QF_LIRA problem and show the correctness of the encoding;

  * •

We perform an evaluation of our certificate checker on existing benchmarks
(?).

MPSROWSRHSCOLUMNSBOUNDSassert: constraintdeclare-fun: variable typeassert:
variable boundSMT-LIB Figure 1: Transformation from MILP instance (MPS format)
to SMT instance (SMT-LIB format)

The rest of this paper is organized as follows. Section II presents the logic
of transformation from MILP instances and VIPR certificates to SMT instances.
Section III outlines the equivalence of VIPR certificates and the transformed
SMT instances. Section IV presents an evaluation of our design tested on known
benchmarks. Section V concludes the paper, and the appendix contains more
proof details of the claims in Section III.

##  2 Methodology

### Transforming MILP instances to SMT instances

As already mentioned in the Introduction, for suitable applications in the
MILP domain where additional safeguards are warranted, translating from MILP
instances to SMT instances may be advantageous. Towards that end, we outline
such a translation tool.

Two common file formats for MILP problems are the LP file format, which is
human-readable and analogous to the algebraic form of linear constraints, and
the MPS file format, which is more machine-friendly with higher precision for
constraint coefficients. In MPS format, constraints are specified in a matrix,
where each column corresponds to a variable and each row corresponds to a
constraint. For each variable, its coefficient at each row is specified,
otherwise the coefficient is assumed to be zero. In our implementation of the
the transformation, we input MILP instances in MPS format and output
equivalent SMT instances in SMT-LIB format.

At a high level, our transformation from MPS to SMT-LIB is straightforward: we
use declare-fun statements to declare variables and assert statements to
capture constraints or bounds specified in the original MPS file. Although it
is likely that further optimizations could improve the performance of
transformed instances in SMT solvers, our simple translation provides a useful
baseline for comparison. It enables us to experimentally examine the
advantages of checking the correctness of a VIPR certificate for a MILP
instance via an SMT solver versus directly solving the translated MILP
instances in an SMT solver.

MPS files encode most instance information in four sections: ROWS, RHS,
COLUMNS, and BOUNDS. The ROWS section specifies the type of each constraint
($>=$, $<=$, or $=$). The RHS section specifies the right hand side value of
each constraint, which is assumed to be a constant. The COLUMNS section
specifies for each variable its corresponding coefficient in each constraint.
The BOUNDS section specifies the upper and lower bounds of each variables.

Figure 1 presents the logic of transformation from these four general
sections. First, each variable specified in the COLUMNS section will be
encoded as a declare-fun statement. Furthermore, sections ROWS, RHS and
COLUMNS encode information on each constraint in the corresponding MILP
problem, and each such constraint is transformed into an assert statement.
Finally, sections COLUMNS and BOUNDS encode lower and upper bounds for each
variable, and each such bound is transformed into an assert statement.222Our
implementation can also handle non-standard statements in MPS format, such as
the RANGE section and the INDICATOR section.

### Transforming VIPR certificates to SMT instances

Next we describe the design of the checker for VIPR certificates. At a high
level, a VIPR certificate contains two main parts: one that describes the
original MILP problem (constraints, variable types, etc.) and an inference
part that describes the reasoning of the certificate (assumptions and
inferenced constraints). As part of our checker design we declare a fixed
variable in SMT-LIB format for each constant (coefficient) specified in the
corresponding VIPR certificate, so that the symbolic computation of the
inferenced reasoning can be wholly captured in an SMT solver.

When transforming the system part into an SMT instance, unlike the
transformation from MPS format, we don’t use assert statements to determine
whether each constraint of the original MILP instance holds. Instead we encode
each coefficient in a given constraint as a fixed variable. Furthermore when
transforming the inference part, we also encode every coefficient in each
inferenced constraint. Finally, the reasoning part of each inferenced
constraint is transformed into several assert statements which check
inequalities between constants.

In short, our transformation ensures that SMT solvers are only burdened with
the work involved in the symbolic computation of the reasoning of the
certificate. Thus we seek to reduce the computational burden to SMT solvers by
mainly checking formulas with fixed variables. 333A relatively expensive
operation we encode in our checker is Chvátal-Gomory rounding. Since the SMT-
LIB format doesn’t natively provide a rounding operation, we enforce it by
encoding several assert statements.

A standard VIPR certificate file contains $7$ sections: VAR, INT, CON, RTP,
SOL, OBJ, and DER. Figure 2 provides an overview of the logic of
transformation from these sections to SMT-LIB statements. The VAR and INT
sections are transformed into assert and declare-fun statements specifying
types of variables in the original MILP problem. The CON section is
transformed into assert and declare-fun statements specifying type, rhs (right
hand side value), and coefficients of each constraint in the original MILP
problem. The SOL section is transformed into assert and declare-fun statements
specifying variable assignment in each solution given by the MILP solver, and
assert statements verifying that these variable assignments do satisfy the
constraints specified in the CON section. The OBJ section is transformed into
assert and declare-fun statements specifying the coefficients of each variable
in the objection function. The DER section is transformed into assert and
declare-fun statements specifying the type, rhs, and coefficients used in each
inferenced (derived) constraint and the reasoning of that constraint. In
addition, RTP, SOL, OBJ, and DER sections together contribute to the assert
statement specifying the lower and upper bounds of the optimum value of the
objective function, when one exists.444For further details on the VIPR format,
please refer to (?).

Next we provide more details with respect to the tranformations of each
sections of the VIPR certificates. The VAR and INT sections specify the type
(real or integer) of variables in the original MILP problem. The type of each
integer is encoded as a boolean variable with fixed value, using a declare-fun
statement and an assert statement. Let’s take a look at an example of the VAR
and INT sections in a VIPR certificate.

VAR 2 x y INT 1 1

The VAR section shows that the original MILP problem has two variables, $x$
and $y$, and our checker will index starting from $0$. Thus $x$ will be
interpreted as $x_{0}$ and $y$ as $x_{1}$. The INT section shows that only the
variable with index $1$ is an integer variable. Thus $x_{1}$ is an integer
variable and $x_{0}$ is a real variable. This information is encoded as:

(declare-fun is$\\_$intx0 () Bool) (assert (not is$\\_$intx0)) (declare-fun
is$\\_$intx1 () Bool) $\displaystyle\texttt{(assert is$\\_$intx1)}.$

where is$\\_$intx0 is a boolean variable representing whether $x_{0}$ is an
integer variable or not. Notice that VIPR does not distinguish boolean
variables from integer variables or bound constraints from general
constraints.

VIPRVARINTCONRTPSOLOBJDERdeclare/assert:variable(type)declare/assert:constraint(type,
rhs,coefficients)assert:objective(boundverification)declare/assert:variable(valueassignment)declare/assert:objective(coefficients)assert:constraintsdeclare/assert:constraint(type,
rhs,coefficients,reasoning)SMT-LIB Figure 2: Transformation from VIPR format
to SMT-LIB format

The OBJ section specifies the coefficients of variables in the objective
function. Each coefficient is encoded as a real variable in SMT-LIB format
using a declare-fun statement and an assert statement. Let’s take a look at an
example of the OBJ section in a VIPR certificate:

OBJ min $\displaystyle\texttt{1 0 2}.$

The first number of the second line, $1$, means there is only one variable in
the objective function with a non-zero coefficient. The next number, $0$, is
the index of this variable. The next number, $2$, is the coefficient of this
variable. Thus the original MILP problem is a minimization problem and its
objective function is $2x_{0}$. In SMT-LIB format, this information is encoded
as:

(declare-fun obj0 () Real) $\displaystyle\texttt{(assert (= obj0 2.0))}.$

We use set structures in C++ to store the indexes of variables with non-zero
coefficients in the objective function.

The RTP section specifies the result the result of the MILP solver. It either
states the system is infeasible, or it gives the upper and lower bounds of the
objective function. These information will be stored during the transformation
for later use and will not be encoded into SMT-LIB format directly.

The CON section specifies the constraints in the original MILP problem
(including bounds of variables). Here is an example line in the CON
constraint:

$\texttt{CX G 1 2 0 2 1 3}.$

The first term, CX, is the name of the constraint. Constraints (including
original constraints and inferenced constraints) in a VIPR certificate will be
given index starting from $0$ in the transformation. If this CX is the first
line of CON section, then it will be referred to as $c_{0}$, meaning the first
constraint, and the name CX will be disregarded. The next term, $G$, means
$c_{0}$ is a $>=$ constraint. In SMT-LIB format this is encoded as:

(declare-fun cs0 () Real) (assert (= cs0 1.0))

where $cs0$ specifies the type of the constraint with index $0$. If it is a
$>=$ constraint, $cs0$ is assigned value $1.0$. If it is a $<=$ constraint,
$cs0$ is assigned value $-1.0$. If it is an $=$ constraint, $cs0$ is assigned
value $0.0$. This information will be used later to check the validity of
inferenced constraints as linear combinations of other valid constraints.

The next term, $1$, is the right hand side value of this constraint. In SMT-
LIB format, this is encoded as:

(declare-fun crhs0 () Real) $\displaystyle\texttt{(assert (= crhs0 1.0))}.$

The next term, $2$, means that there are two variables in this constraint with
non-zero coefficients. The last four terms mean that $x_{0}$ has coefficient
$2$ and $x_{1}$ has coefficient $3$. In SMT-LIB format, this is encoded as

(declare-fun c0x0 () Real) (assert (= c0x0 2.0)) (declare-fun c0x1 () Real)
$\displaystyle\texttt{(assert (= c0x1 3.0))}.$

Thus constraint $c1$ corresponds to inequality $2x_{0}+3x_{1}\geq 1$.

So far, we have outlined how the information of the original MILP problem is
encoded into SMT-LIB format in our checker. The last two sections, SOL and
DER, contain crucial information for the validity of a VIPR certificate.
Together they ensure the verification of the MILP solver reported results in
the RTP section. We’ll discuss more detailed mechanics of this transformation
in the next section and the Appendix.

##  3 Validity of VIPR transformation

The design of the derivations in the VIPR certificates, which in turn aim to
verify the result returned by a MILP solver, is based on well-understood
principles in the MILP domain such as the branch-and-cut method with Chvátal-
Gomory and split cuts (?). The VIPR certificate format “flattens” the
associated branch-and-bound tree explored by MILP solvers and renders it into
a series of statements (corresponding to lines) that can be verified
sequentially. We say that the SOL section of the VIPR certificate format is
_valid_ if it contains at least one solution that satisfies all constraints in
the CON section and satisfies the bound in the RTP section, or it contains no
solutions and the RTP section reports infeasibility. Furthermore we say that
the DER section of the VIPR certificate format is _valid_ if every listed
constraint in the section is derived555We discuss the details of such
derivations on the basis of Chvátal-Gomory and split cuts in the Appendix when
examining the transformation that corresponds to Lemma 2. from previously
listed constraints in the section and the last constraint either implies the
bound in the RTP section or implies that the RTP section reports
infeasibility.

| Base | VIPR2SMT-cvc5 | VIPR2SMT-Z3 | MPS2SMT-cvc5 | MPS2SMT-Z3
---|---|---|---|---|---
| Ver. | Time | Ver. | Trans. | Time | Ver. | Trans. | Time | Ver. | Time | Ver. | Time
Easy | $46$ | $155.6$ | $31$ | $30.8$ | $890.2$ | $26$ | $45.9$ | $1886.9$ | $14$ | $2002.5$ | $6$ | $2243.9$
Hard | $9$ | $34.6$ | $7$ | $59.1$ | $1235.1$ | $5$ | $12.1$ | $47.0$ | $4$ | $65.5$ | $3$ | $62.9$
Table 1: Aggregated computational results for three ways to verify MILP
results: check VIPR by original C++ checker (Base), transform VIPR to SMT and
solve with cvc5/Z3 (VIPR2SMT), and transform MPS file to SMT and solve with
cvc5/Z3 (MPS2SMT). Ver. column represents the number of instances solved
within time and memory limit ($4$ hours and $256$G RAM). Trans. column
represents the average time on VIPR2SMT transformation for the solved
instances. Time column represents the average time (transformation time plus
solver time) for the solved instances.

######  Proposition 1.

The result specified in the RTP section of a VIPR certificate is valid, if and
only if both the SOL and DER sections are valid.

Therefore, in order to show an equivalency (in terms of correctness) between a
VIPR certificate and the analogous transformation into an SMT instance, it
suffices to show the equivalency of the transformation of the SOL and DER
sections. More specifically, given the SOL and DER sections of a given
instance, we can transform then into a series of statements in the SMT-LIB
format, and we claim that these statements will not generate a contradiction
if and only if both the SOL and DER sections are valid.

To this end, we will treat the validity of each section separately in the
following two lemmas.

######  Lemma 1.

The SOL section is valid, if and only if the transformed statements in the
SMT-LIB format do not yield a contradiction.

For details of this lemma, please refer to the Appendix.

######  Lemma 2.

The DER section is valid, if and only if the transformed statements in the
SMT-LIB format do not yield a contradiction.

For details of this lemma, please refer to the Appendix.

######  Theorem 1.

The result specified in the RTP section of a VIPR certificate is valid, if and
only if the transformed statements in the SMT-LIB format do not yield a
contradiction.

Theorem 1 follows directly from Proposition 1, Lemma 1, and Lemma 2.

##  4 Experiments

In this section, we evaluate the proposed proof-checking workflow on MILP
benchmarks studied by the authors of VIPR (?). We focus on each of the
benchmarks that meets the following criterion: 1) a certificate (of either
infeasibility or both lower and upper bounds) was produced; 2) the
corresponding MPS (i.e., a standard format for MILP problem) file is publicly
available. This amounts to 55 benchmarks in total. Following the strategy in
the original paper, we partition the benchmark set into “easy” and “hard”.

Our implementation includes 1) a MPS2SMT transformer that transforms MPS file
format to the SMT-LIB format; 2) a VIPR2SMT transformer that transforms the
VIPR proof format to the corresponding SMT problem in the SMT-LIB format. Both
transformers were written in C++. The former contains $890$ lines of code
(LOC), and the latter contains $821$ LOC. Our implementation of the VIPR2SMT
transformer is essentially a C++ text parser where in addition we make use of
set data structures of C++ to keep track of non-zero coefficients and label
assumptions of each constraint in the DER section. Thus, nearly all the logic
of the correctness of the derivations, and therefore the results in the RTP
section, are entrusted to the SMT solver. In particular, our C++
implementation does not use arithmetic operations and entrusts this
verification when needed to the SMT solver. In contrast, the existing VIPR
proof checker (?) is written in 1685 lines of C++ code, and uses arithmetic
operations and comparisons that are not verified. This gives us reason to
believe that our implementation is a trustworthy alternative to the existing
proof-checker. Our tool and details about each tested instance are publicly
available666https://github.com/zhoum929/Satisfiability-modulo-theories-for-
verifying-MILP-certificates/tree/main.

We compare the following three strategies:

  1. 1.

Check the VIPR certificate with the original C++ proof checker (?) (Base);

  2. 2.

Translate the VIPR certificate to an SMT query, and solve with an SMT solver
(VIPR2SMT);

  3. 3.

Translate the original MILP problem to an SMT query777If the VIPR certificate
declares the MILP instance infeasible, only the MILP constraints are
translated to SMT. Otherwise, the VIPR certificate provides a lower/upper
bound, and this bound is encoded in addition to the MILP constraints., and
solve with an SMT solver (MPS2SMT).

We consider two SMT solvers, Z3 (?) and cvc5 (?), for solving the SMT queries.
All experiments were conducted on a cluster of Intel(R) Xeon(R) Gold 6226R CPU
(2.9Ghz). Each job was given one processor, 256G of RAM, and a 4-hour time
limit. The results are shown in Table 1.

Among the $55$ SMT-LIB files transformed from the VIPR certificates, all
instances that were not solved by either SMT solver ran out of memory. All
instances solved by either cvc5 and Z3, confirm the results in (?), showing
that all corresponding VIPR certificates are valid.

In the VIPR2SMT direction, $38$ instances can be solved by cvc5 and $31$
instances can be solved by Z3. In comparison, in the MPS2SMT direction, only
$18$ can be solved by cvc5 and $9$ can be solved by Z3. Interestingly, MPS2SMT
is able to solve one instance on which VIPR2SMT runs out of memory, which
suggests a complementarity between the two approaches.

##  5 Conclusion

In this work we seek to leverage advances in SMT solvers to verify
certificates for MILP solvers. Thus we design a VIPR certificate checker that
transforms the logic of the VIPR into an equivalent SMT-LIB format. We test
the viability of our checker on a benchmark instances, and compare it to a
straightforward translation of the MPS format to SMT-LIB format. For future
directions we seek to introduce further optimizations for the MPS2SMT
translation, and possibly leverage SMT solvers’ incremental techniques to
improve the efficiency of the VIPR2SMT direction. Finally we aim to extend our
SMT-based checker to accommodate the next version of VIPR (?) which contains
an additional inference rule based on MIR inequalities.

## References

  * [Barbosa et al. 2022] Barbosa, H.; Barrett, C.; Brain, M.; Kremer, G.; Lachnitt, H.; Mann, M.; Mohamed, A.; Mohamed, M.; Niemetz, A.; Nötzli, A.; et al.  2022\.  cvc5: A versatile and industrial-strength smt solver.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 415–442.  Springer.
  * [Bixby 2012] Bixby, R. E.  2012\.  A brief history of linear and mixed-integer programming computation.  Documenta Mathematica 2012:107–121.
  * [Böhme and Nipkow 2010] Böhme, S., and Nipkow, T.  2010\.  Sledgehammer: judgement day.  In Automated Reasoning: 5th International Joint Conference, IJCAR 2010, Edinburgh, UK, July 16-19, 2010. Proceedings 5, 107–121.  Springer.
  * [Cheung, Gleixner, and Steffy 2017] Cheung, K. K.; Gleixner, A.; and Steffy, D. E.  2017\.  Verifying integer programming results.  In Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings 19, 148–160.  Springer.
  * [Cimatti et al. 2013] Cimatti, A.; Griggio, A.; Schaafsma, B. J.; and Sebastiani, R.  2013\.  The mathsat5 smt solver.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 93–107.  Springer.
  * [Cook et al. 2011] Cook, W.; Koch, T.; Steffy, D. E.; and Wolter, K.  2011\.  An exact rational mixed-integer programming solver.  In Integer Programming and Combinatoral Optimization: 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings 15, 104–116.  Springer.
  * [De Moura and Bjørner 2008] De Moura, L., and Bjørner, N.  2008\.  Z3: An efficient smt solver.  In International conference on Tools and Algorithms for the Construction and Analysis of Systems, 337–340.  Springer.
  * [De Moura and Bjørner 2009] De Moura, L., and Bjørner, N.  2009\.  Satisfiability modulo theories: An appetizer.  In Brazilian Symposium on Formal Methods, 23–36.  Springer.
  * [Eifler and Gleixner 2023] Eifler, L., and Gleixner, A.  2023\.  Safe and verified gomory mixed integer cuts in a rational mip framework.  arXiv preprint arXiv:2303.12365.
  * [Eifler, Gleixner, and Pulaj 2022] Eifler, L.; Gleixner, A.; and Pulaj, J.  2022\.  A safe computational framework for integer programming applied to chvátal’s conjecture.  ACM Transactions on Mathematical Software (TOMS) 48(2):1–12.
  * [Ekici et al. 2017] Ekici, B.; Mebsout, A.; Tinelli, C.; Keller, C.; Katz, G.; Reynolds, A.; and Barrett, C.  2017\.  Smtcoq: A plug-in for integrating smt solvers into coq.  In Computer Aiåded Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part II 30, 126–133.  Springer.
  * [Hales 2005] Hales, T. C.  2005\.  A proof of the kepler conjecture.  Annals of mathematics 1065–1185.
  * [Hartke and Stolee 2014] Hartke, S. G., and Stolee, D.  2014\.  A linear programming approach to the manickam–miklós–singhi conjecture.  European Journal of Combinatorics 36:53–70.
  * [Heule, Kullmann, and Marek 2016] Heule, M. J.; Kullmann, O.; and Marek, V. W.  2016\.  Solving and verifying the boolean pythagorean triples problem via cube-and-conquer.  In International Conference on Theory and Applications of Satisfiability Testing, 228–245.  Springer.
  * [Heule 2018] Heule, M.  2018\.  Schur number five.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
  * [Kenter and Skipper 2018] Kenter, F., and Skipper, D.  2018\.  Integer-programming bounds on pebbling numbers of cartesian-product graphs.  In International Conference on Combinatorial Optimization and Applications, 681–695.  Springer.
  * [Koch et al. 2022] Koch, T.; Berthold, T.; Pedersen, J.; and Vanaret, C.  2022\.  Progress in mathematical programming solvers from 2001 to 2020.  EURO Journal on Computational Optimization 10:100031.
  * [Konev and Lisitsa 2015] Konev, B., and Lisitsa, A.  2015\.  Computer-aided proof of erdős discrepancy properties.  Artificial Intelligence 224:103–118.
  * [Lancia, Pippia, and Rinaldi 2020] Lancia, G.; Pippia, E.; and Rinaldi, F.  2020\.  Using integer programming to search for counterexamples: A case study.  In International Conference on Mathematical Optimization Theory and Operations Research, 69–84.  Springer.
  * [Pulaj 2020] Pulaj, J.  2020\.  Cutting planes for families implying frankl’s conjecture.  Mathematics of Computation 89(322):829–857.
  * [Pulaj 2023] Pulaj, J.  2023\.  Characterizing 3-sets in union-closed families.  Experimental Mathematics 32(2):350–361.

## Appendix

In this section we provide justification for the two lemmas used to claim the
equivalence of the SMT transformation to the VIPR certificate format. We only
argue in one direction (from VIPR to SMT) as the other is straightforward once
the proposed transformation is understood.

Next we examine the transformation corresponding to Lemma 1. Each line of the
SOL section specifies a set of value assignments for variables in the original
MILP instance. It is valid if this value assignments satisfy the constraint
specified in the CON section.

The following is a simple example of CON and SOL transformation. Below we
display the portion of the VIPR certificate we seek to convert to an SMT-LIB
statement.

CON 1 0 CX G 1 2 0 2 1 3 SOL 1 opt 1 1 1

The first number after CON is the number of constraints specified in the CON
seciton. The second number is the number of bound constraints. However, the
VIPR format does not distinguish bound constraints from general constraints,
so we disregard this number. Thus the original MILP problem has only one
constraint. As explained in Section II, this constraint is

$2x_{0}+3x_{1}\geq 1.$

The first number after SOL is the number of solutions provided by the MILP
solver. Notice that if the result of MILP solver presented in the RTP section
is infeasible, then SOL must contain no solution. In our example, there is one
solution to be verified, as specified in the next line. The first term, “opt”,
is the name of this solution. The next number is the number of variables that
are not assigned value $0$ in this solution. The next two number specify the
index of this variable and its value assignment. We use a C++ set structure to
store the indices of variables that are assigned non-zero values. Then, this
information is transformed into SMT-LIB format as

(declare-fun sol0x1 () Real) $\displaystyle\texttt{(assert (= sol0x1 1.0))}.$

Notice that solutions are also given indices start from $0$. Thus these two
statements mean $x_{1}$ is given value $1.0$ in the solution with index $0$.
Next, we need to verify this value assignment satisfies the constraints in the
CON section. in the SMT-LIB format, this is encoded as

(assert ($>$= (* c0x1 sol0x1) crhs0))

. Finally, in a minimization problem, at least one solution needs to verify
the upperbound specified in the corresponding RTP section. Suppose the
corresponding RTP section is

$\texttt{RTP range 0 0}.$

Then, since no variable with non-zero coefficient in the objective function is
assigned non-zero value in this solution, the objective function has value $0$
in this solution. Thus in the SMT-LIB it’s encoded as

$\texttt{(assert ($>$= 0.0 0.0))}.$

If there are several solutions, to check that at least one of them verifies
the upperbound specified in RTP section, we will use the “or” operator in the
SMT-LIB format to encode several inequalities in one assert statement. This
concludes the trasformation associated with Lemma 1.

Next we examine the transformation corresponding to Lemma 2. Each line in the
DER section contains three parts: the first part specifies the constraint in
the same way as in the CON section; the second part is the reasoning of this
constraint, specified within $\\{\\}$; the third part is largest index of
later derived constraints that use the current constraint in its reasoning
part. This index is used only to free up space during the transformation, and
will not be encoded into SMT-LIB format. There are four possible reasoning
formats within $\\{\\}$ and we will explain transformation from each of them.

If the reasoning format is $\\{$ asm $\\}$, then this constraint is an
assumption. On a high level, the current constraint is used to open a branch
for later reasoning and does not rely on any other constraints. The set
structure of C++ is used to store indices of constraints that are assumptions.
Each constraint also has a set storing the indices of assumptions it relies
on. We define the only assumption used by an assumption constraint to be
itself, and each constraint in the CON section uses no assumptions. Since
there is no computation in the reasoning part, such a line will be encoded in
the same way as any line in the CON section. For example,

AX L 0 1 0 1 $\\{$ asm $\\}$ -1

is transformed into

(declare-fun cs3 () Real) (assert (= cs3 -1.0)) (declare-fun crhs3 () Real)
(assert (= crhs3 0.0)) (declare-fun c3x0 () Real)
$\displaystyle\texttt{(assert (= c3x0 1.0))}.$

If the reasoning format is $\\{$ lin $\ldots\\}$, it means that the current
constraint is implied by a linear combination of previous constraints.
Consider the following example:

$\texttt{CQ G 1 0 $\\{$ lin 3 0 1 3 -2 5 -3 $\\}$ 12}.$

Suppose this is the $6$th constraint in the VIPR file. The first number after
“lin” means that there are three constraints used in this linear combination.
The next $3$ pairs of numbers each specifies the index of an used constraint
and the multiplier of it. Thus, the reasoning of $c_{6}$ is the linear
combination $c_{0}-2c_{3}-3c_{5}$. The constraint part is encoded in the same
way as any line in the CON section, but we need to add several other
statements to check the validity of the reasoning part.

First, we need to make sure that the reasoning part only uses constraints
already specified, i.e. the indices of the reasoning part should be less than
current index $6$:

(assert ($<$ 0 6)) (assert ($<$ 3 6)) $\displaystyle\texttt{(assert ($<$ 5
6))}.$

Second, we need to make sure the linear combination indeed ensures an
inequality or equality. There are only three possibilities: the addition of
equalities forces equality; the addition of $>=$ forces $>=$; the addition of
$<=$ forces $<=$. Note that a negative multiplier reverse the direction of an
inequality. Recall we use $0.0,-1.0,1.0$ to represent the sign of a
constraint, i.e. $=,<=,>=$. Therefore, if a multiplier times the value of the
sign gives negative value, then it becomes a $<=$ inequality.

Given this, we can use three boolean variables to represent whether the linear
combination forces an $=,<=,>=$ constraint:

(declare-fun cleq6 () Bool)

(declare-fun cgeq6 () Bool)

(declare-fun ceq6 () Bool)

(assert (= ceq6 (and (= (* 1.0 cs0) 0.0) (= (* -2.0 cs3) 0.0) (= (* -3.0 cs5)
0.0))))

(assert (= cleq6 (and ($<$= (* 1.0 cs0) 0.0) ($<$= (* -2.0 cs3) 0.0) ($<$= (*
-3.0 cs5) 0.0))))

(assert (= cgeq6 (and ($>$= (* 1.0 cs0) 0.0) ($>$= (* -2.0 cs3) 0.0) ($>$= (*
-3.0 cs5) 0.0))))

where ceq6, cleq6, cgeq6 represent whether the linear combination in the
reasoning part of $c_{6}$ forces equality, less or equal, or greater or equal.
At least one of them has to be true so that the linear combination is valid,
and we assign sign to this reasoning constraint correspondingly (use rs6 to
represent $=,<=$ or $>=$):
(assert (ite ceq6 (= rs6 0.0) (ite cleq6 (= rs6 -1.0) (ite cgeq6 (= rs6 1.0)
xfalse))))
where xfalse is always false by a statement at the beginning of the
transformed SMT-LIB file.

Given that this linear combination is valid, let’s calculate the coefficients
of variables and right hand side value of the (reasoning) constraint forced by
this linear combination:

(declare-fun r6x0 () Real)

(assert (= r6x0 (+ (* 1.0 c0x0) (* -2.0 c3x0) (* -3.0 c5x0))))

(declare-fun r6x1 () Real)

(assert (= r6x1 (+ (* 1.0 c0x1) (* -2.0 c3x1) (* -3.0 c5x1))))

(declare-fun beta6 () Real)

(assert (= beta6 (+ (* 1.0 crhs0) (* -2.0 crhs3) (* -3.0 crhs5))))

where r6x0 is the coefficient of x0 of this constraint, beta6 is the right
hand side value of this constraint.

The last thing to check is that the reasoning constraint, if true, implies the
current constraint ($c_{6}$).
In VIPR format, only $4$ kinds of implication are allowed. Here is the
description given by VIPR authors:

  * •

A constraint that is $0\geq\beta$ with $\beta>0$ , $0\leq\beta$ with
$\beta<0$, or $0=\beta$ with $\beta\neq 0$ is called an absurdity or
falsehood. Such a constraint dominates any other constraint.

  * •

The constraint $a^{T}x\geq\beta$ or $a^{T}x=\beta$ dominates $a^{\prime
T}x\geq\beta^{\prime}$ if $a=a^{\prime}$ and $\beta\geq\beta^{\prime}.$

  * •

Similarly, the constraint $a^{T}x\leq\beta$ or $a^{T}x=\beta$ dominates
$a^{\prime T}x\leq\beta^{\prime}$ if $a=a^{\prime}$ and
$\beta\leq\beta^{\prime}.$

  * •

Finally, the constraint $a^{T}x=\beta$ dominates $a^{\prime
T}x=\beta^{\prime}$ if $a=a^{\prime}$ and $\beta=\beta^{\prime}.$

We can check whether at least one kind of implication holds with just one
assert statement in the SMT-LIB format, structured as follows:
(assert (or (reasoning constraint is absurdity) (and a = a’ (sign and right
hand side value of reasoning and current constraints satisfy the three cases
listed above))))
In particular for $c_{6}$, this assertion becomes:

(assert (or (and (= r6x0 0.0) (= r6x1 0.0) (=$>$ (= rs6 -1.0) ($<$ beta6 0.0))
(=$>$ (= rs6 1.0) ($>$ beta6 0.0)) (=$>$ (= rs6 0.0) (not (= beta6 0.0))))
(and (= r6x0 c6x0) (= r6x1 c6x1) (or (and (= beta6 crhs6) (= rs6 0.0) (= cs6
0.0)) (and ($<$= beta6 crhs6) (= cs6 -1.0) ($<$= rs6 0.0)) (and ($>$= beta6
crhs6) (= cs6 1.0) ($>$= rs6 0.0))))))

If the reasoning format is $\\{$ rnd $\ldots\\}$, it means that the current
constraint is implied by a linear combination of previous constraints, whose
left hand side is an integer and the right hand side value is rounded to an
integer. Consider the following example:

$\texttt{CE G 1 1 1 1 $\\{$ rnd 1 9 1 $\\}$ 11}.$

Suppose this is the $10$th constraint in the VIPR certificate. Most
information of this linear combination is encoded similar to the case of $\\{$
lin $\ldots\\}$. In addition, we need to verify the reasoning constraint
indeed can be rounded, i.e. the coefficients of real variables are $0$, and
the coefficients of int variables are integers. in the SMT-LIB format, the
type of all coefficients are originally set as real. To check that a
coefficient is an integer, we simply assert another random integer variable to
be equal to it under the to$\\_$real operator:
(declare-fun rndr10x0 () Int)
(assert (ite is$\\_$intx0 (= (to$\\_$real rndr10x0) r10x0) (= r10x0 0.0)))
where is$\\_$intx0 is the boolean variable representing whether x0 is an
integer variable.

In a VIPR certificate, we only allow rounding operation when the reasoning
constraint is $>=$ or $<=$. If the reasoning constraint is equality, either
the right hand side is already integer so there is no need to round, or the
rounding is invalid. Thus,

(assert (or (= rs10 -1.0) (= rs10 1.0))).

Recall the right hand side value of this reasoning constraint is beta10, and
we round it up or down depending on the sign of the reasoning constraint:

(declare-fun rndbeta10 () Int)

(assert (ite (= rs10 -1.0) (and ($\leq$ (to$\\_$real rndbeta10) beta10) ($>$
(to$\\_$real (+ rndbeta10 1)) beta10)) (and ($\geq$ (to$\\_$real rndbeta10)
beta10) ($<$ (to$\\_$real (- rndbeta10 1)) beta10))))

(declare-fun brndbeta10 () Real)

(assert (= brndbeta10 (to$\\_$real rndbeta10)))

where brndbeta10 is the rounded right hand side value, with real type.

Finally, let’s use the same assert statements as in the last case to verify
that the rounded reasoning constraint implies the current constraint:

(assert (or (and (= r10x0 0.0) (= r10x1 0.0) (=$>$ (= rs10 -1.0) ($<$
brndbeta10 0.0)) (=$>$ (= rs10 1.0) ($>$ brndbeta10 0.0)) (=$>$ (= rs10 0.0)
(not (= brndbeta10 0.0)))) (and (= r10x0 c10x0) (= r10x1 c10x1) (or (and (=
brndbeta10 crhs10) (= rs10 0.0) (= cs10 0.0)) (and ($<$= brndbeta10 crhs10) (=
cs10 -1.0) ($<$= rs10 0.0)) (and ($>$= brndbeta10 crhs10) (= cs10 1.0) ($>$=
rs10 0.0))))))

The last type of reasoning is the form $\\{$ uns $i_{1}$ $l_{1}$ $i_{2}$
$l_{2}$ $\\}$. This case is a bit complicated. Notice that each time we
introduce an assumption constraint, it can be interpreted as if we open a
branch in reasoning. In contrary, this reasoning form, “uns”, closes two
branches and goes back in the reasoning track.

Consider the $12$th constraint as an example:

CF G 1 0 $\\{$ uns 6 5 8 7 $\\}$ 13

where $c_{12}$ is $0\geq 0$, $i_{1}=6,l_{1}=5,i_{2}=8,l_{2}=7$.

The constraint is encoded in the same way as in other cases. We also need to
check the constraints used in the reasoning have been specified before:

(assert ($<$ 6 12)) (assert ($<$ 5 12)) (assert ($<$ 8 12)) (assert ($<$ 7
12))

Then, in C++ code, we use the set structure to check that $l_{1},l_{2}$ are
indeed indices of assumptions and they are used by $c_{i_{1}}$ and
$c_{i_{2}}$, correspondingly.

Now we need to verify that $c_{i_{1}},c_{i_{2}}$ both imply $c_{12}$ in the
four criteria specified before, with similar assert statements:

(assert (or (and (= c6x0 0.0) (= c6x1 0.0) (=$>$ (= cs6 -1.0) ($<$ crhs6 0.0))
(=$>$ (= cs6 1.0) ($>$ crhs6 0.0)) (=$>$ (= cs6 0.0) (not (= crhs6 0.0))))
(and (= c6x0 c12x0) (= c6x1 c12x1) (or (and (= crhs6 crhs12) (= cs6 0.0) (=
cs12 0.0)) (and ($<$= crhs6 crhs12) (= cs12 -1.0) ($<$= cs6 0.0)) (and ($>$=
crhs6 crhs12) (= cs12 1.0) ($>$= cs6 0.0))))))

(assert (or (and (= c8x0 0.0) (= c8x1 0.0) (=$>$ (= cs8 -1.0) ($<$ crhs8 0.0))
(=$>$ (= cs8 1.0) ($>$ crhs8 0.0)) (=$>$ (= cs8 0.0) (not (= crhs8 0.0))))
(and (= c8x0 c12x0) (= c8x1 c12x1) (or (and (= crhs8 crhs12) (= cs8 0.0) (=
cs12 0.0)) (and ($<$= crhs8 crhs12) (= cs12 -1.0) ($<$= cs8 0.0)) (and ($>$=
crhs8 crhs12) (= cs12 1.0) ($>$= cs8 0.0)))))).

Finally, let’s verify that at least one of $c_{l_{1}},c_{l_{2}}$ is true. A
VIPR certificate forces this with three properties:

  * •

the left hand side of $c_{l_{1}}$ and $c_{l_{2}}$ are the same;

  * •

the left hand side of $c_{l_{1}}$ and $c_{l_{2}}$ have to be integers, i.e.
all coefficients of real variables are 0, all coefficients of int variables
are integers;

  * •

the sign and right hand side value of $c_{l_{1}}$ and $c_{l_{2}}$ have to be
something like $<=B$ and $>=B+1$ so that it covers all the cases. Namely, if
the left hand side is any integer, then exactly one of $c_{l_{1}}$ and
$c_{l_{2}}$ has to be true.

To check the first property:

(assert (= c5x0 c7x0))

(assert (= c5x1 c7x1)).

To check the second property:

(declare-fun rndr12x0 () Int)

(assert (ite is$\\_$intx0 (= (to$\\_$real rndr12x0 ) c5x0) (= c5x0 0.0)))

(declare-fun rndr12x1 () Int)

(assert (ite is$\\_$intx1 (= (to$\\_$real rndr12x1 ) c5x1) (= c5x1 0.0))).

Finally, to check the third property:

(declare-fun rndbeta12 () Int)

(assert (or (and (= cs5 -1.0) (= cs7 1.0) (= (to$\\_$real rndbeta12) crhs5) (=
(+ crhs5 1.0) crhs7)) (and (= cs7 -1.0) (= cs5 1.0) (= (to$\\_$real rndbeta12)
crhs7) (= (+ crhs7 1.0) crhs5))))

where (= cs5 -1.0) checks whether $c_{5}$ is less or equal constraint.

In addition to the properties verified above, we need to verify that the last
constraint implies the lower or upper bound of the objective function
specified in the RTP section. If RTP states that the MILP is infeasible, then
we check that this constraint is absurdity.
To show a constraint is absurdity, we can show that it implies another
absurdity. In our tranformation, we show that if this constraint is true, then
$0=1$ is true.