How to efficiently add new variables in a loop for a decomposed model?

[Shuvomoy Das Gupta]

Hi,

I am trying to solve the classical cutting stock problem (Introduction To Linear Optimization by Bertsimas and Tsitsiklis, page 234-36) using JuMP, where:

• The master problem produces the number of large rolls cut according to certain number of patterns,
  
• The sub-problem checks for the optimality condition,
• If the master problem is not optimal, the sub-problem produces a new pattern that corresponds to a new decision variable to be added in the master problem. JuMP gives us the ability to add new variables to a model, by using the @defVar macro.

Naturally, it would be more convenient to write a loop that checks the optimality condition every time the sub-problem is solved, and adds the new variables to the original array of decision variables when it is sub-optimal. For built-in containers in Julia,  push! is an excellent choice to grow the set element by element. However, it seems that push! is not defined for any of the containers that represent decision variables in JuMP.

How can I efficiently grow the original set of variables in a loop? Any suggestion will be much appreciated.

Best Regards,
Shuvo

[Miles Lubin]

We don't currently have provisions to expand JuMPContainer objects for adding variables inside of column generation.

I would recommend maintaining your own dictionary or array of Variable objects (using Julia's built-in containers). You can create a single variable to add with the column-wise @defVar syntax described here: https://jump.readthedocs.org/en/latest/probmod.html#modifying-variables. Then just push the variable to the julia container.

It's possible that we could develop a "pure JuMP"-style syntax for this, though given that JuMP is already embedded in a fully featured programming language, I'm more in favor of keeping JuMP lightweight and leaving this sort of complexity to Julia.

Best,

Miles

[Shuvomoy Das Gupta]

Hi Miles,

Thanks a lot for your response. I am still a bit confused about how to add the decision variables in a loop. In the documentation, @defVar has added the decision variables manually one by one, in column generation it might be efficient to do it in a loop.

 

Consider the example in JuMP documentation:

m = Model()
@defVar(m, 0 <= x <= 1)
@defVar(m, 0 <= y <= 1)
@setObjective(m, Max, 5x + 1y)
@addConstraint(m, con, x + y <= 1)
solve(m)  # x = 1, y = 0

Now suppose we have to keep adding  new variables while some condition is true:

while(someCondition) #someCondition is true when the current solution is sub-optimal
      @defVar(m, 0 <= newVariable <= 1, newObjCoef , [con], [newValues]) # The variable names have to be unique every time the macro is executed
      #               -----------       ----------           ---------    newObjCoef and newValues are obtained from the sub-problem
      solve(m)
end

Now for this to work, unique variable names has to be generated every time @defVar is executed inside the loop. I am having trouble implementing this. Can you please give any suggestion on how to do this?

Best Regards,

Shuvo

[Miles Lubin]

Now suppose we have to keep adding  new variables while some condition is true:

while(someCondition) #someCondition is true when the current solution is sub-optimal
      @defVar(m, 0 <= newVariable <= 1, newObjCoef , [con], [newValues]) # The variable names have to be unique every time the macro is executed
      #               -----------       ----------           ---------    newObjCoef and newValues are obtained from the sub-problem
      solve(m)
end

Now for this to work, unique variable names has to be generated every time @defVar is executed inside the loop. I am having trouble implementing this. Can you please give any suggestion on how to do this?

Using the macro:

@defVar(m, x, ...)

is just a fancy syntax for

x = Variable(m, ...)

In particular, there's no difference in scoping rules for variables defined by @defVar from those defined normally in Julia. This has its own set of implications which leads to behavior that differs from standalone modeling languages like AMPL, which can lead to some understandable confusion. Anyway, there's no need for variable names to be unique on each call to @defVar. The only implication of using the same name multiple times is that when printing the model, multiple distinct variables will be displayed using the same string. A workaround for this is calling setName() explicitly, e.g.,

newColumns = Variable[] # collect the new columns here

while(someCondition) #someCondition is true when the current solution is sub-optimal
      @defVar(m, 0 <= newVariable <= 1, newObjCoef , [con], [newValues])

      push!(newColumns, newVariable)
      setName(newVariable, string("newColumn",length(newColumns))) # only needed so that new columns display differently when calling print(m)
      solve(m)
end

This is identical to using the Variable() constructor as follows:

newColumns = Variable[] # collect the new columns here

while(someCondition) #someCondition is true when the current solution is sub-optimal

       newVariable = Variable(m, 0, 1, :Cont, newObjCoef, [con], [newValues], name=string("newColumn",length(newColumns)))
       push!(newColumns, newVariable)
       solve(m)
end

Though we tend to discourage using Variable() directly, this seems to be a use case where it is more natural and clear than using @defVar.

[Shuvomoy Das Gupta]

Hi Miles,

Thanks for your response. It is very nice to know that different variable names do not have to be unique in JuMP. In that case, after arriving at the optimal solution, I can just push the values of new variables defined in the loop in a Julia dict, which might be more efficient rather than using setName at each iteration of the loop. 

However, how do I access different variables with the same name? For example, consider the modified example from the documentation, where adding two variables with the same name z results in the correct solution, however getValue(z) gives only the second one:

using JuMP

using CPLEX

m = Model()

@defVar(m, 0 <= x <= 1)

@defVar(m, 0 <= y <= 1)

@setObjective(m, Max, 5x + 1y)

con = @addConstraint(m, x + y <= 1)

solve(m)  # x = 1, y = 0

# New Variables: Both With The Same Names z

#------------------------------------------

@defVar(m, 0 <= z <= 1, 10.0, [con], [1.0]) # The first z has optimal value 1

@defVar(m, 0 <= z <= 1, -3.0, [con], [-2.0]) # The second z has optimal value 0.5

print(m)

solve(m)

#print("The first z is ", getValue(z1), "and the second z is ", getValue(z2)) # How do I access the differnt z s

print("z= ", getValue(z)) # This seems to give the second z

# How do I access the first one?

Is there a way I can access both of the zs and may be getting some information regarding their chronological order?

Best Regards,

Shuvo

[Miles Lubin]

Is there a way I can access both of the zs and may be getting some information regarding their chronological order?

 

Here you just need to hang on to a reference to the variables after you create them, and then call getValue() on these objects. E.g.,

...

# New Variables: Both With The Same Names z
#------------------------------------------
@defVar(m, 0 <= z <= 1, 10.0, [con], [1.0]) # The first z has optimal value 1

z1 = z

@defVar(m, 0 <= z <= 1, -3.0, [con], [-2.0]) # The second z has optimal value 0.5

z2 = z

print(m)

solve(m)

[Shuvomoy Das Gupta]

It seems that adding a new variable has an issue when the constraint references were defined as an JuMPArray in the initial model. Surprisingly when the new variable is connected with the constraint references manually it works.

For example:

In[1]:

using JuMP
using CPLEX
m = Model()
@defVar(m, 0 <= x <= 1)
@defVar(m, 0 <= y <= 1)
@setObjective(m, Max, 5x + 1y)

@defConstrRef con[1:2]
for i in [1:2]
    con[i]=@addConstraint(m, i* x + y <= i+5)
end
print(m)

solve(m)  # x = 1, y = 0

println("x= ", getValue(x), " y= ", getValue(y))
@defVar(m, 0 <= z <= 1, 10.0, con, [1.0;-2.00]) # This does not work
# Surprisingly
#@defVar(m, 0 <= z <= 1, 10.0, [con[1]; con[2]], [1.0;-2.00])
#works but
#@defVar(m, 0 <= z <= 1, 10.0, [con[i] for i in [1:2]], [1.0;-2.00])
# does not !
solve(m)  # z = 1
println("x= ", getValue(x), " y= ", getValue(y), " z= ", getValue(z))


Out[1]:

Max 5 x + y
Subject to
 x + y <= 6
 2 x + y <= 7
 0 <= x <= 1
 0 <= y <= 1
Tried aggregator 1 time.
LP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = -0.00 sec. (0.00 ticks)
x= 1.0 y= 1.0
`Variable` has no method matching Variable(::Model, ::Int64, ::Int64, ::Symbol, ::Float64, ::JuMPArray##8734{ConstraintRef{T<:JuMPConstraint}}, ::Array{Float64,1})
while loading In[1], in expression starting on line 548

When there are many constraint references, manually associating a new variable with all of them might not very efficient. Is there a way to do this using loop or array comprehension? 

[Miles Lubin]

All three of the forms you list should work, tracking this in https://github.com/JuliaOpt/JuMP.jl/issues/301.

[Miles Lubin]

In the meantime, the following array comprehension syntax should work:

@defVar(m, 0 <= z <= 1, 10.0, ConstraintRef{LinearConstraint}[con[i] for i in [1:2]], [1.0;-2.00])

On Sunday, November 9, 2014 10:21:15 AM UTC-8, Shuvomoy Das Gupta wrote:

[Shuvomoy Das Gupta]

Hi Miles,

Thanks a lot, what you suggested works!

In[3]:

using JuMP

using CPLEX

m = Model()

@defVar(m, 0 <= x <= 1)

@defVar(m, 0 <= y <= 1)

@setObjective(m, Max, 5x + 1y)

@defConstrRef con[1:2]

for i in [1:2]

    con[i]=@addConstraint(m, i*x + y <= i+5)

end

print(m)

solve(m)  # x = 1, y = 1

println("x= ", getValue(x), " y= ", getValue(y))

# The following works: 

# --------------------

@defVar(m, 0 <= z <= 1, 10.0, ConstraintRef{LinearConstraint}[con[i] for i in [1:2]], [1.0;-2.00]) 

#---------------------

# @defVar(m, 0 <= z <= 1, 10.0, con, [1.0;-2.00])

# does not work

# Surprisingly 

# @defVar(m, 0 <= z <= 1, 10.0, [con[1]; con[2]], [1.0;-2.00]) 

# works

# But 

# @defVar(m, 0 <= z <= 1, 10.0, [con[i] for i in [1:2]], [1.0;-2.00])

# does not work

print(m)

solve(m)  # z = 1

println("x= ", getValue(x), " y= ", getValue(y), " z= ", getValue(z))

 

Out[3]:

Max 5 x + y

Subject to

 x + y <= 6

 2 x + y <= 7

 0 <= x <= 1

 0 <= y <= 1

Tried aggregator 1 time.

LP Presolve eliminated 2 rows and 2 columns.

All rows and columns eliminated.

Presolve time = -0.00 sec. (0.00 ticks)

x= 1.0 y= 1.0

Max 5 x + y + 10 z

Subject to

 x + y + z <= 6

 2 x + y - 2 z <= 7

 0 <= x <= 1

 0 <= y <= 1

 0 <= z <= 1

Iteration log . . .

Iteration:     1    Objective     =            16.000000

x= 1.0 y= 1.0 z= 1.0

 

What I am finding very interesting is that typeof can be misleading here. If we look at typeof([con[1]; con[2]]), the elements are shown to be of some complicated type ConstraintRef{GenericRangeConstraint{GenericAffExpr{Float64,Variable}}}

In[4]:
typeof([con[1]; con[2]])
Out[4]:
Array{ConstraintRef{GenericRangeConstraint{GenericAffExpr{Float64,Variable}}},1}

However, enforcing this type to construct the same array using array comprehensions does not work:

In[5]:
ConstraintRef{GenericRangeConstraint{GenericAffExpr{Float64,Variable}}}[con[i] for i in [1:2]]
Out[5]:
GenericRangeConstraint not defined
while loading In[114], in expression starting on line 2
in anonymous at no file

But if we use the type as ConstraintRef{LinearConstraint} for array comprehensions as you suggested, then it works again, though  the type of the elements of the array are shown to be ConstraintRef{GenericRangeConstraint{GenericAffExpr{Float64,Variable}}} !

In[6]:

ConstraintRef{LinearConstraint}[con[i] for i in [1:2]]

Out[6]:
2-element Array{ConstraintRef{GenericRangeConstraint{GenericAffExpr{Float64,Variable}}},1}:
 x + y + z <= 6    
 2 x + y - 2 z <= 7

Thanks again for your suggestion.

Regards,

Shuvo