Details and Options
ResourceFunction["MaximizeOverPermutations"] takes a
Method option that accepts either
"Enumerate" or
"MonteCarlo".
With the default option setting Method→"Enumerate", the maximum is determined by applying the function f to all permutations of the numbers 1… n. This method is only recommended for n≤12, as the time and space required for this enumeration both scale with 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.