# Disambiguating Affective Stimulus Associations for Robot Perception and
Dialogue

Henrique Siqueira*, Alexander Sutherland*, Pablo Barros, Mattias Kerzel, Sven
Magg, Stefan Wermter

Pre-print version of [1] Knowledge Technology, Department of Informatics,
University of Hamburg, Germany, {siqueira, sutherland, barros, kerzel, magg,
<EMAIL_ADDRESS>indicates equal contribution

###### Abstract

Effectively recognising and applying emotions to interactions is a highly
desirable trait for social robots. Implicitly understanding how subjects
experience different kinds of actions and objects in the world is crucial for
natural HRI interactions, with the possibility to perform positive actions and
avoid negative actions. In this paper, we utilize the NICO robot’s appearance
and capabilities to give the NICO the ability to model a coherent affective
association between a perceived auditory stimulus and a temporally
asynchronous emotion expression. This is done by combining evaluations of
emotional valence from vision and language. NICO uses this information to make
decisions about when to extend conversations in order to accrue more affective
information if the representation of the association is not coherent. Our
primary contribution is providing a NICO robot with the ability to learn the
affective associations between a perceived auditory stimulus and an emotional
expression. NICO is able to do this for both individual subjects and specific
stimuli, with the aid of an emotion-driven dialogue system that rectifies
emotional expression incoherences. The robot is then able to use this
information to determine a subject’s enjoyment of perceived auditory stimuli
in a real HRI scenario.

##  I INTRODUCTION

Emotion recognition, the task of identifying external features associated with
internal emotional processes, has recently received significant attention from
the research community. The ability to recognise and act on emotions has been
identified as a core aspect of affective user-centric computing [2]. However,
research attempting to actively apply recognised emotions is still in its
formative stages, with recognised emotions rarely being applied to solving
practical tasks. Instead, researchers have focused heavily on the process of
recognising emotions in available datasets.

Emotion incongruence is a phenomenon that occurs in multimodal input when
different modalities indicate different emotions, such as an individual having
a sad face but laughing leading to a conflicting understanding of an
individual’s emotional state. Exactly how humans handle this mismatch of
multimodal information to reach a final conclusion is an ongoing field of
research [3, 4]. Regardless, humans are often able to solve and understand
these conflicting displays of emotions. Embodied agents, such as robots, will
lack much of the context and dynamic situation handling that humans make use
of to solve misunderstandings [5]. This lack of a holistic context is likely
to become an ever more problematic element of HRI as we continue to attempt to
integrate robots into different facets of human life.

Figure 1: Illustration of our HRI experiment with the NICO robot under a
mismatching condition where NICO initially perceived a positive visual
affective response, but a negative response from speech. This situation leads
NICO to proceed the dialogue in order to accrue affective information about
the auditory stimulus.

As such, multimodal methods of learning what stimuli are experienced
positively or negatively by users, in an implicit manner to avoid frustrating
interactions, are required. Furthermore, practical methods of identifying and
solving detected incoherences in multimodal perception need to be developed,
as robots are likely to be exposed to contradictory expressions relating to
various actions and objects. For these, the robot would ideally want to
associate only positive or negative labels for the sake of simplified decision
making. Our approach addresses both preferred stimuli learning from reactions
and emotional perception coherency with a robot.

In this paper, we present an HRI scenario wherein a NICO robot, seen in Figure
1, actively tracks an affective association between recognised emotional
expressions and a triggering auditory stimulus, trying to determine if a
particular stimulus was positively or negatively received. As
misunderstandings between the visual and language modalities can occur,
dialogue is used as a tool to acquire additional affective information about
the association, with the ultimate goal of achieving a unified position on the
positivity or negativity of the association.

##  II RELATED WORK

Modelling perceived emotions in larger and more continuous contexts is a novel
area of research. Barros et al. [6] have presented initial work towards
modelling perceived emotions in a dynamic context. In their work, the authors
were able to show the emergence of different emotional concepts using Grow
When Required (GWR) Networks [7]. The authors note that although an
associative relation could be created, the conflict between modalities is not
inherently handled by the system. Our approach opts for a simpler affective
representation in order to focus more on the dynamics of general perception
toward certain stimuli and the differences between individuals. We also
present an initial step towards solving incoherent input in a manual fashion.

Some of the prevalent research that actively applies emotions to HRI scenarios
can be described as falling into two application types: emotional colouring
and emotion modulated behaviour. Emotional colouring approaches [8, 9] tend to
focus on how to reciprocate recognised emotions, often with the intention of
invoking empathy through mechanisms such as mirror neurons.

Acosta et al. [8] use learned patterns in emotional responses to change the
prosody of audio responses, with the goal of achieving improved rapport with a
user via an audible dialogue system called Gracie. Gracie’s modulation of
audio was based on the responses given by a student counselor to students
throughout an interaction. The features of the counselor’s responses to the
students through the interactions were applied to Gracie’s response system,
allowing Gracie to mimic the response method. An evaluation showed that users
preferred the emotion-specific modulation over a neutral or randomly varying
version of the system.

In the work of Zhou et al. [9], emotions have been successfully applied to the
generation of responses in a chat-bot scenario. By using a sequence to
sequence encoder-decoder architecture, the authors were able to generate
coherent and emotionally relevant responses in a chatbot scenario. The unique
approach the authors used to achieve this was through the incorporation of an
emotion category embedding as well as internal and external emotional memories
that capture emotion dynamics during the decoding process of generating
responses using a recurrent neural network. Word-by-word responses are
generated with the generated words being influenced by the internal memory and
the decision between emotional or non-emotional output words being influenced
by the external memory.

While all of these colouring approaches are valuable contributions to
enhancing HRI, they currently take a passive approach toward the role emotions
in interactions. In these cases, emotion serves as a method to enhance an
experience with a robot but does not directly contribute to a system’s
decision making procedure. Most emotion colouring scenarios could continue
without a colouring factor and the scenario would still function, albeit in a
less enjoyable manner.

In contrast to emotional colouring approaches, some selected approaches choose
to more actively applying recognised emotions to decision making in order to
achieve some desired task. Kuhnlez et al. [10, 11] have applied recognised
emotions to a Flobi robot’s decision-making process, attempting to use
recognised emotions to inspire a level of both empathy and altruism in users.
In doing so, users were more likely to assist the robot with a monotonous task
for a longer period of time than when the robot did not apply this strategy.
Still, this method relies on attempting to influence and manipulate the state
of the human. In our approach, we seek to actively determine user-preferred
user stimuli based on expressed emotions and to rectify conflicting
expressions to stimuli through dialogue initiated and steered by recognised
emotions.

##  III AFFECTIVE ASSOCIATION MODELLING

Figure 2: The Neuro-Inspired COmpanion robot. On the right, NICO is shown as a
young DJ to better fit the HRI scenario.

The experiments are realized using the humanoid robot platform NICO, the Neuro
Inspired COmpanion. NICO, as seen in Figure 2, is a child-sized humanoid
developed by the Knowledge Technology Group of the University of Hamburg [12]
as an open and highly customizable platform for research on neurobotic models
and human-robot interaction. NICO’s anthropomorphic design is modelled after a
child with an age of three to four years. NICO is about one meter tall when
standing up, it’s head and arm proportions are matching for its size. For the
reported experiment, we use the functionality of the upper body of NICO that
was mounted on a fixed stand positioned behind a table to create the
impression of being seated. NICO’s upper body has two robotic arms based on
human anatomy and range of motion and a head in the form of an abstracted
child-like face with an emotion display and two cameras.

NICO’s arms have six degrees of freedom (DoFs) which are distributed as
follows to enable human-like arm motions: three DoFs form a tight cluster in
each shoulder, emulating the motion range of a shoulder ball joint, one DoF
articulates the elbow, and two DoFs enable wrist rotation and flexation.
NICO’s end effectors are three-fingered HR4D tendon-operated hands from
SeedRobotics111http://www.seedrobotics.com which have the size of a child’s
hand. The shape of NICO’s head is adapted from the iCub robot [13]. It has a
symmetrical and abstracted child-like appearance that aims to enable intuitive
human-robot interaction while avoiding the uncanny-valley effect. Behind the
surface of the head, in the eyebrow and mouth area, a programmable LED display
is placed, that can display basic emotions in the form of stylized facial
expressions [14, 15]. The head features two 2 Megapixel sensors with a
70-degree field of vision. The Head can perform pan and tilt motions. NICO’s
arms and head are articulated with Dynamixel servomotors and controlled via
PyPot222https://github.com/poppy-project/pypot and the open NICO
API333www.inf.uni-hamburg.de/en/inst/ab/wtm/research/neurobotics/nico.html.

Some effort has also gone into enhancing NICO’s childlike qualities. As seen
in Figure 6, the NICO has been dressed to further enhance its childlike and
anthropomorphic appearance. Making these qualities seem plausible is vital to
creating a “character” that is supposedly interested in music and requires
help. The overall appearance of the NICO has been matched with a childlike
voice provided by Amazon Polly service444NICO uses the voice of Justin:
https://aws.amazon.com/polly to further enhance the impression of the NICO for
participants during the interactions. NICO takes on the role of a DJ, having
been provided with headphones and a laptop to further give the impression of a
character that is playing and enjoys music. Subtle hand and head movements
were made to enhance the perceived animacy of the NICO by making it a more
animated interaction partner.

Our aim is to provide NICO with an effective mechanism for modelling affective
associations between stimuli and emotional responses that takes into
consideration mismatching emotional expressions from different modalities. Our
approach consists of two affective perception modules to recognize emotional
expressions based on facial expressions and cues from language, and a
decision-making module to associate the perceived emotional response to a
stimulus and a person. NICO plays a key role in this interaction as an anchor
for subjects to interact with through dialogue and express emotions towards.

###  III-A Affective Visual Perception Module

Figure 3: An ensemble with shared representations based on convolutional
networks for arousal and valence recognition from a facial expression.

To recognize emotion in terms of arousal and valence from facial expressions,
we adopted an ensemble with shared representations based on convolutional
networks proposed by Siqueira et al. [16] shown in Figure 3. Our architecture
consists of a single branch with five convolutional layers (filter size of 3 x
3 with a stride of 1 x 1), each followed by a max-pooling layer (pool size of
3 x 3 with a stride of 2 x 2), for facial feature extraction. On top, five
independent convolutional branches compose the ensemble. Each branch was
trained to learn different higher-level representations from earlier layers in
order to increase diversity in the ensemble, and it consists of one
convolutional layer (filter size of 3 x 3 with a stride of 1 x 1), and two
fully-connected layers with 100 and 2 neurons (i.e., arousal and valence
outputs). As activation functions, we utilized ReLU for the convolutional
layers and the hyperbolic tangent function for the fully-connected layers
which give us a prediction between -1 to 1 for valence and arousal. Although
this approach is able to be continually re-trained using unlabelled samples
based on the ensemble predictions, we did not use this property in our
experiment to avoid any side effects.

We trained the network on the AffectNet dataset [17] which is composed of a
thousand images of facial expressions gathered from social media and annotated
by humans based on discrete and dimensional representations of emotion. As
pre-processing, we cropped the faces using the facial coordinates provided by
the dataset, normalized the pixel values from 0 to 1, and re-scaled the
cropped faces to 96 x 96 pixels in order to reduce the computational cost. Our
results on emotion recognition for the dimensional representation are
comparable with Mollahosseini et al. [17], which is 0.38 RMSE for arousal, and
0.44 RMSE for valence compared to 0.41 and 0.37 achieved by them in the
validation set. We could not evaluate our system on the test set, since it has
not been released when we trained our system.

In the HRI experiment, NICO detects the closest face by applying the Viola and
Jones algorithm [18] in an interval of three times per second. The averages of
arousal and valence for the two most expressive faces among the last four
facial expressions are stored. In our affective visual perception module, we
decided to adopt arousal as a modulation factor for valence in order to cover
a wide range of affective states. According to the circumplex model of affect
by Russel [19], for example, content and delighted have similar values on the
valence scale but are far from each other on the arousal scale. Therefore, the
use of arousal value to modulate valence might provide more conclusive
evidence on how positively or negatively the auditory stimulus was experienced
by a subject than utilizing valence only. In order to preserve the polarity of
the perceived emotion, the arousal prediction is normalized between 0 and 2.
Once a stimulus is presented, an emotional score value for the stimulus played
by NICO is computed by multiplying the arousal and valence averages from half
of the most expressive expressions. The computation of arousal and valence
averages over multiple chunks with the most prominent facial expressions for
estimating the emotional score value acts as an attention mechanism to filter
out the excessive number of neutral expressions during the auditory stimulus.

###  III-B Affective Language Perception Module

Figure 4: A bidirectional long short-term memory network for valence
recognition from language features.

Subjects were asked to express, in natural language, how they felt about the
song during the interaction. The text from spoken utterances acted as input
for the affective language perception module. In order to recognize semantic
polarity i.e. valence from language, a bidirectional long short-term memory
network (BLSTM) with a hidden layer of size 64, an intermediate hidden layer
of size 32, and a final sigmoidal output neuron was trained on the reader
samples of the EmoBank dataset [20, 21]. A hyperbolic tangent activation
function was to the final hidden states of the BLSTM and ReLU was applied to
the output of the fully connected layer. The model is visualised in Figure 4.
The EmoBank is a large text corpus of around ten thousand sentences that were
annotated using a Valence-Arousal-Dominance scale through crowd-sourcing. The
corpus was constructed of sentences from the Manually Annotated Sub-Corpus of
the American National Corpus [22] and the corpus of the SemEval 2007 Affective
Text task [23]. Given that the EmoBank is labelled on a scale of zero to five
we normalise these values from 0 to 1 to train the network.

Sentences labelled with valence were converted to sequences of word embeddings
through the commonly used Google News Vector pre-trained
embedding555https://github.com/mmihaltz/word2vec-GoogleNews-vectors which was
trained using the word2vec algorithm [24]. The sequences of word embeddings
representing the sentences were used to train the BLSTM which learned how to
interpret semantic polarity from the data. Only reader samples were selected,
as these samples were deemed most suitable for recognising emotions from the
language of others. The BLSTM was chosen as it has been shown to outperform
unidirectional LSTMs on language tasks [25] and it has the potential to
capture additional semantic information because of its bidirectional nature,
as it has access to both past and future words as context, whereas the LSTM is
only able to look into the past. We achieved an RMSE of 0.07 on the normalised
labels using the BLSTM trained on the reader samples of the EmoBank dataset,
using 10% of samples as test data.

The BLSTM was used to recognise user emotions when users were describing how
they felt about a particular song. Subject utterances were converted to text
via the top hypothesis provided by Google
Speech666https://cloud.google.com/speech-to-text. The sequences of words were
then converted to word embeddings using the same pre-trained embedding as the
one used to train the language model. The BLSTM then takes the sequence of
word embeddings in order and in reverse order, concatenating the final hidden
state outputs of both sequences before feeding them to the next fully
connected layer. Finally, the fully connected layer is connected to a
sigmoidal activation function, providing the valence classification. Once
valence had been evaluated for a particular utterance, it was combined with
the aforementioned vision evaluation to form the affective stimuli association
for a particular song in order to determine NICO’s next course of action. In
order to align the prediction range of vision and language, the output valence
for language is normalized to be between -1 and 1. We deemed that the strength
of the semantic polarity was sufficient in order to evaluate the emotion, and
thus, opted for the use of valence only for the affective language perception
module.

###  III-C Affective Association Consolidation

Once NICO has evaluated a subject’s visual and language expressions, it has to
consolidate these expressions into an affective association. The association
process is visualised in Figure 5 and the entire decision-making process is
visualised in Figure 6. The initial association is mapped as the product of
the valence and arousal of the visual expression against the valence of the
language expression, denoted as the emotional score values. This distributes
the affective association into the two-dimensional affective association
space, visualised in the first images in the second and third columns of
Figure 5. The association itself is represented as a blue icon in the figure.

Figure 5: Illustration of the interaction flow for the conducted HRI
experiment. The first column on the left shows each state during the
interaction, whereas the second corresponds to NICO’s affective perception of
the subject after each recognition phase, and the last column on the right
shows the affective information associated to a given stimulus. The yellow
region represents a set of states after NICO finds a mismatching condition.
Figure 6: An overview of the operation cycle of our approach. After presenting
an auditory stimulus and gathering affective information from vision and
speech, the decision-making associates this information with a subject and
verifies if more affective evidence is needed or not due to a possible
mismatch between affective responses.

Note that the affective association space can be divided into five different
zones. The white top left and bottom right zones are incongruence zones.
Associations that exist in these zones have conflicting evaluations of visual
expressions and language. The top right green zone is a zone indicating
coherent positive evaluations and the bottom left red zone indicates coherent
negative evaluations. Finally, there is a neutral grey zone in the middle in
the shape of a cross. Emotional score values within these grey areas indicate
that one or both modalities evaluated the subject’s expressions as neutral.
Associations marked as neutral are considered to be coherent, as we lack the
certainty to determine if an expression from a modality is positive or
negative. The neutral region for both modalities has been set after a small
pilot study to avoid mismatching conditions in low affective responses, which
is 0.075 for vision and 0.04 for speech.

If an association is placed in one of the white zones then it is considered to
have an incoherent or mismatching evaluation. These will prompt NICO to
further investigate the subject’s evaluation of the perceived auditory
stimulus through dialogue, as described by steps 5 to 7 in Figure 5. In this
case, NICO will analyse the subject’s response to being asked to clarify their
feelings toward the stimulus. It will analyse both the facial expressions and
language used by the user synchronously, as opposed to the initial reaction
which occurred asynchronously.

Based on the new emotional score evaluations, NICO will adjust the believed
association towards the stimuli. An example of how the perception may change
can be seen in the second image in the second column of Figure 5, represented
by the shift from a hollow icon to a filled icon with a line between
indicating the change between both modalities. However, NICO cannot simply
replace the old perception with the new one, as this would invalidate the
recorded initial emotional reaction to the stimulus. As such, it will use the
new perceived response to modulate the original reaction. The affective
association will only be adjusted when a final coherent expression is reached.

In case of a mismatch, NICO will hypothesize that the most extreme modality
(MEM) was correct, the MEM being either visual perception or language
perception. If the new perceived expressions from the extended dialogue have
the same MEM as the MEM from the original perception, then NICO’s hypothesis
is considered correct. The correct modality is boosted, and the other
attenuated. We see an example of this behaviour for the second image in
columns two and three of Figure 5. In this case, language was the MEM, and
when language again became the MEM in the extended dialogue, NICOs certainty
in the language modality was significantly increased. We also see that NICO’s
belief in the vision modality does not necessarily increase just because
coherent input was reached. Rather, only language was boosted as it was viewed
as being more consistent and therefore more correct.

This is the primary difference between columns two and three in Figure 5, as
column two shows how the perceived emotions change with extended dialogue,
whereas column three shows how NICO internally updates his understanding of
the user’s preference. Figure 5 also shows a practical example of this
happening, where an incongruence is detected and NICO asks for clarification.
NICO assumes that what the subject initially said was correct, rather than how
they looked. During the clarification, the subject confirms NICO’s suspicions
and retains a positive explanation of the stimulus, albeit looking more
positive. NICO will then take this as a confirmation that it was correct,
update the users affective association toward that stimuli and continue the
interaction. As an example of this entire procedure consider Figure 1, where a
person displays a positive facial expressions while giving negative language
feedback. The person says that the song is terrible, NICO detects a
mismatching condition and tries to gather additional evidence by continuing
the dialogue until the subject responds cohesively.

##  IV EXPERIMENTS

To collect data on how NICO performed when modelling affective data,
experiments were conducted with 16 subjects to determine NICO’s capabilities.
The experiment is framed as a scenario where users are helping NICO to learn
what music it should play, as illustrated in the accompanying video
(https://goo.gl/XDCp3L). The experiments are divided into two phases: learning
and evaluation. In the first phase, NICO learns the most positively charged
stimuli by presenting a stimulus and capturing the subject’s emotional
expressions.

Figure 5 illustrates the interaction flow for the conducted HRI experiment.
During the learning phase, NICO presents nine different audio stimuli to a
user. Each audio stimuli was, on average, 17 seconds long. Selected audio
stimuli were a mixture between actual music represented in the figures by the
colour blue; and a number of miscellaneous sound effects intended to confuse
or irritate the user, represented by the colour orange. Even for music that
users disliked they were expected to still be more positively inclined to
these stimuli than to the miscellaneous sound effects.

Between each audio stimulus, NICO asked the user both to describe how they
felt about the played “song” and then to rank how the song made them feel
using a five-point scale. NICO associated the perceived affective response
(middle column in Figure 5) to its affective association space illustrated in
the right column in Figure 5. If NICO identified a mismatch in the emotion
interpretation from perceived vision and language, then NICO initiated the
additional dialogue wherein it attempts to achieve a coherent affective
representation toward the audio stimulus by having the user elaborate on their
feelings regarding the stimulus.

As indicated in Figure 5 by NICO perceiving a negative visual response in
contrast to a positive description about a given song represented by the blue
circles, NICO begins the additional dialogue by presenting a hypothesis based
on the strongest perception modality. As an example, if the subject looked
clearly positive but described the song as a negative experience, then the
NICO leads with stating that it looked like the user enjoyed the experience
before asking for elaboration. NICO will continue to analyse the subjects
facial expressions and language while answering until both input modalities
are aligned in their predictions or until a maximum limit of 5 extensions is
reached (process described in the yellow region of Figure 5). After gathering
sufficient affective evidence about a given stimulus, NICO updates its
affective association space with the novel evidence, and proceed the
interaction by repeating the step 2. Note that, the states in the yellow
region is only reached if a mismatching condition is satisfied.

After all songs are played, the HRI reaches to the step 8, where NICO plays
the three songs it felt were most positively experienced by the subject.
Finally, the subject rates how many of the replayed songs were in their top
and bottom three out of all of the nine songs.

##  V RESULTS & DISCUSSION

###  V-A Modelling Stimuli

Figure 7: The clustering of how different subjects reacted to the same
stimulus. Hollow circles with lines to full circles indicate the movement of a
perceived auditory stimulus when the subject was asked to clarify their
position after an extended dialogue. Figure 8: NICO’s affective association
space or affective memory. This image depicts where NICO thinks a subject’s
emotional state regarding a certain stimuli lies based on emotional
expressions from speech and vision before (hollow circles) and after (full
circles) the extended dialogue as illustrated by the adjustments. Figure 9:
Visually perceived emotions of subject 05 for the fork sound over a period of
25 seconds.

Despite the relatively low number of subjects in our experiment, trends can
already be noticed in the clustering of data seen in Figure 7 and Figure 8.
The actual songs tend to be clustered far more frequently in the top right
quadrant of the affective perception space and the affective association
space. This indicates that NICO is able to determine songs from non-songs to a
certain extent, by examining how subjects react to the stimuli. We initially
expected more annoying sounds, such as chewing and a fork scraping, to be
notably separated from actual songs, such as the classical Ode to Joy or a
classic rock ballad. We noted that this is true when visualizing how different
songs are distributed in the affective association space.

There are still a number of issues that remain, for example, very strong
modalities are not investigated thoroughly enough. Figure 9 exemplifies this
by showing a subject visually reacting very positively to a negative stimulus.
The subject also subsequently described the audio stimulus in a manner that
was negative but did not surpass the neutral boundary for speech.
Nevertheless, this example shows the advantage of our system in comparison
with its unimodal counterpart, where the latter might have led the NICO robot
to wrongly associate a negative stimulus as positive if only vision is used.

###  V-B Modelling Individuals

Similar to the distribution of songs, different subjects affective expression
styles of subjects are also captured by NICO. In Figure 10 we see that the
shapes representing different subjects distribute themselves in a particular
manner unique to the subjects. We see that expressions from particular
subjects tend to cluster in a specific manner, with a spread in song values
being an indication of the expressiveness of users. As an example, the subject
represented by the diamond had very minor fluctuations in regards to visual
expressions and thus was not very expressive, whereas the square subject had
varied expressions both verbally and visually. If users are more emotive in
terms of language or facial expressions, we can see a larger variance in the
affective space.

Figure 10: A visual comparison between three selected samples of the
experiment participants distribution over the affective space, wherein each
subject is represented by a different shape.

The existence of this spread in evaluations and how they are different for
individuals provides valuable information on how to structure a system capable
of effectively perceiving and resolving incoherence in perceived emotions.
Currently, NICO uses a unified baseline for neutrality for all subjects.
However, given that users may possess different expressive baselines, it may
be prudent to have a dynamic and personalised baseline for every user.

###  V-C Resolving Incoherent Perception Through Dialogue

The model attempts to form coherent affective associations by initiating
extended dialogue when a mismatch of the perceived emotion from vision and
language is detected. The practical effect of doing this can be seen in the
shift of points depicted in Figure 7 and Figure 8, wherein a hollow circle
indicates a starting belief or perception, a full circle indicates an ending
belief or perception, and the line between the two indicating the trajectory
of the change for a specific shift.

We see in Figure 7 that the influence of the extended dialogue on subjects
subsequent expressions does shift the perceived expressions towards a coherent
central line that can be drawn between the top-right and bottom-left quadrants
of the figure. This indicates that subjects tend toward expressive coherence
on subsequent elaborations on the stimulus.

The adjusted affective association when using the original perception as a
baseline is depicted in Figure 8. While it is possible for NICO to conclude
coherent associations in some cases, the final association does not always
reach coherent space. This is because NICO currently continues until coherent
input is reached and not until NICO achieves a coherent association state for
a stimulus. We found that out of all the samples we collected NICO never felt
the need to extend the dialogue beyond a single additional interaction to
collect additional information when resolving incoherence.

When performing extended dialogue, we also found that users tended toward more
neutral facial expressions while retaining verbose language answers. This is
exemplified in Figure 11 and manifests as the visual modalities perceptual
transitions towards neutral zones in Figure 7.

Figure 11: Visually perceived emotions of subject 03 for the Queen sound. On
the top row is the initial reaction of vision for the actual presentation of
the stimulus. The second row depicts the facial expression during the
elaboration, which is notably more neutral.

##  VI CONCLUSIONS AND FUTURE WORK

We presented a system that allows a NICO robot to model the relation between
affective expressions and a perceived auditory stimulus. This system is able
to model how audio stimuli are generally perceived by multiple users and how
specific users differ from each other in emotional expressiveness.
Furthermore, it is able to act upon accumulated affective information in order
to be able to adjust its dialogue behaviour throughout the course of the
interaction.

In future work, we aim to increase NICO’s robustness to many of the issues
identified during the experimental procedure, such as the metric for solved
incongruence being based on coherent perception as opposed to a coherent
belief. We also aim to improve NICO’s flexibility regarding classifying
emotions from different subjects by employing a dynamic neutral expression
zone specific to individual users. Further structuring the NICO’s interaction
capabilities through intelligent dialogue will also be a focal point of future
development, allowing NICO to make informed decisions in an interactive
manner.

## ACKNOWLEDGEMENTS

This work has received funding from the European Union under the SOCRATES
project (No. 721619), and the German Research Foundation under the CML project
(TRR 169). We would like to thank Erik Strahl for his valuable contributions
that improved the quality of this paper.

## References

  * [1] H. Siqueira, A. Sutherland, P. Barros, M. Kerzel, S. Magg, and S. Wermter, “Disambiguating affective stimulus associations for robot perception and dialogue,” in _2018 IEEE-RAS 18th International Conference on Humanoid Robots (Humanoids)_ , 2018, pp. 1–9.
  * [2] R. W. Picard, “Affective computing: Challenges,” _International Journal of Human-Computer Studies_ , vol. 59, no. 1-2, pp. 55–64, 2003.
  * [3] E. M. Provost, Y. Shangguan, and C. Busso, “Umeme: University of michigan emotional mcgurk effect data set,” _IEEE Transactions on Affective Computing_ , vol. 6, no. 4, pp. 395–409, 2015.
  * [4] L. Aguado, N. Martínez-García, A. Solís-Olce, T. Dieguez-Risco, and J. A. Hinojosa, “Effects of affective and emotional congruency on facial expression processing under different task demands,” _Acta Psychologica_ , vol. 187, pp. 66–76, 2018.
  * [5] V. I. Müller, U. Habel, B. Derntl, F. Schneider, K. Zilles, B. I. Turetsky, and S. B. Eickhoff, “Incongruence effects in crossmodal emotional integration,” _Neuroimage_ , vol. 54, no. 3, pp. 2257–2266, 2011.
  * [6] P. Barros and S. Wermter, “A self-organizing model for affective memory,” in _IEEE IJCNN_. IEEE, 2017, pp. 31–38.
  * [7] S. Marsland, J. Shapiro, and U. Nehmzow, “A self-organising network that grows when required,” _Neural Networks_ , vol. 15, no. 8-9, pp. 1041–1058, 2002\.
  * [8] J. C. Acosta and N. G. Ward, “Achieving rapport with turn-by-turn, user-responsive emotional coloring,” _Speech Communication_ , vol. 53, no. 9-10, pp. 1137–1148, 2011.
  * [9] H. Zhou, M. Huang, T. Zhang, X. Zhu, and B. Liu, “Emotional chatting machine: Emotional conversation generation with internal and external memory,” _arXiv preprint arXiv:1704.01074_ , 2017.
  * [10] B. Gonsior, S. Sosnowski, C. Mayer, J. Blume, B. Radig, D. Wollherr, and K. Kühnlenz, “Improving aspects of empathy subjective performance for hri through mirroring emotions,” in _IEEE RO-MAN 2011, Atlanta, USA_ , 2011\.
  * [11] B. Kühnlenz, S. Sosnowski, M. Buß, D. Wollherr, K. Kühnlenz, and M. Buss, “Increasing helpfulness towards a robot by emotional adaption to the user,” _International Journal of Social Robotics_ , vol. 5, no. 4, pp. 457–476, 2013.
  * [12] M. Kerzel, E. Strahl, S. Magg, N. Navarro-Guerrero, S. Heinrich, and S. Wermter, “Nico—neuro-inspired companion: A developmental humanoid robot platform for multimodal interaction,” in _26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN)_. IEEE, 2017, pp. 113–120.
  * [13] G. Metta, G. Sandini, D. Vernon, L. Natale, and F. Nori, “The icub humanoid robot: an open platform for research in embodied cognition,” in _8th Workshop on Performance Metrics for Intelligent Systems_. ACM, 2008, pp. 50–56.
  * [14] N. Churamani, M. Kerzel, E. Strahl, P. Barros, and S. Wermter, “Teaching emotion expressions to a human companion robot using deep neural architectures,” in _IEEE International Joint Conference on Neural Networks (IJCNN), 2017_. IEEE, 2017, pp. 627–634.
  * [15] N. Churamani, P. Barros, E. Strahl, and S. Wermter, “Learning empathy-driven emotion expressions using affective modulations,” in _IEEE IJCNN_. IEEE, 2018, pp. 1–1.
  * [16] H. Siqueira, P. Barros, S. Magg, and S. Wermter, “An ensemble with shared representations based on convolutional networks for continually learning facial expressions,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, Oct 2018, pp. 1563–1568. [Online]. Available: https://www2.informatik.uni-hamburg.de/wtm/publications/2018/SBMW18/
  * [17] A. Mollahosseini, B. Hasani, and M. H. Mahoor, “Affectnet: A database for facial expression, valence, and arousal computing in the wild,” _IEEE Transactions on Affective Computing_ , pp. 1–1, 2018.
  * [18] P. Viola and M. J. Jones, “Robust real-time face detection,” _International Journal of Computer Vision_ , vol. 57, no. 2, pp. 137–154, 2004.
  * [19] J. A. Russell, “A circumplex model of affect.” _Journal of Personality and Social Psychology_ , vol. 39, no. 6, p. 1161, 1980.
  * [20] S. Buechel and U. Hahn, “Emobank: Studying the impact of annotation perspective and representation format on dimensional emotion analysis,” in _15th Conference of the European Chapter of the Association for Computational Linguistics_ , vol. 2, 2017, pp. 578–585.
  * [21] S. Buechel and U. Hahn, “Readers vs. writers vs. texts: Coping with different perspectives of text understanding in emotion annotation,” in _11th Linguistic Annotation Workshop_ , 2017, pp. 1–12.
  * [22] N. Ide, C. Baker, C. Fellbaum, C. Fillmore, and R. Passonneau, “Masc: The manually annotated sub-corpus of american english,” in _6th International Conference on Language Resources and Evaluation_. European Language Resources Association, 2008, pp. 2455–2460.
  * [23] C. Strapparava and R. Mihalcea, “Semeval-2007 task 14: Affective text,” in _4th International Workshop on Semantic Evaluations_. Association for Computational Linguistics, 2007, pp. 70–74.
  * [24] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” _arXiv:1301.3781_ , 2013.
  * [25] A. Graves and J. Schmidhuber, “Framewise phoneme classification with bidirectional lstm and other neural network architectures,” _Neural Networks_ , vol. 18, no. 5-6, pp. 602–610, 2005.


# Branch-and-cut algorithms for the covering salesman problem

Lucas Porto Maziero
Institute of Computing
University of Campinas
Av. Albert Einstein 1251, 13083-852, Campinas, SP, Brazil
<EMAIL_ADDRESS>
&Fábio Luiz Usberti
Institute of Computing
University of Campinas
Av. Albert Einstein 1251, 13083-852, Campinas, SP, Brazil
<EMAIL_ADDRESS>
&Celso Cavellucci
Institute of Computing
University of Campinas
Av. Albert Einstein 1251, 13083-852, Campinas, SP, Brazil
<EMAIL_ADDRESS>

###### Abstract

The Covering Salesman Problem (CSP) is a generalization of the Traveling
Salesman Problem in which the tour is not required to visit all vertices, as
long as all vertices are covered by the tour. The objective of CSP is to find
a minimum length Hamiltonian cycle over a subset of vertices that covers an
undirected graph. In this paper, valid inequalities from the generalized
traveling salesman problem are applied to the CSP in addition to new valid
inequalities that explore distinct aspects of the problem. A branch-and-cut
framework assembles exact and heuristic separation routines for integer and
fractional CSP solutions. Computational experiments show that the proposed
framework outperformed methodologies from literature with respect to
optimality gaps. Moreover, optimal solutions were proven for several
previously unsolved instances.

_K_ eywords Covering salesman problem $\cdot$ integer linear programming
$\cdot$ branch-and-cut algorithm

##  1 Introduction

Consider a set of sites scattered in the plane that must be covered by a
single-vehicle tour. Knowing that each site covers some of its neighbors, what
is the minimum length of an enclosed vehicle tour in which all sites are
covered? This question is addressed by the Covering Salesman Problem (CSP),
proposed by Current and Schilling [1] in 1989. More formally, given an
undirected graph, the CSP objective is to find the shortest Hamiltonian cycle
on a subset of vertices that covers the graph. The special case where each
vertex covers strictly itself is the Travelling Salesman Problem (TSP) [2],
which follows that CSP is also NP-hard.

Since its proposal, the CSP has attracted the attention of researchers due to
its complexity and numerous applications. These applications arise in
scenarios where it is unrealistic to visit all locations, e.g., rural health
services, areas affected by natural disasters, or planning mobile service
units [1].

Several variants of CSP were investigated. Current et al. [3] studied the
Shortest Covering Path Problem (SCPP). The goal is to find a minimum cost
$s$-$t$ path in a network that covers all vertices. The authors proposed two
methods to solve the SCPP: a Lagrangian relaxation and a branch-and-bound
algorithm that makes use of the obtained dual bounds.

Current and Schilling [4] introduced two bi-criterion routing problems: the
Median Tour Problem (MTP) and the Maximal Covering Tour Problem (MCTP).
Assuming a network with $n$ vertices and a value $p$ $(p\leqslant n)$, the
criteria for both problems are $(i)$ to find a minimum length tour that visits
exactly $p$ of the $n$ vertices and $(ii)$ to maximize the accessibility of
the vertices that are not in the tour. The problems differ in the way the
accessibility of the second criterion is evaluated. In MTP, the second
criterion is to minimize the sum of distances from each unvisited vertex to
its closest vertex in the tour. In MCTP, the second criterion is to minimize
the number of uncovered vertices. The authors proposed mathematical
formulations and heuristics to solve both MTP and MCTP. Their methodologies
were tested on a real-life scenario requiring the optimal location and
sequence of stops for overnight mail service.

Another variant of CSP, studied by Gendreau et al. [5], is the Covering Tour
Problem (CTP). Let $G=(V\cup W,E)$ be an undirected graph, where $V\cup W$ is
the set of vertices and $E$ is the set of edges. Vertex $v_{0}$ is the depot,
$V$ is the set of vertices that can be visited, $T\subseteq V$ is the set of
vertices that must be visited $(v_{0}\in T)$, and $W$ is the set of vertices
that must be covered but cannot be visited. The goal of the CTP is to
determine a minimum length tour that visits a subset of vertices $S\subseteq
V$ such that $T\subseteq S$ and each vertex of $W$ is covered by some vertex
in $S$. The authors proposed heuristics and a branch-and-cut algorithm to
solve the CTP.

Golden et al. [6] proposed a generalized version of the CSP called the
Generalized Covering Salesman Problem (GCSP). Given an undirected graph
$G=(V,E)$, each vertex $i\in V$ has a covering demand $k_{i}$, meaning vertex
$i$ has to be covered at least $k_{i}$ times. In addition, there is a fixed
cost $F_{i}$ that incurs when the tour visits vertex $i$. The objective of the
GCSP is to minimize the solution cost which is given by the sum of the tour
length and the costs of the visited vertices. The authors developed local
searches that explore exchange, removal, and insertion of tour vertices to
escape from local optimum.

Another similar problem to the CSP is the Generalized Traveling Salesman
Problem (GTSP). In GTSP, the vertices are partitioned into disjoint subsets,
called clusters, and the goal is to determine the minimum length tour that
visits exactly one vertex from each cluster. The GTSP is a special case of the
CSP, where each cluster can be modeled as a subset of vertices that mutually
cover themselves. Fischetti, González, and Toth [7] propose a branch-and-cut
algorithm based on exact and heuristic separation routines for some families
of valid inequalities for the GTSP. These inequalities are translated for the
CSP in Section 3.

Zhang and Xu [8] propose the online CSP, where the vehicle will face up to $k$
blocked edges not known a priori during its tour traversal. The objective is
to find a minimum length tour that covers all vertices while bypassing the
blocked edges. The authors presented a $(k+\alpha)$-competitive algorithm,
where $\alpha=\frac{1}{2}+\frac{(4k+2)r}{OPT}+2\upsilon\rho$, $\upsilon$ is
the approximation ratio for the Steiner Tree Problem, $\rho$ is the maximum
number of vertices that can cover an arbitrary vertex and $r$ is the radius
which defines the covering neighbourhood of each vertex.

Many works in literature have given attention to the geometric CSP, also known
as the Close Enough Traveling Salesman Problem (CETSP). In this version, each
vertex has its neighborhood defined as a compact region of the plane. The goal
is to find a minimum length tour that starts from a depot and intercepts all
neighborhood sets, thus covering all its corresponding vertices. Approximation
algorithms, heuristics and methodologies based on ILP were developed for this
version (Dumitrescu and Mitchell [9], Gulczynski et al. [10], Dong et al.
[11], Shuttleworth et al. [12], Behdani and Smith [13], Coutinho et al. [14]).

Table 1 emphasizes the main differences between CSP and its counterparts. In
CTP, among the vertices that can be visited, for some of them the visitation
is mandatory. As for the vertices that must be covered, in CTP these vertices
cannot be visited. In GTSP, the vertices are clustered into disjoint
neighborhoods, meaning each vertex covers exactly the vertices in the cluster
it belongs. The vertices in GCSP may require multiple coverings and each
visitation incurs into a fixed cost. Finally, in CETSP the vertices are
covered by a compact region on the plane instead of being covered by a subset
of vertices. All of these problems, despite sharing the idea of joining
vehicle routing with set covering, contain important distinctions with respect
to CSP. This explains why this problem still requires customized exact and
heuristic methodologies.

Table 1: Summary of the main differences between CSP, CTP, GTSP, GCSP and CETSP. |  | Required/Forbidden
---
visitations
| Disjoint
---
neighborhoods
| Multiple
---
coverings
| Geometric
---
neighborhood
CSP | ✗ | ✗ | ✗ | ✗
CTP | ✓ | ✗ | ✗ | ✗
GTSP | ✗ | ✓ | ✗ | ✗
GCSP | ✗ | ✗ | ✓ | ✗
CETSP | ✗ | ✗ | ✗ | ✓

Some solution methodologies were proposed in the literature for the CSP.
Current and Schilling [1], for example, developed a two-step heuristic to
solve the CSP: the first step solves a set cover problem; the second step
solves the TSP on the vertices determined by the first step. More than two
decades later Salari and Naju-Azimi [15] revisited the problem by proposing a
heuristic for the CSP embedded within an integer linear programming (ILP)
framework. First, they employ constructive heuristics to find good initial
solutions and then the tour vertices are rearranged by the use of ILP
techniques in an attempt to reduce its length. Salari et al. [16] give a
polynomial-size formulation and a hybrid heuristic for the CSP, which combines
ant colony optimization and dynamic programming. The formulation of Salari et
al., to the best of our knowledge, composes the state-of-the-art exact
methodology for the CSP.

More recently, Venkatesh et al. [17] proposed a multi-start iterated local
search algorithm for the CSP and incorporated a variable degree of
perturbation strategy to further improve the solution obtained through their
heuristic approach. Computational results show that the proposed approach is
competitive with other state-of-the-art heuristic approaches for solving the
CSP. Zang et al. [18] reformulated the CSP as a bilevel CSP (BCSP) with a
leader and a follower sub-problem and proposed two parallel variable
neighborhood search (PVNS) heuristics, namely, synchronous “master–slave” PVNS
and asynchronous cooperative PVNS. Computational results show that the PVNS
has improved previously best known solutions. Venkatesh et al. [19] developed
two hybrid metaheuristic approaches for the CSP. The first is based on the
artificial bee colony algorithm (ABC) and the second is based on the genetic
algorithm (GA). Both approaches were competitive with the state-of-the-art of
heuristic approaches for the CSP.

Our contribution: despite being well studied in the heuristic front, the CSP
still lacks effective exact methods. Many of the current best known solutions
still had not been proven optimal or had an open optimality gap due to the
absence of a dual bound. To address this matter, the first branch-and-cut
framework is proposed for the CSP. The framework employs exact and heuristic
routines to separate families of valid inequalities, some from the GTSP and
others original for the CSP. Computational experiments performed on a
benchmark set of instances compares our methodology with the state-of-the-art
exact methodology from literature. Previous to this work, from a set of $48$
instances, for only $9$ instances there were proven optimal solutions. Our
methodology improves this by certifying optimality for all except one
instance. This represents a major contribution to the current body of
knowledge regarding exact approaches on the CSP.

This paper is organized as follows. Section 2 formally defines the CSP and
presents an integer linear programming formulation. Section 3 shows new valid
inequalities for the CSP. Section 4 describes separation routines for the
proposed valid inequalities, which constitute the branch-and-cut framework. In
Section 5 computational experiments are conducted on a benchmark of instances,
and results are analyzed and discussed. Section 6 gives the concluding
remarks.

##  2 Problem Description and Formulation

The CSP can be formally stated as follows. Consider an undirected graph
$G(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges. Each
edge $e\in E$ is associated with a non-negative cost $c_{e}$. For each vertex
$v\in V$, $C(v)$ is the set of vertices that cover $v$ and $D(v)$ is the set
of vertices that are covered by $v$. It is considered that $v\in C(v)$ and
$v\in D(v)$, $\forall v\in V$. An optimal solution to the CSP is a minimum
length Hamiltonian cycle (tour) over a subset of vertices that covers all
vertices in $G$. Figures 1a, 1b and 1c show optimal solutions for three CSP
instances with $200$ vertices.

(a) Instance kroB200-7

(b) Instance kroB200-9

(c) Instance kroB200-11

Figure 1: Optimal solutions for instances kroB200-7, kroB200-9, and
kroB200-11, where each vertex covers its closest $7$, $9$, and $11$ neighbors,
respectively. Highlighted vertices belong to the tour and their covering sets
are represented by circumferences.

An integer linear programming (ILP) formulation for the CSP is presented.
Binary variable $x_{e}$ shows if an edge $e\in E$ belongs ($1$) or not ($0$)
to the tour and binary variable $y_{v}$ shows if a vertex belongs ($1$) or not
($0$) to the tour. We denote $\delta(v)$ the set of edges incident to $v\in
V$, $\delta(S)$ the set of edges with one endpoint in $S\subset V$ and the
other in $V\backslash S$ and $E(S)$ the set of edges with both endpoints in
$S$.

$\displaystyle(CSP)$ $\displaystyle MIN\quad\sum_{e\in E}{c_{e}x_{e}},$ (1)
subject to $\displaystyle\sum_{e\in\delta(v)}{x_{e}}=2y_{v}\qquad$
$\displaystyle\forall v\in V,$ (2) $\displaystyle\sum_{i\in
C(v)}{y_{i}}\geqslant 1\qquad$ $\displaystyle\forall v\in V,$ (3)
$\displaystyle\sum_{e\in\delta(S)}{x_{e}}\geqslant 2(y_{i}+y_{j}-1)\qquad$
$\displaystyle\forall S\subset V,i\in S,j\in V\backslash S,$ (4)
$\displaystyle x_{e}\in\\{0,1\\}\qquad$ $\displaystyle\forall i,j\in V,$ (5)
$\displaystyle y_{v}\in\\{0,1\\}\qquad$ $\displaystyle\forall i\in V.$ (6)

The CSP formulation is derived from the GTSP formulation proposed by
Fischetti, González, and Toth [7]. The objective function ($1$) minimizes the
cost of a solution given by the sum of the costs of its edges. Constraints
($2$) ensure the number of edges incident at a vertex is $2$ (if $v$ is in the
tour) or $0$ (otherwise). Constraints ($3$) impose that each vertex must be
covered at least once. Constraints ($4$) are subtour elimination constraints
which state that every cut separating two vertices in the tour contains at
least two edges.

##  3 Valid Inequalities

This section presents valid inequalities proposed by Fischetti, González, and
Toth [7] for the GTSP, and here translated for the CSP. It is worth reminding
that the GTSP is a special case of the CSP in which the vertices are
partitioned into clusters, and each cluster is formed by vertices which
mutually cover themselves, i.e., any two vertices $u$ and $v$ from the same
cluster would have $C(u)=C(v)$.

(a) $S\notin\gamma(V)$

(b) $S\in\gamma(V)$

Figure 2: Example of $S\notin\gamma(V)$ (a) and $S\in\gamma(V)$ (b).

Let $D(S)$ be the union of sets $D(v)$ for all $v\in S$, i.e.,
$D(S)=\displaystyle\bigcup_{v\in S}{D(v)}$ and let $\gamma(V)$ be the family
of all the subsets of vertices that contains $C(v)$ for at least one vertex
$v\in V$, i.e., $\gamma(V)=\\{F\subseteq\mathcal{P}(V):\forall S\in F,\exists
v\in S,C(v)\subseteq S\\}$ where $\mathcal{P}(V)$ is the power set of $V$. To
exemplify the concept of $\gamma(V)$, consider sets $C(1)=\\{1,4,8\\}$,
$C(2)=\\{2,5,8\\}$ and $C(3)=\\{3,6,7\\}$ as shown in Figure 2. As exemplified
in Figure 2a, if $S=\\{3,4,5\\}$, then none of the sets $C(1)$, $C(2)$ and
$C(3)$ is a subset of $S$, thus $S\notin\gamma(V)$. However, if
$S=\\{3,4,5,6,7\\}$, then set $C(3)$ is contained in $S$, thus
$S\in\gamma(V)$, as shown in Figure 2b. The following family of inequalities
are valid for the CSP:

$\displaystyle\sum_{e\in\delta(S)}{x_{e}}\geqslant 2\qquad$
$\displaystyle\forall S\in\gamma(V):D(S)\neq V,$ (7)
$\displaystyle\sum_{e\in\delta(S)}{x_{e}}\geqslant 2y_{i}\qquad$
$\displaystyle\forall S\not\in\gamma(V):D(S)\neq V,i\in S,$ (8)
$\displaystyle\sum_{e\in\delta(S)}{x_{e}}\geqslant 2(y_{i}+y_{j}-1)\qquad$
$\displaystyle\forall S\not\in\gamma(V):D(S)=V,i\in S,j\in V\backslash S.$ (9)

Inequalities (7) ensure that each cut separating two sets $C(v)$ and $C(w)$
must be crossed at least twice. Inequalities (8) imply that each cut
separating one vertice in the tour and one set $C(v)$ must be crossed at least
twice. Inequalities (9) ensure that each cut separating two vertices in the
tour must be crossed at least twice. Originally in GTSP, inequalities (7),
(8), and (9) were applied to every subset of vertices containing at least one
cluster, i.e., any subset of family $\gamma(V)$.

In the following, a new family of valid inequalities is proposed to consider a
scenario particular to the CSP.

###  3.1 Cover Intersection Inequalities

Consider the case in which two covering sets $C(v)$ and $C(u)$, for some pair
of vertices $v$ and $u$, overlap. This is a typical scenario for the CSP, and
it does not occur on the GTSP since in that problem the clusters are disjoint.
The new valid inequalities extend the idea of inequalities (7), in the sense
of requiring a minimum weight for any edge cut-set separating two covering
sets. However, to address the overlap of covering sets, the new valid
inequalities (10) also take into account the edge cut-set weight of the
intersection $C(v)\cap C(u)$.

(a) Feasible solution

(b) Infeasible solution

Figure 3: Example of feasible (a) and infeasible (b) solutions in the context
of overlap of covering sets.

For the following new valid inequalities (10), consider $S_{v}=S\cap C(v)$ for
any $v\in V$. These inequalities are here called CI inequalities (cover
intersection inequalities), and they only require a proper subset $S\subset V$
such that $S\in\gamma(V)$, which means it can be employed even if $D(S)=V$,
another case in which inequalities (7) cannot be employed.

$\displaystyle(CI\ inequalities)$
$\displaystyle\sum_{e\in(\delta(S)\bigcup\delta(S_{v}))}{x_{e}}\geqslant
2\qquad$ $\displaystyle\forall v\in V,\forall S\subset V:S\in\gamma(V)$ (10)

According to constraints $(3)$, for any given vertex $v$, at least one vertex
of $C(v)$ must be visited by the tour. In other words, for any subset
$S\subset V$ such that $S\in\gamma(V)$, the tour must visit $S_{v}$ or
$C(v)\setminus S_{v}$. If set $S$ does not intersect with $C(v)$, then $S_{v}$
is empty, and (10) reduces to (7). Otherwise, $S_{v}$ is not empty, and in
this case, to satisfy constraints $(3)$, the solution must contain at least
two edges in either $\delta(S_{v})$ or $\delta(S\setminus S_{v})$. In Figure
3a, a feasible solution is presented in which both covering sets $C(u)$ and
$C(v)$ are visited by the same tour. Despite the fact that the edge cut-set
$\delta(C(u))$ is empty is not a concern, since $\delta(C(u)\cap C(v))$
contains two edges. This is not the case in Figure 3b, where both
$\delta(C(u))$ and $\delta(C(u)\cap C(v))$ are empty, asserting the
infeasibility. It is worth mentioning that the solution depicted in Figure 3b
violates the CI inequality associated to the set $S=C(u)$ and vertex $v$.

##  4 Branch-and-cut framework

This section presents the separation routines for inequalities (7)-(10).
Sections 4.1 and 4.2 present the separation routines for integer and
fractional solutions, respectively. In the following sections, consider
$\mathbf{\\{x^{I},y^{I}\\}}$ and $\mathbf{\\{x^{F},y^{F}\\}}$ as integer and
fractional solutions for the CSP formulation without the subcycle elimination
constraints (4) but possibly including some of the valid inequalities
(7)-(10). Also, let $G^{I}(V^{I},E^{I})$ and $G^{F}(V^{F},E^{F})$ be the
graphs induced by $\mathbf{\\{x^{I},y^{I}\\}}$ and
$\mathbf{\\{x^{F},y^{F}\\}}$, respectively. In $G^{I}$, every vertex $v\in
V^{I}$ has a weight $y_{v}$, such that $y_{v}\in\mathbf{y^{I}}$, and every
edge $e\in E^{I}$ has a cost $x_{e}$, such that $x_{e}\in\mathbf{x^{I}}$.
Similarly, in $G^{F}$, every vertex $v\in V^{F}$ has a weight $y_{v}$, such
that $y_{v}\in\mathbf{y^{F}}$, and every edge $e\in E^{F}$ has a cost $x_{e}$,
such that $x_{e}\in\mathbf{x^{F}}$.

###  4.1 Separation routine for integer solutions

The proposed separation routine searches, in a lazy constraint fashion, for
inequalities (7-10) that are possibly violated by an integer solution
$\mathbf{\\{x^{I},y^{I}\\}}$. First, the routine performs a depth-first search
in $G^{I}$ to check for the existence of illegal subcycles.

Let $S\subset V$ be the vertices of an illegal subcycle in $G^{I}$. To apply
inequality (7) or (10) with respect to set $S$, it is necessary that
$S\in\gamma(V)$. If this is not the case, the proposed routine attempts to
augment $S$ into $S_{aug}$ by including the set $C(v)$ for some $v\in S$.
However, the choice of which $C(v)$ will be included in $S_{aug}$ is relevant
to the effectiveness of the corresponding inequalities, as will be explained
next.

Consider Figure 4, which shows a solution formed by two subcycles in graph
$G^{I}$. In this figure $C(v_{4})=\\{v_{4},v_{8}\\}$,
$C(5)=\\{v_{5},v_{7}\\}$, and $C(v_{6})=\\{v_{6},v_{9}\\}$. By taking the
illegal subcycle represented by $S=\\{v_{4},v_{5},v_{6}\\}$, it is not
possible to apply inequalities (7) or (10), since $S\notin\gamma(V)$. By
taking $S_{aug}=S\cup C(5)$, then $S_{aug}\in\gamma(V)$, however $S_{aug}$
would not generate an effective cut, since vertex $v_{7}\in V^{I}$. Otherwise,
effective cuts can be derived from $S_{aug}=S\cup C(v_{4})$ or $S_{aug}=S\cup
C(v_{6})$. Therefore, for an inequality (7) or (10) associated to $S_{aug}$ to
be effective in cutting solution $\mathbf{\\{x^{I},y^{I}\\}}$, set $S_{aug}$
cannot contain any vertex in $V^{I}\setminus S$.

Algorithm 1 presents the implementation details of the separation routine for
integer solutions, which searches for inequalities (7-10) associated to each
subcycle found in $\mathbf{\\{x^{I},y^{I}\\}}$. The overall complexity of
Algorithm 1 is bounded by $O(V^{2})$.

Figure 4: Example of an invalid CSP solution with two subcycles.

Input: graph $G^{I}(V^{I},E^{I})$ induced by an infeasible integer solution
$\mathbf{\\{x^{I},y^{I}\\}}$ for the CSP.
Output: a set $T$ of valid inequalities that cuts
$\mathbf{\\{x^{I},y^{I}\\}}$.

1:for each subcycle $S$ in $\mathbf{\\{x^{I},y^{I}\\}}$ do

2: $T\leftarrow\emptyset$

3: if $D(S)\neq V$ then

4: if $S\in\gamma(V)$ then

5: $T\leftarrow T\cup$ inequality (7) associated to $S$

6: else

7: $T\leftarrow T\cup$ inequality (8) associated to $S$

8: for each $v\in S$ do

9: $S_{aug}\leftarrow S\cup C(v)$

10: if $S_{aug}\cap(V^{I}\setminus S)=\emptyset$ then

11: if $D(S_{aug})\neq V$ then

12: $T\leftarrow T\cup$ inequality (7) associated to $S_{aug}$

13: else

14: for $u\in V$ do

15: $S_{u}\leftarrow S\cap C(u)$;

16: if $\delta(S_{u})\cap E^{I}=\emptyset$ then

17: $T\leftarrow T\cup$ CI inequality (10) associated to $S_{aug}$ and $S_{u}$

18: else

19: for each subcycle $S^{\prime}$ in
$\mathbf{\\{x^{I},y^{I}\\}}:S^{\prime}\neq S$ do

20: $T\leftarrow T\cup$ inequality (9) associated to $S$ and $S^{\prime}$

21:return $T$;

Algorithm 1 Separation routine for integer solutions.

###  4.2 Exact separation routine for fractional solutions

This section gives the exact separation routines of inequalities (7-10) for a
fractional CSP solution $\mathbf{\\{x^{F},y^{F}\\}}$. In particular, the
separation of inequalities (7), (8) and (9) follows the methodology proposed
by Fischetti, González and Toth [7] for the GTSP. As for the CI inequalities
(10), a transformation of the solution graph $G^{\prime}$ is proposed to
tackle the overlap of covering sets. The routines are described next.

As observed by Fischetti, González and Toth [7], the separation problem to
find one or more inequalities (9) violated by $\mathbf{\\{x^{F},y^{F}\\}}$ can
be reduced to the problem of computing a minimum cut between two vertices $i$
and $j$ in graph $G^{F}$, $i\in S$ and $j\in V^{F}\backslash S$, i.e., finding
the maximum flow from $i$ to $j$ [20]. Similarly, the separation of
inequalities (8) can be reduced to computing a minimum cut in graph $G^{F}$
that separates $i\in S$ and $C(u)\subseteq V^{F}\backslash S$. In other words,
finding the maximum flow from $i$ to $t$ [20], where $t$ is an artificial
vertex connected to each $j\in C(u)$ through edges with infinite capacity. As
for inequalities (7), the separation problem can be reduced to computing a
minimum cut between covering sets $C(v)$ and $C(u)$ in graph $G^{F}$, with
$C(v)\subseteq S$, $C(u)\subseteq V\backslash S$, and $C(v)\cap
C(u)=\emptyset$. A maximum flow from $s$ to $t$ can be computed, such that $s$
and $t$ are artificial vertices connected, respectively, to each vertex in
$C(v)$ and $C(u)$ with infinite capacity edges, as illustrated in Figure 5. It
is worth noting that the separation of inequality (7) does not work when
$C(v)$ and $C(u)$ overlap, since every cut separating $s$ and $t$ has infinite
weight, as exemplified in Figure 6a.

Figure 5: Max-flow instance for the separation of inequality (7) in the case
where $C(v)\cap C(u)=\emptyset$.

An exact separation algorithm for CI inequalities (10) is proposed to
accomodate the case when two covering sets $C(v)$ and $C(u)$ overlap. The
first step is to augment graph $G^{F}$, by including an artificial vertex
$w^{\prime}$ and an artificial edge $(w,w^{\prime})$ for every vertex $w\in
C(v)\cap C(u)$. Vertex $w$ is removed from $C(u)$ and vertex $w^{\prime}$ is
included into $C(u)$. Finally, for each $w\in C(v)\cap C(u)$, let $T_{w}$ be
the set of edges with one endpoint being $w$ and the other is in $V\backslash
C(v)$. The edges of $T_{w}$ are excluded from $G^{F}$ and their total weight
is transferred to the artificial edge $(w,w^{\prime})$. This ensures that
every artificial edge will be counted for in any minimum cut, in the sense
that every edge in $T_{w}$ contributes in their purpose of connecting both
covering sets $C(v)$ and $C(u)$, as expected in a feasible solution. Figure 6
illustrates the augmentation of graph $G^{F}$.

(a) Pre-augmentation

(b) Augmented graph

Figure 6: Graph augmentation for the separation of CI inequalities (10).

The separation of a CI inequality (10) reduces to computing a minimum cut
between sets $C(v)$ and $C(u)$ in the augmented graph. Let $\delta(S_{min})$
be the minimum cut between $C(v)$ and $C(u)$ and $S_{u}=S_{min}\cap C(u)$. If
$\displaystyle\sum_{e\in\delta(S_{min})\bigcup\delta(S_{u})}{x_{e}}$ has a
value less than $2$, then a violated CI inequality (10) was found.

Algorithm 2 presents the implementation of exact separation routine for
fractional solutions. The separation consists in computing a max-flow for each
pair of vertices, thus considering a push-relabel algorithm [20] to solve max-
flow, the time complexity of Algorithm 2 is bounded by $O(V^{4}E)$.

Input: graph $G^{F}(V^{F},E^{F})$ induced by a fractional solution
$\mathbf{\\{x^{F},y^{F}\\}}$ for the CSP.
Output: a set $T$ of valid inequalities that cuts
$\mathbf{\\{x^{F},y^{F}\\}}$.

1:$T\leftarrow\emptyset$

2:for $v\in V$ do

3: for $u\in V\setminus\\{v\\}$ do

4: if $D(C(v))\neq V$ and $C(v)\cap C(u)=\emptyset$ then

5: $S\leftarrow$ minCut($C(v),C(u),G^{F}$)

6: $T\leftarrow T\cup$ inequality (7) associated to $S$.

7: else

8: $G_{aug}^{F}\leftarrow$ augment($G^{F}$)

9: $S\leftarrow$ minCut($C(v),C(u),G_{aug}^{F}$)

10: $T\leftarrow T\cup$ CI inequality (10) associated to $S$ and $u$.

11: if $y_{v}>0$ and $v\notin C(u)$ then

12: $S\leftarrow$ minCut($v,C(u),G^{F}$)

13: $T\leftarrow T\cup$ inequality (8) associated to $S$ and $u$.

14: if $y_{v}+y_{u}-1>0$ then

15: $S\leftarrow$ minCut($v,u,G^{F}$)

16: $T\leftarrow T\cup$ inequality (9) associated to $S$, $v$ and $u$.

17:return $T$;

Algorithm 2 Exact separation routine for fractional solutions.

Given the computational effort required for the exact separation of fractional
solutions, two alternatives were investigated. The first is based on a first-
found policy, which follows the same steps of Algorithm 2, however the
execution is interrupted once the first inequality which surpasses a given
violation threshold $\epsilon$ is found. For example, with respect to
inequalities (7), given a vertex $v\in V$ and a set $S\in\gamma(V):D(S)\neq
V$, if the following holds, $(2-\sum_{e\in\delta(S)}{x_{e}}>\epsilon)$, then
the cut is included in the model and Algorithm 2 halts. The same goes for
inequalities (8-10).

The second alternative for the exact separation routines resides in the
heuristic separation of inequalities (7-10), described in the following
section.

###  4.3 Heuristic separation routine for fractional solutions

A heuristic separation has the purpose of finding inequalities being violated
by a fractional solution $\\{\mathbf{x^{F},y^{F}}\\}$ within short
computational times. In contrast with the exact separation routine however, a
heuristic does not come with any guarantee of finding a violated inequality
even if one exists.

The heuristic separation routine for inequalities (7-10) is composed of four
main steps. The first step searches for inequalities (7) and (10) for every
$u\in V$ and its corresponding covering set $C(u)$. In more details, let
$S=C(u)$ and consider two cases: $(i)$ if $D(S)\neq V$ and
$\sum_{e\in\delta(S)}{x_{e}}<2$, then the inequality (7) associated to $S$
cuts $\\{\mathbf{x^{F},y^{F}}\\}$; $(ii)$ if $D(S)=V$ and
$\sum_{e\in\delta(S)}{x_{e}}+\sum_{e\in\delta(S_{v})\setminus\delta(S)}{x_{e}}<2$
for some vertex $v\in V\setminus\\{u\\}$, then the CI inequality (10)
associated to $S$ and $v$ cuts $\\{\mathbf{x^{F},y^{F}}\\}$.

In the second step, the connected components $S_{1},\ldots,S_{p}$ of $G^{F}$
are computed. For each component $S_{k}$, let $S=S_{k}$ and if $S\in\gamma(V)$
then two cases are considered: $(i)$ if $D(S)\neq V$, then the inequality (7)
associated to $S$ cuts $\\{\mathbf{x^{F},y^{F}}\\}$; $(ii)$ if $D(S)=V$ and
$\sum_{e\in\delta(S_{v})}{x_{e}}<2$ for some vertex $v\in V$, then the CI
inequality (10) associated to $S$ and $v$ cuts $\\{\mathbf{x^{F},y^{F}}\\}$. .

In the third step, for each connected component $S_{k}$, let $S=S_{k}$ and
$i=\arg\max_{v}\\{y_{v}:v\in S\\}$. If $D(S)\neq V$, then the inequality (8)
associated to $S$ and $v$ cuts $\\{\mathbf{x^{F},y^{F}}\\}$.

Finally, the fourth step iterates through all pairs of connected components
$S_{k}$ and $S_{l}$, $k\neq l$. For each pair, let
$i=\arg\max_{v}\\{y_{v}:v\in S_{k}\\}$ and $j=\arg\max_{v}\\{y_{v}:v\in
S_{l}\\}$. If $y_{i}+y_{j}>1$, the inequality (9) associated to $S=S_{k}$,
$i$, and $j$ cuts $\\{\mathbf{x^{F},y^{F}}\\}$.

Algorithm 3, with a time complexity bounded by $O(V^{2})$, details the
heuristic separation routine for fractional solutions.

Input: graph $G^{F}(V^{F},E^{F})$ induced by a fractional solution
$\mathbf{\\{x^{F},y^{F}\\}}$ for the CSP.
Output: a set $T$ of valid inequalities that cuts
$\mathbf{\\{x^{F},y^{F}\\}}$.

1:$T\leftarrow\emptyset$

2:for $u\in V$ do

3: $S\leftarrow C(u)$;

4: if $D(S)\neq V$ then

5: if $\sum_{e\in\delta(S)}{x_{e}}<2$ then

6: $T\leftarrow T\cup$ inequality (7) associated to $S$.

7: else

8: for $v\in V:v\neq u$ do

9: $S_{v}\leftarrow S\cap C(v)$;

10: if
$\sum_{e\in\delta(S)}{x_{e}}+\sum_{e\in\delta(S_{v})\setminus\delta(S)}{x_{e}}<2$
then

11: $T\leftarrow T\cup$ CI inequality (10) associated to $S$ and $v$.

12:Compute the connected components $S_{1},\ldots,S_{p}$ of $G^{F}$;

13:for $k=1,...,p$ do

14: $S\leftarrow S_{k}$

15: if $S\in\gamma(V)$ then

16: if $D(S)\neq V$ then

17: $T\leftarrow T\cup$ inequality (7) associated to $S$.

18: else

19: for $v\in V:v\neq w$ do

20: $S_{v}\leftarrow S\cap C(v)$;

21: if $\sum_{e\in\delta(S_{v})\setminus\delta(S)}{x_{e}}<2$ then

22: $T\leftarrow T\cup$ CI inequality (10) associated to $S$ and $v$.

23: else

24: $i\leftarrow\arg\max_{v}\\{y_{v}:v\in S\\}$.

25: if $D(S)\neq V$ then

26: $T\leftarrow T\cup$ inequality (8) associated to $S$ and $i$.

27: for $l=k,...,p$ do

28: $j\leftarrow\arg\max_{v}\\{y_{v}:v\in S_{l}\\}$

29: $T\leftarrow T\cup$ inequality (9) associated to $S$, $i$ and $j$.

30:return T

Algorithm 3 Heuristic separation routine for fractional solutions.

##  5 Computational Experiments

In this section, the proposed branch-and-cut methodologies are evaluated and
compared to the state-of-the-art using the literature benchmark of instances,
described in the following section.

###  5.1 Instances

The set of instances used in the computational experiments was created by
Salari et al.[16] based on the TSPLIB [21], and they are divided in two types:
small ($36$ instances) and medium ($12$ instances). The small instances have
$51\leqslant|V|\leqslant 100$ vertices and medium-size instances have
$150\leqslant|V|\leqslant 200$ vertices. There is also a set of large
instances with $|V|\geqslant 532$, which Salari et al. assigned only for the
testing of heuristics, and for this reason, the large instances are not
reported in this paper. The covering set of each vertex is defined by its $k$
closest vertices. For each graph, three values of $k$ were used, $k=7$, $k=9$,
and $k=11$. Full experimental data (including results for large instances),
instances, and source codes are available on-
line111http://www.ic.unicamp.br/~fusberti/problems/csp.

###  5.2 Computational Settings

The branch-and-cut methodologies were implemented in C++ using solver Gurobi,
with a one-hour time limit. The experiments were conducted on a PC under
Ubuntu and CPU Intel Xeon E5-2630 $2.2$ GHz, with $64$GB of RAM.

###  5.3 Evaluated Methodologies

Five branch-and-cut methodologies were implemented and evaluated in the
computational experiments:

  1. 1.

$CSP$-$I$: exact separation routine for integer solutions (Algorithm 1)
considering valid inequalities (7), (8), and (9), but excluding the CI
inequalities (10);

  2. 2.

$CSP$-$I\&F_{vp}$: on the root node, exact separation routine for fractional
solutions (Algorithm 2) considering inequalities (7), (8), and (9), but
excluding the CI inequalities for CSP (10). For the non-root nodes, Algorithm
2 was implemented under the first-found policy with violation threshold
$\epsilon=1$ (see Section 4.2).

  3. 3.

$CSP$-$I\&F_{vp}$-$X$: same as $CSP$-$I\&F_{vp}$, but including the CI
inequalities (10);

  4. 4.

$CSP$-$I\&F_{h}$: on the root node, exact separation routine for fractional
solutions (Algorithm 2) considering inequalities (7), (8), and (9), but
excluding the CI inequalities (10). For the non-root nodes, heuristic
separation for fractional solutions (Algorithm 3, considering inequalities
(7), (8), and (9), but excluding the CI inequalities (10);

  5. 5.

$CSP$-$I\&F_{h}$-$X$: Same as $CSP$-$I\&F_{h}$, but including inequalities
(10);

These methodologies were compared with the integer linear programming
formulation proposed by Salari et al.[16], denoted here as $SRS$. To the best
of our knowledge, $SRS$ is the best performing exact methodology for the CSP.

Preliminary experiments have shown that even in cases where the heuristic
separation fails to find violated inequalities in methodologies
$CSP$-$I\&F_{h}$ and $CSP$-$I\&F_{h}$-$X$, applying the exact separation does
not improve the quality of the solutions obtained. This can be justified by
the high computational effort spent by the exact separation routines.

###  5.4 Results

The results of the computational experiments are reported for the small and
medium instances in Tables LABEL:tab:smallInstances and 3, respectively. Each
table reports for each methodology and for each instance, the following:

  * •

LB: best lower bound obtained;

  * •

Gap: optimality gap $(\displaystyle\frac{UB-LB}{UB})\cdot 100$;

  * •

Time: execution time in seconds.

In both tables, the column group BestUB reports the best upper bounds known in
the literature for each instance: column UB gives the best known upper bounds
and column References cites the papers which attained them. For each instance,
the Tables LABEL:tab:smallInstances and 3 highlight the optimal solutions
(underlined) and the best lower bounds (in bold) obtained by each methodology.

Table 2: Results of computacional experiments for the small-size instances.

|  |  | BestUB |  | $SRS$ |  |  $CSP$-$I$ |  |  $CSP$-$I\&F_{vp}$ |  |  $CSP$-$I\&F_{h}$ |  |  $CSP$-$I\&F_{vp}$-$X$ |  |  $CSP$-$I\&F_{h}$-$X$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Instance | NC |  | UB | References |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time
eil51 | 7 |  | 164 | [6, 15, 16, 17] |  | 164 | 0 | 149 |  | 164 | 0 | 2 |  | 164 | 0 | 4 |  | 164 | 0 | 3 |  | 164 | 0 | 3 |  | 164 | 0 | 3
| 9 |  | 159 | [6, 15, 16, 17] |  | 159 | 0 | 220 |  | 159 | 0 | 1 |  | 159 | 0 | 2 |  | 159 | 0 | 2 |  | 159 | 0 | 4 |  | 159 | 0 | 3
| 11 |  | 147 | [6, 15, 16, 17] |  | 147 | 0 | 681 |  | 147 | 0 | 1 |  | 147 | 0 | 2 |  | 147 | 0 | 2 |  | 147 | 0 | 5 |  | 147 | 0 | 4
berlin52 | 7 |  | 3887 | [6, 15, 16, 17] |  | 3887 | 0 | 140 |  | 3887 | 0 | 2 |  | 3887 | 0 | 2 |  | 3887 | 0 | 2 |  | 3887 | 0 | 4 |  | 3887 | 0 | 3
| 9 |  | 3430 | [6, 15, 16, 17] |  | 3430 | 0 | 212 |  | 3430 | 0 | 1 |  | 3430 | 0 | 3 |  | 3430 | 0 | 2 |  | 3430 | 0 | 6 |  | 3430 | 0 | 3
| 11 |  | 3262 | [6, 15, 16, 17] |  | 3262 | 0 | 255 |  | 3262 | 0 | 1 |  | 3262 | 0 | 2 |  | 3262 | 0 | 2 |  | 3262 | 0 | 4 |  | 3262 | 0 | 4
st70 | 7 |  | 288 | [6, 15, 16, 17] |  | 288 | 0 | 490 |  | 288 | 0 | 3 |  | 288 | 0 | 7 |  | 288 | 0 | 5 |  | 288 | 0 | 7 |  | 288 | 0 | 7
| 9 |  | 259 | [6, 15, 16, 17] |  | 259 | 0 | 1391 |  | 259 | 0 | 3 |  | 259 | 0 | 7 |  | 259 | 0 | 6 |  | 259 | 0 | 13 |  | 259 | 0 | 9
| 11 |  | 247 | [6, 15, 16, 17] |  | 218 | 13.14 | 3600 |  | 247 | 0 | 3 |  | 247 | 0 | 7 |  | 247 | 0 | 5 |  | 247 | 0 | 14 |  | 247 | 0 | 9
eil76 | 7 |  | 207 | [6, 15, 16, 17] |  | 193 | 7.45 | 3600 |  | 207 | 0 | 6 |  | 207 | 0 | 29 |  | 207 | 0 | 9 |  | 207 | 0 | 15 |  | 207 | 0 | 12
| 9 |  | 185 | [15] |  | 161 | 14.65 | 3600 |  | 185 | 0 | 10 |  | 185 | 0 | 10 |  | 185 | 0 | 9 |  | 185 | 0 | 13 |  | 185 | 0 | 12
| 11 |  | 170 | [6, 15, 16, 17] |  | 145 | 17.08 | 3600 |  | 170 | 0 | 6 |  | 170 | 0 | 8 |  | 170 | 0 | 7 |  | 170 | 0 | 15 |  | 170 | 0 | 13
pr76 | 7 |  | 50275 | [6, 15, 16, 17] |  | 50275 | 0 | 2488 |  | 50275 | 0 | 7 |  | 50275 | 0 | 8 |  | 50275 | 0 | 6 |  | 50275 | 0 | 12 |  | 50275 | 0 | 8
| 9 |  | 45348 | [6, 15, 16, 17] |  | 42935 | 5.62 | 3600 |  | 45348 | 0 | 6 |  | 45348 | 0 | 32 |  | 45348 | 0 | 10 |  | 45348 | 0 | 16 |  | 45348 | 0 | 14
| 11 |  | 43028 | [6, 15, 16, 17] |  | 39022 | 10.27 | 3600 |  | 43028 | 0 | 28 |  | 43028 | 0 | 17 |  | 43028 | 0 | 46 |  | 43028 | 0 | 27 |  | 43028 | 0 | 28
rat99 | 7 |  | 486 | [6, 15, 16, 17] |  | 433 | 12.21 | 3600 |  | 486 | 0 | 238 |  | 486 | 0 | 19 |  | 486 | 0 | 17 |  | 486 | 0 | 33 |  | 486 | 0 | 17
| 9 |  | 455 | [6, 15, 16, 17] |  | 377 | 20.73 | 3600 |  | 438 | 3.88 | 3600 |  | 455 | 0 | 30 |  | 455 | 0 | 27 |  | 455 | 0 | 28 |  | 455 | 0 | 29
| 11 |  | 444 | [6, 15, 16, 17] |  | 350 | 26.81 | 3600 |  | 444 | 0 | 203 |  | 444 | 0 | 32 |  | 444 | 0 | 138 |  | 444 | 0 | 37 |  | 444 | 0 | 197
kroA100 | 7 |  | 9674 | [6, 15, 16, 17] |  | 9177 | 5.42 | 3600 |  | 9674 | 0 | 15 |  | 9674 | 0 | 18 |  | 9674 | 0 | 27 |  | 9674 | 0 | 27 |  | 9674 | 0 | 30
| 9 |  | 9159 | [6, 15, 16, 17] |  | 7938 | 15.38 | 3600 |  | 9159 | 0 | 154 |  | 9159 | 0 | 28 |  | 9159 | 0 | 2040 |  | 9159 | 0 | 36 |  | 9159 | 0 | 2230
| 11 |  | 8901 | [6, 15, 16, 17] |  | 8593 | 3.59 | 3600 |  | 8608 | 3.40 | 3600 |  | 8901 | 0 | 45 |  | 8640 | 3.02 | 3600 |  | 8901 | 0 | 79 |  | 8801 | 1.14 | 3600
kroB100 | 7 |  | 9537 | [6, 15, 16, 17] |  | - | - | 3600 |  | 9537 | 0 | 45 |  | 9537 | 0 | 22 |  | 9537 | 0 | 20 |  | 9537 | 0 | 26 |  | 9537 | 0 | 23
| 9 |  | 9240 | [6, 15, 16, 17] |  | 7678 | 20.34 | 3600 |  | 9240 | 0 | 363 |  | 9240 | 0 | 21 |  | 9240 | 0 | 21 |  | 9240 | 0 | 31 |  | 9240 | 0 | 28
| 11 |  | 8842 | [6, 15, 16, 17] |  | - | - | 3600 |  | 8842 | 0 | 141 |  | 8842 | 0 | 25 |  | 8842 | 0 | 29 |  | 8842 | 0 | 40 |  | 8842 | 0 | 36
kroC100 | 7 |  | 9723 | [6, 15, 16] |  | 8564 | 13.54 | 3600 |  | 9723 | 0 | 561 |  | 9723 | 0 | 107 |  | 9723 | 0 | 102 |  | 9723 | 0 | 67 |  | 9723 | 0 | 92
| 9 |  | 9171 | [6, 15, 16, 17] |  | 7663 | 19.68 | 3600 |  | 8920 | 2.81 | 3600 |  | 9171 | 0 | 45 |  | 9171 | 0 | 783 |  | 9171 | 0 | 123 |  | 9171 | 0 | 972
| 11 |  | 8632 | [6, 15, 16, 17] |  | 7590 | 13.73 | 3600 |  | 8632 | 0 | 254 |  | 8632 | 0 | 38 |  | 8632 | 0 | 820 |  | 8632 | 0 | 222 |  | 8632 | 0 | 870
kroD100 | 7 |  | 9626 | [6, 15, 16, 17] |  | 8724 | 10.34 | 3600 |  | 9626 | 0 | 59 |  | 9626 | 0 | 17 |  | 9626 | 0 | 20 |  | 9626 | 0 | 34 |  | 9626 | 0 | 23
| 9 |  | 8885 | [6, 15, 16, 17] |  | - | - | 3600 |  | 8885 | 0 | 16 |  | 8885 | 0 | 22 |  | 8885 | 0 | 27 |  | 8885 | 0 | 62 |  | 8885 | 0 | 35
| 11 |  | 8725 | [6, 15, 16, 17] |  | - | - | 3600 |  | 8725 | 0 | 51 |  | 8725 | 0 | 35 |  | 8725 | 0 | 48 |  | 8725 | 0 | 63 |  | 8725 | 0 | 80
kroE100 | 7 |  | 10150 | [6, 15, 16, 17] |  | 9274 | 9.44 | 3600 |  | 10150 | 0 | 520 |  | 10150 | 0 | 81 |  | 10150 | 0 | 42 |  | 10150 | 0 | 76 |  | 10150 | 0 | 32
| 9 |  | 8991 | [6, 15] |  | 8500 | 5.77 | 3600 |  | 8991 | 0 | 336 |  | 8991 | 0 | 31 |  | 8991 | 0 | 55 |  | 8991 | 0 | 28 |  | 8991 | 0 | 88
| 11 |  | 8450 | [6, 15, 16, 17] |  | 7739 | 9.19 | 3600 |  | 8450 | 0 | 237 |  | 8450 | 0 | 23 |  | 8450 | 0 | 261 |  | 8450 | 0 | 33 |  | 8450 | 0 | 193
rd100 | 7 |  | 3461 | [6, 15, 16, 17] |  | 3094 | 11.88 | 3600 |  | 3461 | 0 | 119 |  | 3461 | 0 | 20 |  | 3461 | 0 | 20 |  | 3461 | 0 | 24 |  | 3461 | 0 | 22
| 9 |  | 3194 | [6, 15, 16, 17] |  | 2664 | 19.90 | 3600 |  | 3194 | 0 | 63 |  | 3194 | 0 | 18 |  | 3194 | 0 | 18 |  | 3194 | 0 | 24 |  | 3194 | 0 | 25
| 11 |  | 2922 | [6, 15, 16, 17] |  | 2648 | 10.33 | 3600 |  | 2922 | 0 | 28 |  | 2922 | 0 | 21 |  | 2922 | 0 | 20 |  | 2922 | 0 | 34 |  | 2922 | 0 | 27
Avg |  |  |  |  |  | 7673.50 | 9.27 | 2867.39 |  | 8310.08 | 0.28 | 396.75 |  | 8325.67 | 0.00 | 23.28 |  | 8318.42 | 0.08 | 229.19 |  | 8325.67 | 0.00 | 35.69 |  | 8322.89 | 0.03 | 243.92

Table 3: Results of computacional experiments for the medium-size instances. |  |  | BestUB |  |  $CSP$-$I$ |  |  $CSP$-$I\&F_{vp}$ |  |  $CSP$-$I\&F_{h}$ |  |  $CSP$-$I\&F_{vp}$-$X$ |  |  $CSP$-$I\&F_{h}$-$X$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Instance | NC |  | UB | Reference(s) |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time |  | LB | Gap | Time
kroA150 | 7 |  | 11423 | [6, 15, 16, 17] |  | 10658 | 7.18 | 3600 |  | 11423 | 0 | 174 |  | 11423 | 0 | 137 |  | 11423 | 0 | 147 |  | 11423 | 0 | 90
| 9 |  | 10056 | [6, 15, 16, 17] |  | 10056 | 0 | 147 |  | 10056 | 0 | 84 |  | 10056 | 0 | 85 |  | 10056 | 0 | 92 |  | 10056 | 0 | 122
| 11 |  | 9439 | [6, 15, 16, 17] |  | 9240 | 2.15 | 3600 |  | 9439 | 0 | 95 |  | 9439 | 0 | 67 |  | 9439 | 0 | 243 |  | 9439 | 0 | 91
kroB150 | 7 |  | 11457 | [6, 15, 16, 17] |  | 10663 | 7.45 | 3600 |  | 11457 | 0 | 334 |  | 11457 | 0 | 116 |  | 11457 | 0 | 113 |  | 11457 | 0 | 81
| 9 |  | 10121 | [6, 15, 16, 17] |  | 9951 | 1.71 | 3600 |  | 10121 | 0 | 280 |  | 10121 | 0 | 130 |  | 10121 | 0 | 145 |  | 10121 | 0 | 112
| 11 |  | 9611 | [6, 15, 16, 17] |  | 9611 | 0 | 902 |  | 9611 | 0 | 849 |  | 9611 | 0 | 429 |  | 9611 | 0 | 947 |  | 9611 | 0 | 282
kroA200 | 7 |  | 13285 | [6, 15] |  | 11660 | 13.94 | 3600 |  | 12611 | 5.34 | 3600 |  | 12955 | 2.55 | 3600 |  | 12697 | 4.63 | 3600 |  | 13108 | 1.35 | 3600
| 9 |  | 11708 | [6, 15, 17] |  | 10327 | 13.37 | 3600 |  | 11094 | 5.53 | 3600 |  | 11708 | 0 | 2252 |  | 11537 | 1.48 | 3600 |  | 11708 | 0 | 1008
| 11 |  | 10748 | [6, 15] |  | 9508 | 13.04 | 3600 |  | 10342 | 3.93 | 3600 |  | 10748 | 0 | 1044 |  | 10748 | 0 | 3582 |  | 10748 | 0 | 648
kroB200 | 7 |  | 13051 | [15, 16, 17] |  | 12260 | 6.45 | 3600 |  | 12462 | 4.73 | 3600 |  | 12904 | 1.14 | 3600 |  | 12697 | 2.79 | 3600 |  | 13051 | 0 | 1487
| 9 |  | 11864 | [15, 16, 17] |  | 11209 | 5.84 | 3600 |  | 11379 | 4.26 | 3600 |  | 11864 | 0 | 2281 |  | 11695 | 1.45 | 3600 |  | 11864 | 0 | 1242
| 11 |  | 10644 | [15, 16, 17] |  | 10405 | 2.30 | 3600 |  | 10644 | 0 | 800 |  | 10644 | 0 | 907 |  | 10644 | 0 | 514 |  | 10644 | 0 | 938
Avg |  |  |  |  |  | 10462.33 | 6.12 | 3087.42 |  | 10886.58 | 1.98 | 1718.00 |  | 11077.50 | 0.31 | 1220.67 |  | 11010.50 | 0.86 | 1681.92 |  | 11102.42 | 0.11 | 808.42

For small-size instances, there were previously known lower bounds for $32$
out of $36$ instances, obtained by $SRS$, from which optimal solutions were
proven for $9$ instances. The proposed branch-and-cut framework, on the other
hand, obtained lower bounds for all instances. More importantly, the framework
proved optimality for all $36$ small instances. All branch-and-cut
methodologies outperformed $SRS$ with respect to optimality gap, and they were
fairly robust among themselves; the worst performing ($CSP$-$I$) obtained an
average $0.28\%$ optimality gap, while the best performing ($CSP$-$I\&F_{vp}$
and $CSP$-$I\&F_{vp}$-$X$) with zero optimality gap, shows the exact
separation prevails over the heuristic separation of fractional solutions for
small instances.

With respect to medium-size instances, no lower bound was known for any of the
$12$ instances in the literature. The branch-and-cut framework obtained the
first lower bounds for all these instances. Furthermore, optimality was proven
for all instances except one ($kroA200$-$7$), which remains with an optimality
gap of $1.35\%$. The performance among the branch-and-cut methodologies varied
more significantly this time. The best-performing methodology was
$CSP$-$I\&F_{h}$-$X$, with an average gap of $0.11\%$. Now, the heuristic
separation overcomes the exact separation, mainly due to the reduction in the
computational effort. The worst-performing methodology ($CSP$-$I$) obtained an
average gap of $6.12\%$, showing that by using only integral cuts performs
poorly for more challenging instances.

The effect of the CI inequalities (10) in the performance of the methodologies
was also examined. Comparing $CSP$-$I\&F_{vp}$ and $CSP$-$I\&F_{vp}$-$X$,
their average gaps were both zero for small instances and reduced from
$1.98\%$ to $0.86\%$ for medium instances. Moreover, comparing
$CSP$-$I\&F_{h}$ and $CSP$-$I\&F_{h}$-$X$, their average gaps reduced from
$0.08\%$ to $0.03\%$ for small instances and reduced from $0.31\%$ to $0.11\%$
for medium instances. Therefore, the CI inequalities are confirmed to have a
significant impact on reducing the optimality gaps.

Previously, from $48$ small and medium-size CSP instances, only $9$ optimal
solutions were known. These computational results have shown that the branch-
and-cut framework, by borrowing meaningful valid inequalities from GTSP and
proposing new valid inequalities for CSP, was able to obtain optimal solutions
for all instances except one, thus $38$ instances were proven optimal for the
first time.

##  6 Final Remarks

The proposed branch-and-cut framework for the CSP uses existing valid
inequalities for the GTSP, by Fischetti et al. [7], and a new family of valid
inequalities, CI inequalities, to improve on the state-of-the-art exact
methodology for the CSP. Exact and heuristic separation routines for integer
and fractional solutions are investigated.

The branch-and-cut framework is composed of five methodologies using distinct
families of inequalities and separation routines. Computational experiments
conducted on a benchmark of $48$ instances from literature delves into the
effectiveness of the framework. The overall results show unequivocally the
branch-and-cut methodologies outperforming the best known exact methodology
from literature and unveiling $38$ new optimal solutions. The experiments also
show that the CI inequalities had a major role in the performance of the
methodologies.

The ideas presented in this work can support the exact solution of many
possible developments of the CSP. Future works may consider, for example, CSP
with multiple vehicles, capacity constraints, time constraints, green
vehicles, uncertainty on the covering neighborhood, and other generalizations
of the CSP which better approximate practical routing problems. The new family
of valid inequalities proposed in this work should be considered on the exact
solution for any of these generalizations.

## Acknowledgments

This work was supported by CAPES, CNPq, and Fapesp (grants 140960/2017-1,
314384/2018-9, 435520/2018-0, 2015/11937-9).

## References

  * [1] John R Current and David A Schilling.  The covering salesman problem.  Transportation science, 23(3):208–213, 1989.
  * [2] David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook.  The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics).  Princeton University Press, Princeton, NJ, USA, 2007.
  * [3] John Current, Hasan Pirkul, and Erik Rolland.  Efficient algorithms for solving the shortest covering path problem.  Transportation Science, 28(4):317–327, 1994.
  * [4] John R Current and David A Schilling.  The median tour and maximal covering tour problems: Formulations and heuristics.  European Journal of Operational Research, 73(1):114–126, 1994.
  * [5] Michel Gendreau, Gilbert Laporte, and Frédéric Semet.  The covering tour problem.  Operations Research, 45(4):568–576, 1997.
  * [6] Bruce Golden, Zahra Naji-Azimi, S Raghavan, Majid Salari, and Paolo Toth.  The generalized covering salesman problem.  INFORMS Journal on Computing, 24(4):534–553, 2012.
  * [7] Matteo Fischetti, Juan José Salazar González, and Paolo Toth.  A branch-and-cut algorithm for the symmetric generalized traveling salesman problem.  Operations Research, 45(3):378–394, 1997.
  * [8] Huili Zhang and Yinfeng Xu.  Online covering salesman problem.  Journal of Combinatorial Optimization, pages 1–14, 2018.
  * [9] Adrian Dumitrescu and Joseph SB Mitchell.  Approximation algorithms for tsp with neighborhoods in the plane.  Journal of Algorithms, 48(1):135–159, 2003.
  * [10] Damon J Gulczynski, Jeffrey W Heath, and Carter C Price.  The close enough traveling salesman problem: A discussion of several heuristics.  In Perspectives in Operations Research, pages 271–283. Springer, 2006.
  * [11] Jing Dong, Ning Yang, and Ming Chen.  Heuristic approaches for a tsp variant: The automatic meter reading shortest tour problem.  In Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, pages 145–163. Springer, 2007.
  * [12] Robert Shuttleworth, Bruce L Golden, Susan Smith, and Edward Wasil.  Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network.  In The Vehicle Routing Problem: Latest Advances and New Challenges, pages 487–501. Springer, 2008.
  * [13] Behnam Behdani and J Cole Smith.  An integer-programming-based approach to the close-enough traveling salesman problem.  INFORMS Journal on Computing, 26(3):415–432, 2014.
  * [14] Walton Pereira Coutinho, Roberto Quirino do Nascimento, Artur Alves Pessoa, and Anand Subramanian.  A branch-and-bound algorithm for the close-enough traveling salesman problem.  INFORMS Journal on Computing, 28(4):752–765, 2016.
  * [15] Majid Salari and Zahra Naji-Azimi.  An integer programming-based local search for the covering salesman problem.  Computers & Operations Research, 39(11):2594–2602, 2012.
  * [16] Majid Salari, Mohammad Reihaneh, and Mohammad S Sabbagh.  Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem.  Computers & Industrial Engineering, 83:244–251, 2015.
  * [17] Pandiri Venkatesh, Gaurav Srivastava, and Alok Singh.  A multi-start iterated local search algorithm with variable degree of perturbation for the covering salesman problem.  In Harmony Search and Nature Inspired Optimization Algorithms, pages 279–292. Springer, 2019.
  * [18] Xiaoning Zang, Li Jiang, Mustapha Ratli, and Bin Ding.  A parallel variable neighborhood search for solving covering salesman problem.  Optimization Letters, pages 1–16, 2020.
  * [19] Venkatesh Pandiri, Alok Singh, and André Rossi.  Two hybrid metaheuristic approaches for the covering salesman problem.  Neural Computing and Applications, pages 1–21, 2020.
  * [20] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin.  Network Flows: Theory, Algorithms, and Applications.  Prentice Hall, 1993.
  * [21] Gerhard Reinelt.  Tsplib—a traveling salesman problem library.  ORSA journal on computing, 3(4):376–384, 1991.