TunnelOpt

New optimization algorithms developed over the last two decades can efficiently solve a wide-range of combinatorial optimization problems. Nevertheless, existing combinatorial optimization techniques still struggle to efficiently handle the unprecedented complexity of the problems encountered in modern engineering, scientific, and numerical applications. Often these problems are multi-objective; hence implying other degrees of difficulty. Achieving scalability is a major concern, specifically with respect to the number of variables and the number of objectives; but also with respect to modern parallel and distributed resources, including massively parallel multi-core and multi-GPU based resources. We here focus on the design and the fundamental understanding of innovative stochastic heuristic search algorithms empowered by graybox optimization methods. In fact, new graybox formulations allow us to compute the eigenvectors of the search neighborhood for local search methods that apply to a range of fondamental combinatorial problems such as logical satisfiability (e.g. MAXkSAT) and routing (e.g. the Travelling Salesman Problem). Furthermore, it becomes possible to tunnel between local optima in linear time. By describing how local optima (Pareto or not) are organized into regular hypercube subspaces that form non-planar lattices; we propose to set up the foundations of a tunneling engine to navigate in parallel over multiple lattices in an efficient and effective manner. Such a tunneling engine is by-product of fundamental investigations from fitness landscape analysis, local search hybridized with graybox genetic operators, general-purpose adaptive stochastic search heuristics, multi-objective evolutionary optimization, as well as, parallel and distributed optimization models. The ultimate goal of this work is to lead to a flexible, yet powerful and scalable framework for attacking complex graybox combinatorial optimization problems.