# Combinatorial Optimization with permutation input and black-box function

**URL:** <https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578>\
**Category:** Optimization (Mathematical)\
**Tags:** question, package, jump\
**Created:** [October 28, 2021, 7:07pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578 "2021-10-28T19:07:42Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![duringyear](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/duringyear/32/30304_2.png) [@duringyear](https://discourse.julialang.org/u/duringyear)\
**Post date:** [October 28, 2021, 7:07pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/1 "2021-10-28T19:07:42Z")

</div>

Hi. I’ve been struggling for nights with combinatorial optimization

Input = matrix with permutation.  
Each row represents unit, and column means visit sequence for each place.  
e.g) x = [1 2 3 4 ; 2 3 1 4 ; 3 1 2 4]  
it means, First unit visits 1 first, and 2 3 4 in a row. Second unit visits 2 3 1 4

And also I made a function.  
Based on markov chain, It calculate an expected complete time(=makespan).  
function name is allinone(x). x is a matrix like above

My objective is to find an optimal x (visit sequence).  
And if that is exist, I can calculate an expected complete time as well.

For this problem, I’ve searched for many packages, like JuMP, MHLib, ConstraintSolver, Combo(not available) and so on.  
Based on that, I made a code like below.

```julia
using ConstraintSolver
const CS = ConstraintSolver
prio = [1 2 3 4;
        2 3 1 4;
        3 1 2 4]

function testing()
model = Model(CS.Optimizer)
@variable(model, 1 <= x[1:3,1:4] <= 4, Int)
    
for sqd = 1:3
    @constraint(model, x[sqd,:] in CS.AllDifferent())
end

@objective(model, Min, allinone(x))
    
optimize!(model)

@show JuMP.value.(x)
end
testing()

```

But, When I put this, there is a error.  
“MethodError: Cannot `convert` an object of type VariableRef to an object of type Int64”

How can handle this error? Can I get some advice?  
And I’m not sure that I could solve this problem even if I handle this error.  
So, Would you got some recommendation for this problem?

Thank you for reading this, and hope some replies. 🙂

---

<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:** [October 28, 2021, 7:12pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/2 "2021-10-28T19:12:38Z")

</div>

What is `allinone`?

See [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)

JuMP might not be the right tool for this.

---

<div class="post-metadata">

**Author:** ![duringyear](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/duringyear/32/30304_2.png) [@duringyear](https://discourse.julialang.org/u/duringyear)\
**Post date:** [October 28, 2021, 7:37pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/3 "2021-10-28T19:37:49Z")

</div>

_allinone_ is function to calculate Expected total completion time.  
It is based on Continuous Time markov chain.  
And its parameter is exponential service rate and visit sequence.

As I understand, _allinone_ function is a kind of black-box function.  
So with that point of view, I agree with you.  
But the alternatives; such as Optim, NLopt, seems that there’s nothing with integer or permutation input.

---

<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:** [October 28, 2021, 9:34pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/4 "2021-10-28T21:34:59Z")

</div>

Combinatorial problems with a black-box objective are incredibly difficult to solve.

NLopt has some derivative-free methods.

You could also convert from discrete to continuous variables by assigning each `x` a weight between 0 and 1, and then sorting them based on that.

There are also other options:

- [https://github.com/jbrea/BayesianOptimization.jl](https://github.com/jbrea/BayesianOptimization.jl)
- [https://github.com/robertfeldt/BlackBoxOptim.jl](https://github.com/robertfeldt/BlackBoxOptim.jl)
- [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)

In general though, you might be better with some hand-coded local-search techniques. You won’t be able to find a global optimal solution.

---

<div class="post-metadata">

**Author:** ![duringyear](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/duringyear/32/30304_2.png) [@duringyear](https://discourse.julialang.org/u/duringyear)\
**Post date:** [October 28, 2021, 10:22pm UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/5 "2021-10-28T22:22:58Z")

</div>

Thank you for your advice! I’ll try to figure it out with another options that you gave. 🙂

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [October 29, 2021, 3:35am UTC](https://discourse.julialang.org/t/combinatorial-optimization-with-permutation-input-and-black-box-function/70578/6 "2021-10-29T03:35:32Z")

</div>

> [@duringyear](#):
>
> ```julia
> @variable(model, 1 <= x[1:3,1:4] <= 4, Int)
>     
> for sqd = 1:3
> @constraint(model, x[sqd,:] in CS.AllDifferent())
> end
> 
> ```

If you want to use a “pure” integer programming formulation of the `AllDifferent` (so as to not rely on ConstraintSolver), I would recommend reading [this blog post](https://yetanothermathprogrammingconsultant.blogspot.com/2016/05/all-different-and-mixed-integer.html), noting the recommendation at the beginning.