(Interval) subset optimization with JuMP

Specific Domains Optimization (Mathematical)
1

Hey everyone. I’m trying to figure out how to use JuMP to optimize a function of a slice of data over the left and right endpoints for the range.

I’ve never used JuMP before so I’m piecing this together from tutorials and the docs.

# data
x = randn(100)

# func to optimize
mysum(left, right, x = x) = sum(x[left:right])

m = Model()
@variable(m, left, lower_bound = 1, upper_bound = length(x))
@variable(m, right, lower_bound = 1, upper_bound = length(x))

@constraint(m, left + 20 <= right)
@constraint(m, left in MOI.Integer())
@constraint(m, right in MOI.Integer())

@objective(m, Max, mysum(left, right))

I get ERROR: MethodError: no method matching isless(::GenericAffExpr{Float64,VariableRef}, ::GenericAffExpr{Float64,VariableRef})

What am I doing wrong? What’s the correct way to specify this type of optimization problem?

Appreciate the help!

P.S. I tried rewriting

function mysum(left, right, x)
    x_sub = [el for (i,el) in enumerate(x) if left ≤ i ≤ right]
    sum(x_sub)
end

but it yields the same error.

2

You can’t use the value of a variable (e.g., left) inside a splice.

You should re-formulate your model like so (n.b., I haven’t tested this, so there might be bugs):

x = rand(100)
model = Model()
@variable(model, 1 <= left <= 100, Int)
@variable(model, 1 <= right <= 100, Int)
@variable(model, z[1:100], Bin)
@constraint(model, left + 20 <= right)
@constraint(model, [i = 1:100], (101 - i) * z[i] <= 101 - left)
@constraint(model, [i = 1:100], i * z[i] <= right)
@objective(model, Max, sum(x[i] * z[i] for i in 1:100))
3 Likes
3

Thanks! I had to add the following constraint to your answer to ensure that we don’t get solutions like [0,0,1,1,1,0,1]

@constraint(model, sum(z) == right - left + 1)