Learning Hard Optimization Problems: A Data Generation Perspective
  Optimization problems are ubiquitous in our societies and are present in
almost every segment of the economy. Most of these optimization problems are
NP-hard and computationally demanding, often requiring approximate solutions
for large-scale instances. Machine learning frameworks that learn to
approximate solutions to such hard optimization problems are a potentially
promising avenue to address these difficulties, particularly when many closely
related problem instances must be solved repeatedly. Supervised learning
frameworks can train a model using the outputs of pre-solved instances.
However, when the outputs are themselves approximations, when the optimization
problem has symmetric solutions, and/or when the solver uses randomization,
solutions to closely related instances may exhibit large differences and the
learning task can become inherently more difficult. This paper demonstrates
this critical challenge, connects the volatility of the training data to the
ability of a model to approximate it, and proposes a method for producing
(exact or approximate) solutions to optimization problems that are more
amenable to supervised learning tasks. The effectiveness of the method is
tested on hard non-linear nonconvex and discrete combinatorial problems.
