can Coluna decompose a general large scale MILP model?

[BYS543]

Hello,
I find the Coluna document gives a decomposable model of the Generalized Assignment,which the machine set can be seen as a partitionable set. If I have a more general MILP model(large scale), which consists of the integer and continuous variables, can I use Coluna with branch and price decomposition algorithm? A given example would be better.
Thanks in advance!

[guimarqu]

Hi,

Yes Coluna can decompose a large MILP model as long as you provide an axis to decompose it.

This is the line :

@axis(M, 1:nb_machines)

in the documentation.

In a very near future, BlockDecomposition will provide automatic decomposition (atoptima/BlockDecomposition.jl#31).

What do you mean by a more general MILP model ?

[BYS543]

Thank you for your prompt reply. For example, my MILP model has some integer and continuous variables, So as you said, can I decompose any of my integer varaible sets simultaneously? I find specify!.(subproblems, lower_multiplicity = 0, upper_multiplicity = 1) in the document. So I must specify whether every integer variables in one type of integer set are used or not used?
For example ,my problem is a unit commiment problem, so the unit commiment variables maybe just which generators are on or off in a certain period,so the integer variable set can be defined as ug[gen_set][time_set],gen_set=1:NG,time_set=1:NT, in other words, the integer variable set of specific meaning may be not only related to generator set(may be also related to time set). So I just express it as @axis(gen_set, 1:NG), @axis(time_set, 1:NT).? Can I only decompose the generator set and not decompose the time set? Does it mean I only decompose on the generator axis and one block includes all periods of one generator?

[BYS543]

And one more problem of the expression of Coluna.

NG=5;NT=10;
model=Model();
gen_set=[1,2,3,4,5]
gen_set2=[2,3,4];
gen_set3=setdiff(gen_set,gen_set2);
@axis(gen_set1,gen_set)
@variable(model,ug[gen_set1][1:NT])
@variable(model,uon[gen_set1][1:NT])
@variable(model,uoff[gen_set1][1:NT])

if I use

for t in 1:NT
for i in gen_set # pay attention
    if i in gen_set2
          @constraint(model,uon[i,t]+uoff[i,t]<=1)
          @constraint(model,ug[i,t]>=uon[i,t])
    end
end
end

is it equal to?

for t in 1:NT
for i in gen_set1 # a little different
    if i in gen_set2
          @constraint(model,uon[i,t]+uoff[i,t]<=1)
          @constraint(model,ug[i,t]>=uon[i,t])
    end
end
end

[guimarqu]

I find specify!.(subproblems, lower_multiplicity = 0, upper_multiplicity = 1) in the document. So I must specify whether every integer variables in one type of integer set are used or not used?

It means that in the optimal solution, all the variables of a subproblem may equal 0 (as if the subproblem block disappears). If you are not sure you leave with default value (lower_multiplicity = 1 & upper_multiplicity = 1)

Can I only decompose the generator set and not decompose the time set? Does it mean I only decompose on the generator axis and one block includes all periods of one generator?

Yes you can just define @axis(gen_set1, 1:NG). Yes right.

And one more problem of the expression of Coluna.

Both won't work because you declare anonymous constraints (without name and indices). These constraints will go to the master.
You must give a name to the constraints and use the entries of the axis in the indices of the constraints.
For instance :

new_gen_set = []
for i in gen_set1  # always use axis to perform decomposition
  if i in gen_set2
    push!(new_gen_set, i)
  end
end

@constraint(model,  constraint1[i in new_gen_set, t in 1:NT], uon[i,t] + uoff[i,t]<=1)
@constraint(model,  constraint2[i in new_gen_set, t in 1:NT], ug[i,t] >= uon[i,t])

I'll add this information in the documentation :

The index-set of the subproblems is declared through an BlockDecomposition.@axis. It returns an array. Each value of the array is a subproblem index wrapped into a BlockDecomposition.AxisId. Each time BlockDecomposition finds an AxisId in the indices of a variable and a constraint, it knows to which subproblem the variable or the constraint belongs.

Moreover, you can check to what subproblem a variable or a constraint belongs with method BlockDecomposition.annotation(model, x[g,t]).

[BYS543]

NG=5;NT=10;
model=Model();
gen_set=[1,2,3,4,5]
gen_set2=[2,3,4];
gen_set3=setdiff(gen_set,gen_set2);
@axis(gen_set1,gen_set)
@variable(model,ug[gen_set1,1:NT])
@variable(model,uon[gen_set1,1:NT])
@variable(model,uoff[gen_set1,1:NT])
new_gen_set = []
for i in gen_set1  # always use axis to perform decomposition
  if i in gen_set2
    push!(new_gen_set, i)
  end
end
@constraint(model,  constraint1[i in new_gen_set, t in 1:NT], uon[i,t] + uoff[i,t]<=1)
@constraint(model,  constraint2[i in new_gen_set, t in 1:NT], ug[i,t] >= uon[i,t])
@dantzig_wolfe_decomposition(model, decomposition, gen_set1)

If I run
BlockDecomposition.annotation(model, ug[1,1])
it shows
Annotation(BlockDecomposition.Master, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 2)
If I run
BlockDecomposition.annotation(model, ug[2,1])
it shows the same
Annotation(BlockDecomposition.Master, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 2)
Does it belong to different blocks? why the display is the same?

[guimarqu]

Hi,

Sorry, I forgot to tell you that you can check the annotations only after the call to JuMP.optimize!(model).

You have to declare the model as a BlockModel :

using JuMP, BlockDecomposition

model = BlockModel()

then you have to call JuMP.optimize!(model) even if you did not define a solver, because in BlockDecomposition.BlockModel() we hook a method that define the annotations of all variables and constraints. This method is the first one called by JuMP.optimize!(model).

try
   JuMP.optimize!(model)
catch e
   println("ok")
end

then, you can check the annotations :

julia> BlockDecomposition.annotation(model, constraint1[2,1])
Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 4)

julia> BlockDecomposition.annotation(model, ug[1,1])
Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 3)

And you can see that the constraints and variables are in pricing problems.

Edit: you can print the decomposition to see the annotation associated to each entry of the axis :

julia> decomposition
Root - Annotation(BlockDecomposition.Master, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 2) with 5 subproblems :
	 5 => Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 7) 
	 4 => Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 6) 
	 2 => Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 4) 
	 3 => Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 5) 
	 1 => Annotation(BlockDecomposition.DwPricingSp, BlockDecomposition.DantzigWolfe, lm = 1.0, um = 1.0, id = 3) 

[BYS543]

Many thanks again for this reply.

@axis(gen_set,1:NG)
@variable(model,ug[gen_set])

If I want to assign a variable to the specified block ,e.g. 1
I find the index of gen_set is not supported, i.e. gen_set[1] is not supported,
If I want to assign one variable to one specified block, how can I do it or index it?
Now, the method I use is

New_gen1=[];
for i in gen_set
if i == 1
push!(New_gen1,i)
end
end

But I think it looks a little complex.

[guimarqu]

@variable(model, ug[gen_set[1]]) should work but looks like there is a little bug. I'm going to fix it in BlockDecomposition.

In the meantime, you can do @variable(model, ug[[gen_set[1]]]).