subproblem representative variables (#88)

atoptima · Aug 20, 2022 · a692a1e · a692a1e
1 parent d12df3a
commit a692a1e
Show file tree

Hide file tree

Showing 8 changed files with 215 additions and 10 deletions.
diff --git a/src/BlockDecomposition.jl b/src/BlockDecomposition.jl
@@ -16,14 +16,15 @@ const JC = JuMP.Containers
 
 export BlockModel, annotation, specify!, gettree, getmaster, getsubproblems, ×, indice,
        objectiveprimalbound!, objectivedualbound!, branchingpriority!, branchingpriority,
-       customvars!, customconstrs!, customvars, customconstrs
+       customvars!, customconstrs!, customvars, customconstrs, subproblemrepresentative
 export @axis, @dantzig_wolfe_decomposition, @benders_decomposition
 export AutoDwStrategy
 
 include("axis.jl")
 include("annotations.jl")
 include("tree.jl")
 include("formulations.jl")
+include("subproblem_representative.jl")
 include("checker.jl")
 include("decomposition.jl")
 include("objective.jl")

diff --git a/src/branchingpriority.jl b/src/branchingpriority.jl
@@ -36,6 +36,6 @@ end
 
 function MOI.get(dest::MOIU.UniversalFallback, attribute::VarBranchingPriority, vi::MOI.VariableIndex)
     varattr = get(dest.varattr, attribute, nothing)
-    varattr === nothing && return 1.0
+    isnothing(varattr) && return 1.0
     return get(varattr, vi, 1.0)
 end
diff --git a/src/checker.jl b/src/checker.jl
@@ -23,6 +23,28 @@ struct VarsOfSameDwSpInMaster
     constraint::JuMP.ConstraintRef
 end
 
+"""
+Error thrown when a variable representative of a set of subproblems is involved in a
+constraint that belongs to a subproblem which is to in the set.
+
+For example, consider a variable `x` representative of subproblems `A` and `B`.
+Assume that a constraint of subproblem `C` involves variable `x`.
+BlockDecomposition with throw `NotRepresentativeOfDwSp` error.
+"""
+struct NotRepresentativeOfDwSp
+    variable::JuMP.VariableRef
+    constraint::JuMP.ConstraintRef
+end
+
+"""
+Error thrown when a Dantzig-Wolfe subproblem variable is involed in another Dantzig-Wolfe
+subproblem.
+"""
+struct DwSpVarNotInGoodDwSp
+    variable::JuMP.VariableRef
+    constraint::JuMP.ConstraintRef
+end
+
 # Methods to check constraints and variables.
 
 function _check_annotations(model::JuMP.Model, container::JC.DenseAxisArray)
@@ -67,7 +89,15 @@ abstract type IndepDecompositionCheck <: DecompositionCheck end
 # with caring about the previous verifications (=> accumulator)
 abstract type AccDecompositionCheck <: DecompositionCheck end
 
-struct MasterVarInDwSpCheck <: IndepDecompositionCheck end
+"""
+Checks:
+- master variable in dantzig-wolfe subproblem
+- dantzig-wolfe variable not in good subproblem
+- representative variable not in good subproblem
+
+"""
+struct VarInDwSpCheck <: IndepDecompositionCheck end
+
 struct VarsOfSameDwSpInMasterCheck <: AccDecompositionCheck end
 
 
@@ -99,19 +129,38 @@ _acc_check_dec_constr(
     ::Annotation{T,F,D}
 ) where {T,F,D} = nothing
 
+function _check_varindwsepcheck(annotation::Annotation, var, constr, sp)
+    if getformulation(annotation) == Master
+        throw(MasterVarInDwSp(var, constr))
+    elseif annotation.axis_index_value !== sp.axis_index_value
+        throw(DwSpVarNotInGoodDwSp(var, constr))
+    end
+    return
+end
+
+function _check_varindwsepcheck(annotations::Vector{<:Annotation}, var, constr, sp)
+    axis_index_values = getfield.(annotations, :axis_index_value)
+    if sp.axis_index_value ∉ axis_index_values
+        throw(NotRepresentativeOfDwSp(var, constr))
+    end
+    return
+end
+
 function _check_dec_constr(
-    ::MasterVarInDwSpCheck,
+    ::VarInDwSpCheck,
     model::JuMP.Model,
     var::JuMP.VariableRef,
     constr::JuMP.ConstraintRef,
-    ::Annotation{T,F,D}
+    sp::Annotation{T,F,D}
 ) where {T,F<:DwPricingSp,D<:DantzigWolfe}
-    if MOI.get(model, VariableDecomposition(), var).formulation == Master
-        throw(MasterVarInDwSp(var, constr))
-    end
+    ann = MOI.get(model, VariableDecomposition(), var)
+    _check_varindwsepcheck(ann, var, constr, sp)
     return
 end
 
+_isrepresentative(::Annotation) = false
+_isrepresentative(::Vector{<:Annotation}) = true
+
 function _acc_check_dec_constr(
     ::VarsOfSameDwSpInMasterCheck,
     model::JuMP.Model,
@@ -122,7 +171,7 @@ function _acc_check_dec_constr(
     prev_ann = nothing
     annotations = Iterators.map(((var, _),) -> MOI.get(model, VariableDecomposition(), var), func.terms)
     for annotation in annotations
-        if annotation.formulation != DwPricingSp || annotation.upper_multiplicity > 1 ||
+        if _isrepresentative(annotation) || annotation.formulation != DwPricingSp || annotation.upper_multiplicity > 1 ||
             (!isnothing(prev_ann) && getid(prev_ann) != getid(annotation))
             return
         end
@@ -134,7 +183,7 @@ end
 
 function _check_dec_constr(model::JuMP.Model, func::JuMP.AffExpr, constr::JuMP.ConstraintRef, annotation)
     for (var, _) in func.terms
-        _check_dec_constr(MasterVarInDwSpCheck(), model, var, constr, annotation)
+        _check_dec_constr(VarInDwSpCheck(), model, var, constr, annotation)
     end
     _acc_check_dec_constr(VarsOfSameDwSpInMasterCheck(), model, func, constr, annotation)
     return

diff --git a/src/decomposition.jl b/src/decomposition.jl
@@ -16,6 +16,7 @@ function register_decomposition(model::JuMP.Model)
         for (_, jump_obj) in model.obj_dict
             _annotate_elements!(model, jump_obj, tree)
         end
+        _set_annotations_of_representatives!(model)
         for (_, jump_obj) in model.obj_dict
             _check_annotations(model, jump_obj)
         end
@@ -228,3 +229,33 @@ function setannotations!(
 end
 
 settree!(model::JuMP.Model, tree) = MOI.set(model, DecompositionTree(), tree)
+
+"""
+Error when you try to define a subproblem variable (i.e. that has an AxisId in its indices)
+as a representative of many subproblems.
+
+```julia
+A = @axis(K, [1,2,3])
+@variable(model, x[k in K, e in E]) # cannot be a representative because K is an axis.
+@variable(model, y[e in E]) # can be a representative because no axis in its indices.
+````
+"""
+struct RepresentativeAlreadyInDwSp
+    variable::JuMP.VariableRef
+end
+
+# Subproblem representative variables are assigned to the master by default because
+# they don't have any axis id in its index.
+function _set_annotations_of_representatives!(model::JuMP.Model)
+    vars = MOI.get(JuMP.backend(model), ListOfRepresentatives())
+    isnothing(vars) && return
+
+    for (vi, annotations) in vars
+        cur_annotation = MOI.get(JuMP.backend(model), VariableDecomposition(), vi)
+        if getformulation(cur_annotation) != Master
+            throw(RepresentativeAlreadyInDwSp(JuMP.jump_function(model, vi)))
+        end
+        MOI.set(JuMP.backend(model), VariableDecomposition(), vi, annotations)
+    end 
+    return
+end
diff --git a/src/subproblem_representative.jl b/src/subproblem_representative.jl
@@ -0,0 +1,36 @@
+struct ListOfRepresentatives <: MOI.AbstractModelAttribute end
+struct RepresentativeVar <: MOI.AbstractVariableAttribute end
+
+"""
+    subproblemrepresentative(x, [subproblem1, subproblem2])
+
+Indicate that variable `x` will belongs to many subproblem (`subproblem1` and `subproblem2`
+in the example).
+
+Variable `x` should not contain any axis id in this indices otherwise BlockDecomposition
+will throw a [RepresentativeAlreadyInDwSp](@ref) error.
+"""
+function subproblemrepresentative(x::JuMP.VariableRef, subproblems::Vector{SubproblemForm})
+    @assert x.model == subproblems[1].model
+    MOI.set(x.model, RepresentativeVar(), x, getfield.(subproblems, :annotation))
+    return nothing
+end
+
+function MOI.set(
+    dest::MOIU.UniversalFallback, attribute::RepresentativeVar, vi::MOI.VariableIndex, sp_annotations
+)
+    if !haskey(dest.varattr, attribute)
+        dest.varattr[attribute] = Dict{MOI.VariableIndex,Vector{Annotation}}()
+    end
+    dest.varattr[attribute][vi] = sp_annotations
+    return
+end
+
+function MOI.get(dest::MOIU.UniversalFallback, attribute::RepresentativeVar, vi::MOI.VariableIndex)
+    varattr = get(dest.varattr, attribute, nothing)
+    isnothing(varattr) && return nothing
+    return get(varattr, vi, nothing)
+end
+
+MOI.get(dest::MOIU.UniversalFallback, ::ListOfRepresentatives) =
+    get(dest.varattr, RepresentativeVar(), nothing)
diff --git a/test/dantzigwolfe.jl b/test/dantzigwolfe.jl
@@ -237,5 +237,21 @@ function test_dummy_model_decompositions()
     @testset "Decomposition over an array" begin
         @test_throws BlockDecomposition.DecompositionNotOverAxis{UnitRange{Int64}} dummymodel4()
     end
+
+    @testset "Decomposition with representatives" begin
+        d = CvrpToyData()
+        model, x, cov, dummy_sp, mast, sps, dec = cvrp_with_representatives(d)
+        try
+            JuMP.optimize!(model)
+        catch e
+            @test e isa NoOptimizer
+        end
+
+        x_annotation = BD.annotation(model, x[(1,2)])
+        @test x_annotation == getfield.(sps, :annotation)
+
+        dummy_sp_annotation = BD.annotation(model, dummy_sp[1])
+        test_annotation(dummy_sp_annotation, BD.DwPricingSp, BD.DantzigWolfe, 0, 10)
+    end
     return
 end
diff --git a/test/errors.jl b/test/errors.jl
@@ -5,6 +5,8 @@ function test_errors()
     vars_of_same_sp_in_master2()
     vars_of_same_sp_in_master3()
     decomposition_not_on_axis()
+    not_representative_of_sp()
+    different_dw_sp_vars_in_same_dw_sp()
 end
 
 function master_var_in_subproblem()
@@ -103,3 +105,29 @@ function decomposition_not_on_axis()
     @test_throws BlockDecomposition.DecompositionNotOverAxis{Vector{Int}} @dantzig_wolfe_decomposition(model, dec, I)
     return
 end
+
+function not_representative_of_sp()
+    model = BlockModel(MockOptimizer)
+    I = 1:5
+    @axis(J, 1:3)
+    @variable(model, x[i in I])
+    @constraint(model, cov, sum(x[i] for i in I) >= 1)
+    @constraint(model, sp1[j in J[1:2]], sum(x[i] for i in I) <= 3)
+    @constraint(model, sp2[J[3]], sum(x[i] for i in I) >= 4) # error because of A
+
+    @dantzig_wolfe_decomposition(model, dec, J)
+    subproblemrepresentative.(x, Ref(getsubproblems(dec)[1:2])) # A
+
+    @test_throws BlockDecomposition.NotRepresentativeOfDwSp JuMP.optimize!(model)
+    return
+end
+
+function different_dw_sp_vars_in_same_dw_sp()
+    model = BlockModel(MockOptimizer)
+    @axis(I, 1:3)
+    @variable(model, x[i in I])
+    @constraint(model, sp[I[1]], x[1] + x[2] >= 1) # error
+    @dantzig_wolfe_decomposition(model, dec, I)
+    @test_throws BlockDecomposition.DwSpVarNotInGoodDwSp JuMP.optimize!(model)
+    return
+end
diff --git a/test/formulations.jl b/test/formulations.jl
@@ -235,3 +235,47 @@ function cutting_stock(d::CsData)
     return model, x, y, cov, knp, dec
 end
 
+struct CvrpData
+    vehicle_types
+    E
+    V
+    δ
+    costs
+end
+
+function CvrpToyData()
+    vehicle_types = [1, 2, 3]
+    E = [(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)]
+    V = [1,2,3,4,5]
+    δ = Dict(
+        1 => [(1,2), (1,3), (1,4), (1,5)],
+        2 => [(1,2), (2,3), (2,4), (2,5)],
+        3 => [(1,3), (2,3), (3,4), (3,5)],
+        4 => [(1,4), (2,4), (3,4), (4,5)],
+        5 => [(1,5), (2,5), (3,5), (4,5)]
+    )
+    costs = fill(1, length(E))
+    return CvrpData(vehicle_types, E, V, δ, costs)
+end
+
+function cvrp_with_representatives(data::CvrpData)
+    @axis(VehicleTypes, data.vehicle_types)
+    model = BlockModel()
+    @variable(model, 0 <= x[e in data.E] <= 2, Int)
+
+    @constraint(model, cov[v in data.V], sum(x[e] for e in data.δ[v]) >= 2)
+    @constraint(model, dummy_sp[t in VehicleTypes], sum(x[e] for e in data.E) >= 1)
+
+    @objective(model, Min, sum(data.costs[i] * x[e] for (i,e) in enumerate(data.E)))
+
+    @dantzig_wolfe_decomposition(model, dec, VehicleTypes)
+    master = getmaster(dec)
+    subproblems = getsubproblems(dec)
+
+    subproblemrepresentative.(x, Ref(subproblems))
+
+    for v in VehicleTypes
+        specify!(subproblems[v], lower_multiplicity = 0, upper_multiplicity = 10)
+    end
+    return model, x, cov, dummy_sp, master, subproblems, dec
+end