TY - CHAP
T1 - Structure-preserving instance generation
AU - Malitsky, Yuri
AU - Merschformann, Marius
AU - O’Sullivan, Barry
AU - Tierney, Kevin
N1 - Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - Real-world instances are critical for the development of stateof- the-art algorithms, algorithm configuration techniques, and selection approaches. However, very few true industrial instances exist for most problems, which poses a problem both to algorithm designers and methods for algorithm selection. The lack of enough real data leads to an inability for algorithm designers to show the effectiveness of their techniques, and for algorithm selection it is difficult or even impossible to train a portfolio with so few training examples. This paper introduces a novel instance generator that creates instances that have the same structural properties as industrial instances. We generate instances through a large neighborhood search-like method that combines components of instances together to form new ones. We test our approach on the MaxSAT and SAT problems, and then demonstrate that portfolios trained on these generated instances perform just as well or even better than those trained on the real instances.
AB - Real-world instances are critical for the development of stateof- the-art algorithms, algorithm configuration techniques, and selection approaches. However, very few true industrial instances exist for most problems, which poses a problem both to algorithm designers and methods for algorithm selection. The lack of enough real data leads to an inability for algorithm designers to show the effectiveness of their techniques, and for algorithm selection it is difficult or even impossible to train a portfolio with so few training examples. This paper introduces a novel instance generator that creates instances that have the same structural properties as industrial instances. We generate instances through a large neighborhood search-like method that combines components of instances together to form new ones. We test our approach on the MaxSAT and SAT problems, and then demonstrate that portfolios trained on these generated instances perform just as well or even better than those trained on the real instances.
UR - https://www.scopus.com/pages/publications/85006934327
U2 - 10.1007/978-3-319-50349-3_9
DO - 10.1007/978-3-319-50349-3_9
M3 - Chapter
AN - SCOPUS:85006934327
SN - 9783319503486
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 123
EP - 140
BT - Learning and Intelligent Optimization - 10th International Conference, LION 10, Revised Selected Papers
A2 - Festa, Paola
A2 - Sellmann, Meinolf
A2 - Vanschoren, Joaquin
PB - Springer Verlag
T2 - 10th International Conference on Learning and Intelligent Optimization, LION 10
Y2 - 29 May 2016 through 1 June 2016
ER -