# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find the permutation that maximizes a function

Contributed by:
Roman Schmied, University of Basel

ResourceFunction["MaximizeOverPermutations"][ maximizes |

ResourceFunction["MaximizeOverPermutations"] takes a Method option that accepts either "Enumerate" or "MonteCarlo".

The number of permutations of *n* objects scales very quickly with *n*. The default "Enumerate" method should not be used with *n*≳12 in order to prevent memory overflow, as the time and space required for this enumeration both scale with *n*!. A warning is issued, but the user needs to decide whether or not to call for full enumeration of larger permutation spaces.

With the default option setting Method→"Enumerate", the maximum is determined by applying the function *f* to all permutations of the numbers 1… *n*. The result is guaranteed to be optimal.

With the option setting Method→"MonteCarlo", the maximum is determined by a Monte Carlo Metropolis–Hastings stochastic search. There is no guarantee of the result’s optimality. This method makes it possible to search very large permutation spaces efficiently.

With the suboption settings Method→{"MonteCarlo",*options…*}, the Monte Carlo method can be fine-tuned as follows:

The suboption "Iterations"→*m* specifies the number of iterations that the Monte Carlo algorithm performs in the stochastic search. The algorithm's runtime scales linearly with *m*. The default value is "Iterations"→10^{4}.

The suboption "AnnealingParameter"→*β* specifies the annealing parameter of the Metropolis–Hastings acceptance/rejection step. Smaller values of *β* give a wider search; larger values of *β* tend to restrict the search more toward a monotonically increasing strategy. The default value is "AnnealingParameter"→1.

With "AnnealingParameter"→{*β*_{start},*β*_{end}}, the annealing parameter progresses exponentially from *β*_{start} at the simulation’s beginning to *β*_{end} at the end. An increasing annealing parameter is useful to narrow the search progressively during the course of the simulation.

The suboption "StartingPermutation"→*σ* specifies the initial point of the stochastic search in permutation space and must be given as a list *σ*={*s*_{1},*s*_{2},…,*s*_{n}} that is a permutation of the numbers 1…*n*. The default value is "StartingPermutation"→Automatic, which uses the trivial permutation {1,2,…,*n*} as the starting point.

The Monte Carlo Metropolis–Hastings stochastic search relies on the annealing parameter *β*, which can be kept uniform or varied exponentially during the simulation. A proposed random step from a permutation *σ*_{i} to a new permutation *σ*_{i+1} is accepted with probability Max[1,Exp[*β*(*f*[*σ*_{i+1}]-*f*[*σ*_{i}])]]. The annealing parameter *β* must therefore be chosen in relation to the typically occurring differences in the function *f* to be maximized. The value of this parameter is crucial for the efficiency of the simulation and must be determined by experimentation.

Maximize the second value:

In[1]:= |

Out[1]= |

Given a function that takes a permutation of the numbers {1,2,3}, determine the maximum function value:

In[2]:= |

The result shows that there are two permutations, {1,3,2} and {3,1,2}, that both yield the maximal value *f*=9:

In[3]:= |

Out[3]= |

Construct a function that takes a permutation of the numbers {1,2,…,100} and whose global maximum is known:

In[4]:= |

The global maximum of *g* is given by the permutation that is in the same numerical order as the list *x*:

In[5]:= |

Out[5]= |

Find the maximum of *g* by a Monte Carlo search though the space of *m*!≈9×10^{157} possible permutations:

In[6]:= |

Out[6]= |

This result is not quite optimal, but close. It is much larger than the typical values of *g* found by applying random permutations directly:

In[7]:= |

Out[7]= |

Minimizing a function *f* can be achieved by maximizing -*f*:

In[8]:= |

In[9]:= |

Out[9]= |

Find the extremum of the NUG25 standard Quadratic Assignment Problem:

In[10]:= |

Here is the merit function:

In[11]:= |

The absolute maximum of *f* is known:

In[12]:= |

Out[12]= |

Monte Carlo search for the maximum (with no guarantee of maximality):

In[13]:= |

Out[13]= |

Find the extremum of the NUG30 standard Quadratic Assignment Problem:

In[14]:= |

Here is the merit function:

In[15]:= |

The absolute maximum of *f* is known:

In[16]:= |

Out[16]= |

Monte Carlo search for the maximum (with no guarantee of maximality):

In[17]:= |

Out[17]= |

- Wikipedia–Metropolis-Hastings algorithm
- Optimization of Function Taking a Permutation–Mathematica StackExchange

- 1.0.0 – 12 July 2019

This work is licensed under a Creative Commons Attribution 4.0 International License