Deleting containerized constraints

#1

Hi folks,

I am translating an electricity production cost model from GAMS to JuMP and am struggling to get reasonable model generation times. Generally these models consist of running 365 single-day optimisations to run a full year.

One of the things I am trying to do to improve model generation times is to identify which constraints don’t change and which need to be regenerated in each loop. The idea is then to delete the changed constraints and re-generate them. However, deleting the constraints is taking much more time than regenerating the full model.

Most constraints are containerized and generated similarly to this:

@constraint(model, con[i = 1:2, j = 2:3], i * x <= j + 1)

To delete all of these, I have to do something lke this:

for c in con
    delete(model,c)
end

Some constraints are dimensioned by time and transmission node (48 x 500) and so this is taking a very long time. Is there a way better way of doing what I’m trying to do?

edit: just to add, I know there is set_coefficient and the hack with .fix to change the RHS… but what’s the point of a high level modeling language if I need to aggregate up the coefficients and constants myself - I may as well generate the MPS file from scratch in that case…

Optimize slow constraint generation
#2

Please provide a minimum working example:

In particular

  • what solver are you using?
  • how long does it take to rebuild the model vs delete the constraints?
  • the way you are deleting in the loop is the correct syntax

just to add, I know there is set_coefficient and the hack with .fix to change the RHS… but what’s the point of a high level modeling language if I need to aggregate up the coefficients and constants myself

Using fix to change the RHS is not a hack. It is the official way to change the RHS. Why?

  • @constraint(model, 2x + 1 <= 3) Is the RHS 3 or 3-1=2?
  • @constraint(model, 1 <= 2x + 1 <= 3). What is the RHS?

If you have lots of duplicate variables, it should be possible to restructure your code to simplify things.

#3

Thanks for the reply.

I’m using CPLEX at the moment as the solver.

Regarding a minimum working example, I really wanted to confirm that this was the correct way to delete a containerized constraint. There are many of these in the model so I can’t think of what a MWE would be.

for c in con
    delete(model,c)
end

Regarding the RHS thing - my understanding was always that the RHS was the constant term.

#4

I really wanted to confirm that this was the correct way to delete a containerized constraint.

I haven’t tried, but delete.(model, con) might work as well.

For a MWE, try to create a simple example where deleting the constraints takes a considerable amount of time. We can use that example as a benchmark to make improvements.

Regarding the RHS thing - my understanding was always that the RHS was the constant term.

Constant term of the function (2x + 1) or constant term of the set (<= 3)? Here is a relevant JuMP issue if you want to discuss further: https://github.com/JuliaOpt/JuMP.jl/issues/1890

#5

So…

using JuMP,CPLEX

const C = 300000
const N = 100

function test_const()
    m=Model(with_optimizer(CPLEX.Optimizer, CPX_PARAM_SCRIND=0))
    coef = rand(C,N)
    @variable(m, 0 <= x[1:N] <= 1)
    @variable(m, 0 <= Θ <= 1000)
    val, time, = @timed @constraint(m, Θ .<= coef*x  )
    println("time to create constraints: ", time)
    val, time, = @timed delete_constraints(m,x)
    println("time to delete constraints: ", time)
end

function delete_constraints(m,x)
    for con in x
        delete(m, con)
    end
end

test_const()

output:

time to create constraints: 21.936897123
time to delete constraints: 591.988164435

edit: and with delete(m, x)

ERROR: LoadError: MethodError: no method matching delete(::Model, ::Array{VariableRef,1})
#6

It’s delete.(m, x). Note the sneaky . after delete which tells Julia to use broadcasting.

Deleting constraints is an expensive operation, although @ndinsmore has been putting in great work improving this. See: https://github.com/JuliaOpt/LinQuadOptInterface.jl/pull/95

Could you try with m = JuMP.direct_model(CPLEX.Optimizer(CPX_PARAM_SCRIND=0))?

If you’re deleting large numbers of constraints, you might be better off just rebuilding the model from scratch?

#7

Thanks for that…delete.(m, x) produces the same timings, but I don’t believe you were suggesting otherwise.

As in my op, I am solving a model in a loop and am looking for ways to reduce the model building time. I was hoping to do this by rebuilding only the constraints that change which is a small subset of all the constraints in the model - but it doesn’t look like this approach will work.

So it looks like I will need to turn my attention to problem modification… but for this to be a real option, I do feel we need a solution that doesn’t involve adding dummy variables to the problem.

#8

I’ve just realized that delete_constraints(m,x) is actually deleting variables? This is slow because it has to remove things from the constraint objects. Do you mean delete_constraints(m, val)?

#9

Indeed!

#10

Goodness… look at this:

using JuMP,CPLEX

const C = 300000
const N = 10

function test_const()
    m=Model(with_optimizer(CPLEX.Optimizer, CPX_PARAM_SCRIND=0))
    coef = rand(C,N)
    @variable(m, 0 <= x[1:N] <= 1)
    @variable(m, 0 <= Θ <= 1000)
    val, time, = @timed @constraint(m, Θ .<= coef*x  )
    println("time to create constraints: ", time)
    val2, time = @timed delete_constraints(m,val)
    println("time to delete constraints: ", time)
end

function delete_constraints(m,x)
    delete.(m, x)
end

test_const()

Output:

time to create constraints: 4.891016396
time to delete constraints: 2522.593128827
#11

The problem is that JuMP has to store a mapping between the constraint object (e.g., val[10]) and the row in the CPLEX constraint matrix (i.e., 10). Thus, deleting constraints like this is n^2 in the number of constraints. When you delete a constraint, JuMP has to loop through all other constraints and update the mapping between the constraint and the row.

Deleting a few constraints is cheap. Deleting lots of constraints (e.g. 30_000) is expensive. Do you really need to do this?

#12

As I was saying, I am solving in a loop and it would be nice if I could replace only those constraints that change… so the idea was to only the constraints that change and add a new version of them. But it looks like this is not the way to get the performance improvements I would like.

I am looking at ParameterJuMP.jl - this looks like it could do what we need.

Given that I want to add back the constraint, I wonder would something like constraint_replace or constraint update make sense where you rebuild the constraint but don’t need to update the mapping? You also don’t need to worry about what’s the RHS etc. because you rebuild it from scratch.

#13

Alternatively, you could use Parametron, which I built for these kinds of parameterized problems.

using Parametron, CPLEX
using Random

const C = 30000#300000
const N = 10

# Basic problem setup. Mostly the same as with JuMP, except
# the @constraint macro isn't quite as advanced.
const m = Model(CPLEX.Optimizer(CPX_PARAM_SCRIND=0))
x = [Variable(m) for i in 1 : N]
Θ = Variable(m)
@constraint m 0 <= Θ
@constraint m Θ <= 1000
for i in 1 : N
    @constraint m 0 <= x[i]
    @constraint m x[i] <= 1
end

# Now the interesting part: you can explicitly create a Parameter
# with an update function that will be called before each solve. Here
# create an update function that is a closure over a pre-allocated matrix
# using the standard `do` syntax.
const coef_val = zeros(C, N)
const coef = Parameter(coef_val, m) do coef_val
    rand!(coef_val)
end
@constraint m fill(Θ, C) <= coef * x

# Solve the first time
@time solve!(m) # currently produces some warnings...

# solving a second time will call the update function for the `coef`
# parameter and update the corresponding constraints in place.
@time solve!(m)
#14

Nice… this is exactly the kind of thing we’re looking at… thanks for the steer…

edit: never mind, I needed to scroll down!!