AGILE OPTIMIZATION: COMBINING BIASED-RANDOMIZED HEURISTICS WITH PARALLEL COMPUTING

Agile Optimization refers to the concept of using fast optimization algorithms that might be used to generate ‘high-quality’ solutions in real time (e.g., in the order of milliseconds) to large-scale and complex (NP-hard) optimization problems that might repeatedly appear every few seconds or minutes as the environmental conditions change and new data is available. In our case, these algorithms are based on the hybridization of biased-randomized heuristics and parallel computing. By using skewed probability distributions, biased randomization techniques introduce aspecial (non-uniform) randomization effect into a heuristic procedure. As a result, a deterministic heuristic – which is extremely fast in execution – is extended into a probabilistic algorithm without losing the logic behind the original heuristic. Thousands of these probabilistic algorithms can be run in parallel by using an affordable computing device (e.g., a GPU), thus requiring the same wall-clock time as the original heuristic (typically in the order of milliseconds), but with the benefit that many alternative solutions – some of them outperforming in quality the one provided by the original heuristic – can be considered by the decision maker. Examples of applications of this agile optimization concept can be found in smart cities (e.g., routing drones and other autonomous vehicles), telecommunication systems, production systems, financial markets, etc.