Construct, Merge, Solve & Adapt: A Hybrid Metaheuristic for Combinatorial Optimization

✍ Scribed by Christian Blum

• Publisher: Springer
• Year: 2024
• Tongue: English
• Leaves: 202
• Series: Computational Inteligence Methods and Applications
• Category: Library

✦ Synopsis

This book describes a general hybrid metaheuristic for combinatorial optimization labeled Construct, Merge, Solve & Adapt (CMSA). The general idea of standard CMSA is the following one. At each iteration, a number of valid solutions to the tackled problem instance are generated in a probabilistic way. Hereby, each of these solutions is composed of a set of solution components. The components found in the generated solutions are then added to an initially empty sub-instance. Next, an exact solver is applied in order to compute the best solution of the sub-instance, which is then used to update the sub-instance provided as input for the next iteration. In this way, the power of exact solvers can be exploited for solving problem instances much too large for a standalone application of the solver.

✦ Table of Contents

Preface
Acknowledgments
Contents
Acronyms
1 Introduction to CMSA
1.1 Introduction to Optimization
1.1.1 Examples of Continuous Optimization Problems
1.1.2 Examples of Combinatorial Optimization Problems
1.1.3 Modelling an Optimization Problem
1.1.4 Basic Optimization Techniques
1.1.5 Hybrid Optimization Techniques
1.2 Tools Used in This Book
1.2.1 irace: A Tool for Parameter Tuning
1.2.2 STNWeb: A Tool for the Graphical Comparison of Algorithms
1.2.3 scmamp: A Tool for the Statistical Comparison of Algorithms
1.3 CMSA: Construct, Merge, Solve & Adapt
1.3.1 Standard CMSA
1.4 Application to Minimum Dominating Set
1.4.1 An Intuitive Way of Defining the Solution Components
1.4.1.1 Constructing Solutions to the MDS Problem
1.4.1.2 Solving Sub-instances of the MDS Problem
1.4.2 A Generic Way of Defining the Solution Components
1.4.2.1 Solution Construction
1.4.2.2 Sub-instance Solving
1.4.3 Experimental Evaluation
1.4.3.1 MDS Benchmark Sets
1.4.3.2 Parameter Tuning
1.4.3.3 Results
1.5 Algorithmic Proposals Related to CMSA
References
2 Self-adaptive CMSA
2.1 Introduction
2.2 Self-adaptive CMSA: General Description
2.3 Application to the MPIDS Problem
2.3.1 Generic Definition of the Solution Components
2.3.2 Constructing Solutions to the MPIDS Problem
2.3.3 Sub-instance Solving
2.3.4 Experimental Evaluation
2.3.4.1 MPIDS Benchmark Sets
2.3.4.2 Parameter Tuning
2.3.4.3 First Results
2.3.4.4 Results with a Specialized Parameter Tuning
2.4 Application to the FFMS Problem
2.4.1 Augmented Objective Function
2.4.2 Intuitive Definition of the Solution Components
2.4.3 Constructing Solutions to the FFMS Problem
2.4.4 Sub-instance Solving
2.4.5 Experimental Evaluation
2.4.5.1 FFMS Benchmark Set
2.4.5.2 Parameter Tuning
2.4.5.3 Results
2.5 Conclusions
References
3 Adding Learning to CMSA
3.1 Introduction
3.2 The Bacterial Algorithm
3.3 The Learn_Cmsa Algorithm: A General Description
3.4 Application to the MDS Problem
3.4.1 Generating the Initial Population
3.4.2 Implementation of Conjugation
3.4.3 Implementation of Regeneration
3.4.4 Experimental Evaluation
3.4.4.1 Benchmark Instances
3.4.4.2 Algorithm Tuning
3.4.4.3 Results
3.5 Application to the FFMS Problem
3.5.1 Generating the Initial Population
3.5.2 Implementation of Conjugation
3.5.3 Implementation of Regeneration
3.5.4 Experimental Evaluation
3.5.4.1 Benchmark Instances
3.5.4.2 Parameter Tuning
3.5.4.3 Results
3.6 Conclusions and Possible Research Directions
References
4 Replacing Hard Mathematical Models with Set Covering Formulations
4.1 Introduction
4.2 Application to Variable-Sized Bin Packing
4.2.1 Short Literature Review Concerning the VSBP Problem
4.2.2 Set-Covering Based ILP Model of the VSBP Problem
4.2.3 Application of Standard CMSA to the VBSP Problem
4.2.3.1 Probabilistic Construction of VSBP Solutions
4.2.3.2 Sub-instance Generation and Solving
4.2.4 Application of Set-Covering Based CMSA to the VSBP Problem
4.2.5 Experimental Evaluation
4.2.5.1 VSBP Problem Instances
4.2.5.2 Parameter Tuning
4.2.5.3 Numerical Results
4.2.5.4 Performance Difference Between the Two VSBP ILP Models
4.2.5.5 STNWeb Graphics Concerning the VSBP Results
4.3 Application to an Electric Vehicle Routing Problem
4.3.1 Short Literature Review Concerning the EVRP-TW-SPD
4.3.2 Set-Covering Based ILP Model of the EVRP-TW-SPD
4.3.3 Application of Adapt_Cmsa to the EVRP-TW-SPD
4.3.4 The Adapt_Cmsa Algorithm
4.3.4.1 Constructing Solutions to the EVRP-TW-SPD
4.3.4.2 Sub-instance Solving
4.3.5 The Adapt_Cmsa_SetCov Algorithm
4.3.6 Experimental Evaluation
4.3.6.1 Problem Instances for the EVRP-SPD-TW
4.3.6.2 Parameter Tuning
4.3.6.3 Results
4.3.6.4 Performance Difference Between the Two EVRP-TW-SPD ILP Models
4.3.6.5 STNWeb Graphics Concerning the EVRP-TW-SPD Results
4.4 Conclusions and Future Research Directions
References
5 Application of CMSA in the Presence of Non-binary Variables
5.1 Introduction
5.2 The Bounded Knapsack Problem with Conflicts
5.2.1 Converting the BKPWC ILP to a Binary Program
5.3 Application of CMSA to the BKPWC
5.3.1 Probabilistic Solution Construction
5.3.2 Sub-instance Solving
5.4 Experimental Evaluation
5.4.1 Problem Instances
5.4.2 Parameter Tuning
5.4.3 Results
5.5 Conclusions and Further Research Directions
References
6 Additional Research Lines Concerning CMSA
6.1 A Problem-Agnostic CMSA for Binary Problems
6.1.1 Application of Cmsa_Gen
6.1.1.1 Before the Start of Cmsa_Gen
6.1.1.2 Solution Construction
6.1.1.3 Extension of the Standard Algorithm
6.1.2 Experimental Evaluation
6.1.2.1 Benchmark Instances
6.1.2.2 Results
6.1.3 Discussion
6.2 Applying a Metaheuristic in the CMSA Framework
6.2.1 The Weighted Independent Domination (WID) Problem
6.2.1.1 ILP Model of the WID Problem
6.2.2 A Greedy Heuristic for the WID Problem
6.2.3 A PBIG Metaheuristic for the WID Problem
6.2.4 Using Pbig for Solving Sub-instances in CMSA
6.2.5 Experimental Evaluation
6.2.5.1 Problem Instances
6.2.5.2 Parameter Tuning
6.2.5.3 Results
6.2.6 Discussion
6.3 Relation Between CMSA and LNS
6.3.1 Destruction-Based LNS
6.3.2 Empirical Comparative Study
6.3.2.1 Discussion
6.4 Future Work on CMSA
References
A C++ Program Code: CMSA Applied to the MDS Problem
Index