# Need a combinatorial optimizer for black box function

I’m looking for a combinatorial optimizer (decision variables are a permutation of the integers 1, 2, \ldots, N, where N is between, say, 50, and 500, for a black box function (i.e., only the value of the objective function is obtainable, no derivatives.). This is for a short-fuse project, so I would prefer a solution that I can just plug in and use as-is without extensive customization. I am aware of Combo which looks like it is untouched for > 3 years and doesn’t work under Julia 1.x. I’ve also looked at MHLib which might be made to work but has no documentation, so it may require quite a bit of time and effort to understand and set up properly. Any other leads would be appreciated. I have very little experience with `JuMP` but I am open to using it if someone can explain how it can be used for this type of problem.

I’ve also considered using a continuous variable optimizer, say, DE or CMA-ES, where the N floating-point decision variables are bounded between 0 and 1, and the permutation is inferred by their order. Can anyone comment on the advantages/pitfalls of using such a scheme?

I don’t have a suggestion, but JuMP is not suitable for this problem: Should I use JuMP? · JuMP

In general, this seems like a very difficult problem. Even for `N=50`, there are something like 10^64 possible solutions…

You’re going to need more domain knowledge in order to solve this.

Thanks, I suspected JuMP was not right for this problem and I appreciate your confirming this.

Regarding the difficulty, I think it is not too bad. I’ve used a Matlab genetic algorithm years ago for a similar problem and it worked quite well. I just don’t want to have to spend the time translating and debugging the Matlab code if there is a canned solution waiting for me.

Edit: Here is an example of someone using a genetic algorithm to solve the traveling salesman problem in seconds with about the same number of unknowns as I need. I don’t believe any domain knowledge was used here, just the distances between cities.

There are a variety of packages you could take a look at:

However, unless you have domain knowledge, you’re unlikely to do better than:

``````function solve(f, N; time_limit)
start = time()
x = collect(1:N)
best_x, best_f = copy(x), Inf
while time() - start < time_limit
cost = f(x)
if cost < best_f
best_f = cost
best_x .= x
end
sortperm!(x, rand(N))
end
return best_x, best_f
end

function black_box(x::Vector{Int})
return sum(i * x[i] for i in 1:length(x))
end

solve(black_box, 50; time_limit = 1.0)
``````
2 Likes

Thanks for the suggestions. I believe that Metaheuristics and BlackBoxOptim are intended only for objective functions depending on continuous variables. I looked at Evolutionary, and as far as I can tell from the documentation the only type of combinatorial operators provided by the package are for use with binary variables.

The random search function you supplied takes N continuous random samples between 0 and 1 and infers the permutation from their order, the technique I was asking about. Instead of just using randomly generated samples, these N continuous variables could be optimized using a standard, continuous variable black-box optimizer like the ones you pointed me to. I wanted to know if anyone has experience doing this sort of thing and how it compares to an optimizer specialized for combinatorial domains.

`MHLib.jl` may indeed be a good starting point for your work when you want to apply a heuristic approach. To realize a basic (general) variable neighborhood search, GRASP, (adaptive) large neighborhood search etc. is easy for a black-box permutation problem by just updating the TSP demo, see the more detailed comments at here.

Note, however, that as for any challenging combinatorial optimization problem, it always is a good idea to think about the problem structure and to possibly realize more specialized methods you can provide to the framework. For example, a problem-specific construction heuristic for creating an initial solution might be a good idea, or some more specific neighborhood structures, possibly allowing an incremental solution evaluation. `MHLib.jl` only contains basic functionality, but is designed for efficiency and to give much flexibility for such problem-specific extensions.

Disclaimer: I am one of the authors of `MHLib.jl`.

3 Likes

Thanks for your response and the detailed advice you provided in the issue.

I will wait to mark your answer as the solution pending any more responses to my original post.