BoundsError when re-solving a model

Specific Domains Optimization (Mathematical)
1

I’ve implemented a neighbourhood search technique wherein I deepcopy the original model, hot-start it and then solve it repeatedly. While the first iteration went smooth, during the second iteration however, I get this error while solving the modified MIP

ERROR: LoadError: BoundsError: attempt to access 15469-element Array{Float64,1} at index [15470]
Stacktrace:
 [1] set_constrLB!(::CPLEX.Model, ::Array{Float64,1}) at /home/user/.julia/v0.6/CPLEX/src/cpx_constrs.jl:243
 [2] setconstrLB!(::CPLEX.CplexMathProgModel, ::Array{Float64,1}) at /home/user/.julia/v0.6/CPLEX/src/CplexSolverInterface.jl:123
 [3] #build#119(::Bool, ::Bool, ::JuMP.ProblemTraits, ::Function, ::JuMP.Model) at /home/user/.julia/v0.6/JuMP/src/solvers.jl:337
 [4] (::JuMP.#kw##build)(::Array{Any,1}, ::JuMP.#build, ::JuMP.Model) at ./<missing>:0
 [5] #solve#116(::Bool, ::Bool, ::Bool, ::Array{Any,1}, ::Function, ::JuMP.Model) at /home/user/.julia/v0.6/JuMP/src/solvers.jl:168

I’m not sure where the error is. Besides, the error is thrown after the MIP is passed to the solver.

2

Hi @varun7rs, can you provide a minimum working example that triggers this bug? It’s a little hard to find out what is going wrong otherwise.

3

Hi @odow, thanks for your reply. The original problem was too complicated to post. This is a condensed version of the problem I’m solving but I encounter a different error now. The stacktrace seems a little too similar to the previous error however.

Just to briefly explain what the heuristic does, we solve a relaxation of a MIP and then employ a rounding technique (the one in the MWE is a simplified version. In my problem I use the ACO heuristic for rounding). To improve the rounded solutions, we use a neighbourhood search technique.

using JuMP
using CPLEX

profit = [ 5, 3, 2, 7, 4 ]
weight = [ 2, 8, 4, 2, 5 ]
capacity = 10

const ϵ = 0.1
K = length(profit)

type MyProblem
  model
  x
  z
end

function createproblem(profit, weight, capacity)

  K = length(profit)

  m = Model(solver=CplexSolver())
  @variable(m, x[1:K], Bin)
  @variable(m, z ≥ 0.0)
  @objective(m, Max, dot(profit, x))
  @constraint(m, dot(weight, x) <= capacity)
  return MyProblem(m, x, z)
end

# A simple rounding heuristic

p = createproblem(profit, weight, capacity)
status = solve(p.model, relaxation = true)
xR, zR = getvalue(p.x), getvalue(p.z)
obj = getobjectivevalue(p.model)

x = zeros(Float64,K) # Fixed variables

for k = 1:K
  if xR[k] ≥ 1-ϵ
    x[k] = 1.0
  end
end

# A Neighbourhood search heuristic

start = time(); TILIM = 300.0;
θ = 0.005 * obj; M = 1e+15;

i = 0
while (time()-start) < TILIM

  i += 1
  temp = deepcopy(p)
  # Hot-start
  for k = 1:K
    setvalue(temp.x[k], x[k])
  end

  # Cut-off
  @constraint(temp.model, dot(profit, temp.x) ≥ obj + θ - temp.z)
  @objective(temp.model, Min, sum((x[k] == 0.0) ? temp.x[k] : 0.0 for k = 1:K)
                            + sum((x[k] == 1.0) ? (1-temp.x[k]) : 0.0 for k = 1:K)
                            + M * temp.z)

  println("Iteration $i")
  solve(temp.model)

  if getvalue(temp.z) == 0.0
    x = getvalue(temp.x); z = getvalue(temp.z)
    obj = dot(profit, x)
  else
    θ = θ / 2.0
  end
end
4

deepcopy is not intended to be used on JuMP models. It can lead to unexpected behaviour as you observe.

Why do you need the copy instead of just using the model p everywhere?

5

Since I modify model p at every iteration(I add a cut-off constraint which is modified over the course of the heuristic), I wanted to have a different copy of the model. And since I had trouble doing this, I used deepcopy. Is there another way around this problem?

For now, I’ve settled with re-building the problem at each iteration by calling createproblem but I’m worried if model building would consume a lot of time for larger problem instances

6

Instead of the deepcopy, you should just rebuild the model using createproblem.

The upcoming release of JuMP will support constraint deletion which should help this situation a lot. Then you can just delete the cut and add a new one in each iteration to the same model.

Some solvers will also support constraint coefficient modification, so you don’t even have to delete and then re-add, you can just modify the coefficients of the constraint in-place.

1 Like
7

Thanks a lot for the help.