Introduction to CMSA

Construct, Merge, Solve & Adapt (CMSA) is an award-winning, hybrid algorithm for solving hard combinatorial optimization problems. The main idea consists in the iterated application of an exact approach—such as, for example, an integer linear programming (ILP) solver—to sub-instances of the original problem instances to be solved. These sub-instances are extended at each iteration by adding solution components from a set of valid solutions that are obtained either by probabilistic solution construction or by any other means. In this first chapter, we will give an introduction to CMSA including related work and the application of basic CMSA variants to a well-known combinatorial optimization problem known as the Minimum Dominating Set (MDS) problem in undirected graphs. In addition, we will describe all the tools that are used for the experimental evaluation of the algorithms presented in this book. This includes the parameter tuning software called irace, an R-based tool for the statistical comparison of multiple algorithms called scmamp, and a web-based tool for the graphical comparison of multiple algorithms called STNWeb.