Combinatorial Optimization with permutation input and black-box function

Specific Domains Optimization (Mathematical)
, ,
1

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.

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. :slight_smile:

2

What is allinone?

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

3

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.

4

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:

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.

5

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

6

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, noting the recommendation at the beginning.