Random-key Optimizers

This mini-course presents problem-independent metaheuristics using the random-key optimizer (RKO) paradigm. SA (simulated annealing), GRASP (greedy randomized adaptive search procedure), VNS (variable neighborhood search), ILS (iterated local search), and PSO (particle swarm optimization) are classic metaheuristics for combinatorial optimization. A random-key optimizer (RKO) uses a vector of random keys to encode a solution to a combinatorial optimization problem. It uses a decoder to evaluate a solution encoded by the vector of random keys.  An RKO is a metaheuristic where points in the unit hypercube are evaluated using a decoder. We describe RKO as comprising a problem-independent component and a problem-dependent decoder. As a proof of concept, the RKO with different metaheuristics is tested on five NP-hard combinatorial optimization problems: traveling salesman problem, tree of hubs location problem, Steiner triple covering problem, node capacitated graph partitioning problem, and job sequencing and tool switching problem.