---
_id: '46310'
abstract:
- lang: eng
  text: 'Classic automated algorithm selection (AS) for (combinatorial) optimization
    problems heavily relies on so-called instance features, i.e., numerical characteristics
    of the problem at hand ideally extracted with computationally low-demanding routines.
    For the traveling salesperson problem (TSP) a plethora of features have been suggested.
    Most of these features are, if at all, only normalized imprecisely raising the
    issue of feature values being strongly affected by the instance size. Such artifacts
    may have detrimental effects on algorithm selection models. We propose a normalization
    for two feature groups which stood out in multiple AS studies on the TSP: (a)
    features based on a minimum spanning tree (MST) and (b) nearest neighbor relationships
    of the input instance. To this end we theoretically derive minimum and maximum
    values for properties of MSTs and k-nearest neighbor graphs (NNG) of Euclidean
    graphs. We analyze the differences in feature space between normalized versions
    of these features and their unnormalized counterparts. Our empirical investigations
    on various TSP benchmark sets point out that the feature scaling succeeds in eliminating
    the effect of the instance size. A proof-of-concept AS-study shows promising results:
    models trained with normalized features tend to outperform those trained with
    the respective vanilla features.'
author:
- first_name: Jonathan
  full_name: Heins, Jonathan
  last_name: Heins
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Janina
  full_name: Pohl, Janina
  last_name: Pohl
- first_name: Moritz
  full_name: Seiler, Moritz
  id: '105520'
  last_name: Seiler
- first_name: Heike
  full_name: Trautmann, Heike
  id: '100740'
  last_name: Trautmann
  orcid: 0000-0002-9788-8282
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
citation:
  ama: Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. A study on the
    effects of normalized TSP features for automated algorithm selection. <i>Theoretical
    Computer Science</i>. 2023;940:123-145. doi:<a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>
  apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., &#38; Kerschke,
    P. (2023). A study on the effects of normalized TSP features for automated algorithm
    selection. <i>Theoretical Computer Science</i>, <i>940</i>, 123–145. <a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>
  bibtex: '@article{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2023, title={A study
    on the effects of normalized TSP features for automated algorithm selection},
    volume={940}, DOI={<a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>},
    journal={Theoretical Computer Science}, author={Heins, Jonathan and Bossek, Jakob
    and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal},
    year={2023}, pages={123–145} }'
  chicago: 'Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann,
    and Pascal Kerschke. “A Study on the Effects of Normalized TSP Features for Automated
    Algorithm Selection.” <i>Theoretical Computer Science</i> 940 (2023): 123–45.
    <a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>.'
  ieee: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “A
    study on the effects of normalized TSP features for automated algorithm selection,”
    <i>Theoretical Computer Science</i>, vol. 940, pp. 123–145, 2023, doi: <a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>.'
  mla: Heins, Jonathan, et al. “A Study on the Effects of Normalized TSP Features
    for Automated Algorithm Selection.” <i>Theoretical Computer Science</i>, vol.
    940, 2023, pp. 123–45, doi:<a href="https://doi.org/10.1016/j.tcs.2022.10.019">https://doi.org/10.1016/j.tcs.2022.10.019</a>.
  short: J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical
    Computer Science 940 (2023) 123–145.
date_created: 2023-08-04T07:18:38Z
date_updated: 2024-06-10T11:57:21Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.tcs.2022.10.019
intvolume: '       940'
keyword:
- Feature normalization
- Algorithm selection
- Traveling salesperson problem
language:
- iso: eng
page: 123-145
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
status: public
title: A study on the effects of normalized TSP features for automated algorithm selection
type: journal_article
user_id: '15504'
volume: 940
year: '2023'
...