  The Linear Ordering Problem (LOP) is a very popular NP-hard combinatorial
optimization problem with many practical applications that may require the use
of large instances. The Linear Ordering Library (LOLIB) gathers a set of
standard benchmarks widely used in the validation of solvers for the LOP. Among
them, the xLOLIB2 collects some of the largest and most challenging instances
in current literature. In this work, we present new best-known solutions for
each of the 200 complex instances that comprises xLOLIB2. Moreover, the
proposal devised in this research is able to achieve all current best-known
solutions in the rest of instances of LOLIB and improve them in other 93 cases
out of 485, meaning that important advances in terms of quality and robustness
are attained. This important advance in the field of the LOP has been possible
thanks to the development of a novel Memetic Algorithm (MA) that was designed
by taking into account some of the weaknesses of state-of-the-art LOP solvers.
One of the keys to success is that the novel proposal allows for a gradual
shift from exploration to exploitation, which is done by taking into account
the stopping criterion and elapsed period of execution to alter the internal
decisions taken by the optimizer. The novel diversity-aware proposal is called
the Memetic Algorithm with Explicit Diversity Management (MA-EDM) and extensive
comparisons against state-of-the-art techniques provide insights into the
reasons for the superiority of MA-EDM.
