Transformer-based feature learning for algorithm selection in combinatorial optimisation

Alessio Pellegrino; Özgür Akgün; Nguyen Dang; Zeynep Kiziltan; Ian Miguel

doi:10.4230/LIPIcs.CP.2025.31

Transformer-based feature learning for algorithm selection in combinatorial optimisation

Alessio Pellegrino^*, Özgür Akgün^*, Nguyen Dang^*, Zeynep Kiziltan^*, Ian Miguel^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a combinatorial optimisation problem, there are typically multiple ways of modelling it for presentation to an automated solver. Choosing the right combination of model and target solver can have a significant impact on the effectiveness of the solving process. The best combination of model and solver can also be instance-dependent: there may not exist a single combination that works best for all instances of the same problem. We consider the task of building machine learning models to automatically select the best combination for a problem instance. Critical to the learning process is to define instance features, which serve as input to the selection model. Our contribution is the automatic learning of instance features directly from the high-level representation of a problem instance using a transformer encoder. We evaluate the performance of our approach using the Essence modelling language via a case study of three problem classes.

Original language	English
Title of host publication	31st international conference on principles and practice of constraint programming, CP 2025
Editors	Maria Garcia de la Banda
Place of Publication	Saarbrücken/Wadern
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	1-22
Number of pages	22
ISBN (Electronic)	9783959773805
DOIs	https://doi.org/10.4230/LIPIcs.CP.2025.31
Publication status	Published - 8 Aug 2025
Event	31st International Conference on Principles and Practice of Constraint Programming, CP 2025 - Glasgow, United Kingdom Duration: 10 Aug 2025 → 15 Aug 2025 Conference number: 31 https://cp2025.a4cp.org/

Publication series

Name	Leibniz international proceedings in informatics, LIPIcs
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume	340
ISSN (Print)	1868-8969

Conference

Conference	31st International Conference on Principles and Practice of Constraint Programming, CP 2025
Abbreviated title	CP 2025
Country/Territory	United Kingdom
City	Glasgow
Period	10/08/25 → 15/08/25
Internet address	https://cp2025.a4cp.org/

Keywords

Algorithm selection
Constraint modelling
Feature extraction
Machine learning
Transformer architecture

Access to Document

10.4230/LIPIcs.CP.2025.31Licence: CC BY

Pellegrino-et-al-Transformer-based-feature-learning-LIPIcs-CP-2025-31-CCBY
Copyright: © Alessio Pellegrino, Özgür Akgün, Nguyen Dang, Zeynep Kiziltan, and Ian Miguel; licensed under Creative Commons License CC-BY 4.0.
Final published version, 1.29 MBLicence: CC BY

Keep Learning: Keep Learning
Miguel, I. (PI)
EPSRC
1/07/21 → 31/12/24
Project: Standard

Cite this

Pellegrino, A., Akgün, Ö., Dang, N., Kiziltan, Z., & Miguel, I. (2025). Transformer-based feature learning for algorithm selection in combinatorial optimisation. In M. G. de la Banda (Ed.), 31st international conference on principles and practice of constraint programming, CP 2025 (pp. 1-22). Article 31 (Leibniz international proceedings in informatics, LIPIcs; Vol. 340). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CP.2025.31

Pellegrino, Alessio ; Akgün, Özgür ; Dang, Nguyen et al. / Transformer-based feature learning for algorithm selection in combinatorial optimisation. 31st international conference on principles and practice of constraint programming, CP 2025. editor / Maria Garcia de la Banda. Saarbrücken/Wadern : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. pp. 1-22 (Leibniz international proceedings in informatics, LIPIcs).

@inproceedings{0b66b4c44d5945b9af5a91b839475873,

title = "Transformer-based feature learning for algorithm selection in combinatorial optimisation",

abstract = "Given a combinatorial optimisation problem, there are typically multiple ways of modelling it for presentation to an automated solver. Choosing the right combination of model and target solver can have a significant impact on the effectiveness of the solving process. The best combination of model and solver can also be instance-dependent: there may not exist a single combination that works best for all instances of the same problem. We consider the task of building machine learning models to automatically select the best combination for a problem instance. Critical to the learning process is to define instance features, which serve as input to the selection model. Our contribution is the automatic learning of instance features directly from the high-level representation of a problem instance using a transformer encoder. We evaluate the performance of our approach using the Essence modelling language via a case study of three problem classes.",

keywords = "Algorithm selection, Constraint modelling, Feature extraction, Machine learning, Transformer architecture",

author = "Alessio Pellegrino and {\"O}zg{\"u}r Akg{\"u}n and Nguyen Dang and Zeynep Kiziltan and Ian Miguel",

note = "Funding: This work was supported by the European Union's Justice programme, under GA No 101087342, POLINE (Principles Of Law In National and European VAT), by a scholarship from the Department of Computer Science and Engineering of the University of Bologna, and by UK EPSRC grant EP/V027182/1.; 31st International Conference on Principles and Practice of Constraint Programming, CP 2025, CP 2025 ; Conference date: 10-08-2025 Through 15-08-2025",

year = "2025",

month = aug,

day = "8",

doi = "10.4230/LIPIcs.CP.2025.31",

language = "English",

series = "Leibniz international proceedings in informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--22",

editor = "{de la Banda}, {Maria Garcia}",

booktitle = "31st international conference on principles and practice of constraint programming, CP 2025",

url = "https://cp2025.a4cp.org/",

}

Pellegrino, A, Akgün, Ö , Dang, N, Kiziltan, Z & Miguel, I 2025, Transformer-based feature learning for algorithm selection in combinatorial optimisation. in MG de la Banda (ed.), 31st international conference on principles and practice of constraint programming, CP 2025., 31, Leibniz international proceedings in informatics, LIPIcs, vol. 340, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, pp. 1-22, 31st International Conference on Principles and Practice of Constraint Programming, CP 2025, Glasgow, United Kingdom, 10/08/25. https://doi.org/10.4230/LIPIcs.CP.2025.31

Transformer-based feature learning for algorithm selection in combinatorial optimisation. / Pellegrino, Alessio; Akgün, Özgür ; Dang, Nguyen et al.
31st international conference on principles and practice of constraint programming, CP 2025. ed. / Maria Garcia de la Banda. Saarbrücken/Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. p. 1-22 31 (Leibniz international proceedings in informatics, LIPIcs; Vol. 340).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Transformer-based feature learning for algorithm selection in combinatorial optimisation

AU - Pellegrino, Alessio

AU - Akgün, Özgür

AU - Dang, Nguyen

AU - Kiziltan, Zeynep

AU - Miguel, Ian

N1 - Conference code: 31

PY - 2025/8/8

Y1 - 2025/8/8

N2 - Given a combinatorial optimisation problem, there are typically multiple ways of modelling it for presentation to an automated solver. Choosing the right combination of model and target solver can have a significant impact on the effectiveness of the solving process. The best combination of model and solver can also be instance-dependent: there may not exist a single combination that works best for all instances of the same problem. We consider the task of building machine learning models to automatically select the best combination for a problem instance. Critical to the learning process is to define instance features, which serve as input to the selection model. Our contribution is the automatic learning of instance features directly from the high-level representation of a problem instance using a transformer encoder. We evaluate the performance of our approach using the Essence modelling language via a case study of three problem classes.

AB - Given a combinatorial optimisation problem, there are typically multiple ways of modelling it for presentation to an automated solver. Choosing the right combination of model and target solver can have a significant impact on the effectiveness of the solving process. The best combination of model and solver can also be instance-dependent: there may not exist a single combination that works best for all instances of the same problem. We consider the task of building machine learning models to automatically select the best combination for a problem instance. Critical to the learning process is to define instance features, which serve as input to the selection model. Our contribution is the automatic learning of instance features directly from the high-level representation of a problem instance using a transformer encoder. We evaluate the performance of our approach using the Essence modelling language via a case study of three problem classes.

KW - Algorithm selection

KW - Constraint modelling

KW - Feature extraction

KW - Machine learning

KW - Transformer architecture

U2 - 10.4230/LIPIcs.CP.2025.31

DO - 10.4230/LIPIcs.CP.2025.31

M3 - Conference contribution

AN - SCOPUS:105013083870

T3 - Leibniz international proceedings in informatics, LIPIcs

SP - 1

EP - 22

BT - 31st international conference on principles and practice of constraint programming, CP 2025

A2 - de la Banda, Maria Garcia

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

CY - Saarbrücken/Wadern

T2 - 31st International Conference on Principles and Practice of Constraint Programming, CP 2025

Y2 - 10 August 2025 through 15 August 2025

ER -

Pellegrino A, Akgün Ö , Dang N, Kiziltan Z, Miguel I. Transformer-based feature learning for algorithm selection in combinatorial optimisation. In de la Banda MG, editor, 31st international conference on principles and practice of constraint programming, CP 2025. Saarbrücken/Wadern: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. p. 1-22. 31. (Leibniz international proceedings in informatics, LIPIcs). doi: 10.4230/LIPIcs.CP.2025.31

Transformer-based feature learning for algorithm selection in combinatorial optimisation

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Projects

Keep Learning: Keep Learning

Cite this