Use of machine learning techniques to determine parameter values

Question

It is quite frequent that optimization algorithms have quite some parameters controlling their behavior (cooling schedule of a Simulated Annealing, length of the tabu list for a Tabu Search, population size for a Genetic Algorithm, etc...).

One will typically spend quite some time fine tuning those parameters using a "representative" set of instances. However it can happen that a set of parameters will work very well on one instance but quite poorly on another one (particularly if the set of representative instances is quite heterogeneous).

It would seem interesting, based on some instance characteristics to determine (probably using supervised learning techniques) before solving which parameters values are the most likely to give good results.

I have tried to find some information about this idea in the literature but could not find anything. Do you know of any success/failure stories related to this idea?

On a related note I know about Adaptive Large Neighborhood Search (ALNS), where one tries to figure out during the search which neighborhoods are the most efficient for the instance being currently solved. I am more interested about an approach where the parameters are completely determined before starting the actual solving process.

Answer 1

You are touching three similar but different subjects in your question.

Choosing the set of parameter values for an algorithm and a set of instances is a task known as offline parameter tuning, algorithm configuration, or (as indicated in @EhsanK) hyper-parameter tuning (mostly in machine learning, where the term parameters means something else). There is now a considerable amount of research in the area, for example irace, SMAC, ParamILS, GGA, mrlMBO, Spearmint and many more, both from OR and ML. These are all general-purpose configurators that can be applied to different algorithms. Other specialized tuners exist for specific software, e.g. Opentuner for GCC.

This is different from online tuning, as you note, where one tries to find at runtime the best parameter configuration to solve the instance currently being tackled.

Instance features are usually considered in algorithm selection, where an instance is analyzed to select the best algorithm to solve it. See e.g. this recent survey and this comprehensive literature list. Instance features are often problem-specific.

To the best of my knowledge, the use of features in algorithm configuration has not been studied as much as general-purpose offline algorithm configuration and problem-specific algorithm selection. Some works in this category are Hydra and ISAC, but there is certainly room for more research here.

Answer 2

The problem you are referring to is hyper-parameter optimization and a simple search in google will bring up many blogs (and of course) research that has been done in this area.

You haven't asked this, but since you mentioned a few algorithms (SA, Tabu search, ...), in case you are also interested to select the best algorithm for different data sets, then you are looking at meta learning.

A few other useful links to give you an idea of the research in this area can be:

• Efficient Benchmarking of Hyperparameter Optimizers via Surrogates
• Metalearning and Algorithm Selection: progress, state of the art and introduction to the 2018 Special Issue

Answer 3

There was a similar question on Cross Validated and as in my comment there, I would look into the use of statistical experimental design, specifically factorial designs and fractional factorial designs. There is a very good book on that topic Box, Hunter & Hunter and here is a paper on its use in hyperparameter optimization Design of Experiments for the Tuning of Optimisation Algorithms.

Answer 4

To my understanding, the tuning process you just mentioned is also an learning technique where your training set is your set of representative instances. The problem is with generalization because your training has been too biased or representative set has not been a good training set. In parameter tuning, you may wish to do cross validations similar to ML. Moreover, the combinatorial problems are very unpredictable and one cannot fix a parameter and hope that it works well for all instances. For this reason, one may come up with a set of rules to determine the value of a search parameter (e.g., in root node use primal simplex and in the child nodes use dual simplex when you want to decide on what LP algorithm to use in branch-and-cut) instead having one fix a predetermined value.

You may find these works interesting as well:

• A Simulated Annealing Algorithm within the Variable Neighbourhood Search Framework to Solve the Capacitated Facility Location-Allocation Problem Learning Mechanisms and Local Search Heuristics for the Fixed Charge Capacitated Multicommodity Network Design

• A Learning-Based Matheuristic for Stochastic Multicommodity Network Design