AbstractCustomConstrData

Every custom data associated to a non-robust constraint should inherit from AbstractCustomConstrData.

This data is used to determine the coefficient of the columns in non-robust constraints.

AbstractCustomData

Left for compatibility with BlockDecomposition versions 1.14.1 and below. One should use AbstractCustomVarData or AbstractCustomConstrData instead.

AbstractCustomVarData

Every custom data associated to a solution passed in PricingSolution should inherit from AbstractCustomVarData.

This data is used to

• Determine the coefficient of the corresponding column in non-robust constraints
• Store the information about pricing solution not expressed with subproblem variables (and thus not used in the master formulation); this information can then be retrieved using [customdata(info)]@ref by the user.
• determine the branching priority of the corresponding column (if [branchingpriority(::AbstractCustomVarData)] is defined for the concrete type).

The following scores rank bordered block-diagonal structures according to their suitability to a Dantzig-Wolfe reformulation.

white_score: Prefer structures with a low relative border area and many blocks.

blockborderscore: Both the quality of the border area and of the block-diagonal are taken into account. Desired characteristics of the block-diagonal are granularity, homogeneity and isomorphism. Score is taken from https://doi.org/10.1287/ijoc.2017.0797.

relativeborderarea_score: Prefer structures with a low relative border area. Score is taken from https://doi.org/10.1007/s10107-014-0761-5.

inactive: Automatic Dantzig-Wolfe decomposition is not used.

DecompositionNotOverAxis{T}

Decomposition must be done over an axis. Getting started guide available at https://atoptima.github.io/Coluna.jl/stable/start/start/

The container on which you try to decompose is of type T and available at error.container.

Error thrown when a Dantzig-Wolfe subproblem variable is involed in another Dantzig-Wolfe subproblem.

InitialColumn(cbdata)

Solution to a subproblem that is provided to the optimizer ahead of optimization.

A callback to provide initial columns to the optimizer before starting the optimization.

Error thrown when a master variable is in a constraint that belongs to a Dantzig-Wolfe subproblem.

You can retrieve the JuMP variable and the JuMP constraint where the error occurs:

error.variable
error.constraint

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.

PricingDualBound(cbdata)

Dual bound of the pricing subproblem. This bound is used to compute the contribution of the subproblem to the dual bound in column generation.

PricingSolution(cbdata)

Solution to a subproblem. The user submits the solution as variables, values where values[i] gives the value of variables[i].

PricingSubproblemId(cbdata)

A model attribute to get the id of the subproblem treated within a pricing callback.

PricingVariableCost(cbdata)

A variable attribute to get the reduced cost of a variable within a pricing callback.

PricingVariableLowerBound(cbdata)

A variable attribute to get the current lower bound of a variable within a pricing callback.

PricingVariableUpperBound(cbdata)

A variable attribute to get the current upper bound of a variable within a pricing callback.

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.`

Error thrown if you try to attach a custom data type to a variable or a constraint that has not been registered with customvars! or customconstrs!.

Checks:

• master variable in dantzig-wolfe subproblem
• dantzig-wolfe variable not in good subproblem
• representative variable not in good subproblem

Warning when a master constraint involves variables that belong to the same Dantzig-Wolfe subproblem. It means you can move the constraint in a subproblem.

BlockModel(optimizer [, direct_model = false])

Return a JuMP model which BlockDecomposition will decompose using instructions given by the user.

If you define direct_model = true, the method creates the model with JuMP.direct_model, otherwise it uses JuMP.Model.

annotation(node)

Return the annotation that describes the master/subproblem of a given node of the decomposition tree.

annotation(model, variable)
annotation(model, constraint)

Return the subproblem to which a variable or a constraint belongs.

branchingpriority!(x, value::Float64)

Set the branching priority of variable x to value.

You can use fractional branching priorities. The idea is to have both "soft" and "hard" branching priorities. For instance :

• if the number of branching candidates with priority 4.0 is less than the maximum number of candidates considered, no branching candidates with priority 3.0 will be considered
• if the number of branching candidates with priority 3.5 is less than the maximum number of candidates considered, then some branching candidates with priority 3.0 will be considered (to bring the total number to the maximum)
• if the number of branching candidates with priority 3.5 is not less than the maximum number, then no branching candidates with priority 3.0 will be considered

Branching priority is also used in rounding and diving heuristics to determine which variables should be fixed first.

branchingpriority(<:AbstractCustomVarData)

This function should be redefined for a concrete type which inherits from AbstractCustomVarData if a custom branching priority is defined for columns associated with this data type. If this function is not redefined, the branching priority of each column equals to the branching priority of the pricing problem which generated it.

branchingpriority(x)

Return the branching priority of variable x.

customconstrs!(model, customconstr::Type{AbstractCustomConstrData})
customconstrs!(model, customconstrs::Vector{Type{AbstractCustomConstrData}})

Set the possible custom data types of constraints in a model.

customconstrs(model)

Return the custom data types of constraints in a model.

customdata!(var, custom_data)
customdata!(constr, custom_data)

Attach a custom data to a variable or a constraint.

customdata(info)

Returns the custom data attached to the master column variable associated to info.

customdata(var)
customdata(constr)

Returns the custom data attached to a variable or a constraint; nothing if no custom data.

customvars!(model, customvar::Type{<:AbstractCustomVarData})
customvars!(model, customvars::Vector{Type{<:AbstractCustomVarData}})

Set the possible custom data types of variables in a model.

customvars(model)

Return the possible custom data types of variables in a model.

getmaster(node) -> MasterForm

Return an object that wraps the annotation that describes the master formulation of a decomposition stored at the node of the decomposition tree.

This method is not defined if the node is a leaf of the decomposition tree.

getsolutions(model, k)

Return a vector of information about the columns in the subproblem k solution.

getsubproblems(node) -> Vector{SubproblemForm}

Return a vector of objects that wrap the annotations that describe subproblem formulations of a decomposition stored at node of the decomposition tree.

This method is not defined if the node is a leaf of the decomposition tree.

objectivedualbound!(model, db)

Define a dual bound on the optimal objective value. (lower bound for a minimisation, upper bound for a maximisation)

objectiveprimalbound!(model, pb)

Define a primal bound on the optimal objective value (upper bound for a minimisation, lower bound for a maximisation).

register_decomposition(model)

Assign to each variable and constraint an annotation indicating in which partition (master/subproblem) of the original formulation the variable or the constraint is located.

This method is called by the JuMP.optimize! hook.

specify!(
    subproblem, 
    lower_multiplicity = 1,
    upper_multiplicity = 1,
    solver = nothing,
    branching_priority = 1
)

Method that allows the user to specify additional property of the subproblems.

The multiplicity of subproblem is the number of times that the same independent block shaped by the subproblem in the coefficient matrix appears in the model. It is equivalent to the number of solutions to the subproblem that can appear in the solution of the original problem.

Branching priority of a subproblem is equal to the branching priority of the associated integer variable (the number of columns from this subproblem in the global solution). It also determines the default branching priority of columns generated by this subproblem. Branching priority is also used in rounding and diving heuristics to prioritize which variables and columns to fix the first.

The solver of the subproblem is the way the subproblem will be optimized. It can be either a function (pricing callback), an optimizer of MathOptInterface (e.g. Gurobi.Optimizer, CPLEX.Optimizer, Glpk.Optimizer... with attributes), or nothing. In the latter case, the solver will use a default optimizer that should be defined in the parameters of the main solver.

Advanced usage : The user can use several solvers to optimize a subproblem :

specify!(subproblem, solver = [Gurobi.Optimizer, my_callback, my_second_callback])

Coluna always uses the first solver by default. Be cautious because changes are always buffered to all solvers. So you may degrade performances if you use a lot of solvers.

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 error.

value(info, x)

Return the coefficient of original variable x in the column associated to info.

value(info)

Return the value of the master column variable associated to info.

@axis(name, collection)

Declare collection as an index-set of subproblems. You can access the axis using the variable name.

Examples

Consider a formulation that has a decomposition which gives raise to 5 subproblems. Let {1,2,3,4,5} be the index-set of the subproblems.

To perform this decomposition with BlockDecomposition, we must declare an axis that contains the index-set of the subproblems :

julia> L = 1:5
1:5

julia> @axis(K, L)
BlockDecomposition.Axis{:K, Int64}(:K, BlockDecomposition.AxisId{:K, Int64}[1, 2, 3, 4, 5])

julia> K[1]
1

julia> typeof(K[1])
BlockDecomposition.AxisId{:K, Int64}

The elements of the axis are AxisId. You must use AxisId in the indices of the variables and the constraints that you declare otherwise BlockDecomposition assign them to the master problem.

@variable(model, x[l in L]) # x[l] belongs to the master for any l ∈ L
@variable(model, y[k in K]) # y[k], k ∈ K, belongs to subproblem k (because K is an axis)

@benders_decomposition(model, name, axis)

Register a Benders decomposition on the JuMP model model where the index-set of the subproblems is defined by the axis axis.

Create a variable name from which the user can access decomposition tree.

@dantzig_wolfe_decomposition(model, name, axis)

Register a Dantzig-Wolfe decomposition on the JuMP model model where the index-set of the subproblems is defined by the axis axis.

Create a variable name from which the user can access the decomposition tree.