Название: Matheuristics: Algorithms and Implementations
Автор: Vittorio Maniezzo, Marco Antonio Boschetti
Издательство: Springer
Год: 2021
Страниц: 222
Язык: английский
Формат: pdf (true), epub
Размер: 14.9 MB

Includes over 40 algorithms with associated codes and step-by-step trace of sample runs.

This book is the first comprehensive tutorial on matheuristics. Matheuristics are based on mathematical extensions of previously known heuristics, mainly metaheuristics, and on original, area-specific approaches. This tutorial provides a detailed discussion of both contributions, presenting the pseudocodes of over 40 algorithms, abundant literature references, and for each case a step-by-step description of a sample run on a common Generalized Assignment Problem example. C++ source codes of all algorithms are available in an associated SW repository.

All these methods are proposed as pseudocodes suitable for any combinatorial optimization problem and are then detailed specifically for the GAP. The pseudocode for the GAP has actually been implemented in C++ and run on the common simple GAP instance, so that significant events appearing in the run traces can be commented in the text, and the runs can be replicated. A possibly arguable choice we made when reporting the run traces is to keep the relevant variables indexed as in the C++ code, thus as in the results it provides. This means that arrays and matrices are indexed from 1 throughout the text when in the context of formulations, in coherence with most optimization literature, but are indexed from 0 in the trace logs and in their comments.

The code is available at the Github as plain C++ and is provided with an optional Visual Studio project, in the future hopefully along with encompassing projects for other IDEs. The code can be directly applied to any GAP instance encoded according to the JSON format specified in the first section of the book.

Every software solution can inherently be expanded and updated, and this is all the more true for the accompanying code of this text, which is based on the code written only for teaching purposes by one of the authors, and as such it has been mainly validated only on simple instances. The code is purposefully kept at minimum complexity. We are quite aware that much more efficient implementations are possible by the inclusion of further elements. We leave the effort of optimizing performance to the interested students and provide our codebase only as a skeleton, a basement upon which possibly building even marketable commodities, besides further research achievements.