Neural Improvement Heuristics for Preference Ranking
In recent years, Deep Learning based methods have been a revolution in the
field of combinatorial optimization. They learn to approximate solutions and
constitute an interesting choice when dealing with repetitive problems drawn
from similar distributions. Most effort has been devoted to investigating
neural constructive methods, while the works that propose neural models to
iteratively improve a candidate solution are less frequent. In this paper, we
present a Neural Improvement (NI) model for graph-based combinatorial problems
that, given an instance and a candidate solution, encodes the problem
information by means of edge features. Our model proposes a modification on the
pairwise precedence of items to increase the quality of the solution. We
demonstrate the practicality of the model by applying it as the building block
of a Neural Hill Climber and other trajectory-based methods. The algorithms are
used to solve the Preference Ranking Problem and results show that they
outperform conventional alternatives in simulated and real-world data.
Conducted experiments also reveal that the proposed model can be a milestone in
the development of efficiently guided trajectory-based optimization algorithms.