Design of Heuristic Algorithms for Hard Optimization: With Python Codes for the Travelling Salesman Problem

Preface
	Heuristics and Metaheuristics
	Book Structure
	Source Codes for the Traveling Salesman Problem
	Exercises
	Acknowledgements
Contents
Part I Combinatorial Optimization, Complexity Theory, and Problem Modeling
	1 Elements of Graphs and Complexity Theory
		1.1 Combinatorial Optimization
			1.1.1 Linear Programming
			1.1.2 A Small Glossary on Graphs and Networks
				1.1.2.1 Undirected Graph, Vertex, (Undirected) Edge
				1.1.2.2 Directed Graph, Arcs
				1.1.2.3 Incidence Matrix
				1.1.2.4 Adjacency Matrix
				1.1.2.5 Degree
				1.1.2.6 Path, Simple Path, Elementary Path, and Cycle
				1.1.2.7 Connected Graph
				1.1.2.8 Tree, Subgraph, and Line Graph
				1.1.2.9 Eulerian, Hamiltonian Graph
				1.1.2.10 Complete, Bipartite Graphs, Clique, and Stable Set
				1.1.2.11 Graph Coloring and Matching
				1.1.2.12 Network
				1.1.2.13 Flow
		1.2 Elements of Complexity Theory
			1.2.1 Algorithmic Complexity
			1.2.2 Bachmann-Landau Notation
				1.2.2.1 Definitions
			1.2.3 Basic Complexity Classes
				1.2.3.1 Encoding Scheme, Language, and Turing Machine
				1.2.3.2 Class P of Languages
				1.2.3.3 Class NP of Languages
				1.2.3.4 Class NP-Complete
				1.2.3.5 Strongly NP-Complete Class
			1.2.4 Other Complexity Classes
		Problems
		References
	2 A Short List of Combinatorial Optimization Problems
		2.1 Optimal Trees
			2.1.1 Minimum Spanning Tree
			2.1.2 Steiner Tree
		2.2 Optimal Paths
			2.2.1 Shortest Path
				2.2.1.1 Linear Programming Formulation of the Shortest Path
			2.2.2 Elementary Shortest Path: Traveling Salesman
				2.2.2.1 Integer Linear Programs for the TSP
			2.2.3 Vehicle Routing
		2.3 Scheduling
			2.3.1 Permutation Flowshop Scheduling
			2.3.2 Jobshop Scheduling
		2.4 Flows in Networks
		2.5 Assignment Problems
			2.5.1 Linear Assignment
			2.5.2 Generalized Assignment
			2.5.3 Knapsack
			2.5.4 Quadratic Assignment
		2.6 Stable Set
		2.7 Clustering
			2.7.1 k-Medoids or p-Median
			2.7.2 k-Means
		2.8 Graph Coloring
			2.8.1 Edge Coloring of a Bipartite Graph
		Problems
		References
	3 Problem Modeling
		3.1 Objective Function and Fitness Function
			3.1.1 Lagrangian Relaxation
				3.1.1.1 Lagrangian Relaxation for the Vertex Coloring Problem
				3.1.1.2 Lagrangian Relaxation for the TSP
			3.1.2 Hierarchical Objectives
		3.2 Multi-Objective Optimization
			3.2.1 Scalarizing
			3.2.2 Sub-goals to Reach
		3.3 Practical Applications Modeled as Classical Problems
			3.3.1 Traveling Salesman Problem Applications
				3.3.1.1 Minimizing Unproductive Moves in 3D Printing
				3.3.1.2 Scheduling Coloring Workshop
			3.3.2 Linear Assignment Modeled by Minimum Cost Flow
			3.3.3 Map Labeling Modeled by Stable Set
		Problems
Part II Basic Heuristic Techniques
	4 Constructive Methods
		4.1 Systematic Enumeration
			4.1.1 Branch and Bound
				4.1.1.1 Example of Implementation of a Branch and Bound
		4.2 Random Construction
		4.3 Greedy Construction
			4.3.1 Greedy Heuristics for the TSP
				4.3.1.1 Greedy on the Edges
				4.3.1.2 Nearest Neighbor
				4.3.1.3 Largest Regret
				4.3.1.4 Cheapest Insertion
				4.3.1.5 Farthest Insertion
			4.3.2 Greedy Heuristic for Graph Coloring
		4.4 Improvement of Greedy Procedures
			4.4.1 Beam Search
			4.4.2 Pilot Method
		Problems
		References
	5 Local Search
		5.1 Local Search Framework
			5.1.1 First Improvement Heuristic
			5.1.2 Best Improvement Heuristic
			5.1.3 Local Optima
				5.1.3.1 TSP 3-Opt
				5.1.3.2 TSP Or-Opt
				5.1.3.3 Data Structure for TSP 2-Opt
			5.1.4 Neighborhood Properties
				5.1.4.1 Connectivity
				5.1.4.2 Low Diameter
				5.1.4.3 Low Ruggedness
				5.1.4.4 Small Size
				5.1.4.5 Fast Evaluation
		5.2 Neighborhood Limitation
			5.2.1 Candidate List
				5.2.1.1 Candidate List for the Euclidean TSP
				5.2.1.2 TSP Neighborhood Limitation with 1-Trees
			5.2.2 Granular Search
		5.3 Neighborhood Extension
			5.3.1 Filter and Fan
			5.3.2 Ejection Chain
				5.3.2.1 Lin-Kernighan Neighborhood
		5.4 Using Several Neighborhoods or Models
		5.5 Multi-Objective Local Search
			5.5.1 Scalarizing
			5.5.2 Pareto Local Search
			5.5.3 Data Structures for Multi-Objective Optimization
				5.5.3.1 Array
				5.5.3.2 KD-Tree
		Problems
		References
	6 Decomposition Methods
		6.1 Consideration on the Problem Size
		6.2 Recursive Algorithms
			6.2.1 Master Theorem for Divide-and-Conquer
		6.3 Low Complexity Constructive Methods
			6.3.1 Proximity Graph Construction
			6.3.2 Linearithmic Heuristic for the TSP
		6.4 Local Search for Large Instances
			6.4.1 Large Neighborhood Search
			6.4.2 POPMUSIC
				6.4.2.1 POPMUSIC for the TSP
			6.4.3 Comments
		Problems
		References
Part III Popular Metaheuristics
	7 Randomized Methods
		7.1 Simulated Annealing
		7.2 Threshold Accepting
		7.3 Great Deluge Algorithm
		7.4 Demon Algorithm
		7.5 Noising Methods
		7.6 Late Acceptance Hill Climbing
		7.7 Variable Neighborhood Search
		7.8 GRASP
		Problems
		References
	8 Construction Learning
		8.1 Artificial Ants
			8.1.1 Real Ant Behavior
			8.1.2 Transcription of Ant Behavior to Optimization
			8.1.3 MAX-MIN Ant System
			8.1.4 Fast Ant System
		8.2 Vocabulary Building
		Problems
		References
	9 Local Search Learning
		9.1 Taboo Search
			9.1.1 Hash Table Memory
				9.1.1.1 Hash Functions
			9.1.2 Taboo Moves
				9.1.2.1 Implementation of Taboo Status
				9.1.2.2 Taboo Duration
				9.1.2.3 Aspiration Criterion
		9.2 Strategic Oscillations
			9.2.1 Long-Term Memory
				9.2.1.1 Forced Moves
				9.2.1.2 Penalized Moves
				9.2.1.3 Restarts
		Problems
		References
	10 Population Management
		10.1 Evolutionary Algorithms Framework
		10.2 Genetic Algorithms
			10.2.1 Selection for Reproduction
				10.2.1.1 Rank-Based Selection
				10.2.1.2 Proportional Selection
				10.2.1.3 Natural Selection
				10.2.1.4 Complete Selection
			10.2.2 Crossover Operator
				10.2.2.1 Uniform Crossover
				10.2.2.2 Single-Point Crossover
				10.2.2.3 Two-Point Crossover
				10.2.2.4 OX Crossover
			10.2.3 Mutation Operator
			10.2.4 Selection for Survival
				10.2.4.1 Generational Replacement
				10.2.4.2 Evolutionary Strategy
				10.2.4.3 Stationary Replacement
				10.2.4.4 Elitist Replacement
		10.3 Memetic Algorithms
		10.4 Scatter Search
			10.4.1 Illustration of Scatter Search for the Knapsack Problem
				10.4.1.1 Initial Population
				10.4.1.2 Creation of the Reference Set
				10.4.1.3 Combining solutions
		10.5 Bias Random Key Genetic Algorithm
		10.6 Path Relinking
			10.6.1 GRASP with Path Relinking
		10.7 Fixed Set Search
		10.8 Particle Swarm
			10.8.1 Electromagnetic Method
			10.8.2 Bestiary
		Problems
		References
	11 Heuristics Design
		11.1 Problem Modeling
			11.1.1 Model Choice
			11.1.2 Decomposition into a Series of Sub-problems
		11.2 Algorithmic Construction
			11.2.1 Data Slicing
			11.2.2 Local Search Design
		11.3 Heuristics Tuning
			11.3.1 Instance Selection
			11.3.2 Graphical Representation
			11.3.3 Parameter and Option Tuning
			11.3.4 Measure Criterion
				11.3.4.1 Success Rate
				11.3.4.2 Computational Time Measure
				11.3.4.3 Solution Quality Measure
		Problems
		References
	12 Codes
		12.1 Random Numbers
		12.2 TSP Utilities
		12.3 TSP Lin and Kernighan Improvement Procedure
		12.4 KD-Tree Insertion and Inspection
		12.5 KD-Tree Delete
		12.6 KD-Tree Update Pareto Set
		12.7 TSP 2-Opt and 3-Opt Test Program
		12.8 Multi-objective TSP Test Program
		12.9 Fast Ant TSP Test Program
		12.10 Taboo Search TSP Test Program
		12.11 Memetic TSP Test Program
		12.12 GRASP with Path Relinking TSP Test Program
		References
Solutions to the Exercises
	Problems of Chap. 1
	Problems of Chap. 2
	Problems of Chap. 3
	Problems of Chap. 4
	Problems of Chap. 5
	Problems of Chap. 6
	Problems of Chap. 7
	Problems of Chap. 8
	Problems of Chap. 9
	Problems of Chap. 10
	Problems of Chap. 11
	Reference
Index