# Need a combinatorial optimizer for black box function

**URL:** <https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791>\
**Category:** Optimization (Mathematical)\
**Tags:** combinatorics\
**Created:** [September 26, 2021, 9:25pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791 "2021-09-26T21:25:37Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![PeterSimon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petersimon/32/25193_2.png) [@PeterSimon](https://discourse.julialang.org/u/PeterSimon)\
**Post date:** [September 26, 2021, 9:25pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/1 "2021-09-26T21:25:37Z")

</div>

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](https://github.com/uripatish/Combo.jl) which looks like it is untouched for \> 3 years and doesn’t work under Julia 1.x. I’ve also looked at [MHLib](https://github.com/ac-tuwien/MHLib.jl) 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?

Thanks in advance!

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 26, 2021, 9:44pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/2 "2021-09-26T21:44:48Z")

</div>

I don’t have a suggestion, but JuMP is not suitable for this problem: [https://jump.dev/JuMP.jl/stable/background/should\_i\_use/#Black-box,-derivative-free,-or-unconstrained-optimization](https://jump.dev/JuMP.jl/stable/background/should_i_use/#Black-box,-derivative-free,-or-unconstrained-optimization)

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.

---

<div class="post-metadata">

**Author:** ![PeterSimon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petersimon/32/25193_2.png) [@PeterSimon](https://discourse.julialang.org/u/PeterSimon)\
**Post date:** [September 26, 2021, 9:50pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/3 "2021-09-26T21:50:27Z")

</div>

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](https://www.youtube.com/watch?v=bUEOuI2fK-M) 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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 26, 2021, 9:58pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/4 "2021-09-26T21:58:51Z")

</div>

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

- [https://github.com/jmejia8/Metaheuristics.jl](https://github.com/jmejia8/Metaheuristics.jl)
- [GitHub - wildart/Evolutionary.jl: Evolutionary & genetic algorithms for Julia](https://github.com/wildart/Evolutionary.jl)
- [https://github.com/robertfeldt/BlackBoxOptim.jl](https://github.com/robertfeldt/BlackBoxOptim.jl)

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

```nohighlight
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)

```

---

<div class="post-metadata">

**Author:** ![PeterSimon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petersimon/32/25193_2.png) [@PeterSimon](https://discourse.julialang.org/u/PeterSimon)\
**Post date:** [September 26, 2021, 10:26pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/5 "2021-09-26T22:26:00Z")

</div>

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](https://wildart.github.io/Evolutionary.jl/stable/mutation/#Combinatorial-Mutations) 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.

---

<div class="post-metadata">

**Author:** ![graidl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/graidl/32/29508_2.png) [@graidl](https://discourse.julialang.org/u/graidl)\
**Post date:** [September 27, 2021, 8:04am UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/6 "2021-09-27T08:04:06Z")

</div>

[`MHLib.jl`](https://github.com/ac-tuwien/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](https://github.com/ac-tuwien/MHLib.jl/issues/3).

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`.

---

<div class="post-metadata">

**Author:** ![PeterSimon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petersimon/32/25193_2.png) [@PeterSimon](https://discourse.julialang.org/u/PeterSimon)\
**Post date:** [September 27, 2021, 1:34pm UTC](https://discourse.julialang.org/t/need-a-combinatorial-optimizer-for-black-box-function/68791/7 "2021-09-27T13:34:03Z")

</div>

> [@graidl](#):
>
> any challenging combinatorial optimization problem, it always is a good idea to think about the problem structure and to possibly re

Thanks for your response and the detailed advice you provided in the [issue](https://github.com/ac-tuwien/MHLib.jl/issues/3).

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